Decomposition-Based Algorithms for Mixed-Integer Linear Programs with Integer Subproblems

Mathematical decomposition methods have been extensively used in the last decades to solve large scale optimization problems. In this chapter, we study a special class of problems that, once reformulated through Benders decomposition, exhibit mixed-integer variables in the master problem and subproblems. In these problems, some master problem variables are bounded, and cardinality constraints restrict their use. We propose two decomposition-based algorithms to address these problems. The first algorithm generates classical optimality cuts from the linear programming relaxation of the subproblem. When no more of these classical cuts can be added, the algorithm adds a new type of integer Benders optimality cut to ensure the convergence of the method to an optimal solution. The second algorithm adds the relaxation of the Benders subproblem variables in the master problem and includes these variables in the composition of integer Benders optimality cuts. These approaches were tested on two problems: the multi-commodity facility location problem and the multi-activity shift scheduling problem. Computational results are presented on numerous instances with different characteristics to demonstrate the efficacy of these approaches.