Integer Programming

An MILP-Based Solution Scheme for Factored and Robust Factored Markov Decision Processes

  • Huikang Liu
  • Wolfram Wiesemann
  • Man-Chung Yue
    • Categories (Mixed) Integer Linear Programming, Robust Optimization Tags ,

    Factored Markov decision processes (MDPs) are a prominent paradigm within the artificial intelligence community for modeling and solving large-scale MDPs whose rewards and dynamics decompose into smaller, loosely interacting components. Through the use of dynamic Bayesian networks and context-specific independence, factored MDPs can achieve an exponential reduction in the state space of an MDP and … Read more

    Network Flow Models for Robust Binary Optimization with Selective Adaptability

  • Ian Zhu
    • Categories Combinatorial Optimization, Integer Programming, Robust Optimization

    Adaptive robust optimization problems have received significant attention in recent years, but remain notoriously difficult to solve when recourse decisions are discrete in nature. In this paper, we propose new reformulation techniques for adaptive robust binary optimization (ARBO) problems with objective uncertainty. Without loss of generality, we focus on ARBO problems with “selective adaptability”, a … Read more

    A diving heuristic for mixed-integer problems with unbounded semi-continuous variables

  • Katrin Halbig
  • Alexander Hoen
  • Ambros Gleixner
  • Jakob Witzig
  • Dieter Weninger
    • Categories Integer Programming Tags , , , ,

    Semi-continuous decision variables arise naturally in many real-world applications. They are defined to take either value zero or any value within a specified range, and occur mainly to prevent small nonzero values in the solution. One particular challenge that can come with semi-continuous variables in practical models is that their upper bound may be large … Read more

    Adjustable Robust Nonlinear Network Design under Demand Uncertainties

  • Johannes Thürauf
  • Julia Grübel
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Energy, Robust Optimization Tags , , , ,

    We study network design problems for nonlinear and nonconvex flow models under demand uncertainties. To this end, we apply the concept of adjustable robust optimization to compute a network design that admits a feasible transport for all, possibly infinitely many, demand scenarios within a given uncertainty set. For solving the corresponding adjustable robust mixed-integer nonlinear … Read more

    On the integrality Gap of Small Asymmetric Travelling Salesman Problems: A Polyhedral and Computational Approach

  • Eleonora Vercesi
  • Luca Maria Gambardella
  • Stefano Gualandi
  • Monaldo Mastrolilli
  • Janos Barta
    • Categories Combinatorial Optimization, Integer Programming, Linear, Cone and Semidefinite Programming Tags ,

    \(\) In this paper, we investigate the integrality gap of the Asymmetric Traveling Salesman Problem (ATSP) with respect to the linear relaxation given by the Asymmetric Subtour Elimination Problem (ASEP) for small-sized instances. In particular, we focus on the geometric properties and symmetries of the ASEP polytope ( \(P_{ASEP}^n\) ) and its vertices. The polytope’s … Read more

    Representing Integer Program Value Function with Neural Networks

  • Tu Anh-Nguyen
  • Joey Huchette
  • Andrew J. Schaefer
    • Categories (Mixed) Integer Linear Programming, Integer Programming Tags , ,

    We study the value function of an integer program (IP) by characterizing how its optimal value changes as the right-hand side varies. We show that the IP value function can be approximated to any desired degree of accuracy using machine learning (ML) techniques. Since an IP value function is a Chvátal-Gomory (CG) function, we first … Read more

    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, 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 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 by … 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) that are 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