Linear Programming

On the Single-Multi-Commodity Gap: Lifting Single- to Multicommodity Flow Instances

  • Felix P. Broesamle
  • Stefan Nickel
    • Categories Applications - OR and Management Sciences, Linear Programming, Network Optimization Tags , , , , ,

    Benchmark instances for multicommodity flow problems frequently lack the structural nuances of real-world networks or fail to maintain a rigorous mathematical relationship with their single-commodity counterparts. This paper introduces a formal meta-generation framework that addresses these limitations by lifting single-commodity minimum-cost flow instances into the multicommodity space while strictly preserving the underlying network topology, capacity … Read more

    Data-driven Policies For Two-stage Stochastic Linear Programs

  • Chhavi Sharma
  • Harsha Gangammanavar
    • Categories Linear Programming, Optimization in Data Science, Stochastic Programming Tags , , ,

    A stochastic program typically involves several parameters, including deterministic first-stage parameters and stochastic second-stage elements that serve as input data. These programs are re-solved whenever any input parameter changes. However, in practical applications, quick decision-making is necessary, and solving a stochastic program from scratch for every change in input data can be computationally costly. This … Read more

    Folding Mixed-Integer Linear Programs and Reflection Symmetries

  • Rolf van der Hulst
    • Categories (Mixed) Integer Linear Programming, Linear Programming Tags , , , ,

    For mixed-integer linear programming and linear programming it is well known that symmetries can have a negative impact on the performance of branch-and-bound and linear optimization algorithms. A common strategy to handle symmetries in linear programs is to reduce the dimension of the linear program by aggregating symmetric variables and solving a linear program of … Read more

    A simulation framework for Formula 1 race strategy based on pit-stop optimization

  • Mario Borruso
  • Pasquale Avella
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Optimization Software and Modeling Systems Tags , , , ,

    In modern Formula~1, strict regulations and highly optimized cars limit performance gains through hardware, increasing the importance of strategic decision-making. This work tackles the problem of computing a race strategy that minimizes total race time by jointly optimizing tire stints, compound selection, fuel load, and Energy Recovery System (ERS) deployment. We present a high-performance simulation … Read more

    A single loop method for quadratic minmax optimization

  • Stefano Cipolla
  • Oliver Stein
  • Alain Zemkoho
    • Categories Linear Programming, Quadratic Programming, Robust Optimization Tags

    We consider a quadratic minmax problem with coupled inner constraints and propose a method to compute a class of stationary points. To motivate the need to compute such stationary points, we first show that they are meaningful, in the sense that they can be locally optimal for our problem under suitable linear independence and second-order … Read more

    Column Generation for Generalized Min-Cost Flows with Losses

  • Jonas Alker
  • Marc E. Pfetsch
    • Categories Combinatorial Optimization, Linear Programming, Network Optimization Tags ,

    The generalized flow problem deals with flows through a network with losses or gains along the arcs. Motivated by energy networks, this paper concentrates on the case with losses along cycles. Such networks can become extremely large, mostly because they are considered over large time horizons. We therefore develop a column generation approach for a … Read more

    Optimization in Theory and Practice

  • Stephen Wright
    • Categories Convex Optimization, Linear Programming, Unconstrained Optimization Tags , ,

    Algorithms for continuous optimization problems have a rich history of design and innovation over the past several decades, in which mathematical analysis of their convergence and complexity properties plays a central role. Besides their theoretical properties, optimization algorithms are interesting also for their practical usefulness as computational tools for solving real-world problems. There are often … Read more

    An extension of an interior-point method to include risk aversion in large-scale multistage stochastic optimization

  • Jordi Castro
  • Laureano F. Escudero
  • Juan F. Monge
    • Categories Linear Programming, Stochastic Programming Tags , , , ,

    In the earlier paper “On solving large-scale multistage stochastic optimization problems with a new specialized interior-point approach, European Journal of Operational Research, 310 (2023), 268–285” the authors presented a novel approach based on a specialized interior-point method (IPM) for solving (risk neutral) large-scale multistage stochastic optimization problems. The method computed the Newton direction by combining … 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