The feasible ideal-point conjecture for the MIN NODES–MIN DOUBLE problem

Let V\mathcal{V} be the vertex set of a discretizable distance geometry problem, let rankrank assign vertices to ranks, and let nodes(rank(v))nodes(rank(v)) denote the number of nodes at the rank of vv. Let double(rank1(r))double(rank^{-1}(r)) indicate whether the vertex at rank rr is a double, and consider the multi-objective problem

min{vVnodes(rank(v)),r[n1]double(rank1(r))}\min \left\{\sum_{v\in\mathcal{V}} nodes(rank(v)),\sum_{r\in[n-1]} double(rank^{-1}(r))\right\}

subject to the rank and predecessor constraints. Feasible ideal-point conjecture. The MIN NODES\texttt{MIN NODES}MIN DOUBLE\texttt{MIN DOUBLE} multi-objective problem has a feasible ideal point; equivalently, its Pareto frontier consists of a single non-dominated point. If true, solving MIN DOUBLE\texttt{MIN DOUBLE} would yield an optimal solution to MIN NODES\texttt{MIN NODES}. The conjecture concerns simultaneous optimization of the number of nodes and doubles in discretizable distance geometry problems; the supplied text gives no resolution status.

Sources & referencesView supporting material

Primary source

Moira MacNeil and Merve Bodur, “Integer Programming, Constraint Programming, and Hybrid Decomposition Approaches to Discretizable Distance Geometry Problems”, arXiv:1907.12468 (2020).

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.