文献

J-GLOBAL ID：201802267981264279   整理番号：18A0331698

二次ナップサック問題のための反復「超平面探査」アプローチ【Powered by NICT】

An iterated “hyperplane exploration” approach for the quadratic knapsack problem

著者 (3件)： Chen Yuning (LERIA, Universite d’Angers, 2 Bd Lavoisier, 49045 Angers, France) ,  Hao Jin-Kao (LERIA, Universite d’Angers, 2 Bd Lavoisier, 49045 Angers, France) ,  Hao Jin-Kao (Institut Universitaire de France, Paris, France)
資料名： Computers & Operations Research  (Computers & Operations Research)
巻： 77  ページ： 226-239  発行年： 2017年 
JST資料番号： H0216B  ISSN： 0305-0548  CODEN： CMORAP  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 二次ナップサック問題(QKP)は多くの応用を持つ良く知られた組合せ最適化問題である。そのNP困難性で,一般的な場合におけるQKPに対する最適解または高品質の準最適解を見出すことは挑戦的な仕事である。本論文では,QKPを近似的に解くための反復「超平面探査」アプローチ(IHEA)を提案した。全解空間を考慮することの代わりに,提案した手法は,解空間の有望な地域に探索範囲を定めるために基数制約により定義される超表面の集合上の探索のアイデアを採用した。これら超平面を効率よく探索するために,IHEAは可変固定戦略を採用している各超平面制約部分問題を低減し,その後減少解空間内の高品質解を探し出すのに専用タブー探索法を適用した。三セットの220QKPインスタンスの上で包括的な実験研究はIHEAは解の質と計算効率の両方に関して最先端のアルゴリズムと非常によく競合することを示した。は提案した手法の重要な成分についての洞察を得るために付加的な情報を提供する。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： タブー探索 ,  近似法 ,  組合せ最適化問題 ,  NP困難 ,  発見的方法 ,  アルゴリズム ,  *ナップサック問題
準シソーラス用語： 計算効率 ,  部分問題 ,  基数 ,  解空間 ,  準最適解 ,  高品質 ,  最適解 ,  *超平面 , 【Automatic Indexing@JST】

著者キーワード (5件)： 二次ナップサック問題 ,  超平面探査 ,  タブー探索 ,  可変固定 ,  発見的方法

分類 (2件)： その他のオペレーションズリサーチの手法  (KA03070E) ,  ネットワーク法  (KA03040X)

タイトルに関連する用語 (4件)： ナップサック問題 ,  反復 ,  超平面 ,  探査