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

Abstract

An algorithm is presented for solving mixed-integer linear programming problems with an angular structure, based on the decomposition technique of Dantzig and Wolfe. The subproblem is a mixed-integer problem of a smaller size than that of the original one. A sufficient condition for optimality is obtained. In the case where the optimality condition is not satisfied, a search for improving the solution is being continued within a restricted extent. By examining illustrative examples, it is observed that the present algorithm is efficient because it has less computing time than the conventional branch and bound method.