In situ column generation for a cutting-stock problem (Q868997)

The paper deals with the development of a new model for the cutting stock problem (CSP). A bilinear programming model describes the CSP and a modification of it is proposed. Some patterns are fixed and the rest of the linear terms are linearized. A computational method is developed and some experiments are used for evaluating its behavior. Upper bounds for the number of bits (integer encoded patterns), used for representing the number of rolls to be cut, are computed using proposed formulae. The Boolean quadric polytope of the involved bipartite graphs is derived. The computation implemented is supported by the software AMPL. Numerical experiments are performed using the ILP solver CPLEX90, Xpress-MP14J and CBC (an open aces one). The results are very close to those obtained through the use of the classic IPL solver but the author claims that his proposal appears as a more practical alternative. The data used in the experiments come from chemical fibber instances. Two tables present the relevant results of the study.