Integer Programming

Globally Converging Algorithm for Multistage Stochastic Mixed-Integer Programs via Enhanced Lagrangian Cuts

  • Hanbin Yang
  • Haoxiang Yang
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , ,

    This paper proposes a globally converging cutting-plane algorithm for solving multistage stochastic mixed-integer programs with general mixed-integer state variables. We demonstrate the generation process of Lagrangian cuts and show that Lagrangian cuts capture the convex envelope of value functions on a restricted region. To approximate nonconvex value functions to exactness, we propose to iteratively add … Read more

    A 2-index Stage-based Formulation and a Construct-Merge-Solve & Adapt Algorithm for the Flying Sidekick Traveling Salesman Problem

  • Tran Khanh
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Meta Heuristics

    In this work, we present the first 2-index stage-based formulation for the Flying Sidekick Traveling Salesman Problem (FSTSP). Additionally, we propose a Construct-Merge-Solve & Adapt (CMSA) algorithm designed to generate high-quality feasible solutions. Experimental results demonstrate that the proposed algorithm consistently produces good solutions in a fraction of the time required by state-of-the-art mixed-integer linear … Read more

    Climate-Resilient Nodal Power System Expansion Planning for a Realistic California Test Case

  • Amelia Musselman
  • Tomas Valencia Zuluaga
  • Elizabeth Glista
  • Minda Monteagudo
  • J Michael Grappone
  • Jean-Paul Watson
    • Categories (Mixed) Integer Linear Programming, Energy, Stochastic Programming Tags , , , ,

    Climate change is increasingly impacting power system operations, not only through more frequent extreme weather events but also through shifts in routine weather patterns. Factors such as increased temperatures, droughts, changing wind patterns, and solar irradiance shifts can impact both power system production and transmission and electric load. The current power system was not designed … Read more

    A Branch and Price Algorithm for Scheduling in Surgery Pre-admission Testing Clinics

  • Ankit Bansal
    • Categories 0-1 Programming, Combinatorial Optimization, Scheduling Tags , , , ,

    A Surgery Pre-Admission Testing (PAT) clinic is a hospital unit designed to serve pre-operative patients by gathering critical patient information and performing procedure-specific tests to prepare them for surgery. Patients may require multiple tests, each conducted by a specialized nurse. A patient must be assigned to a room before starting any test and must stay … Read more

    Integer Control Approximations for Graphon Dynamical Systems

  • Martin T. Köhler
  • Artemi Makarow
  • Christian Kirches
    • Categories (Mixed) Integer Nonlinear Programming, Nonlinear Optimization, Systems governed by Differential Equations Optimization Tags , , ,

    Graphons generalize graphs and define a limit object of a converging graph sequence. The notion of graphons allows for a generic representation of coupled network dynamical systems. We are interested in approximating integer controls for graphon dynamical systems. To this end, we apply a decomposition approach comprised of a relaxation and a reconstruction step. We … Read more

    Operationalizing Experimental Design: Data Collection for Remote Ocean Monitoring

  • Jean Pauphilet
  • Baizhi Song
    • Categories (Mixed) Integer Nonlinear Programming, Statistics, Transportation Tags , , , ,

    Problem definition: To collect data on ocean plastic pollution and build more accurate predictive models, we need to manually take high-resolution pictures of the sea surface via floating or flying drones. Operating these vehicles, like many data collection problems in agriculture or environmental science, challenges the traditional optimal experimental design (OED) formulation from statistics by … Read more

    Risk-aware Logic-based Benders Decomposition for a Location-Allocation-Pricing Problem with Stochastic Price-Sensitive Demands

  • Maryam Daryalal
  • Ahmadi-Javid Amir
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design, Stochastic Programming Tags , ,

    We consider a capacitated location-allocation-pricing problem in a single-commodity supply chain with stochastic price-sensitive demands, where the location, allocation and pricing decisions are made simultaneously. Under a general risk measure representing an arbitrary risk tolerance policy, the problem is modeled as a two-stage stochastic mixed-integer program with a translation-invariant monotone risk measure. To solve the … Read more

    Analyzing the numerical correctness of branch-and-bound decisions for mixed-integer programming

  • Alexander Hoen
  • Ambros Gleixner
    • Categories (Mixed) Integer Linear Programming, Integer Programming Tags , ,

    Most state-of-the-art branch-and-bound solvers for mixed-integer linear programming rely on limited-precision floating-point arithmetic and use numerical tolerances when reasoning about feasibility and optimality during their search. While the practical success of floating-point MIP solvers bears witness to their overall numerical robustness, it is well-known that numerically challenging input can lead them to produce incorrect results. … Read more

    Multi-Stage Selection under Bounded Variation

  • Christoph Buchheim
  • Maja Hügging
    • Categories 0-1 Programming, Dynamic Programming Tags , , , ,

    We investigate a multi-stage version of the selection problem where the variation between solutions in consecutive stages is either penalized in the objective function or bounded by hard constraints. While the former problem turns out to be tractable, the complexity of the latter problem depends on the type of bounds imposed: When bounding the number … Read more

    A Two-stage Stochastic Programming Approach for CRNA Scheduling with Handovers

  • Ankit Bansal
  • Osman Y. Ozaltin
    • Categories (Mixed) Integer Linear Programming, Scheduling, Stochastic Programming Tags , , ,

    We present a two-stage stochastic integer program for assigning Certified Registered Nurse Anesthetists (CRNAs) to Operating Rooms (ORs) under surgery duration uncertainty. The proposed model captures the trade-offs between CRNA staffing levels, CRNA handovers and under-staffing in the ORs. Since the stochastic program includes binary variables in both stages, we present an Integer L-shaped Algorithm … Read more