We formulated the problem using mixed-integer programming (MIP). There are two pertinent issues that make solving our MIP challenging. First, it contains a large number of variables due to the combinatorial proliferation of possible end-products. Second, the conventional approach to implement the complementarity conditions modeling the machine set-ups uses a large number of auxiliary binary variables. To address the first issue we use the branch-and-price method; we dynamically add variables only when it is profitable to do so. This is accomplished by iteratively solving a set of shortest-path problems as illustrated in Figure 2. A directed walk from the source to sink node then corresponds to a feasible product combination for the customer. For the second issue, we enforce machine set-up requirements directly by using specialized branching rules inside the tree-search algorithm. Hence, no auxiliary variables are used. Furthermore, to improve the linear relaxations in the branch-and-bound tree-search, we augment strong valid inequalities based on the complementarity knapsack polytope using a branch-and-cut approach. Finally, we develop an efficient separating hyper-plane algorithm to dynamically identify these cuts during the solution process.

In our computational studies we coded our algorithms using the Java programming language. ILOG CPLEX 10.0 was used to solve the linear programming sub-problems. Our main finding was that when the cuts were augmented during the solution, more problem instances were solved to optimality; otherwise, the upper bounds obtained were much tighter, and the number of nodes processed was significantly lower. The separating hyper-plane algorithms were also very computationally economical. Our numerical studies thus demonstrate that the augmentation of these cuts into the branch-and-bound search can be very beneficial in reducing the amount of computational work required to obtain the optimal production plans.