Finding the true nondominated points is typically hard for Multi-objective
Combinatorial Optimization (MOCO) problems. Furthermore, it is not practical to
generate all of them since the number of nondominated points may grow
exponentially as the problem size increases. In this thesis, we develop an exact
algorithm to find all nondominated points in a specified region. We combine this
exact algorithm with a heuristic algorithm that approximates the possible locations of
the nondominated points. Interacting with a decision maker (DM), the heuristic
algorithm first approximately identifies the region that is of interest to the DM. Then,
the exact algorithm is employed to generate all true nondominated points in this
region. We conduct experiments on Multi-objective Assignment Problems (MOAP),
Multi-objective Knapsack Problems (MOKP) and Multi-objective Shortest Path
(MOSP) Problems / and the algorithms work well.
Finding the worst possible value for each criterion among the set of efficient
solutions has important uses in multi-criteria problems since the proper scaling of
each criterion is required by many approaches. Such points are called nadir points.
v
It is not straightforward to find the nadir points, especially for large problems with
more than two criteria. We develop an exact algorithm to find the nadir values for
multi-objective integer programming problems. We also find bounds with
performance guarantees. We demonstrate that our algorithms work well in our
experiments on MOAP, MOKP and MOSP problems.
Assuming that the DM' / s preferences are consistent with a quasiconcave value
function, we develop an interactive exact algorithm to solve MIP problems. Based on
the convex cones derived from pairwise comparisons of the DM, we generate
constraints to prevent points in the implied inferior regions. We guarantee finding the
most preferred point and our computational experiments on MOAP, MOKP and
MOSP problems show that a reasonable number of pairwise comparisons are
required.
| Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/12613379/index.pdf |
| Date | 01 July 2011 |
| Creators | Lokman, Banu |
| Contributors | Koksalan, Murat |
| Publisher | METU |
| Source Sets | Middle East Technical Univ. |
| Language | English |
| Detected Language | English |
| Type | Ph.D. Thesis |
| Format | text/pdf |
| Rights | To liberate the content for public access |
Page generated in 0.0022 seconds