Solved at Scale

Solved with CP-SAT

An external CP-SAT solver solves the pinned ten-alternative instance under deterministic parameters and proves the optimum. The lesson quotes only the deterministic fields of the run, and the chosen alternatives are decoded from the run's own solution values.

highlighted = computed this step

Invocation

The invocation is cpsat_stream_solve solve set_covering_lundgren.jsonl --params num_search_workers:1,random_seed:1, with the solution values written to a temporary --sol file. Why: a single search worker and a fixed seed make the run deterministic, so the cost quoted below is reproducible rather than anecdotal.

one worker, one seed, deterministic solve\text{one worker, one seed, deterministic solve}
A bigger covering problemThe real instance: 10 candidate alternatives, 8 objects each needing at least one cover.10 alternatives, solver inputx1x2x3x4x5x6x7x8x9x10object_01010000001object_10101111000object_20001011010object_30010001100object_40001100100object_51100000011object_60010000001object_70100000110minimize; alternative costsx1x2x3x4x5x6x7x8x9x10cost19161813151915171615

Solver result

The solver reports status OPTIMAL with objective (total cost) 45 and best objective bound 45. Why: OPTIMAL means the solver proved a matching bound, not merely found a good solution.

status OPTIMAL, cost 45\text{status OPTIMAL, cost }45
Chosen alternativesThe decoded 0/1 solution, one column per alternative.decoded chosen alternatives, cost 45x1x2x3x4x5x6x7x8x9x10chosen0001000101

The chosen alternatives

Alternative 4, alternative 8, and alternative 10 — columns x4, x8, and x10 in the table above, matching the textbook's own numbering — are chosen; every other alternative is left unchosen. Why: these are the literal decoded solution values from the real solve, and this is the textbook's own documented unique answer (Lundgren, Roennqvist, Vaebrand's textbook 'Optimeringslaera' ('Optimization theory'), via OR-Tools' own contrib set-covering example code).

decoded chosen set, exactly as solved\text{decoded chosen set, exactly as solved}
Chosen alternativesThe decoded 0/1 solution, one column per alternative.decoded chosen alternatives, cost 45x1x2x3x4x5x6x7x8x9x10chosen0001000101

Diagram note

The table has one column per alternative and one row carrying each decoded binary value; the caption's cost is recomputed from those values on every build. Pixel positions are rounded for layout; every displayed coverage, cost, and comparison is exact.

one value per alternative, exact\text{one value per alternative, exact}
Chosen alternativesThe decoded 0/1 solution, one column per alternative.decoded chosen alternatives, cost 45x1x2x3x4x5x6x7x8x9x10chosen0001000101