Integer Programming

An algorithm for generating Lagrangian bound sets in Multiobjective Integer Programming

  • Lavinia Amorosi
  • mcairo
  • Dellolmo
  • ssayin
    • Categories Integer Programming, Multi-Criteria Optimization Tags , , ,

    Lagrangian relaxation is a well-established technique for deriving strong bounds in single-objective discrete optimization. Its generalization to the multiobjective setting is not straightforward, as preserving the multiobjective structure leads to bound sets rather than scalar bounds. Recent studies show the existence of Lagrange multipliers that can yield tighter bound sets than those obtained from convex … Read more

    Convex Hulls of Binary Reflected Gray Code Intervals

  • Gustavo Angulo
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Polyhedra Tags , ,

    The binary reflected Gray code orders the vertices of the unit hypercube along a Hamiltonian path in which consecutive vertices differ in exactly one coordinate. While Gray codes have been extensively studied from a combinatorial perspective, much less is known about the polyhedral structure of convex hulls of contiguous subpaths of this order. This paper … Read more

    A Binary Search-Based Criterion Space Algorithm for Solving Bi-Objective Integer Programs: The Quadtree Search Method

  • Lagnajita Basu
  • Aadya Bhattarai
  • Tapas Das
  • Kimia Keshanian
  • Hadi Charkhgard
    • Categories Integer Programming, Multi-Criteria Optimization Tags , , , ,

    We propose an exact binary search-based branch-and-bound algorithm, termed the Quadtree Search Method, for solving bi-objective integer programs. The existing literature on criterion space search methods for multi-objective optimization predominantly assumes that subproblems can be solved to optimality, an assumption that becomes computationally prohibitive for hard instances. In contrast, our approach departs from this assumption … Read more

    Exact Methods for Solving k-Delete Recoverable Robust 0–1 Problems Under Budgeted Uncertainty

  • Yasmine Beck
  • Christina Büsing
  • Ivana Ljubić
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Robust Optimization

    We study the k-delete recoverable robust 0–1 problem in which a decision-maker solves a combinatorial optimization problem subject to objective uncertainty. The model follows a two-stage robust setup. The decision-maker first commits to an initial plan and may then revoke up to k components of this decision after the uncertainty is revealed. The underlying uncertainty … Read more

    A computational comparison of handling distance constraints in MINLP

  • Christopher Hojny
  • Leo Liberti
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    Minimum distance constraints (minDCs) appear in many geometric optimization problems. They pose major challenges for mixed-integer nonlinear programming (MINLP) due to their reverse-convexity. We develop new algorithms for tightening variable bounds in general MINLPs with minDCs. Because many such problems exhibit substantial symmetry, we further introduce a practical approach for handling rotation symmetries via separation … Read more

    Benders Cut Filtering for Affine Potential-Based Flow Problems with Robustness Scenarios and Topology Switching

  • Tim Donkiewicz
  • Oliver Gaul
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Energy Tags , , , ,

    Many large-scale optimization problems decompose into a master problem and scenario subproblems, a structure that can be exploited by Benders decomposition. In Benders decomposition, each iteration may generate many cuts from scenario subproblems, and adding all of them as constraints then causes the master problem to grow rapidly. These are constraints that may need to … Read more

    Multi-Fidelity Benders Decomposition for Generation, Storage, and Transmission Expansion Planning

  • Drew Mitchell
  • Andreas T. Ernst
  • Pierre Le Bodic
    • Categories (Mixed) Integer Linear Programming, Energy Tags , , , ,

    Modern energy grid expansion planning, by necessity, includes timeseries data to accurately model storage and renewable assets. Representative time periods are commonly used as a way to decrease problem size and therefore mitigate the increased complexity from this inclusion. However, there are many choices around these representative periods: length; location in planning horizon; boundary conditions. … Read more

    A polynomial-time solvable class of sparse box-constrained polynomial optimization problems

  • Aida Khajavirad
    • Categories (Mixed) Integer Nonlinear Programming Tags , , , , ,

    We study the problem of minimizing a multivariate polynomial function over the unit hypercube. By representing the polynomial through a hypergraph and exploiting its sparsity structure, we establish a new sufficient condition under which the problem can be solved in time polynomial in the encoding length of the input. Our approach identifies a subset of … Read more

    Probabilistic analysis of dual decomposition on two-stage stochastic integer programs

  • Jingye Xu
    • Categories Integer Programming, Stochastic Programming Tags ,

    Two-stage stochastic integer programs provide a powerful framework for modeling decision-making under uncertainty, but they are notoriously difficult to solve at scale due to their high dimensionality and intrinsic nonconvexity. Decomposition-based algorithms such as Benders methods and Branch-and-Price (related dual decomposition methods) have become standard computational approaches for such problems and demonstrate excellent empirical performance … Read more

    Reverse stress testing for supply chains

  • Busra Gultekin
  • Frans J.C.T. de Ruiter
  • Meike Reusken
  • Sander de Leeuw
    • Categories Applications - OR and Management Sciences, Integer Programming, Supply Chain Management Tags , , ,

    This study introduces reverse stress testing for supply chains, designed to identify the minimal deviations from normal operations that would drive supply chains to a predefined performance failure. First, we present a framework for reverse stress testing with the purpose of assessing supply chain vulnerabilities. The framework involves six steps: selecting risk variables, defining baselines, … Read more