Linear Programming

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

    Inspection Games with Incomplete Information and Heterogeneous Resources

  • Bobak McCann
  • Mathieu Dahan
    • Categories Game Theory, Linear Programming, Stochastic Programming Tags , , , ,

    We study a two-player zero-sum inspection game with incomplete information, where an inspector deploys resources to maximize the expected damage value of detected illegal items hidden by an adversary across capacitated locations. Inspection and illegal resources differ in their detection capabilities and damage values. Both players face uncertainty regarding each other’s available resources, modeled via … Read more

    On Parametric Linear Programming Duality

  • Benjamin Hamlin
  • Nathan Adelgren
  • Margaret Wiecek
    • Categories Linear Programming, Other Topics Tags , , ,

    Recognizing the strength of parametric optimization to model uncertainty, we extend the classical linear programming duality theory to a parametric setting. For linear programs with parameters in general locations, we prove parametric weak and strong duality theorems and parametric complementary slackness theorems. ArticleDownload

    Solving a linear program via a single unconstrained minimization

  • Adilet Otemissov
  • Alina Abdikarimova
    • Categories Linear Programming, Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , , , ,

    This paper proposes a novel approach for solving linear programs. We reformulate a primal-dual linear program as an unconstrained minimization of a convex and twice continuously differentiable merit function. When the optimal set of the primal-dual pair is nonempty, its optimal set is equal to the optimal set of the proposed merit function. Minimizing this … Read more

    Efficient LP warmstarting for linear modifications of the constraint matrix

  • Guillaume Derval
  • Bardhyl Miftari
  • Quentin Louveaux
    • Categories Linear Programming, Robust Optimization

    We consider the problem of computing the optimal solution and objective of a linear program under linearly changing linear constraints. The problem studied is given by $\min c^t x \text{ s.t } Ax + \lambda Dx \leq b$ where $\lambda$ belongs to a set of predefined values $\Lambda$. Based on the information given by a … Read more

    High-Probability Polynomial-Time Complexity of Restarted PDHG for Linear Programming

  • Zikai Xiong
    • Categories Linear Programming Tags , , ,

    The restarted primal-dual hybrid gradient method (rPDHG) is a first-order method that has recently received significant attention for its computational effectiveness in solving linear program (LP) problems. Despite its impressive practical performance, the theoretical iteration bounds for rPDHG can be exponentially poor. To shrink this gap between theory and practice, we show that rPDHG achieves … Read more

    On parametric formulations for the Asymmetric Traveling Salesman Problem

  • Gustavo Angulo
  • Diego Moran Ramirez
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Polyhedra

    The traveling salesman problem is a widely studied classical combinatorial problem for which there are several integer linear formulations. In this work, we consider the Miller-Tucker-Zemlin (MTZ), Desrochers-Laporte (DL) and Single Commodity Flow (SCF) formulations. We argue that the choice of some parameters of these formulations is arbitrary and, therefore, there are families of formulations … Read more

    When Does Primal Interior Point Method Beat Primal-dual in Linear Optimization?

  • Wenzhi Gao
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , ,

    The primal-dual interior point method (IPM) is widely regarded as the most efficient IPM variant for linear optimization. In this paper, we demonstrate that the improved stability of the pure primal IPM can allow speedups relative to a primal-dual solver, particularly as the IPM approaches convergence.  The stability of the primal scaling matrix makes it … Read more

    Sensitivity analysis for linear changes of the constraint matrix of a (mixed-integer) linear program

  • Bardhyl Miftari
  • Quentin Louveaux
  • Guillaume Derval
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming, Robust Optimization

    Understanding how the optimal value of an optimisation problem changes when its input data is modified is an old question in mathematical optimisation. This paper investigates the computation of the optimal values of a family of (possibly mixed-integer) linear optimisation problems in which the constraint matrix is subject to linear perturbations controlled by a scalar … Read more