A Method for Solving Mixed-Integer Linear Programming Problems with Angular Structure

Abstract

An algorithm for solving mixed-integer linear programming problems with an angular structure is proposed. The basic idea is to decompose the original problem in the same way as the Dantzig-Wolfe decomposition principle in the linear programs, and to solve a restricted master program and subproblems iteratively. The subproblems are mixed-integer problems of smaller sizes than that of the original one. The termination of this algorithm is checked in two stages. If the optimality test is satisfied, the procedure terminates with the optimal solution. If not, the search for improvement is continued within a restricted extent. If the search terminates with no improved solution, the best solution obtained so far is given as a suboptimal solution. The numerical results making comparisons between the present method and the branch and bound method are shown.