Optimization Online


On LP Relaxations for the Pattern Minimization Problem

Alessandro Aloisio (aloisio***at***di.univaq.it)
Claudio Arbib (arbib***at***di.univaq.it)
Fabrizio Marinelli (marinelli***at***diiga.univpm.it)

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 $z_i^{LP}(u)$ be the bound given by the linear relaxation of ($i$) under a given vector $u = (u_k)$ of parameters. We show that $z_2^{LP}(u}) \ge z_1^{LP}(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 parameters $u$. The paper is completed by a numerical test comparing the lower bounds obtained through (1) and (2) for different values of $u$.

Keywords: Cutting stock, Integer decomposition, Linear relaxations

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: NETWORKS, 57, 3 (2011) p. 247-253, DOI 10.1002/net


Entry Submitted: 10/09/2008
Entry Accepted: 10/09/2008
Entry Last Modified: 09/03/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society