Open question · OPEN-STRONGER-BB

Are there tighter bounds for exact search?

Openpublication: open

Meaning

Improve branch-and-bound ceilings beyond singleton refinement.

Statement

Improve singleton-refinement upper bounds using moment relaxations, SDP/convex envelopes, affine-realizability pruning, or mass constraints.

Relationships

Related settled results

Singleton-refinement branch-and-bound upper bound for DD-BB-SINGLETON-BOUND

The full chain beneath it

Where it comes from

Raised by

Singleton-refinement branch-and-bound upper bound for DD-BB-SINGLETON-BOUND

Local graph

Prerequisites to the left, what it enables or raises to the right, boundary cases below. Open in the map.

The question in full

Stronger branch-and-bound upper bounds

Improve singleton-refinement bounds via moment relaxations, SDP/convex envelopes, affine-realizability pruning or minimum-cell-mass constraints, to certify larger instances (the mathematical alternative to a compiled port of certify.py).

From OPEN_PROBLEMS.md