Multi-objective Branch and Bound based on Decomposition

カテゴリ: 論文誌(論文単位)

グループ名: 【C】電子・情報・システム部門

発行日: 2022/03/01

タイトル(英語): Multi-objective Branch and Bound based on Decomposition

著者名: Tomoki Kaho (Muroran Institute of Technology), Shinya Watanabe (Muroran Institute of Technology), Kazutoshi Sakakibara (Toyama Prefectural University)

著者名(英語): Tomoki Kaho (Muroran Institute of Technology), Shinya Watanabe (Muroran Institute of Technology), Kazutoshi Sakakibara (Toyama Prefectural University)

キーワード: branch-and-bound，multi-objective optimization，multi-objective mixed-integer linear programming，simplex method

要約(英語): Traditional multi-objective branch-and-bound approaches to multi-objective mixed-integer linear programming (MOMILP) problems are very expensive to search due to the huge number of Pareto-optimal solutions. In this research, we propose a practical method of dividing a multi-objective problem into multiple single-objective problems by weight vectors and applying the branch-and-bound method (BB) to each subproblem. The proposed method is named multi-objective branch-and-bound based on decomposition (MOBB/D) because it is a combination of the concept of multi-objective evolutionary algorithm based on decomposition (MOEA/D) and BB. The most important feature of MOBB/D is to obtain many Pareto solutions efficiently by sharing information between nearby subproblems in MOMILP problems. In this paper, we describe an approach to share tables in the simplex method as an example of information. Moreover, MOBB/D can control computation cost for solving MOMILP problems by adjusting the number of obtained Pareto solutions. To verify the effectiveness of the proposed method, we compared the search performance of MOBB/D with and without the use of neighborhood information.

本誌: 電気学会論文誌C（電子・情報・システム部門誌） Vol.142 No.3 （2022） 特集Ⅰ：スマートシステムと計測・制御技術 －Withコロナ社会に向けて－　 特集Ⅱ：高機能化合物半導体エレクトロニクス技術と将来システムへの応用　特集Ⅲ：国際会議ICESS 2020

本誌掲載ページ: 373-381 p

原稿種別: 論文／英語

電子版へのリンク: https://www.jstage.jst.go.jp/article/ieejeiss/142/3/142_373/_article/-char/ja/