CS Paper Radar

Linear Objective Problems: A Complexity Framework for Bilevel Optimization

Christoph Grüne, James B. Orlin, Lasse Wulf

cs.CC cs.DMmath.COmath.OC ·submitted 2026-11-08 13:35 UTC · v1
theory

Abstract

Many bilevel and robust optimization problems are complete for the second level of the polynomial hierarchy, but such results are usually proven one problem at a time with problem-specific reductions. A recurring obstacle is that the lower level must select an optimal solution rather than merely a feasible one, whereas standard reductions preserve only whether a solution exists, not which solutions are optimal. We introduce linear objective problems (LOP), a framework for optimization problems whose solutions are explicit subsets of a ground set and whose objective is linear in these elements. We define tight solution-embedding reductions, which map the optimal solutions of one problem element by element onto the optimal solutions of another, without having to recognize optimal solutions, which is coNP-hard in general. This gives a notion of LOP-completeness, with Satisfiability as the canonical complete problem, even with unit weights. We show that many classical problems are LOP-complete, including Vertex Cover, Dominating Set, TSP, Knapsack, and Steiner Tree, and we introduce a duality that transfers LOP-completeness between minimization and maximization problems. As our main application, we prove a meta-theorem for min-max regret optimization under interval uncertainty: for every LOP-complete problem, the min-max regret version is $Σ_2^p$-complete. Instead of a separate proof for each nominal problem, it suffices to show that the nominal problem is LOP-complete. This recovers known results for the interval min-max regret versions of Knapsack and Maximum Benefit Set Cover and yields completeness for over 50 further problems.

Closest papers

Nearest neighbours by meaning across the whole index.

On the Tightness of Standard Relaxations for Mixed-Integer Bilevel Linear Programs

cs.CC math.OC ·2026-09-09 ·Sergey S. Ketkov, Oleg A. Prokopyev
theory similarity 0.67
Abstract

Exact algorithms for solving mixed-integer bilevel linear programs (MIBLPs) typically rely on sequences of lower and upper bounds that converge to the optimal value. These procedures are commonly initialized using the single-level relaxation (SLR), obtained by omitting the follower's optimality condition and solving the resulting single-level optimization problem. In this paper, we investigate whether, for broad classes of MIBLPs, the resulting standard bounds admit uniform improvements that can be computed within the same computational complexity regime. For pure continuous bilevel linear programs, we show that, unless $P = NP$, neither the SLR-based lower bound nor its associated upper bound can be uniformly improved in polynomial time, even for the class of min-max problems. We then extend this analysis to the class of pure integer min-max bilevel linear programs under the assumption that the polynomial hierarchy does not collapse. First, we show that the continuous relaxation of the SLR admits no uniform polynomial-time computable improvement. We then prove that neither the SLR itself nor its associated upper bound admits a uniform improvement by a polynomial-time algorithm with access to a mixed-integer linear programming (MILP) oracle. Importantly, this rules out uniform improvements by iterative MILP-based approaches, including cutting-plane-based and decomposition algorithms. Overall, our results demonstrate that the SLR-based bounds are, in a complexity-theoretic sense, unimprovable systematically within their natural computational regimes.

0.24

Tight Approximation Results for Matroid Optimization with a Linear Constraint

cs.DS ·2026-09-23 ·Ilan Doron-Arad, Hadas Shachnai, Gilad Shmerler
similarity 0.66
Abstract

