3401 分解法の多段階利用による大規模混合整数線形計画問題の一解法(OS03/近似最適化)

概要

論文の詳細を見る
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. A decomposition method has been proposed to derive good feasible solutions of large-scale MILP problems by the authors. The method is composed of solution of original and reduced MILP master problems, solution of MILP subproblems, and assumption of values of part of integer variables, which are repeated until a suboptimal solution is obtained. The objective of this paper is to propose a strategy to determine appropriately the number of integer variables whose values are assumed by means of multistage use of the decomposition method. A multi-period operational planning problem of a heat supply system is investigated numerically to show the validity and effectiveness of the strategy. It turns out that the strategy can derive a better suboptimal solution and an effective approximate lower bound for the optimal value of the objective function.
2001-11-01