Objective-value conjecture for the naive semidefinite relaxation of the mKPC
Objective-value conjecture for the naive semidefinite relaxation of the mKPC
Consider an instance of the multiple knapsack problem with compacity constraints, its linear relaxation , and its naive semidefinite relaxation. Write for the corresponding optimal objective value. Objective-value conjecture.
The conjecture concerns the ordering of the objective values of the semidefinite relaxation, the linear relaxation, and the original integer formulation. The paper notes that the stronger ROAD property can fail and that feasibility of the ROAD matrix does not ensure semidefinite optimality; the status of this objective-value inequality is not resolved in the supplied text.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.