The integer quadratic moment hull is the closed convex hull of the pairs \((z,zz^{\top})\) with \(z\in\mathbb{Z}^n\). We prove that one round of Chvátal–Gomory (CG) cuts applied to its basic semidefinite relaxation recovers this hull exactly if and only if \(n\le6\). Our approach identifies its facets with perfect Delaunay polyhedra and characterizes their recovery through depth, … Read more
The branch-and-cut paradigm has led to effective solvers for a wide range of mathematical optimization problems. Despite significant theoretical work on pure branching and pure cutting, less is known about their interaction. We study an extended abstract branch-and-cut model to investigate tradeoffs between branching and cutting, including the time to generate cuts. We prove that, … Read more
A rational polyhedron has Chvátal rank at most one if a single round of Chvátal–Gomory cuts yields its integer hull. In 1973, Chvátal asked whether 0/1 integer programs over polytopes of bounded Chvátal rank can be solved in polynomial time. For polyhedra of bounded Chvátal rank, integer feasibility is in NP ∩ coNP, so it … Read more
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
We study cutting-plane generation for binary polynomial optimization (BPO), whose feasible region is the multilinear set of a hypergraph. Strong inequalities for this set—such as two-links, flowers, and odd $\beta$-cycles—are classically hand-derived for fixed support patterns. Instead, we propose a decision-diagram (DD) approach: for any chosen support, it separates a facet-defining cut in the local … Read more
Many large-scale optimization problems decompose into a master problem and scenario subproblems, a structure that can be exploited by Benders decomposition. In Benders decomposition, each iteration may generate many cuts from scenario subproblems, and adding all of them as constraints then causes the master problem to grow rapidly. These are constraints that may need to … Read more
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
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
We consider a two-stage optimization problem with sparsity constraints, motivated by a common challenge in packaging logistics: minimizing the volume of transported air by optimizing the size and number of available packaging boxes, given the demand for order items. In the first stage, we select the optimal dimensions of the boxes, while in the second … Read more
This paper investigates the a posteriori analysis of Branch-and-Bound (BB) trees to extract structural information about the feasible region of mixed-binary linear programs. Using only the branching decisions of a tree and one dual bound per node, we introduce three polyhedral outer approximations of the feasible region, namely a disjunctive, a network-flow-based, and a mixing-set-based … Read more