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.
Alex: Welcome to another episode of ResearchPod. Sam, what research are we looking at today?
Sam: We're discussing a paper called "Beyond Binarity: Semidefinite Programming for Ternary Quadratic Problems" by Frank de Meijer and colleagues. It tackles ternary quadratic problems—optimization tasks where each decision is one of three choices: zero, plus one, or minus one. The goal is to minimize a quadratic expression involving those choices, plus some linear rules.
Alex: Okay, so these are like planning problems where you assign +1, -1, or nothing to items to hit a low cost score. And the paper's main point is...?
Sam: The central advance is the first exact formulation using integer semidefinite programming for these ternary cases. For binary choices—just zero-one or plus-minus one—semidefinite methods revolutionized problems like max-cut. But ternary broke those tools until now.
Alex: Right, so binary worked great with these matrix relaxations, but adding the zero option made it fall apart? What's the real-world snag that shows why this matters?
Sam: Exactly—general solvers like GUROBI fail on instances around 80 variables, such as turbomachine design where you balance parts with a sum-zero constraint over ternary choices. This paper provides a tailored branch-and-bound method that solves all up to 90 variables exactly, where others can't.
Alex: Huh. So the bottleneck was lacking a solid way to handle those ternary matrices in semidefinite relaxations. That sets up why their inequalities and branching are key...
Sam: Yes—and that's where the theoretical insights on disjoint blocks and pair separations come in, enabling the exact reformulation.
Alex: So those disjoint blocks and separations... how exactly do they let you build an exact formulation? Walk me through the logic there.
Sam: Picture the matrix as a grid where entries are only 0, +1, or -1, and it has to stay "positive semidefinite"—meaning it's built from outer products of ternary vectors without going negative in a certain math sense. The key insight is that such matrices naturally split into separate clumps: some areas are all zeros, and others are tight-packed blocks of just +1s and -1s, with no mixing between clumps. Theorem 2.6 proves this structure holds exactly if two types of rules are met: for any three spots in the grid, their values can't add up in ways that break "triangle inequalities"—like how sides of a triangle must satisfy certain length rules to form a shape—and "pair inequalities" that force zeros between different clumps.
Alex: Okay, so the triangle rules keep each +1/-1 block acting like a single rigid unit, almost like a team's formation in soccer where no one drifts out of position. And the pair rules build walls between blocks? But how does that plug into the optimization?
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.