On the Complexity of Linear Programs with Parametric Constraint Matrices
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.
Related
- Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time
- Riemannian Structure and Optimization for a Class of Low-Parametric Orthogonal Matrices
- The Complexity of KKT Points of Quadratic Programs with Polynomially-Bounded Coefficients
- Super-approximation and optimal L2 convergence of the stabilized BGN method with piecewise linear parametric finite elements for curve-shortening flow
- Treewidth and the complexity of box-constrained quadratic programs
BibTeX
@misc{boveroux2026complexity,
title = {{On the Complexity of Linear Programs with Parametric Constraint Matrices}},
author = {Laurie Boveroux and Margarida Carvalho and Andrea Lodi and Quentin Louveaux},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20422},
eprint = {2610.20422},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20422},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - On the Complexity of Linear Programs with Parametric Constraint Matrices
AU - Laurie Boveroux
AU - Margarida Carvalho
AU - Andrea Lodi
AU - Quentin Louveaux
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20422
UR - https://arxiv.org/abs/2610.20422
AB - 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.
ER -