A METHOD FOR DECOMPOSING MIXED-INTEGER LINEAR-PROGRAMS WITH STAIRCASE STRUCTURE

An algorithm is presented for solving mixed-integer linear programs with a staircase structure. The basic idea of the algorithm is to decompose the original problem into a series form of small-scale mixed-integer problems. For each problem decomposed, the solution is obtained by the conventional branch-and-bound method. In this algorithm the feasibility of the solution is always assured, but in order to save computation time the optimality condition is checked restrictedly for the solution obtained. The difference between the optimal objective value and the objective value obtained can be estimated. By examining numerical results, it is observed that the algorithm is efficient, requiring less computation time than other methods.