(Mixed) Integer Nonlinear Programming

Decomposition-Based Reformulation of Nonseparable Quadratic Expressions in Convex MINLP

Published: 2026/04/11

In this paper, we present a reformulation technique for convex mixed-integer nonlinear programming (MINLP) problems with nonseparable quadratic terms. For each convex non-diagonal matrix that defines quadratic expressions in the problem, we show that an eigenvalue or LDLT decomposition can be performed to transform the quadratic expressions into convex additively separable constraints. The reformulated problem … Read more

Beyond binarity: Semidefinite programming for ternary quadratic problems

Published: 2026/03/30

(Mixed) Integer Nonlinear Programming, Quadratic Programming, Semi-definite Programming Branch-and-Bound, integer semidefinite programming, quadratic ratio problems, ternary optimization problem

We study the ternary quadratic problem (TQP), a quadratic optimization problem with linear constraints where the variables take values in {0,±1}. While semidefinite programming (SDP) techniques are well established for {0,1}- and {±1}-valued quadratic problems, no dedicated integer semidefinite programming framework exists for the ternary case. In this paper, we introduce a ternary SDP formulation … Read more

Hardness of some optimization problems over correlation polyhedra

Published: 2026/03/20

(Mixed) Integer Nonlinear Programming, Global Optimization Theory, Polyhedra boolean quadric polytope, cone, cut polytope, matrix decomposition

We prove the NP-hardness, using Karp reductions, of some problems related to the correlation polytope and its corresponding cone, spanned by all of the n×n rank-one matrices over {0, 1}. The problems are: membership, rank of the decomposition, and a “relaxed rank” obtained from relaxing the zero-norm expression for the rank to an ℓ1 norm. … Read more

Modeling Adversarial Wildfires for Power Grid Disruption

Published: 2026/03/19

Matthew Brun

Xu Andy Sun

Jean-Paul Watson

(Mixed) Integer Nonlinear Programming, Energy, Second-Order Cone Programming contingency analysis, mixed-integer conic programming, resilient power grid, robust optimization, wildfire

Electric power infrastructure faces increasing risk of damage and disruption due to wildfire. Operators of power grids in wildfire-prone regions must consider the potential impacts of unpredictable fires. However, traditional wildfire models do not effectively describe worst-case, or even high-impact, fire behavior. To address this issue, we propose a mixed-integer conic program to characterize an … Read more

Modeling Network Congestion under Demand Uncertainty Using Wardrop Principles

Published: 2026/03/14

(Mixed) Integer Nonlinear Programming, Bilevel Optimization, Global Optimization bilevel optimization, Mixed-integer nonlinear optimization, traffic networks, Wardrop principles

Motivated by the need for reliable traffic management under fluctuating travel demand, we study the problem of determining the worst-case congestion in a multi-commodity traffic network subject to demand uncertainty. To this end, we stress-test a given network by identifying demand realizations and corresponding travelers’ route choices that maximize congestion. The users of the traffic … Read more

From Computational Certification to Exact Coordinates: Heilbronn’s Triangle Problem on the Unit Square Using Mixed-Integer Optimization

Published: 2026/03/10

Nathan Sudermann-Merx

(Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Integer Programming Exact refinement, Heilbronn triangle problem, Mixed-integer nonlinear optimization, symbolic computation, symmetry breaking

We develop an optimize-then-refine framework for the classical Heilbronn triangle problem that integrates global mixed-integer nonlinear programming with exact symbolic computation. A novel symmetry-breaking strategy, together with the exploitation of structural properties of determinants, yields a substantially stronger optimization model: for n=9, the problem can be solved to certified global optimality in 15 minutes on … Read more

Solving Convex Quadratic Optimization with Indicators Over Structured Graphs

Published: 2026/03/02

(Mixed) Integer Nonlinear Programming, Dynamic Programming dynamic programming, mixed-integer programming

This paper studies convex quadratic minimization problems in which each continuous variable is coupled with a binary indicator variable. We focus on the structured setting where the Hessian matrix of the quadratic term is positive definite and exhibits sparsity. We develop an exact parametric dynamic programming algorithm whose computational complexity depends explicitly on the treewidth … Read more

Separating Hyperplanes for Mixed-Integer Polynomial Optimization Problems

Published: 2026/02/25

(Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Semi-definite Programming Mixed-integer nonlinear programming (MINLP), polyhedral outer approximation, polynomial optimization, semidefinite programming

Algorithms based on polyhedral outer approximations provide a powerful approach to solving mixed-integer nonlinear optimization problems. An initial relaxation of the feasible set is strengthened by iteratively adding linear inequalities and separating infeasible points. However, when the constraints are nonconvex, computing such separating hyperplanes becomes challenging. In this article, the moment-/sums-of-squares hierarchy is used in … Read more

Tight semidefinite programming relaxations for sparse box-constrained quadratic programs

Published: 2026/02/15

Aida Khajavirad

(Mixed) Integer Nonlinear Programming, Semi-definite Programming convex hull, nonconvex quadratic programming, polynomial-size extended formulation, reformulation-linearization technique, semidefinite programming relaxation, sparsity

We introduce a new class of semidefinite programming (SDP) relaxations for sparse box-constrained quadratic programs, obtained by a novel integration of the Reformulation Linearization Technique into standard SDP relaxations while explicitly exploiting the sparsity of the problem. The resulting relaxations are not implied by the existing LP and SDP relaxations for this class of optimization … Read more

Fast Presolving Framework For Sparsity Constrained Convex Quadratic Programming: Screening-Based Cut Generation and Selection

Published: 2026/02/14

Haozhe Tan

Guanyi Wang

(Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Nonlinear Optimization Cutting plane, mixed-integer nonlinear programming, presolving, Screening, sparsity

Screening is widely utilized for Mixed-Integer Programming (MIP) presolving. It aims to certify a priori whether one or multiple specific binary variables can be fixed to optimal values based on solutions from convex relaxations. This paper studies the challenge of solving Sparsity-constrained (strongly) Convex Quadratic Programming (SCQP) and proposes the Screening-based Cut Presolving Framework (SCPF). … Read more