fixed dimension

Cubic Optimization over Three Nonnegative Integers Is NP-hard

Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , , ,

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

Integer quadratic programming in fixed dimension is polynomial-time solvable

Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Quadratic Programming Tags , ,

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