A packing puzzle by MIPUn puzzle di impaccamento con la MIP

The twelve pentominoes fill a rectangle 6 x 10 in 2339 ways, a rectangle 3 x 20 in only 2, and the square 8 x 8 with a hole of 2 x 2 in the middle in 65 (Dana Scott found them all in 1958, by one of the first backtracking programs); the seven pieces of the Soma cube of Piet Hein fill a cube 3 x 3 x 3. In this page the solution is found by no search procedure: every placement \(p\) of a piece in the tray (a translation of one of its orientations) is a binary variable \(y_p\), and an integer program maximizes the area covered; hence, the tray is full at an optimal solution, and every other feasible solution leaves holes. The program was solved offline by HiGHS (through scipy).

I dodici pentamini riempiono un rettangolo 6 x 10 in 2339 modi, un rettangolo 3 x 20 in 2 soli, e il quadrato 8 x 8 con un foro di 2 x 2 al centro in 65 (Dana Scott li ha trovati tutti nel 1958, con uno dei primi programmi di backtracking); i sette pezzi del cubo Soma di Piet Hein riempiono un cubo 3 x 3 x 3. In questa pagina la soluzione non viene da un algoritmo di ricerca: ogni piazzamento \(p\) di un pezzo nel vassoio (una traslazione di una delle sue orientazioni) è una variabile binaria \(y_p\), e un programma intero massimizza l'area coperta; quindi il vassoio è pieno in una soluzione ottima, e ogni altra soluzione ammissibile lascia dei buchi. Il programma è stato risolto offline da HiGHS (tramite scipy).

\(\max \sum_p |p|\, y_p \quad \text{s.t.} \quad \sum_{p \ni c} y_p \le 1 \ \ \forall\, c, \quad \sum_{p \in P_i} y_p \le 1 \ \ \forall\, i, \quad y \in \{0,1\}\)

The tray and the pieces as they are printed, each piece where the MIP put it (the slider lifts them apart); \(c\) runs over the cells of the tray, \(P_i\) over the placements of piece \(i\). Since the bound of the linear relaxation already equals the area, all the work of branch and bound goes into making \(y\) integer. Drag to turn, wheel or pinch to zoom.Il vassoio e i pezzi come vengono stampati, ogni pezzo dove l'ha messo la MIP (il cursore li solleva e li separa); \(c\) corre sulle celle del vassoio, \(P_i\) sui piazzamenti del pezzo \(i\). Poiché il bound del rilassamento lineare vale già l'area, tutto il lavoro del branch and bound sta nel rendere \(y\) intero. Trascina per ruotare, usa la rotella o il pizzico per lo zoom.

Download for 3D printingScarica per la stampa 3D

The tray and the pieces laid out beside it, separate bodies in one file, in the puzzle chosen above; the clearance is the gap between two neighbors, taken half from each piece and half from the pocket (0.2 to 0.3 mm usually suits a printer), and the pieces stand 1 mm above the rim, so that they can be picked out.

Il vassoio e i pezzi disposti accanto, corpi separati in un solo file, per il puzzle scelto sopra; il gioco è lo spazio fra due vicini, preso per metà da ogni pezzo e per metà dalla tasca (da 0.2 a 0.3 mm di solito va bene), e i pezzi sporgono di 1 mm dal bordo per poterli estrarre.