Combinatorial Optimization

Structural Insights and an IP-based Solution Method for Patient-to-room Assignment Under Consideration of Single Room Entitlements

  • Tabea Brandt
  • Christina Büsing
  • Felix Engelhardt
    • Categories 0-1 Programming, Applications - OR and Management Sciences, Combinatorial Optimization Tags , , ,

    Patient-to-room assignment (PRA) is a scheduling problem in decision support for large hospitals. This work proposes Integer Programming (IP) formulations for dynamic PRA, where either full, limited or uncertain information on incoming patients is available. The applicability is verified through a computational study. Results indicate that large, real world instances can be solved to a … Read more

    A widespread belief about county splits in political districting plans is wrong

  • Austin Buchanan
  • Soraya Ezazipour
  • Maral Shahmizad
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming Tags , ,

    Consider the task of dividing a state into k contiguous political districts whose populations must not differ by more than one person, following current practice for congressional districting in the USA. A widely held belief among districting experts is that this task requires at least k-1 county splits. This statement has appeared in expert testimony, … Read more

    A Family of Spanning-Tree Formulations for the Maximum Cut Problem

  • Sven Mallach
    • Categories Combinatorial Optimization, Integer Programming, Quadratic Programming

    We present a family of integer programming formulations for the maximum cut problem. These formulations encode the incidence vectors of the cuts of a connected graph by employing a subset of the odd-cycle inequalities that relate to a spanning tree, and they require only the corresponding edge variables to be integral explicitly. They so describe … Read more

    Facets of the knapsack polytope from non-minimal covers

  • Guneshwar Anand
  • Sachin Jayaswal
  • B. Srirangacharyulu
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Transportation Tags , , , , ,

    We propose two new classes of valid inequalities (VIs) for the binary knapsack polytope, based on non-minimal covers. We also show that these VIs can be obtained through neither sequential nor simultaneous lifting of well-known cover inequalities. We further provide conditions under which they are facet-defining. The usefulness of these VIs is demonstrated using computational … Read more

    Relaxation strength for multilinear optimization: McCormick strikes back

  • Matthias Walter
    • Categories (Mixed) Integer Linear Programming, Nonlinear Optimization, Polyhedra Tags , , , , ,

    We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick linearization (Operations Research Letters 51 (2023) 146-152). In this paper we extend the result to more general linearizations, and present a simpler proof. Moreover, … Read more

    Price of Anarchy in Paving Matroid Congestion Games

  • Bainian Hao
  • Carla Michini
    • Categories Combinatorial Optimization, Game Theory Tags , , ,

    Congestion games allow to model competitive resource sharing in various distributed systems. Pure Nash equilibria, that are stable outcomes of a game, could be far from being socially optimal. Our goal is to identify combinatorial structures that limit the inefficiency of equilibria. This question has been mainly investigated for congestion games defined over networks. Instead, … Read more

    Exact Solutions for the NP-hard Wasserstein Barycenter Problem using a Doubly Nonnegative Relaxation and a Splitting Method

  • Woosuk L. Jung
  • Walaa M. Moursi
  • Henry Wolkowicz
    • Categories Combinatorial Optimization, Meta Heuristics, Semi-definite Programming

    The simplified Wasserstein barycenter problem, also known as the cheapest hub problem, consists in selecting one point from each of \(k\) given sets, each set consisting of \(n\) points, with the aim of minimizing the sum of distances to the barycenter of the \(k\) chosen points. This problem is also known as the cheapest hub … Read more

    Branch-and-Bound versus Lift-and-Project Relaxations in Combinatorial Optimization

  • Yatharth Dubey
  • Gérard Cornuéjols
    • Categories 0-1 Programming, Branch and Cut Algorithms Tags , ,

    In this paper, we consider a theoretical framework for comparing branch-and-bound with classical lift-and-project hierarchies. We simplify our analysis of streamlining the definition of branch-and-bound. We introduce “skewed $k$-trees” which give a hierarchy of relaxations that is incomparable to that of Sherali-Adams, and we show that it is much better for some instances. We also … Read more

    A polytime preprocess algorithm for the maximum independent set problem

  • Samuel Kroger
  • Hamidreza Validi
  • Illya V. Hicks
    • Categories Combinatorial Optimization, Graphs and Matroids

    The maximum independent set (MIS) seeks to find a subset of vertices with the maximum size such that no pair of its vertices are adjacent. This paper develops a recursive fixing procedure that generalizes the existing polytime algorithm to solve the maximum independent set problem on chordal graphs, which admit simplicial orderings. We prove that … Read more

    Hardness of pricing routes for two-stage stochastic vehicle routing problems with scenarios

  • Matheus Jun Ota
  • Ricardo Fukasawa
    • Categories Combinatorial Optimization, Integer Programming, Stochastic Programming Tags , ,

    The vehicle routing problem with stochastic demands (VRPSD) generalizes the classic vehicle routing problem by considering customer demands as random variables. Similarly to other vehicle routing variants, state-of-the-art algorithms for the VRPSD are often based on set-partitioning formulations, which require efficient routines for the associated pricing problems. However, all these set-partitioning-based approaches have strong assumptions … Read more