On LP relaxations for the pattern minimization problem
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(u) be the bound given by the linear relaxation of (i) under a given vector u of parameters. We show that z(u) ≥ z(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, 2011Keywords
This publication has 11 references indexed in Scilit:
- New lower bounds based on column generation and constraint programming for the pattern minimization problemComputers & Operations Research, 2009
- Fast lifting procedures for the bin packing problemDiscrete Optimization, 2005
- Integrating process optimization and inventory planning in cutting-stock with skiving option: An optimization model and its applicationEuropean Journal of Operational Research, 2005
- One-dimensional cutting stock problem to minimize the number of different patternsEuropean Journal of Operational Research, 2003
- LP models for bin packing and cutting stock problemsEuropean Journal of Operational Research, 2002
- Exact Algorithm for Minimising the Number of Setups in the One-Dimensional Cutting Stock ProblemOperations Research, 2000
- A Unified Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling Problems1998
- CUTGEN1: A problem generator for the standard one-dimensional cutting stock problemEuropean Journal of Operational Research, 1995
- A Linear Programming Approach to the Cutting Stock Problem—Part IIOperations Research, 1963
- Mathematical Methods of Organizing and Planning ProductionManagement Science, 1960