Integer Programming

Spectral relaxations and branching strategies for global optimization of mixed-integer quadratic programs

  • Carlos Nohra
  • Arvind U. Raghunathan
  • Nikolaos Sahinidis
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    We consider the global optimization of nonconvex quadratic programs and mixed-integer quadratic programs. We present a family of convex quadratic relaxations which are derived by convexifying nonconvex quadratic functions through perturbations of the quadratic matrix. We investigate the theoretical properties of these quadratic relaxations and show that they are equivalent to some particular semidefinite programs. … Read more

    New algorithms for hierarchical optimisation in kidney exchange programmes

  • Maxence Delorme
  • Jacek Gondzio
  • William Pettersson
  • Sergio García
  • Joerg Kalcsics
  • David Manlove
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming Tags , , , ,

    Kidney exchange programmes (KEPs) across the world help match donors and recipients to identify kidney transplantations. Almost all KEPs use a hierarchical set of objectives to determine an optimal set of transplants to perform, and integer linear programming is often used to find such optimal matchings. In this work, we identify the barriers in existing … Read more

    Matching Algorithms and Complexity Results for Constrained Mixed-Integer Optimal Control with Switching Costs

  • Felix Bestehorn
  • Christian Kirches
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms Tags , , , ,

    We extend recent work on the performance of the combinatorial integral approximation decomposition approach for Mixed-Integer Optimal Control Problems (MIOCPs) in the presence of combinatorial constraints or switching costs on an equidistant grid. For the time discretized problem, we reformulate the emerging rounding problem in the decomposition approach as a matching problem on a bipartite … Read more

    Feasible rounding approaches for equality constrained mixed-integer optimization problems

  • Christoph Neumann
  • Oliver Stein
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , ,

    A feasible rounding approach is a novel technique to compute good feasible points for mixed-integer optimization problems. The central idea of this approach is the construction of a continuously described inner parallel set for which any rounding of any of its elements is feasible in the original mixed-integer problem. It is known that this approach … Read more

    Mathematical Models and Approximate Solution Approaches for the Stochastic Bin Packing Problem

  • John Martinovic
  • Maximilian Selch
    • Categories 0-1 Programming, Combinatorial Optimization, Stochastic Programming Tags , , , , ,

    We consider the (single-stage) stochastic bin packing problem (SBPP) which is based on a given list of items the sizes of which are represented by stochastically independent random variables. The SBPP requires to determine the minimum number of unit capacity bins needed to pack all the items, such that for each bin the probability of … Read more

    Short-Term Inventory-Aware Equipment Management in Service Networks

  • Natashia Boland
  • Alan L. Erera
  • Martin Savelsbergh
  • Yassine Ridouane
    • Categories (Mixed) Integer Linear Programming, Production and Logistics, Transportation

    Logistics companies often operate a heterogeneous fleet of equipment to support their service network operations. This introduces a layer of planning complexity as facilities need to maintain appropriate levels of equipment types to support operations throughout the planning horizon. We formulate an optimization model that minimizes the cost of executing a load plan, assuming knowledge … Read more

    A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem

  • Dionne M. Aleman
  • Merve Bodur
  • Lizeth Carolina Riascos-Alvarez
    • Categories Integer Programming

    Kidney paired donation programs allow patients registered with an incompatible donor to receive a suitable kidney from another donor, as long as the latter’s co-registered patient, if any, also receives a kidney from a different donor. The kidney exchange problem (KEP) aims to find an optimal collection of kidney exchanges taking the form of cycles … Read more

    The Bipartite Boolean Quadric Polytope with Multiple-Choice Constraints

  • Andreas Bärmann
  • Alexander Martin
  • Oskar Schneider
    • Categories (Mixed) Integer Nonlinear Programming, Chemical Engineering, Polyhedra Tags , , , ,

    We consider the bipartite boolean quadric polytope (BQP) with multiple-choice constraints and analyse its combinatorial properties. The well-studied BQP is defined as the convex hull of all quadric incidence vectors over a bipartite graph. In this work, we study the case where there is a partition on one of the two bipartite node sets such … Read more

    Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories Cutting Plane Approaches, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , ,

    We propose a framework for modeling and solving low-rank optimization problems to certifiable optimality. We introduce symmetric projection matrices that satisfy $Y^2 = Y$, the matrix analog of binary variables that satisfy $z^2 = z$, to model rank constraints. By leveraging regularization and strong duality, we prove that this modeling paradigm yields tractable convex optimization … Read more

    Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices

  • Ambros Gleixner
  • Sebastian Pokutta
  • Boro Sofranac
    • Categories Integer Programming Tags , , , ,

    Fast domain propagation of linear constraints has become a crucial component of today’s best algorithms and solvers for mixed integer programming and pseudo-boolean optimization to achieve peak solving performance. Irregularities in the form of dynamic algorithmic behaviour, dependency structures, and sparsity patterns in the input data make efficient implementations of domain propagation on GPUs and, … Read more