Solving the Linear Programming Relaxation of Cutting and Packing Problems: A Hybrid Simplex Method/Subgradient Optimization Procedure

摘要

In this paper we present a new method for solving the linear programming relaxation of the Cutting Stock Problem. The method is based on the relationship betweencolumn generation and Lagrange relaxation. We have called our method the Hybrid Simplex Method/Subgradient Optimization Procedure. We test our procedure ongenerated data sets and compare it with the classical column generation approach.