0-1 Programming

Pessimistic bilevel optimization approach for decision-focused learning

  • Diego Jiménez
  • Bernardo K. Pagnoncelli
  • Hande Yaman
    • Categories 0-1 Programming, Stochastic Programming Tags , ,

    The recent interest in contextual optimization problems, where randomness is associated with side information, has led to two primary strategies for formulation and solution. The first, estimate-then-optimize, separates the estimation of the problem’s parameters from the optimization process. The second, decision-focused optimization, integrates the optimization problem’s structure directly into the prediction procedure. In this work, … Read more

    Cut-based Conflict Analysis in Mixed Integer Programming

  • Gioni Mexi
  • Felipe Serrano
  • Ambros Gleixner
  • Timo Berthold
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Integer Programming Tags , , , , ,

    For almost two decades, mixed integer programming (MIP) solvers have used graph- based conflict analysis to learn from local infeasibilities during branch-and-bound search. In this paper, we improve MIP conflict analysis by instead using reasoning based on cuts, inspired by the development of conflict-driven solvers for pseudo- Boolean optimization. Phrased in MIP terminology, this type … Read more

    Facets from solitary items for the 0/1 knapsack polytope

  • Shreyas Bhowmik
  • Sachin Jayaswal
    • Categories 0-1 Programming Tags , , , ,

    We introduce a new class of valid inequalities for any 0/1 knapsack polytope, called Solitary item inequality, which are facet-defining. We prove that any facet-defining inequality of a 0/1 knapsack polytope with nonnegative integral coefficients and right hand side 1 belongs to this class, and hence, the set of facet-defining inequalities corresponding to strong covers … Read more

    Application of the Lovász-Schrijver Operator to Compact Stable Set Integer Programs

  • Federico Battista
  • Fabrizio Rossi
  • Stefano Smriglio
    • Categories 0-1 Programming, Combinatorial Optimization, Semi-definite Programming Tags , ,

    The Lov\’asz theta function $\theta(G)$ provides a very good upper bound on the stability number of a graph $G$. It can be computed in polynomial time by solving a semidefinite program (SDP), which also turns out to be fairly tractable in practice. Consequently, $\theta(G)$ achieves a hard-to-beat trade-off between computational effort and strength of the … Read more

    Interdiction of minimum spanning trees and other matroid bases

  • Noah Weninger
  • Ricardo Fukasawa
    • Categories 0-1 Programming, Dynamic Programming, Graphs and Matroids Tags , , , , , ,

    In the minimum spanning tree (MST) interdiction problem, we are given a graph \(G=(V,E)\) with edge weights, and want to find some \(X\subseteq E\) satisfying a knapsack constraint such that the MST weight in \((V,E\setminus X)\) is maximized. Since MSTs of \(G\) are the minimum weight bases in the graphic matroid of \(G\), this problem … Read more

    Factorized binary polynomial optimization

  • Alberto Del Pia
    • Categories (Mixed) Integer Nonlinear Programming, 0-1 Programming, Integer Programming Tags , , , , ,

    In binary polynomial optimization, the goal is to find a binary point maximizing a given polynomial function. In this paper, we propose a novel way of formulating this general optimization problem, which we call factorized binary polynomial optimization. In this formulation, we assume that the variables are partitioned into a fixed number of sets, and … Read more

    The if-then Polytope: Conditional Relations over Multiple Sets of Binary Variables

  • Tobias Kuen
  • Robert Burlacu
  • Patrick Gemander
    • Categories 0-1 Programming, Polyhedra, Quadratic Programming Tags , , , , , , , ,

    Inspired by its occurrence as a substructure in a stochastic railway timetabling model, we study in this work a special case of the bipartite boolean quadric polytope. It models conditional relations across three sets of binary variables, where selections within two “if” sets imply a choice in a corresponding “then” set. We call this polytope … 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

    Binary Integer Program Reformulation: A Set System Approximation Approach

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

    This paper presents a generic reformulation framework for binary integer programs (BIPs) that does not impose additional specifications on the objective function or constraints. To enable this generality, we introduce a set system approximation theory designed to identify the tightest inner and outer approximations for any binary solution space using special types of set systems. … Read more

    Structural Insights and an IP-based Solution Method for Patient-to-room Assignment Under Consideration of Single Room Entitlements

  • Tabea Brandt
  • Christina Büsing
  • Felix Engelhardt
    • Categories 0-1 Programming, Applications - OR and Management Sciences, Combinatorial Optimization Tags , , ,

    Patient-to-room assignment (PRA) is a scheduling problem in decision support for large hospitals. This work proposes Integer Programming (IP) formulations for dynamic PRA, where either full, limited or uncertain information on incoming patients is available. The applicability is verified through a computational study. Results indicate that large, real world instances can be solved to a … Read more