We discuss two formulations of the pattern minimization problem: (1) introduced by Vanderbeck, and (2) obtained adding setup variables to the cutting stock formulation by Gilmore-Gomory. Let zLP(u) be the bound given by the linear relaxation of (i) under a given vector u of parameters. We show that zLP(u) ≥ zLP(u) and provide a class of instances for which the inequality holds strict. We observe that the linear relaxation of both formulations can be solved by the same column generation procedure and discuss the critical role of parameter u. The article is completed by a numerical test comparing the lower bounds obtained through (1) and (2) for different values of u.

On LP Relaxations for the Pattern Minimization Problem

ARBIB, CLAUDIO;
2011-01-01

Abstract

We discuss two formulations of the pattern minimization problem: (1) introduced by Vanderbeck, and (2) obtained adding setup variables to the cutting stock formulation by Gilmore-Gomory. Let zLP(u) be the bound given by the linear relaxation of (i) under a given vector u of parameters. We show that zLP(u) ≥ zLP(u) and provide a class of instances for which the inequality holds strict. We observe that the linear relaxation of both formulations can be solved by the same column generation procedure and discuss the critical role of parameter u. The article is completed by a numerical test comparing the lower bounds obtained through (1) and (2) for different values of u.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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: https://hdl.handle.net/11697/20043
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 8
social impact