| Presentation | 1997/11/13 A Method for Constraint Optimization Problem Using Linear Programming Dongfeng Cai, Mitsuru Ishizuka, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | CSP / constraint optimization problem / local search / optimal solution |
| Paper # | AI97-26 |
| Date of Issue |
| Conference Information | |
| Committee | AI |
|---|---|
| Conference Date | 1997/11/13(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Artificial Intelligence and Knowledge-Based Processing (AI) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A Method for Constraint Optimization Problem Using Linear Programming |
| Sub Title (in English) | |
| Keyword(1) | CSP |
| Keyword(2) | constraint optimization problem |
| Keyword(3) | local search |
| Keyword(4) | optimal solution |
| 1st Author's Name | Dongfeng Cai |
| 1st Author's Affiliation | Dept. of Information & Commun. Eng., Faculty of Eng., The University of Tokyo() |
| 2nd Author's Name | Mitsuru Ishizuka |
| 2nd Author's Affiliation | Dept. of Information & Commun. Eng., Faculty of Eng., The University of Tokyo |
| Date | 1997/11/13 |
| Paper # | AI97-26 |
| Volume (vol) | vol.97 |
| Number (no) | 373 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |