(Mixed) Integer Linear Programming

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

    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 valid inequalities to tighten … Read more

    MIP-DD: Delta Debugging for Mixed Integer Programming Solvers

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

    The recent performance improvements in mixed-integer programming (MIP) have been accompanied by a significantly increased complexity of the codes of MIP solvers, which poses challenges in fixing implementation errors. In this paper, we introduce MIP-DD, a solver-independent tool, which to the best of our knowledge is the first open-source delta debugger for MIP. Delta debugging … Read more

    Integrated Schedule Planning for Regional Airlines Using Column Generation

  • Alberto Santini
    • Categories (Mixed) Integer Linear Programming, Airline Optimization, Combinatorial Optimization Tags , , , ,

    Problem definition: More than one-third of US domestic flights are operated by regional airlines. This paper focuses on optimizing medium-term schedule planning decisions for a network of regional airlines through the joint optimization of frequency planning, timetable development, fleet assignment, and some limited aspects of route planning, while capturing passengers’ travel decisions through a general … Read more

    Risk-Averse Antibiotics Time Machine Problem

  • Deniz Tuncer
  • Burak Kocuk
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering, Stochastic Programming Tags , , ,

    Antibiotic resistance, which is a serious healthcare issue, emerges due to uncontrolled and repeated antibiotic use that causes bacteria to mutate and develop resistance to antibiotics. The Antibiotics Time Machine Problem aims to come up with treatment plans that maximize the probability of reversing these mutations. Motivated by the severity of the problem, we develop … 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 Low-Rank Problems Using Semidefinite Optimization

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

    Inspired by the impact of the Goemans-Williamson algorithm on combinatorial optimization, we construct an analogous relax-then-sample strategy for low-rank optimization problems. First, for orthogonally constrained quadratic optimization problems, we derive a semidefinite relaxation and a randomized rounding scheme, which obtains provably near-optimal solutions, mimicking the blueprint from Goemans and Williamson for the Max-Cut problem. We … 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