2026-03-14T17:56:34Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00233726 2025-01-19T10:00:34Z 581:11492:11496

A Subtour Elimination Constraint for Non-simpl e Circuit Problems A Subtour Elimination Constraint for Non-simpl e Circuit Problems Seiji, Kataoka Seiji, Kataoka [一般論文] Non-simple circuit, Orienteering problem, Subtour elimination constraint, Callback function provided in solvers 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 ------------------------------ 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 ------------------------------ journal article 情報処理学会 2024-04-15 application/pdf 情報処理学会論文誌 4 65 1882-7764 AN00116647 https://ipsj.ixsq.nii.ac.jp/record/233726/files/IPSJ-JNL6504007.pdf eng