Premium
On LP relaxations for the pattern minimization problem
Author(s) -
Aloisio Alessandro,
Arbib Claudio,
Marinelli Fabrizio
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20422
Subject(s) - minification , column generation , linear programming relaxation , mathematics , relaxation (psychology) , combinatorics , class (philosophy) , linear programming , mathematical optimization , discrete mathematics , computer science , artificial intelligence , psychology , social psychology
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 of parameters. We show that z 2 LP ( u ) ≥ 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 parameter u . The article is completed by a numerical test comparing the lower bounds obtained through (1) and (2) for different values of u . © 2011 Wiley Periodicals, Inc. NETWORKS, 2011