A Strategy for Partitioning Variables in Using a Decomposition Method for Mixed-Integer Linear Programming

Mixed-integer linear programming (MILP) can be used for a variety of optimization problems. However, it is limited to relatively small-scale problems, because its computation time increases dramatically with the number of integer variables. Decomposition methods have been presented to derive good feasible solutions of MILP problems. The objective of this paper is to propose a strategy for partitioning variables in using a decomposition method presented by the authors. The strategy proposed here is to decompose an original MILP problem into the smallest MILP subproblems, each of which has a single integer variable, and enables one to assume the values of part of integer variables efficiently to obtain a reduced MILP master problem. A single-period operational planning problem of a simplified heat supply system is investigated analytically to show the meaning and validity of the strategy. A multi-period operational planning problem of a practical heat supply system is also investigated numerically to show the validity and effectiveness of the decomposition method into which the strategy is incorporated.