(Mixed) Integer Nonlinear Programming

Solution of Binary-Constrained Quadratic-Defined Optimization Problems by a Progressive Integer Programming Method

Published: 2026/09/17

Extending a classic result of Giannessi and Tomasin [\textit{Lecture Notes in Comput. Sci. 3}, Springer, 1973, pp. 437–449], this paper shows that a binary-constrained quadratic-defined optimization problem can be formulated as a binary-constrained linear program with linear complementarity constraints (Bi-LPCC). The term “quadratic-defined problems” encompasses many problems that are defined by quadratic functions in the … Read more

Integer quadratic programming in fixed dimension is polynomial-time solvable

Published: 2026/09/14

Linchuan Wei

(Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Quadratic Programming fixed dimension, halfspace depth, integer quadratic programming

We give a deterministic polynomial-time algorithm for integer quadratic programming in every fixed dimension: it minimizes an arbitrary rational quadratic exactly over the integer points of a rational polyhedron, or certifies infeasibility or integer unboundedness. The core is a sign test that decides whether \(d^{\mathsf{T}}Qd\ge 0\) for every integer point \(d\) of a bounded symmetric … Read more

Nonlinear optimization over trees with binary coupling decisions

Published: 2026/09/07, Updated: 2026/09/22

(Mixed) Integer Nonlinear Programming, Dynamic Programming, Optimization in Data Science

Mixed integer nonlinear programs with binary coupling decisions naturally model selective coordination tasks where a fixed penalty is incurred whenever adjacent continuous variables differ. A prominent example is the classical Potts model, which is widely used in statistical inference. However, exact solvability remains theoretically challenging since the problem is NP hard on general graphs, and … Read more

Convexification of mixed-integer quadratic optimization via decision diagrams

Published: 2026/08/24, Updated: 2026/09/07

(Mixed) Integer Nonlinear Programming, Dynamic Programming convexification, decision diagrams, mixed-integer quadratic optimization

We study mixed-integer quadratic optimization (MIQO) problems with indicator variables. We propose a unified framework, based on decision diagrams, that serves both to solve the associated optimization problems and to construct ideal conic quadratic extended formulations of the closure of the convex hull of the underlying mixed-integer set. The construction applies to arbitrary quadratics and … Read more

Congressional Apportionment

Published: 2026/08/17

(Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Integer Programming allocation problems, apportionment, MINLP, public sector operations

This book chapter is a gentle introduction to the mathematics of congressional apportionment. It emphasizes the connections between mathematical optimization and the classical apportionment methods (e.g., Jefferson, Adams, Hamilton, Webster, Huntington-Hill, Dean). CitationPrepared for a forthcoming book edited by Bruce Golden and Doug ShierArticleDownload View PDF

Rational Jacobi Rotations and the Complexity of Approximating Mixed Integer Quadratic Programming

Published: 2026/08/03

Alberto Del Pia

(Mixed) Integer Nonlinear Programming, Global Optimization Theory, Quadratic Programming approximation algorithm, computational complexity, Jacobi rotations, mixed-integer quadratic programming, Simultaneous diagonalization

We present an algorithm that finds an epsilon-approximate solution to a mixed integer quadratic programming (MIQP) problem, and that runs on a Turing machine in time polynomial in the size of the instance and in 1/epsilon, provided that the number of integer variables and the number of negative eigenvalues of the Hessian of the objective … Read more

Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators

Published: 2026/08/02

(Mixed) Integer Nonlinear Programming, Quadratic Programming disjunctive optimization, indicator constraints, mixed-integer convex programming

We consider mixed-integer convex optimization problems in which binary indicators control continuous variables. We introduce the Coordinate Optimality Reformulation (CORe) framework, which augments standard indicator formulations by incorporating coordinate-wise optimality information. The resulting reformulations preserve global optimality while substantially improving branch-and-bound performance, particularly in sparse and structured settings where the coordinate-wise optimality conditions expose exploitable … Read more

Robust Network Design for Potential-Based Flows with Controllable Elements

Published: 2026/06/19, Updated: 2026/07/07

(Mixed) Integer Nonlinear Programming, Bilevel Optimization, Robust Optimization bilevel optimization, mixed-integer nonlinear programming, potential-based flows, robust optimization, uncertainty

We study adjustable robust network design for potential-based flows with controllable elements under load uncertainty. The resulting problem combines discrete here-and-now expansion decisions with wait-and-see operational decisions governed by nonconvex flow constraints. Moreover, controllable elements introduce adjustable integer decisions, which are algorithmically challenging. We equivalently characterize robust feasibility and robust optimality of a fixed network … Read more

A computational comparison of handling distance constraints in MINLP

Published: 2026/05/04, Updated: 2026/08/13

(Mixed) Integer Nonlinear Programming bound tightening, cutting planes, minimum distance constraints, rotation symmetry

Minimum distance constraints (minDCs) appear in many geometric optimization problems. They pose major challenges for mixed-integer nonlinear programming (MINLP) due to their reverse-convexity. We develop new algorithms for tightening variable bounds in general MINLPs with minDCs. Because many such problems exhibit substantial symmetry, we further discuss an approach for handling rotation symmetries. In a computational … Read more

A polynomial-time solvable class of sparse box-constrained polynomial optimization problems

Published: 2026/04/28, Updated: 2026/08/20

Aida Khajavirad

(Mixed) Integer Nonlinear Programming binary polynomial optimization, box-constrained polynomial optimization, hypergraph, polynomial-time algorithm, sparsity, treewidth

We study the problem of minimizing a multivariate polynomial function over the unit hypercube. Exploiting sparsity in the interaction graph or hypergraph, we identify variables that can be restricted to binary values at optimality and eliminate the remaining continuous variables component-wise, reducing the problem to structured binary polynomial optimization. For quadratic objectives, we obtain exact … Read more