Solved at Scale

Solved with CP-SAT

An external CP-SAT solver solves the pinned eleven-item instance under deterministic parameters and reports a provable optimum. The lesson quotes only the deterministic fields of the run, and the packing shown is decoded from the run's own solution values.

highlighted = computed this step

Invocation

The invocation is cpsat_stream_solve solve bin_packing.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 solution quoted below is reproducible rather than anecdotal.

one worker, one seed, deterministic solve\text{one worker, one seed, deterministic solve}
Instance handed to the solverThe exact integer weights are the solver's input; no packing is shown yet.11 items, capacity 100, solver inputsizeA48B30C19D36E36F27G42H42I36J24K30capacity100total370

Solver result

The solver reports status OPTIMAL with objective value 4 and best objective bound 4. Why: OPTIMAL means the solver proved a matching bound, not merely found a good packing. The output also carries timing, conflict, and branch counts; those fields are omitted here because they vary from run to run, and only the status, the objective value, the bound, and the solution values are deterministic.

status OPTIMAL, objective 4\text{status OPTIMAL, objective }4
CP-SAT certified packingThe solver's own decoded packing, one row per used bin; fill labels are exact integer ratios of capacity.4 bins, certified optimalB1D 36B 30K 30fill 96/100left 4B2A 48F 27J 24fill 99/100left 1B3H 42E 36C 19fill 97/100left 3B4G 42I 36fill 78/100left 22capacity 100total size 370lower bound 4bins used 4optimal for this instance

The packing

B1 packs D 36, B 30 and K 30 with fill 96/100. B2 packs A 48, F 27 and J 24 with fill 99/100. B3 packs H 42, E 36 and C 19 with fill 97/100. B4 packs G 42 and I 36 with fill 78/100. Why: each bin's fill stays within capacity and every item appears exactly once. The rows are the solver's own decoded packing: its four used bins are relabeled B1 through B4 in ascending bin order, and those labels and the item blocks are the diagram's own labels.

bins used=4\text{bins used}=4
CP-SAT certified packingThe solver's own decoded packing, one row per used bin; fill labels are exact integer ratios of capacity.4 bins, certified optimalB1D 36B 30K 30fill 96/100left 4B2A 48F 27J 24fill 99/100left 1B3H 42E 36C 19fill 97/100left 3B4G 42I 36fill 78/100left 22capacity 100total size 370lower bound 4bins used 4optimal for this instance

Diagram note

Each row is one used bin from the solver's decoded solution, headed B1 through B4, with item blocks labeled by item id and exact integer weight, a fill label as an exact ratio of capacity, a left annotation for the leftover space in the bin, and a summary footer with the capacity, total size, lower bound, and bins used. Pixel positions are rounded for layout; every item size, fill, total size, and bound is exact.

one row per used bin, exact fills\text{one row per used bin, exact fills}
CP-SAT certified packingThe solver's own decoded packing, one row per used bin; fill labels are exact integer ratios of capacity.4 bins, certified optimalB1D 36B 30K 30fill 96/100left 4B2A 48F 27J 24fill 99/100left 1B3H 42E 36C 19fill 97/100left 3B4G 42I 36fill 78/100left 22capacity 100total size 370lower bound 4bins used 4optimal for this instance