CS Paper Radar

Mixed-integer dual network problems are solvable in strongly polynomial time

Giacomo Zambelli

cs.DS math.OC ·submitted 2026-11-10 13:13 UTC · v1

Abstract

In this paper we show that mixed-integer linear programming is solvable in strongly polynomial time if the constraint matrix is totally unimodular with at most two nonzero entries in every row. This is done by reducing the problem to an instance of minimization of an $L$-convex function.

Closest papers

Nearest neighbours by meaning across the whole index.

Parametrize Integer Programming by Packing Imbalanced Circuits

cs.DS math.OC ·2026-11-08 ·Yuheng Shi
similarity 0.63
Abstract

We study the standard form Integer Programming problem (IP) parametrized by the imbalanced circuit packing number. This number is $0$ if and only if $A$ can be transformed to a totally unimodular matrix by row operations, in which case (IP) is solvable in polynomial time. We show that if the constraint matrix represents a graphic matroid, (IP) is fixed-parameter tractable when parametrized by the imbalanced circuit packing number of the matrix. The proof combines an Erdős-Pósa property for edge-colored non-monochromatic cycles with a reduction to mixed-integer programming using few integer variables. In contrast, by a reduction from the parity potential problem, we show NP-completeness of feasibility of (IP) when the constraint matrix represents a cographic matroid, even if kernel of the constraint matrix is $2$-regular and imbalanced circuits pairwise intersect.

0.27

Extending Tardos's Theorem to Separable Convex Quadratic Programming

cs.DS ·2026-10-05 ·Bin Cui, Hanqing Li, Xupeng Miao
theory similarity 0.60
Abstract · 13 pages, no figures. Substantially revised with a simplified algorithm and proofs. Title and author list updated

For an integer equality matrix $A\in\mathbb{Z}^{r\times m}$ of binary encoding length $\langle A\rangle$, Tardos's theorem solves linear programs using $\operatorname{poly}(r,m,\langle A\rangle)$ rational arithmetic operations and comparisons, independently of the right-hand side and objective coefficients. We extend this guarantee to continuous separable convex quadratic programming over $Ax=b$, $x\ge0$: the operation count is independent of the right-hand side, linear costs, and all nonnegative quadratic weights. The algorithm returns an exact optimal primal-dual pair or a certificate of infeasibility or unboundedness. All intermediate rational numbers have encoding lengths polynomial in the total input length. As an application, we obtain a strongly polynomial algorithm for continuous multicommodity flow with shared capacities and quadratic costs of aggregate arc flow, independently of demands, capacities, and cost coefficients. Objective compression and continuous-integer proximity yield a local solver returning a point close to an optimum. We relax nonnegativity on coordinates with zero optimal dual slack, minimize the largest remaining coordinate, and optimize over the relaxed coordinates. A descent LP over the recession cone provides a complementary bound. Circuit decomposition combines these bounds into a scale ensuring that each local call reveals a new coordinate. At most $m$ calls, followed by two LPs, recover an exact optimum and its dual certificate.

0.20

Hardness of integer linear feasibility with cyclic support

cs.DM math.OC ·2026-11-05 ·Marco Di Summa
theory similarity 0.59
Abstract

We prove that integer linear feasibility is strongly $NP$-complete even when the constraint matrix has exactly two nonzero entries in every row and column, with its support forming a single cycle. This holds already for monotone systems (one positive and one negative coefficient in each inequality) with nonzero coefficients of absolute value $2$ or $3$ and right-hand sides in $\{-1,0,1,2\}$. No variable bounds are supplied separately from the system. For systems in which each inequality involves at most two variables, this strengthens known hardness results by restricting all numerical data to fixed finite sets. For systems in which each variable occurs in at most two inequalities, this establishes, to the best of our knowledge, the first $NP$-hardness result for feasibility. We also give negative answers, unless $P=NP$, to questions on polynomial-time solvability of integer programs with bounded coefficients and bounded totally $Δ$-modular treewidth, and on fixed-parameter tractability of integer bound propagation with respect to coefficient and right-hand-side magnitudes.

0.24

Two-Stage Mixed-Integer Quadratic Programming in Polynomial Time

cs.CC math.OCcs.DS ·2026-11-10 ·Alberto Del Pia
similarity 0.58
Abstract

