Frank de Meijer, Veronica Piccialli, Renata Sotirov, Antonio M. Sudoso
11 min
Abstract
We study the ternary quadratic problem (TQP), a quadratic optimization problem with linear constraints where the variables take values in $\{0, \pm 1\}$. While semidefinite programming (SDP) techniques are well established for $\{0,1\}$- and $\{\pm 1\}$-valued quadratic problems, no dedicated integer semidefinite programming framework exists for the ternary case. In this paper, we introduce a ternary SDP formulation for the TQP that forms the basis of an exact solution approach. We derive new theoretical insights in rank-one ternary positive semidefinite matrices, which lead to a basic SDP relaxation that is further strengthened by valid triangle, RLT, split and $k$-gonal inequalities. These are embedded in a tailored branch-and-bound algorithm that iteratively solves strengthened SDPs, separates violated inequalities, applies a ternary branching strategy and computes high-quality feasible solutions. We test our algorithm on TQP variations motivated by practice, including unconstrained, linearly constrained and quadratic ratio problems. Computational results on these instances demonstrate the effectiveness of the proposed algorithm.
Sam: Right—the blocks are like independent Lego pieces: each +1/-1 block is rank-1 PSD thanks to the triangle inequalities mimicking a cut-set in a graph, and pair inequalities enforce zero walls outside. This yields the exact ISDP: minimize the quadratic cost over a big matrix Y that's positive semidefinite, with entries forced to 0,±1, diagonal matching absolute values of the variable vector x, and linear constraints embedded. No rank-one needed; integrality on Y does the work, as submatrices force X_ij = x_i x_j.
Alex: Huh—that's clever, turning the hard rank constraint into entry-wise rules. Does this relaxation hold up alone, or do they tighten it further for branch-and-bound?
Sam: They start with a basic SDP relaxation by dropping integrality and diag(X)=|x|, adding bounds like diag(X) ≤1 and linear projections for constraints. To strengthen it, they separate valid inequalities at branch-and-bound nodes: the triangle ones from Theorem 2.6, plus RLT cuts—think of multiplying constraints and linearizing products to cut off fractions—standard split cuts, non-standard splits, and k-gonal inequalities that refine polytope facets. This combo, with ternary branching on fractional x_i, lets it solve nonconvex TQPs up to n=90 exactly where GUROBI fails.
Alex: You mentioned variants like unconstrained or linear-constrained TQPs—how do they adapt the relaxation there?
Sam: For the unconstrained case, called quadratic unconstrained ternary optimization or QUTO, they drop linear rules entirely. If the diagonal of the cost matrix Q has non-positive entries—meaning no penalty for setting variables to plus or minus one over zero—the optimum always lands on just plus-minus choices, reducing exactly to the max-cut problem we know from binary cases.
Alex: So in QUTO, certain costs make zeros suboptimal, forcing full plus-minus like binary. Right—and for the linear-constrained version, like sum of x_i equals zero in turbomachine balance?
Sam: Yes, TQP-Linear adds one linear equality, like all ones dot x equals zero. The relaxation embeds it as a quadratic trace constraint on X, making the direct sum x equals zero redundant since PSD plus that forces balance. But it lacks strict interior points—solutions sit on the boundary—so they use facial reduction: project onto the subspace orthogonal to the all-ones vector using a sparse basis matrix W, reformulating as a smaller PSD over Z with adjusted diagonals and traces, now strictly feasible for better numerics.
Alex: Huh—that subspace trick sidesteps the flatness issue without losing equivalence. And these strengthened cuts—like RLT or splits—get separated dynamically in branch-and-bound for all variants?
Sam: Precisely—they add triangle and pair inequalities from the block theorem, plus RLT cuts. RLT works by taking bounds like x_i over minus-one to one, multiplying pairs like x_i times x_j bounds, then linearizing those products into inequalities on X_ij plus x terms, slicing off fractional points. Splits come from disjunctions: force variables into integer gaps, like w dot x floor or ceiling, lifting to quadratic on the matrix and linearizing to cut deeper; non-standard ones target off-diagonals directly, matching the pair rules.
Alex: So RLT multiplies bounds for pairwise envelopes, splits enforce integer gaps via disjunctions... You mentioned TQP-Ratio earlier—the one minimizing a ratio of two quadratics. How do they handle that fractional objective?
Sam: Ternary quadratic problems with ratio objectives minimize something like f(x) over g(x), where both f and g are quadratic in the ternary choices, and g stays positive. One way is Dinkelbach's method for fractional programming: guess a ratio value lambda, then solve easier subproblems minimizing f minus lambda times g until the minimum hits zero at the true optimum—each subproblem reduces exactly to a QUTO we already know how to handle. The second directly reformulates without fractions by rescaling: set rho to one over g(x), y to rho times x, and Y to rho times x x transpose, turning the ratio into a linear objective over rho, y, Y with a constraint that the rescaled g equals one. This embeds into a bigger PSD matrix Z with rho on top-left, y and Y below, plus bounds like diagonal of Y between zero and rho.
Alex: Huh—rescaling flips the denominator into a constraint, avoiding the fraction entirely. That fits neatly into the branch-and-bound framework.
Sam: Exactly—they wrap it all into an SDP-based branch-and-bound called SDP-B&B, tailored per variant. A key piece is the primal heuristic: Variable Neighborhood Search starts with random ternary points, then shakes by flipping a few coordinates to escape stuck spots—like randomly swapping players in a game to try new strategies—and runs local search checking all single flips for objective drops, evaluating changes in constant time using an auxiliary vector of matrix times current solution. It feeds good upper bounds from these feasible solutions back into the tree.
Alex: So VNS diversifies with shakes and hones with fast neighbor checks, improving bounds as relaxations tighten. What about adding those cuts and picking branches?
Sam: At each node, they separate violated cuts iteratively: exhaustive search finds most triangle, RLT, split, and pair ones exactly since they're low-combo checks, but for higher k-gonal like pentagonal on five indices, they heuristically solve a quadratic assignment approximating the worst violation via simulated annealing over permutations. Branching picks the most-fractional x_i—farthest from -1,0,1—splitting into three kids fixing it there; best-first search with gap tolerance under 0.01% solves instances where general solvers stall.
Alex: Notable how these pieces—heuristics for uppers, dynamic cuts for lowers, ternary splits—make it scale. How does it all hold up computationally against something like GUROBI?
Sam: The paper tests on structured instances from 60 to 90 variables for unconstrained and linear-constrained cases, plus random ones for ratios. SDP-B&B solves all of them to exactness within an hour, while GUROBI leaves gaps on many, up to 25 percent in tougher cases. For larger ones up to 120 variables, it keeps gaps under two percent on average.
Alex: So it handles twice the size reliably where general solvers stall. Makes sense for turbomachine designs around 80 variables. Any catches in practice?
Sam: They prioritize cheap cuts first—triangles, RLT, splits—then add five- and seven-sided gonal ones heuristically. Skipping nine-sided due to exploding computation time, and heuristics might overlook some deeper cuts. No analysis of worst-case runtime either.
Alex: Fair limits—keeps it practical without overclaiming. Pulls together the block theory into a solver that actually works at scale.
Sam: Exactly—this positions integer semidefinite methods as viable for nonconvex quadratic problems up to thousands of variables in engineering and machine learning, swapping out generic solvers when ternary structure fits. A solid, incremental advance on the theoretical foundation from Theorem 2.6 and the variants handled.
Alex: Ties the ternary characterization to real performance gains. Thanks for joining us on ResearchPod.