In recent literature, a new technique has been proposed for the exact solution of a class of integer programming problems whose linear programming relaxation could efficiently be solved by column generation. This technique, called 'branch and price', embeds the column generation procedure with a branch and bound scheme. Various authors describe an implementation of the technique for cutting stock and bin packing problem with varying success. We present an efficient implementation of branch and price for these problems using a number of algorithmic enhancements, a dominance rule and a heuristic. We demonstrate that for branch and price, in addition to the resource pricing information, important additional efficiencies can be achieved by providing also resource requirement information to the subproblem. We validate our methodology using both industrial data sets and generated data sets. The performance of our algorithm is compared extensively with other implementations and the various heuristics for the problem. The main result of our methodology is that we solve industrial sizes of an NP hard problem practically in a time to solve its LP relaxation.
展开▼
