Counterexample conjecture to the ROAD property for compact knapsack instances

For each integer m2m\geq 2, consider the integer program (CE)m(\mathrm{CE})_m with variables x{0,1}2mx\in\{0,1\}^{2m} and its linear relaxation. Let xmx_m^\circ denote an optimal solution of that linear relaxation, and define

X:=xmxm+Diag(xm(xm)2).\mathbf{X}:=x_m^\circ {x_m^\circ}^{\top}+\operatorname{Diag}\left(x_m^\circ-(x_m^\circ)^2\right).

The ROAD property means that this matrix is feasible for the naive semidefinite relaxation. Counterexample conjecture. For all m2m\geq 2, there is an optimal solution xmx_m^\circ of the linear relaxation for which there exist i,j{1,,2m}i,j\in\{1,\dots,2m\} with ji>2j-i>2 such that

ji12(xm)i(xm)j>k=i+1j1(xm)k.\left\lfloor\frac{j-i-1}{2}\right\rfloor (x_m^\circ)_i(x_m^\circ)_j>\sum_{k=i+1}^{j-1}(x_m^\circ)_k.

In particular, X\mathbf{X} is not a solution of the naive semidefinite relaxation, and (CE)m(\mathrm{CE})_m does not have the ROAD property. The supplied status evidence disproves this conjecture, so the asserted universal failure has a counterexample; the exact refutation is not specified in the provided material.

Sources & referencesView supporting material

Primary source

Hubert Villuendas, Mathieu Besançon and Jérôme Malick, “Knapsack with compactness: a semidefinite approach”, arXiv:2504.17543 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.