Modelli ed algoritmi per un problema di pallet loading

A prescindere dalla scelta dell'ordinamento, l'euristica aggiunge un collo alla volta, verificando se, nell'impilamento in esame, questi può essere inserito.
Quando un collo rispetta tutti i vincoli viene inserito nella colonna formata e non sarà mai più rimosso dalla soluzione corrente.
Nel caso in cui uno dei due vincoli, (altezza, sopportabilità), non può essere rispettato, il collo viene scartato. Quando ciò accade, vengono implicitamente resi liberi, per quell'istanza di caricamento, tutti i colli che ne avevano dipendenza, questo significa che se un collo non può essere caricato su una data pila possono però esservi caricati tutti quei colli che erano destinati a giacere su di esso.
La causa di questa situazione la si determina poiché l'impilamento parziale, si applica ad ogni coppia di colli, scartando un collo decade anche il vincolo.
L'algoritmo chiude un impilamento quando:
- non esiste alcun collo valido
- non esistono più colli
L'algoritmo costuttivo termina quando tutti i colli in esame sono stati assegnati ad un impilamento ammissibile.

Il metodo algoritmico, come mostrato, costruisce, sicuramente, una soluzione ammissibile, di contro rappresenta un metodo di denizione della soluzione, chiuso, ciò vuole dire che nella costruzione dell'impilamento,vengono automaticamente escluse qualsiasi varianti a posizionamenti dierenti dei colli, quali, ad esempio, permutazioni tra colli o scambi di colli. In altre parole: non è possibile modificare lo stato della soluzione definita nelle istanze precedenti, questo aspetto riduce la grandezza, in termini di colli, della soluzione ammissibile.
In quest'ottica se consideriamo l'impilamento più grande, tra quelli costituiti per una data istanza, possiamo affermare concretamente che la soluzione dell'Euristica Costruttiva determina un Lower Bound per il nostro problema. Scopo dell'Algoritmo Esatto sarà quello di verificare se esiste una soluzione migliore di quella Costruttiva, analizzando sottoinsiemi di colli.