Integer Programming

Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework

  • Stephen J. Maher
    • Categories Integer Programming, Optimization Software and Modeling Systems Tags , , , ,

    Benders’ decomposition is a popular mathematical and constraint programming algorithm that is widely applied to exploit problem structure arising from real-world applications. While useful for exploiting structure in mathematical and constraint programs, the use of Benders’ decomposition typically requires significant implementation effort to achieve an effective solution algorithm. Traditionally, Benders’ decomposition has been viewed as … Read more

    Mixed-Integer Optimal Control under Minimum Dwell Time Constraints

  • Nicolò Robuschi
  • Sebastian Sager
  • Clemens Zeile
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Systems governed by Differential Equations Optimization Tags , , , , ,

    Tailored mixed-integer optimal control policies for real-world applications usually have to avoid very short successive changes of the active integer control. Minimum dwell time constraints express this requirement and can be included into the combinatorial integral approximation decomposition, which solves mixed-integer optimal control problems by solving one continuous nonlinear program and one mixed-integer linear program. … Read more

    A smaller extended formulation for the odd cycle inequalities of the stable set polytope

  • Sven de Vries
  • Bernd Perscheid
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Graphs and Matroids Tags , , , ,

    For sparse graphs, the odd cycle polytope can be used to compute useful bounds for the maximum stable set problem quickly. Yannakakis introduced an extended formulation for the odd cycle inequalities of the stable set polytope in 1991, which provides a direct way to optimize over the odd cycle polytope in polynomial time, although there … Read more

    Decentralized Online Integer Programming Problems with a Coupling Cardinality Constraint

  • Shabbir Ahmed
  • George L. Nemhauser
  • Ezgi Karabulut
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms Tags , ,

    We consider a problem involving a set of agents who need to coordinate their actions to optimize the sum of their objectives while satisfying a common resource constraint. The objective functions of the agents are unknown to them a priori and are revealed in an online manner. The resulting problem is an online optimization problem … Read more

    Tight compact extended relaxations for nonconvex quadratic programming problems with box constraints

  • Sven de Vries
  • Bernd Perscheid
    • Categories (Mixed) Integer Nonlinear Programming, Graphs and Matroids, Quadratic Programming Tags ,

    Cutting planes from the Boolean Quadric Polytope (BQP) can be used to reduce the optimality gap of the NP-hard nonconvex quadratic program with box constraints (BoxQP). It is known that all cuts of the Chvátal-Gomory closure of the BQP are A-odd cycle inequalities. We obtain a compact extended relaxation of all A-odd cycle inequalities, which … Read more

    Two-row and two-column mixed-integer presolve using hash-based pairing methods

  • Weikun Chen
  • Ambros Gleixner
  • Dieter Weninger
  • Patrick Gemander
  • Leona Gottwald
  • Alexander Martin
    • Categories (Mixed) Integer Linear Programming, Optimization Software Benchmark, Polyhedra Tags , , ,

    In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on the solvability of a given problem. However, a crucial property for employing presolving techniques successfully is … Read more

    The risk-averse ultimate pit problem

  • Gianpiero Canessa
  • Bernardo K. Pagnoncelli
  • Eduardo Moreno
    • Categories 0-1 Programming, Stochastic Programming

    In this work, we consider a risk-averse ultimate pit problem where the grade of the mineral is uncertain. We propose a two-stage formulation of the problem and discuss which properties are desirable for a risk measure in this context. We show that the only risk measure that satisfies these properties is the entropic. We propose … Read more

    Branch-and-Cut-and-Price for Multi-Agent Pathfinding

  • Daniel Harabor
  • Edward Lam
  • Pierre Le Bodic
  • Peter J. Stuckey
    • Categories 0-1 Programming, Branch and Cut Algorithms, Transportation Tags , , , ,

    There are currently two broad strategies for optimal Multi-agent Pathfinding (MAPF): (1) search-based methods, which model and solve MAPF directly, and (2) compilation-based solvers, which reduce MAPF to instances of well-known combinatorial problems, and thus, can benefit from advances in solver techniques. In this work, we present an optimal algorithm, BCP, that hybridizes both approaches … Read more

    Logic-based Benders Decomposition and Binary Decision Diagram Based Approaches for Stochastic Distributed Operating Room Scheduling

  • Dionne M. Aleman
  • Merve Bodur
  • Cheng Guo
  • David R. Urbach
    • Categories Cutting Plane Approaches, Scheduling, Stochastic Programming

    The distributed operating room (OR) scheduling problem aims to find an assignment of surgeries to ORs across collaborating hospitals that share their waiting lists and ORs. We propose a stochastic extension of this problem where surgery durations are considered to be uncertain. In order to obtain solutions for the challenging stochastic model, we use sample … Read more

    Near-optimal Robust Bilevel Optimization

  • Miguel F. Anjos
  • Mathieu Besançon
  • Luce Brotcorne
    • Categories (Mixed) Integer Nonlinear Programming, Complementarity and Variational Inequalities, Robust Optimization Tags , , , , , ,

    Bilevel optimization studies problems where the optimal response to a second mathematical optimization problem is integrated in the constraints. Such structure arises in a variety of decision-making problems in areas such as market equilibria, policy design or product pricing. We introduce near-optimal robustness for bilevel problems, protecting the upper-level decision-maker from bounded rationality at the … Read more