Integer Programming

New Dynamic Discretization Discovery Strategies for Continuous-Time Service Network Design

  • Shengnan Shu
  • Zhou Xu
  • Roberto Baldacci
    • Categories Applications - OR and Management Sciences, Integer Programming, Network Optimization Tags , , ,

    Service Network Design Problems (SNDPs) are prevalent in the freight industry. While the classic SNDP is defined on a discretized planning horizon with integral time units, the Continuous-Time SNDP (CTSNDP) uses a continuous-time horizon to avoid discretization errors. Existing CTSNDP algorithms primarily rely on the Dynamic Discretization Discovery (DDD) framework, which iteratively refines discretization and … Read more

    A Single-Level Reformulation of Binary Bilevel Programs using Decision Diagrams

  • Sebastian Vasquez
  • Leonardo Lozano
  • Willem-Jan van Hoeve
    • Categories Bilevel Optimization, Combinatorial Optimization, Integer Programming Tags , ,

    Binary bilevel programs are notoriously difficult to solve due to the absence of strong and efficiently computable relaxations. In this work, we introduce a novel single-level reformulation of these programs by leveraging a network flow-based representation of the follower’s value function, utilizing decision diagrams and linear programming duality. This approach enables the development of scalable … Read more

    Mixed Integer Linear Programming Formulations for Robust Surgery Scheduling

  • Ankit Bansal
    • Categories (Mixed) Integer Linear Programming, Robust Optimization, Scheduling

    We introduce Mixed Integer Linear Programming (MILP) formulations for the two-stage robust surgery scheduling problem (2SRSSP). We derive these formulations by modeling the second-stage problem as a longest path problem on a layered acyclic graph and subsequently converting it into a linear program. This linear program is then dualized and integrated with the first-stage, resulting … Read more

    Improved Approximation Algorithms for Orthogonally Constrained Problems Using Semidefinite Optimization

  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms, Semi-definite Programming

    Building on the blueprint from Goemans and Williamson (1995) for the Max-Cut problem, we construct a polynomial-time approximation algorithm for orthogonally constrained quadratic optimization problems. First, we derive a semidefinite relaxation and propose a randomized rounding algorithm to generate feasible solutions from the relaxation. Second, we derive constant-factor approximation guarantees for our algorithm. When optimizing … Read more

    Bi-Parameterized Two-Stage Stochastic Min-Max and Min-Min Mixed Integer Programs

  • Sumin Kang
  • Manish Bansal
    • Categories Integer Programming, Network Optimization, Stochastic Programming Tags , , , ,

    We introduce two-stage stochastic min-max and min-min integer programs with bi-parameterized recourse (BTSPs), where the first-stage decisions affect both the objective function and the feasible region of the second-stage problem. To solve these programs efficiently, we introduce Lagrangian-integrated \(L\)-shaped (\(L^2\)) methods, which guarantee exact solutions when the first-stage decisions are pure binary. For mixed-binary first-stage … Read more

    Proximity results in convex mixed-integer programming

  • Burak Kocuk
  • Diego Moran Ramirez
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Cone Programming Tags , , , ,

    We study proximity (resp. integrality gap), that is, the distance (resp. difference) between the optimal solutions (resp. optimal values) of convex integer programs (IP) and the optimal solutions (resp. optimal values) of their continuous relaxations. We show that these values can be upper bounded in terms of the recession cone of the feasible region of … Read more

    Solving Multi-Follower Mixed-Integer Bilevel Problems with Binary Linking Variables

  • Vladimir Stadnichuk
  • Arie M.C.A. Koster
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Network Optimization Tags , , , ,

    We study multi-follower bilevel optimization problems with binary linking variables where the second level consists of many independent integer-constrained subproblems. This problem class not only generalizes many classical interdiction problems but also arises naturally in many network design problems where the second-level subproblems involve complex routing decisions of the actors involved. We propose a novel … Read more

    Polynomial-Time Algorithms for Setting Tight Big-M Coefficients in Transmission Expansion Planning with Disconnected Buses

  • Behnam Jabbari Marand
  • Adolfo Escobedo
    • Categories Combinatorial Optimization, Cutting Plane Approaches, Energy Tags , , ,

    The increasing penetration of renewable energy into power systems necessitates the development of effective methodologies to integrate initially disconnected generation sources into the grid. This paper introduces the Longest Shortest-Path-Connection (LSPC) algorithm, a graph-based method to enhance the mixed-integer linear programming disjunctive formulation of Transmission Expansion Planning (TEP) using valid inequalities (VIs). Traditional approaches for … Read more

    Neural Embedded Mixed-Integer Optimization for Location-Routing Problems

  • Waquar Kaleem
  • Anirudh Subramanyam
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design, Production and Logistics Tags , , ,

    We present a novel framework that combines machine learning with mixed-integer optimization to solve the Capacitated Location-Routing Problem (CLRP). The CLRP is a classical yet NP-hard problem that integrates strategic facility location with operational vehicle routing decisions, aiming to simultaneously minimize both fixed and variable costs. The proposed method first trains a permutationally invariant neural … Read more

    Mixed-Integer Bilevel Optimization with Nonconvex Quadratic Lower-Level Problems: Complexity and a Solution Method

  • Immanuel M. Bomze
  • Martin Schmidt
  • Horländer Andreas
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , ,

    We study bilevel problems with a convex quadratic mixed-integer upper-level, integer linking variables, and a nonconvex quadratic, purely continuous lower-level problem. We prove $\Sigma_p^2$-hardness of this class of problems, derive an iterative lower- and upper-bounding scheme, and show its finiteness and correctness in the sense that it computes globally optimal points or proves infeasibility of … Read more