(Mixed) Integer Linear Programming

The Surprising Performance of Random Partial Benders Decomposition

  • Jean Pauphilet
  • Yupeng Wu
    • Categories (Mixed) Integer Linear Programming, Integer Programming, Stochastic Programming Tags ,

    Benders decomposition is a technique to solve large-scale mixed-integer optimization problems by decomposing them into a pure-integer master problem and a continuous separation subproblem. To accelerate convergence, we propose Random Partial Benders Decomposition (RPBD), a decomposition method that randomly retains a subset of the continuous variables within the master problem. Unlike existing problem-specific approaches, RPBD … Read more

    Discovering Heuristics with Large Language Models (LLMs) for Mixed-Integer Programs: Single-Machine Scheduling

  • I. Esra Buyuktahtakin Toy
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Meta Heuristics Tags , , , , , , ,

    TitleDiscovering Heuristics with Large Language Models (LLMs) for Mixed-Integer Programs: Single-Machine Scheduling Authorsİbrahim Oğuz Çetinkaya^1; İ. Esra Büyüktahtakın^1*; Parshin Shojaee^2; Chandan K. Reddy^2 Affiliations^1 Grado Department of Industrial and Systems Engineering, Virginia Tech, Blacksburg, VA, USA^2 Department of Computer Science, Virginia Tech, Arlington, VA, USA Abstract: Our study contributes to the scheduling and combinatorial optimization … Read more

    Optimizing Expeditionary Logistics: Dynamic Discretization for Fleet Management

  • Haden Boone
  • Mathieu Dahan
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Production and Logistics Tags , , ,

    We introduce the Expeditionary Logistics Network Design Problem (ELNDP), a new formulation for operational-level planning in expeditionary environments where multi-modal vehicle coordination is critical and penalties for unmet demand dominate transportation costs. ELNDP extends the classical Scheduled Service Network Design Problem by incorporating flexible commodity sourcing and heterogeneous vehicle capabilities, both essential in military logistics. … Read more

    Extracting Alternative Solutions from Benders Decomposition

  • Matthew Viens
  • William E. Hart
  • Michael C. Ferris
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Stochastic Programming Tags , , , , ,

    We show how to extract alternative solutions for optimization problems solved by Benders Decom- position. In practice, alternative solutions provide useful insights for complex applications; some solvers do support generation of alternative solutions but none appear to support such generation when using Benders Decomposition. We propose a new post-processing method that extracts multiple optimal and … Read more

    What is the Best Way to Do Something? A Discreet Tour of Discrete Optimization

  • Thiago Serra
    • Categories (Mixed) Integer Linear Programming, Integer Programming Tags ,

    In mathematical optimization, we want to find the best possible solution for a decision-making problem. Curiously, these problems are harder to solve if they have discrete decisions. Imagine that you would like to buy chocolate: you can buy no chocolate or one chocolate bar, but typically you cannot buy just half of a bar. Now … Read more

    Integrated Bus Fleet Electrification Planning Through Accelerated Logic-Based Benders Decomposition and Restriction Heuristics

  • Robin Legault
  • Filipe Cabral
  • Xu Andy Sun
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design, Transportation Tags , ,

    To meet sustainability goals and regulatory requirements, transit agencies worldwide are planning partial and complete transitions to electric bus fleets. This paper presents the first comprehensive and computationally efficient multi-period optimization framework integrating the key planning decisions necessary to support such electrification initiatives. Our model, formulated as a two-stage integer program with integer subproblems, jointly … Read more

    Solving the Partial Inverse Knapsack Problem

  • Eva Ley
  • Nikolas Lykourinos
  • Maximilian Merkert
  • Andreas M. Tillmann
    • Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Branch and Cut Algorithms Tags , , , ,

    In this paper, we investigate the partial inverse knapsack problem, a bilevel optimization problem in which the follower solves a classical 0/1-knapsack problem with item profit values comprised of a fixed part and a modification determined by the leader. Specifically, the leader problem seeks a minimal change to given item profits such that there is … Read more

    An exact approach for the Train Single-Routing Selection Problem

  • Anna Livia Croella
  • Fabio Furini
  • Ivana Ljubić
  • Pablo San Segundo
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Transportation Tags , , , ,

    Given a set of train routes with route costs and a set of compatible route pairs with pairing costs, the Train Single-Routing Selection Problem (TSRSP) seeks to assign one route to each train, minimizing the total cost while ensuring pairwise compatibility among the selected routes. This problem is of significant practical relevance in rail traffic … Read more

    The Minimization of the Weighted Completion Time Variance in a Single Machine: A Specialized Cutting-Plane Approach

  • Stefano Nasini
  • Rabia Nessah
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Scheduling

    This study addresses the problem of minimizing the weighted completion time variance (WCTV) in single-machine scheduling. Unlike the unweighted version, which has been extensively studied, the weighted variant introduces unique challenges due to the absence of theoretical properties that could guide the design of efficient algorithms. We propose a mathematical programming framework based on a … Read more