| 講演名 | 1997/11/13 数理計画法を用いた制約最適化問題の解法 蔡 東風, 石塚 満, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 人工知能における様々な問題は制約充足問題に帰着できる. 特に, 実用的には, CSPの変数の各値または制約の各要素に非負の数値の重みを付けて, 解の重み和を最小にするような解を求める制約最適化問題(COP)が重要である. 本研究では, 数理計画法を用いて, 値に重みを付ける制約最適化問題(VCOP)の近似解法を提案する. まず, VCOPを0-1整数線形計画問題 (ILP) に帰着し, このILPの連続緩和問題の実数最適解を求める. そして, この「実数最適解の周り」の局所探索によって, O-1整数最適解或いは0-1準最適解を求める. 実験により, 特に困難な緩い制約のVCOPに対して、本手法が有効であることを示した。 |
| 抄録(英) | Many problems in AI can be formulated as Constraint Satisfaction Problems(CSPs). In actual problems, Constraint Optimization Problem(COP) or Constraint Satisfaction Optimization Problem (CSOP) is more important. In this paper, we present a new method for CSOP, in witch linear programming method is used. CSOP is transformed at first into a 0-1 integer linear programming problem, then it's relaxation problem is solved by simplex method. Then with using the optimal solution of this relaxation problem, a near-optimal solution of the CSOP can be obtained by a local search method. In our experiments, this method shows a good performance on CSOP, especially on loosely constrained CSOP. |
| キーワード(和) | 制約充足間題 / 制約最適化問題 / 局所探索 / 最適解 |
| キーワード(英) | CSP / constraint optimization problem / local search / optimal solution |
| 資料番号 | AI97-26 |
| 発行日 |
| 研究会情報 | |
| 研究会 | AI |
|---|---|
| 開催期間 | 1997/11/13(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Artificial Intelligence and Knowledge-Based Processing (AI) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 数理計画法を用いた制約最適化問題の解法 |
| サブタイトル（和） | |
| タイトル（英） | A Method for Constraint Optimization Problem Using Linear Programming |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 制約充足間題 / CSP |
| キーワード(2)（和/英） | 制約最適化問題 / constraint optimization problem |
| キーワード(3)（和/英） | 局所探索 / local search |
| キーワード(4)（和/英） | 最適解 / optimal solution |
| 第 1 著者 氏名（和/英） | 蔡 東風 / Dongfeng Cai |
| 第 1 著者 所属（和/英） | 東京大学工学部電子情報工学科 Dept. of Information & Commun. Eng., Faculty of Eng., The University of Tokyo |
| 第 2 著者 氏名（和/英） | 石塚 満 / Mitsuru Ishizuka |
| 第 2 著者 所属（和/英） | 東京大学工学部電子情報工学科 Dept. of Information & Commun. Eng., Faculty of Eng., The University of Tokyo |
| 発表年月日 | 1997/11/13 |
| 資料番号 | AI97-26 |
| 巻番号（vol） | vol.97 |
| 号番号（no） | 373 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |