A novel decomposition method for MILP and its application to optimal operation of a thermal storage system

A novel decomposition method for solving large scale mixed integer linear programming (MILP) problems with block angular structure is proposed to conduct operational planning of energy supply systems with storage units rationally and efficiently. The method is composed of solving two types of problems repeatedly: one is a large scale MILP master problem with the values of part of the integer variables fixed from the results of the other; the other is a small scale MILP subproblem with the values of the simplex multipliers obtained from the results of the former. The method is applied to the operational planning of a heat supply system with cold and hot water storage tanks. The validity and effectiveness of the method is evaluated in terms of solution optimality and computation time. As a result, it turns out that the method is superior to the conventional branch and bound method with the depth-first or best-bound search, (C) 2000 Elsevier Science Ltd. All rights reserved.