Lenstra showed that mixed-integer linear programming can be solved in polynomial time when the number of integer variables is fixed and the number of continuous variables is arbitrary. Mixed-integer quadratic programming (MIQP) can be solved in polynomial time when the total number of variables is fixed. However, since MIQP is NP-hard already without integer variables, the analog of Lenstra's result fails unless P = NP. Hence, polynomial-time algorithms for MIQP with an arbitrary number of continuous variables must exploit additional structure. We study MIQPs with two-stage structure, which underlies Benders decomposition and two-stage stochastic programming. A few linking variables, including all integer variables, are coupled with many blocks of continuous variables that interact only through them, both in the constraints and in the objective. We give a polynomial-time algorithm for MIQP with an arbitrary quadratic objective when the number of linking variables and the block size are fixed, while the number of blocks, and hence the number of variables, is arbitrary. The case with no blocks is MIQP in fixed dimension. None of our assumptions can be dropped. Unless P = NP, the number of linking variables and the block size must both be fixed, the blocks cannot interact or contain integer variables, and large blocks cannot be allowed even if their objective is linear. Unless FPT = W[1], the exponent of the running time must depend on both the number of linking variables and the block size.

0.34

Low-Rank and Lifted Semidefinite Programming for Mixed-Integer Polynomial Power Grid Optimization

eess.SY math.OC ·2026-09-29 ·Samuel Chevalier
similarity 0.56
Abstract · Submitted to Allerton 2026

Can a local solver return the guaranteed globally optimal solution to a nonconvex mixed-integer polynomial power grid optimization problem? By mixing low-rank semidefinite programming (SDP) and moment-based lifting in the Lasserre hierarchy, this paper provides anecdotal evidence in the affirmative. Specifically, we iteratively tighten a moment-based relaxation of the AC Optimal Transmission Switching (AC-OTS) problem, including higher order moment-based constraints, rooted in the Lasserre hierarchy, until it is tight (i.e., primal feasible). We then re-solve this problem using a local, low-rank SDP solver (Knitro), plugging the associated dual variables into a bounding Lagrange dual function. By demonstrating primal and dual objective agreement and primal feasibility, we confirm the solution as the exact, global solution. From these initial results, we hypothesize that mixing (i) low-rank (i.e., highly scalable) SDP methods with (ii) moment-based relaxation tightening could be a scalable alternative to global branch-and-bound-based methods.

0.49

Integer Quadratic Programming is W[1]-Hard Parameterized by the Number of Variables

cs.CC cs.DSmath.OC ·2026-08-18 ·Anton Herrmann
highly cited similarity 0.56
Abstract

We show that Integer Quadratic Programming is W[1]-hard parameterized by the number of variables. Thus, under standard complexity assumptions, Integer Quadratic Programming cannot be solved in f(n)|I|^{O(1)} time for any computable function f where |I| is the size of the encoding and n is the number of variables.

0.47

Tight Approximation Results for Matroid Optimization with a Linear Constraint

cs.DS ·2026-09-23 ·Ilan Doron-Arad, Hadas Shachnai, Gilad Shmerler
similarity 0.56
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

Budget-Constrained Graph Augmentation for Robust Network Design via Kirchhoff Index Minimization

cs.SI math.OCeess.SP ·2026-09-24 ·Omkar Bhoite, V Sateeshkrishna Dhuli, Stefan Werner, Kimmo Kansanen
benchmarktheory similarity 0.55
Abstract · 12 pages, 7 figures, 3 tables. Submitted to IEEE Transactions on Network Science and Engineering. A preliminary version of this work was pre…

Enhancing the robustness of deployed networks against failures and disruptions is critical for reliable operation. This requires deciding which new links to install and how strongly to weight them under limited resources. We study this problem through the Kirchhoff index, or total effective resistance, a spectral measure of global connectivity. The resulting augmentation problem couples discrete candidate-edge selection with continuous weight allocation under heterogeneous per-unit deployment costs, a total budget, and an exact-cardinality constraint. For a fixed weighted base graph, this yields a mixed-integer formulation and a semidefinite relaxation whose optimum lower-bounds the mixed-integer optimum. We cast the relaxation as a cone program and solve it numerically using a homogeneous self-dual embedding and first-order operator splitting. Feasible discrete designs are recovered through rounding-and-repair procedures and assessed by \emph{a posteriori} gap estimates relative to the numerical semidefinite program (SDP) benchmark. As a scalable alternative, we develop an exact-$k$, budget-feasible greedy heuristic built on rank-one Laplacian updates and biharmonic-distance caching, and interpret its progress through a Bellman value-to-go benchmark with a conservative spectral lower bound on the local policy ratio. Experiments on synthetic and real infrastructure networks across graph sizes, budgets, weight distributions, and cost regimes show that, under fixed budgets, distance-proportional costs limit the achievable resistance reduction and shift installed conductance toward shorter links relative to uniform per-unit costs.

0.21