(Mixed) Integer Linear Programming

An interactive optimization framework for incorporating a broader range of human feedback into stochastic multi-objective mixed integer linear programs

  • Damsara Jayarathne
  • Jennifer Pazour
  • John E. Mitchell
    • Categories (Mixed) Integer Linear Programming, Multi-Criteria Optimization, Stochastic Programming Tags , , , ,

    Interactive optimization leverages the strengths of optimization frameworks alongside the expertise of human users. Prior research in this area tends to either ask human users for the same type of information, or when varying information is requested, users must manually modify the optimization model directly. These limitations restrict the incorporation of wider human knowledge into … Read more

    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

    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