| Item type |
SIG Technical Reports(1) |
| 公開日 |
2015-01-06 |
| タイトル |
|
|
タイトル |
Min-Max Regret基準の一般化割当問題に対する解法 |
| 言語 |
|
|
言語 |
eng |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
Nagoya University |
| 著者所属 |
|
|
|
University of Modena and Reggio Emilia |
| 著者所属 |
|
|
|
University of Bologna |
| 著者所属 |
|
|
|
Nagoya University |
| 著者所属(英) |
|
|
|
en |
|
|
Nagoya University |
| 著者所属(英) |
|
|
|
en |
|
|
University of Modena and Reggio Emilia |
| 著者所属(英) |
|
|
|
en |
|
|
University of Bologna |
| 著者所属(英) |
|
|
|
en |
|
|
Nagoya University |
| 著者名 |
呉, 偉
Manuel, Iori
Silvano, Martello
柳浦, 睦憲
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Many real life optimization problems do not have accurate estimates of the problem parameters at the optimization phase. For this reason, the min-max regret criteria are widely used to obtain robust solutions. In this paper we consider the generalized assignment problem (GAP) with min-max regret criterion under interval costs. We show that the decision version of this problem is Σp2-complete. We present two heuristic methods: a fixed-scenario approach and a dual substitution algorithm. For the fixed-scenario approach, we show that solving the classical GAP under a median-cost scenario leads to a solution of the min-max regret GAP whose objective function value is within twice the optimal value. We also propose exact algorithms, including a Benders' decomposition approach and branch-and-cut methods which incorporate various methodologies, including Lagrangian relaxation and variable fixing. The resulting Lagrangian-based branch-and-cut algorithm performs satisfactorily on benchmark instances. |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Many real life optimization problems do not have accurate estimates of the problem parameters at the optimization phase. For this reason, the min-max regret criteria are widely used to obtain robust solutions. In this paper we consider the generalized assignment problem (GAP) with min-max regret criterion under interval costs. We show that the decision version of this problem is Σp2-complete. We present two heuristic methods: a fixed-scenario approach and a dual substitution algorithm. For the fixed-scenario approach, we show that solving the classical GAP under a median-cost scenario leads to a solution of the min-max regret GAP whose objective function value is within twice the optimal value. We also propose exact algorithms, including a Benders' decomposition approach and branch-and-cut methods which incorporate various methodologies, including Lagrangian relaxation and variable fixing. The resulting Lagrangian-based branch-and-cut algorithm performs satisfactorily on benchmark instances. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2015-AL-151,
号 2,
p. 1-5,
発行日 2015-01-06
|
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL15151002.pdf (594.5 kB)
