文献

J-GLOBAL ID：201802236184343145   整理番号：18A0180247

大規模組合せ最適化問題に対する数理アプローチの基礎

Basics of Mathematical Approaches to Large-Scale Combinatorial Optimization Problems

著者 (1件)： 田中俊二 (京都大学 国際高等教育院/工学研究科電気工学専攻)
資料名： 計測と制御  (Journal of the Society of Instrument and Control Engineers)
巻： 56  号： 12  ページ： 967-972(J-STAGE)  発行年： 2017年 
JST資料番号： F0131A  ISSN： 0453-4662  CODEN： KESEA  資料種別： 逐次刊行物 (A)
記事区分： 解説  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 大規模組合せ最適化問題に対する数理アプローチとして,制約条件の一部を取り除く代わりに,その違反度合いを目的関数にペナルティとして組み込んで新しい問題を生成するLangange緩和問題の例として,一般化割当問題(generalized assignment problem)を検討した。,列生成法(column generation)の例として容量制約付き配車問題(capacitated vehicle routing problem)を紹介した。また,Benders分解(Benders decomposition)の例として,発電機の運転計画問題を考察した。

シソーラス用語： *組合せ最適化問題 ,  *緩和法 ,  *方式 ,  分解 ,  割当問題 ,  整数線形計画法
準シソーラス用語： *大規模組合せ最適化問題 ,  *Lagrange緩和 ,  *列生成法 ,  Benders分解 ,  一般化割当問題 ,  容量制約付き配車問題

著者キーワード (6件)： Lagrange緩和 ,  列生成法 ,  Benders分解 ,  Lagrangian relaxation ,  column generation ,  Benders decomposition

分類 (1件)： 数理計画法  (KA03030M)

引用文献 (7件)：

• 1) O. E. Kundakcioglu and S. Alizamir: Generalized Assignment Problem, In: C. A. Floudas and P. M. Pardalos (Eds.): Encyclopedia of Optimization, Springer, 1153/1162 (2008)
• 2) G. B. Dantzig and P. Wolfe: Decomposition principle for linear programs, Operations Research, 8-1, 101/111 (1960)
• 3) J. Lysgaard, A. N. Letchford, and R. W. Eglese: A new branch-and-cut algorithm for the capacitated vehicle routing problem, Mathematical Programming, Ser. A, 100, 423/445 (2004)
• 4) M. Guignard: Lagrangean relaxation, Top, 11-2, 151/228 (2003)
• 5) G. Desqulniers, J. Desrosiers, and M. M. Solomon (Eds.): Column Generation, Springer (2010)

タイトルに関連する用語 (3件)： 大規模 ,  組合せ最適化問題 ,  基礎