  This paper investigates the column generation (CG) for solving cutting stock
problems (CSP). Traditional CG method, which repeatedly solves a restricted
master problem (RMP), often suffers from two critical issues in practice -- the
loss of solution quality introduced by linear relaxation of both feasible
domain and objective and the high time cost of last iterations close to
convergence. We empirically find that the first issue is common in ordinary
CSPs with linear cutting constraints, while the second issue is especially
severe in CSPs with nonlinear cutting constraints that are often generated by
approximating chance constraints. We propose an alternative approach, ensembles
of multiple column generation processes. In particular, we present two methods
-- \mc (multi-column) which return multiple feasible columns in each RMP
iteration, and \mt (multi-path) which restarts the RMP iterations from
different initialized column sets once the iteration time exceeds a given time
limit. The ideas behind are same: leverage the multiple column generation
pathes to compensate the loss induced by relaxation, and add earlier
sub-optimal columns to accelerate convergence of RMP iterations. Besides, we
give theoretical analysis on performance improvement guarantees. Experiments on
cutting stock problems demonstrate that compared to traditional CG, our method
achieves significant run-time reduction on CSPs with nonlinear constraints, and
dramatically improves the ratio of solve-to-optimal on CSPs with linear
constraints.
