A decomposition technique for mixed integer programming problems

A technique for decomposing mixed integer programming problems, having block angular structure, is presented in this paper. Applying Lagrangean relaxation to the set of coupling constraints permits a decomposition of the mixed integer programming problem into several smaller mixed integer subproblems. Consequently, each subproblem contains variables and constraints pertaining to only the subproblem. The subproblems can be solved independently and simultaneously. Rather than obtaining only the optimal solutions to the subproblems, their several suboptimal solutions are also recorded. Then, an integer master program is constructed and solved by subgradient optimization and/or by an enumeration method. Optimality conditions are specified. Also discussed is a criterion which helps disqualify suboptimal solutions that cannot become part of the optimal solution to the original problem. The decomposition technique is independent of the method used to solve the subproblems. This technique is demonstrated by solving an airline routing problem.