We study the following class of matroid optimization problems with a linear constraint (P-MOL). Given a matroid M=(E,I), two weight functions $v,w:E\to R_{\ge 0}$, and a threshold $L\in R_{\ge 0}$, find $opt v(S)$ where S is either an independent set or a base of M satisfying a budget-type constraint: $w(S)\le L$ or $w(S)\ge L$, and $opt\in\{min,max\}$. P-MOL provides a unified representation for a broad family of NP-hard optimization problems, including budgeted matroid independent set, constrained minimum-basis, and knapsack-cover variants with a matroid constraint. Also, it naturally extends to multiple matroid constraints. In particular, we consider the matroid intersection cover (MIC) problem, where feasibility is defined by the common independent sets of two matroids and one seeks minimum $v(S)$ subject to $w(S)\ge L$. Our main result is a unified EPTAS for all nontrivial P-MOL variants, obtained by generalizing a technique of Hassin and Levin (SIAM J. Comput., 2004) for solving the constrained minimum spanning tree problem. Specifically, for any fixed $ε>0$, we present an algorithm running in time $|E|^{O(1)} (1/{ε^2})^{O(1/ε)}$ that outputs a feasible solution S whose value is at most $(1+ε)OPT$ for minimization variants and at least $(1-ε)OPT$ for maximization variants. This resolves the complexity status of all members of P-MOL, as none of these problems admits an FPTAS (Doron-Arad, Kulik and Shachnai, ICALP'24). Finally, we separate the P-MOL family from its extension to matroid intersection. We show that an EPTAS is unlikely to exist for the matroid intersection variant of P-MOL under a covering constraint, whereas an EPTAS is known to exist under a budget constraint. This highlights a qualitative difference between these two types of linear constraints that does not arise in the single-matroid setting.

0.14

On the Complexity of Linear Programs with Parametric Constraint Matrices

cs.CC math.OC ·2026-10-14 ·Laurie Boveroux, Margarida Carvalho, Andrea Lodi, Quentin Louveaux
benchmark similarity 0.65
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.

0.38

The Complexity of Recognizing SDP Exactness for the Maximum Cut Problem

cs.CC math.OC ·2026-09-03 ·Avinash Bhardwaj
similarity 0.65
Abstract

The standard semidefinite programming (SDP) relaxation of Max-Cut is exact when its optimum equals the maximum cut value. Delorme and Poljak resolved NP-completeness of recognizing exactness for weighted graphs and left the unweighted case open. We show that recognition is NP-complete even for connected simple unweighted graphs, and hence strongly NP-complete for nonnegative integer edge weights. The reduction provides an explicit SDP optimum and makes the additive integrality gap equal to the minimum number of unsatisfied clauses in the source formula. Recognition remains NP-complete even when an exact rational optimal primal--dual pair is supplied. We also establish strong NP-hardness of recognizing exactness of the Frieze--Jerrum Max-$k$-Cut relaxation for every fixed $k\ge3$, even for connected graphs with nonnegative integer edge weights. An independent bounded-weight construction gives a second proof for Max-Cut. Finally, reductions preserving the additive gap up to explicit factors establish strong NP-completeness of exactness recognition for a basic Max-DiCut SDP and NP-hardness for a Max-Bisection SDP.

0.33

Integrality gap preserving reductions

cs.DM cs.DS ·2026-09-17 ·Koppány István Encz, Monaldo Mastrolilli, Eleonora Vercesi
theory similarity 0.64
Abstract · 30 pages, 2 figures

We propose a framework for the systematic study of integrality gaps of combinatorial optimization problems with respect to a fixed linear programming formulation. The method, called \emph{integrality gap preserving reduction}, consists of iteratively shrinking the input universe of the problem while guaranteeing that gap-maximizing instances remain selected. When the subset of remaining instances becomes specific enough, we calculate the integrality gap explicitly. Besides applying integrality gap preserving reductions to three well-known optimization problems via their standard linear programming formulations (weighted vertex cover problem, multiple knapsack problem, and unrelated machine scheduling problem), we analyse the restricted assignment problem via its configuration LP relaxation. We prove that the integrality gap is equal to $1$ for three ``easy'' subclasses of the problem that are either solvable in polynomial time or admit a PTAS (e.g., the all-one processing time case). For some remaining cases, we improve the current lower bound using our technique.

0.43

Standard Quadratic Formulations of Many NP Problems: A Simplex-Based Compilation Framework for Combinatorial Optimization

cs.ET ·2026-10-01 ·Mohammad-Ali Miri, Babak Emami, PoJen Wang
similarity 0.62
Abstract

The standard quadratic program (StQP) minimizes a quadratic form over nonnegative variables that sum to one. We compose classical graph reductions with regularized Motzkin--Straus clique formulations to express discrete optimization problems in this continuous domain. The graph matrix has diagonal entries $τ$, zeros on edges, and ones on nonedges. For $0<τ<1$, its minimum is $τ/ω(G)$, where $ω(G)$ is the clique number. Its strict local minimizers are precisely the uniform distributions on maximal cliques, and its global minimizers encode maximum cliques. At $τ=1/2$, integer scaling gives coefficients in $\{0,1,2\}$ and minimum $1/ω(G)$, yielding an NP-complete StQP threshold problem with a restricted coefficient alphabet. We give explicit formulations for satisfiability, coloring, Hamiltonian cycles, independent set, vertex cover, set packing, three-dimensional matching, and graph isomorphism. A regularized weighted clique formulation combined with local-state compatibility graphs gives an exact compiler for finite-domain factor models specified by complete local tables, including QUBO, with at most four simplex coordinates per binary pair factor. The catalog covers Karp's 21 problems: twelve use direct graph formulations, and nine use factor-state formulations, including six obtained through binary-linear feasibility. For each route we record dimensions, coefficient structure, and recovery rules. We analyze interaction count, coefficient range, objective separation, perturbation tolerance, support recovery, and decoding overhead. The separation bounds quantify the effects of clique size, factor weights, and offsets. In the complete factor-state construction, every assignment, including each suboptimal assignment, is a strict local minimum.

0.16

Tight Algorithms for Conservative Finite-Valued CSPs Parameterized by Treewidth

cs.DS cs.CC ·2026-11-12 ·Jakob Greilhuber, Dániel Marx, George Osipov, Marta Piecyk, Paweł Rzążewski +1 more
similarity 0.61
Abstract · The abstract has been truncated for arXiv

We consider valued constraint satisfaction problems (VCSPs) with a fixed finite domain $D$ and a fixed finite constraint language $Γ$, in the setting where $Γ$ contains all crisp unary constraints (called hard lists) and the remaining cost functions are finite-valued. We call such a language a finite-valued hard-list language. Let $c_Γ$ be the size of the largest set $S\subseteq D$ such that $Γ$ can express (using the usual VCSP closure operations) a binary disequality function on elements of $S$. Our main result tightly connects the complexity of the problem parameterized by treewidth to this value $c_Γ$. (1) The problem can be solved in time $(c_Γ)^{\mathsf{tw}} \cdot (|I| + |\mathcal{T}|)^{O(1)}$ when given an instance $I$ with a tree decomposition $\mathcal{T}$ of width $\mathsf{tw}$ of the primal graph of $I$. (2) If $c_Γ\geq 2$, there is no such algorithm solving the problem in time $(c_Γ- \varepsilon)^{\mathsf{tw}} \cdot (|I| + |\mathcal{T}|)^{O(1)}$ for any $\varepsilon > 0$, unless the Primal Treewidth SETH (and hence CNF-SETH) fails. In particular, this gives a far-reaching generalization of a similar result of Esmer et al. [ESA 2024] on the optimization version of list homomorphism for graphs.

0.23

Combinatorial optimization with bounded subdeterminants

cs.DS cs.DMmath.COmath.OC ·2026-11-09 ·Samuel Fiorini, J. Pascal Gollin, Tony Huynh, Simon Keil, O-joung Kwon +3 more
similarity 0.61
Abstract · 25 pages

We take a first step toward a broader study of classical combinatorial optimization problems through the maximum subdeterminants of their standard integer programming formulations, yielding new positive results for several famous (NP-hard) problems. An integer matrix is totally $Δ$-modular if every square submatrix has determinant of absolute value at most $Δ$. For every fixed $Δ$, it has been known that maximum clique, maximum stable set, and minimum vertex cover can be solved in polynomial time on instances for which the coefficient matrix of the natural formulation is totally $Δ$-modular. We extend this list by showing that the same holds for many other problems, including the weighted versions of maximum cut, the traveling salesman problem, feedback vertex set, odd cycle transversal, dominating set, max 2-sat, induced matching, and cluster vertex deletion, as well as for $k$-colorability and graph isomorphism. Our proofs reveal several new ways in which bounded subdeterminants impose combinatorial structure: they bound the size or maximum degree of the input graph, bound packings of cycles and other obstructions, or yield decompositions into tractable graph classes such as forests, chordal graphs, graphs of bounded treewidth, and graphs of bounded linear mim-width.

0.20