OpenAlex ·
On the Complexity of Linear Programs with Parametric Constraint Matrices
- Published
- Source
- OpenAlex
- DOI
- 10.48550/arxiv.2610.20422
- Original
- Read it at the publisher
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Adaptive Randomized Neural Networks for PDEs: Structure-Aware Feature Redistribution and Residual-Driven Block Enrichment
Orientation Estimation of Cryo-EM Images for Molecules with Arbitrary Symmetry by Semidefinite Programming
Change the Number, Change the Answer: Assessing Rating Scale Sensitivity in LLM-Based Text Scoring
Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT
Optimal approximation of smooth functions by ReLU neural networks
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.