Integer Programming

Sub-Exponential Lower Bounds for Branch-and-Bound with General Disjunctions via Interpolation

  • Max Gläser
  • Marc E. Pfetsch
    • Categories Integer Programming

    \(\) This paper investigates linear programming based branch-and-bound using general disjunctions, also known as stabbing planes, for solving integer programs. We derive the first sub-exponential lower bound (in the encoding length \(L\) of the integer program) for the size of a general branch-and-bound tree for a particular class of (compact) integer programs, namely \(2^{\Omega(L^{1/12 -\epsilon})}\) … Read more

    Optimization-based Learning for Dynamic Load Planning in Trucking Service Networks

  • Ritesh Ojha
  • Reem Khir
  • Alan L. Erera
    • Categories (Mixed) Integer Linear Programming, Production and Logistics, Transportation Tags , ,

    Citation Ojha, R., Chen, W., Zhang, H., Khir, R., Erera, A. & Van Hentenryck, P. (2023). Optimization-based Learning for Dynamic Load Planning in Trucking Service Networks. Article Download View Optimization-based Learning for Dynamic Load Planning in Trucking Service Networks

    Shattering Inequalities for Learning Optimal Decision Trees

  • Justin Boutilier
  • Carla Michini
  • Zachary Zhou
    • Categories (Mixed) Integer Linear Programming, Optimization in Data Science

    Recently, mixed-integer programming (MIP) techniques have been applied to learn optimal decision trees. Empirical research has shown that optimal trees typically have better out-of-sample performance than heuristic approaches such as CART. However, the underlying MIP formulations often suffer from weak linear programming (LP) relaxations. Many existing MIP approaches employ big-M constraints to ensure observations are … Read more

    Recycling Valid Inequalities for Robust Combinatorial Optimization with Budget Uncertainty

  • Christina Büsing
  • Timo Gersing
  • Arie M.C.A. Koster
    • Categories 0-1 Programming, Polyhedra, Robust Optimization Tags , , , ,

    Robust combinatorial optimization with budget uncertainty is one of the most popular approaches for integrating uncertainty into optimization problems. The existence of a compact reformulation for (mixed-integer) linear programs and positive complexity results give the impression that these problems are relatively easy to solve. However, the practical performance of the reformulation is quite poor when … Read more

    Exploiting user-supplied Decompositions inside Heuristics

  • Katrin Halbig
  • Adrian Göß
  • Dieter Weninger
    • Categories Integer Programming Tags , , , ,

    Numerous industrial fields, like supply chain management, face mixed-integer optimization problems on a regular basis. Such problems typically show a sparse structure and vary in size, as well as complexity. However, in order to satisfy customer demands, it is crucial to find good solutions to all such problems quickly. Current research often focuses on the … Read more

    The set partitioning problem in a quantum context

  • Rafael Farias Cacao
  • Lucas Ramos Cardoso Tinoco Cortez
  • Jackson Forner
  • Hamidreza Validi
  • Ismael de Farias
  • Illya V. Hicks
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Integer Programming

    The set partitioning problem and its decision variant (i.e., the exact cover problem) are combinatorial optimization problems that were historically crucial in the quantum optimization community. This problem is also employed in the main problem of the branch-and-price approach in many real-world optimization problems, including, but not limited to, redistricting and scheduling. Motivated by recent … Read more

    Gain Confidence, Reduce Disappointment: A New Approach to Cross-Validation for Sparse Regression

  • Ryan Cory-Wright
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Data Science Algorithms

    Ridge regularized sparse linear regression involves selecting a subset of features that explains the relationship between a high-dimensional design matrix and an output vector in an interpretable manner. To select the sparsity and robustness of linear regressors, techniques like leave-one-out cross-validation are commonly used for hyperparameter tuning. However, cross-validation typically increases the cost of sparse … Read more

    Distributionally Risk-Receptive and Robust Multistage Stochastic Integer Programs and Two-player Interdiction Games with(out) Decision-Dependent Uncertainty

  • Sumin Kang
  • Manish Bansal
    • Categories (Mixed) Integer Nonlinear Programming, Robust Optimization, Stochastic Programming Tags , , , , , ,

    In this paper, we study distributionally risk-receptive and distributionally robust (or risk-averse) multistage stochastic mixed-integer programs (denoted by DRR- and DRA-MSIPs). These frameworks are useful for optimization problems under uncertainty where the focus is on analyzing outcomes based on multiple decision-makers’ differing perspectives, such as interdiction problems that are attacker-defender games having non-cooperative players. We … Read more

    Using dual relaxations in multiobjective mixed-integer quadratic programming

  • Marianna De Santis
  • Gabriele Eichfelder
  • Daniele Patria
  • Leo Warnow
    • Categories (Mixed) Integer Nonlinear Programming, Multi-Criteria Optimization Tags , , ,

    We present a branch-and-bound method for multiobjective mixed-integer convex quadratic programs that computes a superset of efficient integer assignments and a coverage of the nondominated set. The method relies on outer approximations of the upper image set of continuous relaxations. These outer approximations are obtained addressing the dual formulations of specific subproblems where the values … Read more