Parametric linear program complexity varies for minimum and maximum values
On the Complexity of Linear Programs with Parametric Constraint Matrices
Computational Complexity
Summary
Linear programs help solve problems with many conditions, but when those conditions depend on a changing number, it's trickier to understand how the best answers change. The authors found that figuring out the worst or best possible answers when the problem’s rules change is very hard in general. However, under some specific conditions, the problem becomes easier to solve. They also noticed that finding the smallest best answer is usually fast, but finding the largest best answer can be slow, due to some mathematical details.
What this means in practice
- •For operations research analysts: Identify cases when varying constraints lead to efficiently solvable parametric linear programs, enabling better decision support under changing conditions.
- •For supply chain planners: Understand when fluctuations in constraints affect optimization speed to better plan resource allocations under uncertainty.
Tested on standard benchmark instances.
Authors
Laurie Boveroux, Margarida Carvalho, Andrea Lodi, Quentin Louveaux
Abstract
While sensitivity analysis for linear programs with parametric right- hand side vectors is well established, cases involving parametric constraint matrices remain less explored. To address this gap, we investigate linear programs where the constraint matrix depends linearly on a scalar parameter. Our goal is to compute the minimum and maximum optimal values of these parametric linear programs within a fixed parameter range. This corresponds to solving two bilevel programs. We show that both decision versions of these optimization problems are NP-complete by proving both NP-hardness and membership in NP. We additionally identify three sufficient conditions on the parametric matrix under which the bilevel programs are no longer NP-hard. We introduce a reformulation for both problems, together with a Farkas-based certificate for the lower-level feasibility condition, and compare the execution time for solving them on standard benchmark instances. The experiments highlight a practical dichotomy. Although both bilevel optimizations are NP-hard, computing the parameter value corresponding to the minimum of the linear program is fast, whereas computing the value corresponding to the maximum is not. We relate this asymmetry to the parametric equality constraints, whose free dual variables leave the relaxation of the maximum reformulation unbounded.