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

Abstract

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.

Related Papers

• → On the existence of optimal solutions to integer and mixed-integer programming problems(1974)168 cited
• → Finding integer efficient solutions for multiple objective network programming problems(2010)4 cited
• → A reference direction approach to multiple objective integer linear programming(1995)28 cited
• → Differences between real and integer production possibility sets in data envelopment analysis(2015)1 cited
• → Optimal Weapon-Target Assignment of Multiple Dissimilar Closed-In Weapon Systems Using Mixed Integer Linear Programming(2019)