Prove the optimal value of MIPLIB 2017 instance assign1-10-4
Difficulty 40: a small MIPLIB instance (572 variables) still open since MIPLIB 2010 points to weak relaxations and symmetry rather than size, so stronger cuts, symmetry handling or long exact runs plausibly close it; harder than an engineering task but far below the TSP optimality questions (58–62). Application value 8 and leverage 10: one test instance whose closure mainly benefits MIP solver development.
The problem
Prove what the best possible score is for one small but stubborn planning puzzle from the MIPLIB test library.
- 1Best known plan scores 422
- 2No proof that it is the best
- 3Solver search must beat symmetry
- 4Exact certificate closes the gap
The setting. A mixed-integer program (MIP) asks for the cheapest plan: minimise a linear cost subject to linear constraints (like a first-year system of equations with in place of ), where some variables must be whole numbers, here mostly 0 or 1 for yes/no decisions. Solvers prove a plan optimal by finding a matching : a guarantee that no plan can cost less.
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- Fast matrix multiplicationAlgorithm
- Step 4
- Linear programmingAlgorithm
- Step 5
- Then
- Prove the optimal value of MIPLIB 2017 instance assign1-10-4The problem
State of the art
The library lists one solution, with objective value 422, found in October 2018 during the MIPLIB 2017 selection, and shows no dual bound that proves it optimal. The instance is tiny compared with most of the 212 instances tagged open (many have more than 100,000 variables), which makes it a candidate for new branching and cut-separation methods and for symmetry handling. No proof of optimality has been published or recorded in the library. Verification machinery exists: VIPR certificates (checked by vprchck) and the exact rational mode of SCIP.
Realistic applications
No direct application: the value is as a hard small test case. Closing it would sharpen cut and symmetry-handling techniques used by general MIP solvers.
What counts as solved
A feasible solution file (MIPLIB .sol format) with an objective value equal to a dual bound that is certified by a VIPR file accepted by vprchck, with the MPS file and solver version published.
How it gets verified
Bound / recordA numeric bound or record checked from a certificate or recomputation.
Quantity: the optimal objective value of MIPLIB 2017 instance assign1-10-4 (MPS file from miplib.zib.de; current best known value 422, status open, no dual bound listed). An improved primal solution is checked against the MPS file by the MIPLIB solution checker; optimality is certified by a VIPR certificate (exact rational derivation of the dual bound) accepted by vprchck from scipopt/vipr. Report solver, version, hardware and wall time; the certificate and the MPS hash must be published.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
Closing the instance needs a better dual bound: stronger cuts or symmetry reduction (theory), solver changes (engineering) and long runs with exact certificates (compute).
Bottlenecks
ranked by votes- #1TheoryWeak LP relaxation and symmetry
The set partitioning plus cardinality structure leaves large symmetric search trees. Without cuts or orbital reductions that exploit it, the bound does not close.
Community grades
Sign in to add your own grade.
Connected problems
No connections yet.
Progress
- Oct 13, 2018Best known solution recordedsource
The solution with objective 422 was recorded during MIPLIB 2017 problem selection.