Integer Programming

Certified Constraint Propagation and Dual Proof Analysis in a Numerically Exact MIP Solver

  • Sander Borst
  • Leon Eifler
  • Ambros Gleixner
    • Categories Integer Programming, Optimization Software and Modeling Systems Tags , ,

    This paper presents the integration of constraint propagation and dual proof analysis in an exact, roundoff-error-free MIP solver. The authors employ safe rounding methods to ensure that all results remain provably correct, while sacrificing as little computational performance as possible in comparison to a pure floating-point implementation. The study also addresses the adaptation of certification … Read more

    Using Disjunctive Cuts in a Branch-and-Cut Method to Solve Convex Integer Nonlinear Bilevel Problems

  • Horländer Andreas
  • Ivana Ljubić
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Bilevel Optimization, Cutting Plane Approaches Tags , , ,

    We present a branch-and-cut method for solving convex integer nonlinear bilevel problems, i.e., bilevel models with nonlinear but jointly convex objective functions and constraints in both the upper and the lower level. To this end, we generalize the idea of using disjunctive cuts to cut off integer-feasible but bilevel-infeasible points. These cuts can be obtained … Read more

    Neur2BiLO: Neural Bilevel Optimization

  • Justin Dumouchelle
  • Esther Julien
  • Jannis Kurtz
  • Elias B. Khalil
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , ,

    Bilevel optimization deals with nested problems in which a leader takes the first decision to minimize their objective function while accounting for a follower best-response reaction. Constrained bilevel problems with integer variables are particularly notorious for their hardness.  While exact solvers have been proposed for mixed-integer~linear bilevel optimization, they tend to scale poorly with problem … Read more

    A Polyhedral Characterization of Linearizable Quadratic Combinatorial Optimization Problems

  • Lucas Waddell
    • Categories 0-1 Programming, Combinatorial Optimization, Quadratic Programming Tags , , ,

    We introduce a polyhedral framework for characterizing instances of quadratic combinatorial optimization programs (QCOPs) as being linearizable, meaning that the quadratic objective can be equivalently rewritten as linear in such a manner that preserves the objective function value at all feasible solutions. In particular, we show that an instance is linearizable if and only if … Read more

    The MIP Workshop 2023 Computational Competition on Reoptimization

  • Suresh Bolusani
  • Mathieu Besançon
  • Ambros Gleixner
  • Timo Berthold
  • Claudia D'Ambrosio
  • Gonzalo Muñoz
  • Joseph Paat
  • Dimitri Thomopulos
    • Categories Combinatorial Optimization, Integer Programming, Optimization Software and Modeling Systems Tags , , , ,

    This paper describes the computational challenge developed for a computational competition held in 2023 for the 20th anniversary of the Mixed Integer Programming Workshop. The topic of this competition was reoptimization, also known as warm starting, of mixed integer linear optimization problems after slight changes to the input data for a common formulation. The challenge … Read more

    Adjustable robust optimization for fleet sizing problem in closed-loop supply chains with simultaneous delivery and pickup

  • Ali Borumand
  • Ali Nookabadi
    • Categories (Mixed) Integer Linear Programming, Meta Heuristics, Robust Optimization Tags , , , ,

    The Fleet Sizing Problem (FSP) stands as a critical challenge within the realm of logistics and supply chain management, particularly in the context of Closed-Loop Supply Chains (CLSC). The significance of addressing the FSP lies in its direct impact on operational costs, resource utilization, and environmental sustainability. By effectively optimizing fleet size, organizations can streamline … Read more

    The SCIP Optimization Suite 9.0

  • Suresh Bolusani
  • Mathieu Besançon
  • Ksenia Bestuzheva
  • Antonia Chmiela
  • João Dionísio
  • Tim Donkiewicz
  • Jasper van Doornmalen
  • Leon Eifler
  • Mohammed Ghannam
  • Ambros Gleixner
  • Christoph Graczyk
  • Katrin Halbig
  • Ivo Hedtke
  • Alexander Hoen
  • Christopher Hojny
  • Rolf van der Hulst
  • Dominik Kamp
  • Thorsten Koch
  • Kevin Kofler
  • Jurgen Lentz
  • Julian Manns
  • Gioni Mexi
  • Erik Mühmer
  • Marc E. Pfetsch
  • Franziska Schlösser
  • Felipe Serrano
  • Yuji Shinano
  • Mark Turner
  • Stefan Vigerske
  • Dieter Weninger
  • Liding Xu
    • Categories Integer Programming, Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , , , , , , ,

    The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming (CIP) framework SCIP. This report discusses the enhancements and extensions included in the SCIP Optimization Suite 9.0. The updates in SCIP 9.0 include improved symmetry handling, additions and improvements of nonlinear handlers and primal heuristics, a … Read more

    Distributed Task Assignment in a Swarm of UAVs

  • Luigi Bobbio
  • Jörg Fliege
  • Antonio Martinez-Sykora
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Scheduling

    We consider the problem of distributed task assignment in a swarm of Unmanned Aerial Vehicles (UAVs), where heterogeneous agents that can have different capabilities need to work in teams to execute tasks. We consider the case where communication between UAVs is costly or dangerous and should be limited or avoided, while individual UAVs have uncertain … Read more

    Set System Approximation for Binary Integer Programs: Reformulations and Applications

  • Ningji Wei
    • Categories 0-1 Programming, Cutting Plane Approaches, Integer Programming Tags , , , ,

    Covering and elimination inequalities are central to combinatorial optimization, yet their role has largely been studied in problem-specific settings or via no-good cuts. This paper introduces a unified perspective that treats these inequalities as primitives for set system approximation in binary integer programs (BIPs). We show that arbitrary set systems admit tight inner and outer … Read more

    On Coupling Constraints in Linear Bilevel Optimization

  • Dorothee Henke
  • Henri Lefebvre
  • Martin Schmidt
  • Johannes Thürauf
    • Categories (Mixed) Integer Linear Programming, Complementarity and Variational Inequalities, Other Topics Tags ,

    It is well-known that coupling constraints in linear bilevel optimization can lead to disconnected feasible sets, which is not possible without coupling constraints. However, there is no difference between linear bilevel problems with and without coupling constraints w.r.t. their complexity-theoretical hardness. In this note, we prove that, although there is a clear difference between these … Read more