WEKO3
アイテム
探索木を用いた優先順位付き割当問題のための近似解法
https://ipsj.ixsq.nii.ac.jp/records/32495
https://ipsj.ixsq.nii.ac.jp/records/32495476a3498-05ec-4e12-a312-e65c90a305d2
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL92031002.pdf (1.3 MB)
|
Copyright (c) 1993 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1993-01-25 | |||||||
| タイトル | ||||||||
| タイトル | 探索木を用いた優先順位付き割当問題のための近似解法 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | AN APPROXIMATION METHOD USING SEARCH TREES FOR SOLVING ASSIGNMENT PROBLEMS WITH PRIORITY ORDER | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 広島県立大学 | ||||||||
| 著者所属 | ||||||||
| 広島県立大学 | ||||||||
| 著者所属 | ||||||||
| 大阪工業大学 | ||||||||
| 著者所属 | ||||||||
| 広島県立大学 | ||||||||
| 著者所属 | ||||||||
| 広島県立大学 | ||||||||
| 著者所属 | ||||||||
| 広島県立大学 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Hiroshima Prefectural University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Hiroshima Prefectural University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Osaka Institute of Technology | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Hiroshima Prefectural University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Hiroshima Prefectural University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Hiroshima Prefectural University | ||||||||
| 著者名 |
錦織昭峰
× 錦織昭峰
|
|||||||
| 著者名(英) |
Akimine, Nishikori
× Akimine, Nishikori
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 本論文では、利益あるいは費用が金額として数値的に明確に与えることができない割当問題に対して、優先順位に従った割当をした解を求めるための近似解法を提案する。提案法では、（）単調減少しにくい実行不可能和の最小化を行うためには、どのような複数の整数変数を一度に変化させるべきかを探索木を用いて調べており、（）得られた探索によって逐次割当を変更する際には、変更したところ以外の探索木のアークは残しておいて、次の探索の際の情報として用いており、(）割当状態を変更した結果不要となるアークの削除個数をできるだけ少なくしている。大規模な割当問題を用いて数値シミュレーション実験を行った結果、提案法は効率的む方法であることが示された。 | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | This paper presents an approximation method for obtaining a feasible solution of an assignment problem with priority order. The proposed method is applicable to assignment problems whose cost coefficients cannot clearly be determined. In the method, the following three procedures are iteratively carried out to decrease the sum of infeasibilities: (i) a set of integer variables to be changed is chosen by means of search trees. (ii) the trees are modified after the integer variables are changed, and (iii) the assignment is altered so that the number of deleted arcs is as small as possible. The method has proved to be efficient as a result of applying it to large-scale assignment problems. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1993, 号 10(1992-AL-031), p. 9-16, 発行日 1993-01-25 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
