The Guided Improvement Algorithm for Exact, General-Purpose, Many-Objective Combinatorial Optimization
This paper presents a new general-purpose algorithm for exact solving of combinatorial many-objective optimization problems. We call this new algorithm the guided improvement algorithm. The algorithm is implemented on top of the non-optimizing relational constraint solver Kodkod. We compare the perf...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Published: |
2009
|
| Online Access: | http://hdl.handle.net/1721.1/46322 |
| _version_ | 1811076452251074560 |
|---|---|
| author | Jackson, Daniel Estler, H.-Christian Rayside, Derek |
| author2 | Daniel Jackson |
| author_facet | Daniel Jackson Jackson, Daniel Estler, H.-Christian Rayside, Derek |
| author_sort | Jackson, Daniel |
| collection | MIT |
| description | This paper presents a new general-purpose algorithm for exact solving of combinatorial many-objective optimization problems. We call this new algorithm the guided improvement algorithm. The algorithm is implemented on top of the non-optimizing relational constraint solver Kodkod. We compare the performance of this new algorithm against two algorithms from the literature [Gavanelli 2002, Lukasiewycz et alia 2007, Laumanns et alia 2006]) on three micro-benchmark problems (n-Queens, n-Rooks, and knapsack) and on two aerospace case studies. Results indicate that the new algorithm is better for the kinds of many-objective problems that our aerospace collaborators are interested in solving. The new algorithm returns Pareto-optimal solutions as it computes. |
| first_indexed | 2024-09-23T10:22:23Z |
| id | mit-1721.1/46322 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T10:22:23Z |
| publishDate | 2009 |
| record_format | dspace |
| spelling | mit-1721.1/463222019-04-12T07:36:35Z The Guided Improvement Algorithm for Exact, General-Purpose, Many-Objective Combinatorial Optimization Jackson, Daniel Estler, H.-Christian Rayside, Derek Daniel Jackson Software Design This paper presents a new general-purpose algorithm for exact solving of combinatorial many-objective optimization problems. We call this new algorithm the guided improvement algorithm. The algorithm is implemented on top of the non-optimizing relational constraint solver Kodkod. We compare the performance of this new algorithm against two algorithms from the literature [Gavanelli 2002, Lukasiewycz et alia 2007, Laumanns et alia 2006]) on three micro-benchmark problems (n-Queens, n-Rooks, and knapsack) and on two aerospace case studies. Results indicate that the new algorithm is better for the kinds of many-objective problems that our aerospace collaborators are interested in solving. The new algorithm returns Pareto-optimal solutions as it computes. 2009-07-03T19:15:04Z 2009-07-03T19:15:04Z 2009-07-03 http://hdl.handle.net/1721.1/46322 MIT-CSAIL-TR-2009-033 Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported http://creativecommons.org/licenses/by-nc-nd/3.0/ 20 p. application/pdf application/postscript |
| spellingShingle | Jackson, Daniel Estler, H.-Christian Rayside, Derek The Guided Improvement Algorithm for Exact, General-Purpose, Many-Objective Combinatorial Optimization |
| title | The Guided Improvement Algorithm for Exact, General-Purpose, Many-Objective Combinatorial Optimization |
| title_full | The Guided Improvement Algorithm for Exact, General-Purpose, Many-Objective Combinatorial Optimization |
| title_fullStr | The Guided Improvement Algorithm for Exact, General-Purpose, Many-Objective Combinatorial Optimization |
| title_full_unstemmed | The Guided Improvement Algorithm for Exact, General-Purpose, Many-Objective Combinatorial Optimization |
| title_short | The Guided Improvement Algorithm for Exact, General-Purpose, Many-Objective Combinatorial Optimization |
| title_sort | guided improvement algorithm for exact general purpose many objective combinatorial optimization |
| url | http://hdl.handle.net/1721.1/46322 |
| work_keys_str_mv | AT jacksondaniel theguidedimprovementalgorithmforexactgeneralpurposemanyobjectivecombinatorialoptimization AT estlerhchristian theguidedimprovementalgorithmforexactgeneralpurposemanyobjectivecombinatorialoptimization AT raysidederek theguidedimprovementalgorithmforexactgeneralpurposemanyobjectivecombinatorialoptimization AT jacksondaniel guidedimprovementalgorithmforexactgeneralpurposemanyobjectivecombinatorialoptimization AT estlerhchristian guidedimprovementalgorithmforexactgeneralpurposemanyobjectivecombinatorialoptimization AT raysidederek guidedimprovementalgorithmforexactgeneralpurposemanyobjectivecombinatorialoptimization |