This chapter focuses on the famous cutting stock/bin packing problem which was the first problem to be modeled by column generation. The compact equivalent counterpart of this problem has a very interesting structure of a particular flow problem. Two other packing problems for which we may show compact extended formulations are the robust knapsack problem and the cycle packing problem. For the former problem we show, by using LP techniques, that of two different formulations appeared in the literature one is indeed the compact extended formulation of the other.

Packing

Lancia G.;Serafini P.
2018

Abstract

This chapter focuses on the famous cutting stock/bin packing problem which was the first problem to be modeled by column generation. The compact equivalent counterpart of this problem has a very interesting structure of a particular flow problem. Two other packing problems for which we may show compact extended formulations are the robust knapsack problem and the cycle packing problem. For the former problem we show, by using LP techniques, that of two different formulations appeared in the literature one is indeed the compact extended formulation of the other.
978-3-319-63975-8
978-3-319-63976-5
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11390/1214315
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact