Lezione 22.2: dai simplessi al Branch & Bound
Completion requirements
A cosa serve il simplesso duale: riottimizzazione nel caso di inserzione di un vincolo. Accenno agli altri casi (cambio di c / b, inserzione di variabile). Branch&Bound (enumerazione implicita) per il problema dello zaino senza averlo mai formalmente definito. Risoluzione del rilassamento continuo e tecnica "greedy" per l'individuazione di una soluzione ammissibile (entrambe basate sui rendimenti decrescenti), quando questo risolverebbe il problema (soluzione del continuo intera), branching whack-a-mole sulla variabile frazionaria. Potatura dei nodi per ottimalità.