A Subtour Elimination Constraint for Non-simpl e Circuit Problems

• Item type: Journal(1)
• 公開日: 2024-04-15
• タイトル: A Subtour Elimination Constraint for Non-simpl e Circuit Problems
• タイトル / 言語: en
• タイトル: A Subtour Elimination Constraint for Non-simpl e Circuit Problems
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [一般論文] Non-simple circuit, Orienteering problem, Subtour elimination constraint, Callback function provided in solvers
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Department of Computer Science, National Defense Academy
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, National Defense Academy
• 著者名: Seiji, Kataoka
• 著者名(英): Seiji, Kataoka
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: In various problems on graphs to find the optimal path or circuit, feasible solutions are normally assumedto be simple. In reality, however, one-way or return roads, bridges connecting enclaves, etc. often lead to multiplepasses through the same points or roads, i.e. a non-simple path or circuit. The difficulty in considering a non-simplepath or circuit is that conventional subtour elimination constraints are of no use. Taking the orienteering problem as atarget, we newly develop a subtour elimination constraint that works directly against non-simple type problems, andshow its effectiveness in computational experiments.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.32(2024) (online); DOI http://dx.doi.org/10.2197/ipsjjip.32.346; ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In various problems on graphs to find the optimal path or circuit, feasible solutions are normally assumedto be simple. In reality, however, one-way or return roads, bridges connecting enclaves, etc. often lead to multiplepasses through the same points or roads, i.e. a non-simple path or circuit. The difficulty in considering a non-simplepath or circuit is that conventional subtour elimination constraints are of no use. Taking the orienteering problem as atarget, we newly develop a subtour elimination constraint that works directly against non-simple type problems, andshow its effectiveness in computational experiments.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.32(2024) (online); DOI http://dx.doi.org/10.2197/ipsjjip.32.346; ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 65, 号 4, 発行日 2024-04-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764
• 公開者 / 言語: ja
• 公開者 / 出版者: 情報処理学会