Integer Programming

Solving Binary-Constrained Mixed Complementarity Problems Using Continuous Reformulations

  • Steven A. Gabriel
  • Martin Schmidt
  • Marina Leal
    • Categories (Mixed) Integer Nonlinear Programming, Complementarity and Variational Inequalities, Transportation Tags , , ,

    Mixed complementarity problems are of great importance in practice since they appear in various fields of applications like energy markets, optimal stopping, or traffic equilibrium problems. However, they are also very challenging due to their inherent, nonconvex structure. In addition, recent applications require the incorporation of integrality constraints. Since complementarity problems often model some kind … Read more

    Evaluating on-demand warehousing via dynamic facility location models

  • Kaan Unnu
  • Jennifer Pazour
    • Categories (Mixed) Integer Linear Programming, Supply Chain Management, Transportation Tags , , , , , ,

    On-demand warehousing platforms match companies with underutilized warehouse and distribution capabilities with customers who need extra space or distribution services. These new business models have unique advantages, in terms of reduced capacity and commitment granularity, but also have different cost structures compared to traditional ways of obtaining distribution capabilities. This research is the first quantitative … Read more

    Mixed-Integer Optimal Control Problems with switching costs: A shortest path approach

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

    We investigate an extension of Mixed-Integer Optimal Control Problems (MIOCPs) by adding switching costs, which enables the penalization of chattering and extends current modeling capabilities. The decomposition approach, consisting of solving a partial outer convexification to obtain a relaxed solution and using rounding schemes to obtain a discrete-valued control can still be applied, but the … Read more

    Learning Generalized Strong Branching for Set Covering, Set Packing, and 0-1 Knapsack Problems

  • Yu Yang
  • Natashia Boland
  • Bistra Dilkina
  • Martin Savelsbergh
    • Categories (Mixed) Integer Linear Programming, Integer Programming Tags , ,

    Branching on a set of variables, rather than on a single variable, can give tighter bounds at the child nodes and can result in smaller search trees. However, selecting a good set of variables to branch on is even more challenging than selecting a good single variable to branch on. Generalized strong branching extends the … Read more

    Quantum Bridge Analytics II: Network Optimization and Combinatorial Chaining for Asset Exchange

  • Yu Du
  • Fred Glover
  • Gary Kochenberger
  • Moses Ma
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Network Optimization Tags , , , , ,

    Quantum Bridge Analytics relates to methods and systems for hybrid classical-quantum computing, and is devoted to developing tools for bridging classical and quantum computing to gain the benefits of their alliance in the present and enable enhanced practical application of quantum computing in the future. This is the second of a two-part tutorial that surveys … Read more

    A new combinatorial branch-and-bound algorithm for the Knapsack Problem with Conflict Graph

  • Stefano Coniglio
  • Fabio Furini
  • Pablo San Segundo
    • Categories Combinatorial Optimization, Integer Programming

    We study the Knapsack Problem with Conflict Graph (KPCG), a generalization of the Knapsack Problem in which a conflict graph specifies pairs of items (vertices of the graph) which cannot be simultaneously selected in a solution. The KPCG asks for determining a maximum-profit subset of items of total weight no larger than the knapsack capacity … Read more

    Autonomous traffic at intersections: an optimization-based analysis of possible time, energy, and CO2 savings

  • Do Duc Le
  • Maximilian Merkert
  • Stephan Sorgatz
  • Mirko Hahn
  • Sebastian Sager
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering, Network Optimization Tags , , , , , ,

    In the growing field of autonomous driving, traffic-light controlled intersections as the nodes of large traffic networks are of special interest. We want to analyze how much an optimized coordination of vehicles and infrastructure can contribute to a more efficient transit through these bottlenecks. In addition, we are interested in sensitivity of the results with … Read more

    Integer packing sets form a well-quasi-ordering

  • Alberto Del Pia
  • Dion C. Gijswijt
  • Jeff Linderoth
  • Haoran Zhu
    • Categories (Mixed) Integer Linear Programming

    An integer packing set is a set of non-negative integer vectors with the property that, if a vector x is in the set, then every non-negative integer vector y with y ≤ x is in the set as well. Integer packing sets appear naturally in Integer Optimization. In fact, the set of integer points in … Read more

    A Finitely Convergent Disjunctive Cutting Plane Algorithm for Bilinear Programming

  • Hamed Rahimian
  • Sanjay Mehrotra
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Quadratic Programming Tags , , , ,

    In this paper we present and analyze a finitely-convergent disjunctive cutting plane algorithm to obtain an \(\epsilon\)-optimal solution or detect infeasibility of a general nonconvex continuous bilinear program. While the cutting planes are obtained in a manner similar to Saxena, Bonami, and Lee [Math. Prog. 130: 359–413, 2011] and Fampa and Lee [J. Global Optim. … Read more