Tightness of locally valid cuts for the nonnegative two-dimensional feasible space

Let F:={xR2:x1, xeTx}={x0:x1}\mathcal{F}:= \{x \in \mathbb{R}^2: \|x\| \leq 1,\ \|x\| \leq e^T x\} = \{x \geq 0: \|x\| \leq 1\}. Let G\mathcal{G} denote the convex hull defined in the source, and let Rshor\mathcal{R}_{\mathrm{shor}} and Rksoc\mathcal{R}_{\mathrm{ksoc}} denote the stated relaxations. The locally valid cuts are those given by the source's referenced constraints.

Locally valid-cut conjecture. The intersection of RshorRksoc\mathcal{R}_{\mathrm{shor}} \cap \mathcal{R}_{\mathrm{ksoc}} with the locally valid cuts captures G\mathcal{G}.

The conjecture is supported by computational experiments on 100 additional instances, all of which were solved exactly after adding the locally valid cuts. Whether these cuts always recover the convex hull in the stated setting remains open in the supplied source.

Sources & referencesView supporting material

Primary source

Anders Eltved and Samuel Burer, “Strengthened SDP Relaxation for an Extended Trust Region Subproblem with an Application to Optimal Power Flow”, arXiv:2009.12704 (2021).

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.