文献

J-GLOBAL ID：202202236720947362   整理番号：22A0436878

有向固定電荷多重商品ネットワーク設計:極性双対性を用いた切断面アプローチ【JST・京大機械翻訳】

Directed fixed charge multicommodity network design: A cutting plane approach using polar duality

著者 (3件)： Agarwal Y.K. (Jaipuria Institute of Management, Lucknow 226010, India) ,  Aneja Y.P. (Odette School of Business, University of Windsor, N9B 3P4, Canada) ,  Jayaswal Sachin (Production & Quantitative Methods, Indian Institute of Management Ahmedabad, 380015, India)
資料名： European Journal of Operational Research  (European Journal of Operational Research)
巻： 299  号： 1  ページ： 118-136  発行年： 2022年 
JST資料番号： A0547A  ISSN： 0377-2217  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 有向固定電荷ネットワーク設計(DFCND)問題を正確に解くための効率的な切断面ベースアプローチを提示し,そこでは,この問題に対する有効な不等式を極性双対性アプローチを用いて生成する。このアプローチを用いることにおける最大の課題は,問題の極性二重構築において生じる。これは,DFCNDの凸包の全ての極値点を列挙することを必要とし,それは妥当なサイズの任意の例に対して計算的に実用的ではない。さらに,得られた極性二重は,効率的に解くには大きすぎず,切断面アルゴリズムのあらゆる反復で必要とされる。この解法の新規性は,基礎となるグラフの2,3および4分割から得た制約および変数の小さな部分集合のみを含む,より小さな下部構造の極性双対性を用いて,この課題を回避する方法を示唆する。ゼロフローコストのスパースグラフに基づく問題事例に対して,これらの不等式の追加は,文献で使用されるナップサックカバー不等式の追加後に残る最適ギャップの20%以上を閉じる。これにより,平均で400秒以下の問題インスタンスを解決でき,そうでなければ,ナップサックカバー不等式のみを付加し,そのデフォルト設定でCplex MIPソルバーに対して約4時間を要した。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  極性 ,  *双対性 ,  不等式 ,  整数計画法 ,  *ネットワーク ,  *多重化 ,  下部構造 ,  凸包
準シソーラス用語： 固定電荷 ,  *ネットワーク設計 ,  ソルバ , 【Automatic Indexing@JST】

著者キーワード (4件)： ネットワーク ,  整数計画法 ,  極性双対性 ,  切断面

分類 (2件)： グラフ理論基礎  (IA02020S) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (7件)： 固定電荷 ,  多重 ,  商品 ,  ネットワーク設計 ,  極性 ,  双対性 ,  切断面