A branch-and-price algorithm for a class of assortment problems

In the Cutting Stock Problem, one calls for an efficient way to cut a given demand of small parts from a given collection of large parts. Many cutting processes, however, must also face the problem of determining a restricted subset of large sizes to be stocked. In this work we deal with the special case where just one part type can be cut from each large size. We describe a PLI formulation obtained by convexifying a straightforward big-M formulation. A pricing problem is indicated and Ryan-Foster's branching rule adapted with a view to implement a branch-and-price exact algorithm