6533b7ddfe1ef96bd127474d
RESEARCH PRODUCT
A branch-and-cut algorithm for the pallet loading problem
Francisco ParreñoJosé Manuel TamaritRamón Alvarez-valdéssubject
Mathematical optimizationGeneral Computer ScienceManagement Science and Operations ResearchReduction (complexity)PolyhedronCover (topology)Cutting stock problemModeling and SimulationIndependent setGraph (abstract data type)PalletBranch and cutAlgorithmMathematicsdescription
We propose a branch-and-cut algorithm for the pallet loading problem. The 0-1 formulation proposed by Beasley for cutting problems is adapted to the problem, adding new constraints and new procedures for variable reduction. We then take advantage of the relationship between this problem and the maximum independent set problem to use the partial linear description of its associated polyhedron. Finally, we exploit the specific structure of our problem to define the solution graph and to develop efficient separation procedures. We present computational results for the complete sets Cover I (up to 50 boxes) and Cover II (up to 100 boxes).
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2005-11-01 | Computers & Operations Research |