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

About 7 years old · traced to

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(rank−1(r))double(rank^{-1}(r)) indicate whether the vertex at rank rr is a double, and consider the multi-objective problem

min⁡{∑v∈Vnodes(rank(v)),∑r∈[n−1]double(rank−1(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.

References

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.