Polynomial-Time Solvability of the Multi-Dimensional Slope Change Problem

Slope change detection seeks to identify changes in the trends of time-ordered signals. We study the problem of fitting a multidimensional time series by continuous piecewise-linear functions with a common, continuously varying breakpoint and unrestricted slopes. We consider both the dense setting, in which every dimension may change slope, and the sparse setting, in which … Read more

Intersection Cuts for Mixed-Integer Nonlinear Programs via Decision-Diagram-Free Sets

We introduce a novel decision-diagram-based framework for generating intersection cuts to strengthen polyhedral relaxations of bounded mixed-integer nonlinear programs (MINLPs) with general nonlinear constraints. Building on decision diagrams (DDs) that provide outer approximations of MINLP feasible regions, we propose the concept of DD-free sets, which are convex regions whose interiors do not intersect the sets … Read more

Frank–Wolfe Theorems for Mixed Integer Quadratic Optimization

The Frank–Wolfe theorem states that a quadratic function bounded from below on a polyhedron attains its infimum. We study when this remains true in the presence of integer variables, for sets defined by quadratic inequalities. Our main result is a complete classification for sets defined by convex quadratic inequalities with rational coefficients and a rational … Read more

Probabilistically Exact Convexification of Mixed-Integer Quadratic Optimization with Indicators

We study the convexification of mixed-integer quadratic optimization with indicator variables. The problem remains NP-hard even when the quadratic matrix has bandwidth two, posing a fundamental obstacle to tractable exact convexification. To overcome this challenge in realistic settings, we introduce probabilistically exact (inner) convexification, a framework that relaxes the requirement of exactness for every objective … Read more

Cubic Optimization over Three Nonnegative Integers Is NP-hard

We prove that deciding whether an integer cubic polynomial takes a value at most one over three nonnegative integers is NP-hard. Hardness holds even when every feasible objective value is a positive integer, so every constructed instance has a finite, attained minimum. This establishes a sharp dimension boundary for the tractability of cubic integer optimization … Read more

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

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

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

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

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

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