Cyclic exchange and related neighborhood structures for combinatorial optimization problems
Thesis (Ph.D.)--Massachusetts Institute of Technology, Sloan School of Management, 2002.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/8526 |
| _version_ | 1826213180331786240 |
|---|---|
| author | Sharma, Dushyant, 1975- |
| author2 | James B. Orlin. |
| author_facet | James B. Orlin. Sharma, Dushyant, 1975- |
| author_sort | Sharma, Dushyant, 1975- |
| collection | MIT |
| description | Thesis (Ph.D.)--Massachusetts Institute of Technology, Sloan School of Management, 2002. |
| first_indexed | 2024-09-23T15:44:36Z |
| format | Thesis |
| id | mit-1721.1/8526 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T15:44:36Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/85262019-04-11T13:56:13Z Cyclic exchange and related neighborhood structures for combinatorial optimization problems Sharma, Dushyant, 1975- James B. Orlin. Sloan School of Management. Sloan School of Management. Sloan School of Management. Thesis (Ph.D.)--Massachusetts Institute of Technology, Sloan School of Management, 2002. Includes bibliographical references (p. 122-126). In this thesis, we concentrate on neighborhood search algorithms based on very large-scale neighborhood structures. The thesis consists of three parts. In the first part, we develop a cyclic exchange neighborhood search based approach for partitioning problems. A partitioning problem is to divide a set of n elements into K subsets S1,... ,SK so as to minimize f(S1)+...+f(SK) for some specified function f. A partition S'1,.. ,S'K is called a cyclic exchange neighbor of the partition S1,...,SK if [...]. The problem of searching the cyclic exchange neighborhood is NP-hard. We develop new exact and heuristic algorithms to search this neighborhood structure. We propose cyclic exchange based neighborhood search algorithms for specific partitioning problems. We provide computational results on these problems indicating that the cyclic exchange is very effective and can be implemented efficiently in practice. The second part deals with the Combined Through and Fleet Assignment Model (ctFAM). This model integrates two airline planning models: (i) Fleet Assignment Model and (ii) Through Assignment Model, which are currently solved in a sequential manner because the combined problem is too large. This leads to sub-optimal solutions for the combined problem we develop very large-scale neighborhood search algorithms for the ctFAM. We also extend our neighborhood search algorithms to solve the multi-criteria objective function version of the ctFAM. Our computational results using real-life data show that neighborhood search can be a useful supplement to the current integer-programming optimization methods in airline scheduling. (cont.) In the third part, we investigate the structure of neighborhoods in general. We call two neighborhood structures LO-equivalent if they have the same set of local optima for all instances of a combinatorial optimization problem. We define the extended neighborhood of a neighborhood structure N as the largest neighborhood structure that is LO-equivalent to N. In this thesis, we develop some theoretical properties of the extended neighborhood and relate these properties to the performance of a neighborhood structure. In particular, we show that the well-known 2-opt neighborhood structure for the Traveling Salesman Problem has a very large extended neighborhood, providing justification for its favorable empirical performance. by Dushyant Sharma. Ph.D. 2005-08-23T20:55:08Z 2005-08-23T20:55:08Z 2002 2002 Thesis http://hdl.handle.net/1721.1/8526 50873335 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 126 p. 10221977 bytes 10221733 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Sloan School of Management. Sharma, Dushyant, 1975- Cyclic exchange and related neighborhood structures for combinatorial optimization problems |
| title | Cyclic exchange and related neighborhood structures for combinatorial optimization problems |
| title_full | Cyclic exchange and related neighborhood structures for combinatorial optimization problems |
| title_fullStr | Cyclic exchange and related neighborhood structures for combinatorial optimization problems |
| title_full_unstemmed | Cyclic exchange and related neighborhood structures for combinatorial optimization problems |
| title_short | Cyclic exchange and related neighborhood structures for combinatorial optimization problems |
| title_sort | cyclic exchange and related neighborhood structures for combinatorial optimization problems |
| topic | Sloan School of Management. |
| url | http://hdl.handle.net/1721.1/8526 |
| work_keys_str_mv | AT sharmadushyant1975 cyclicexchangeandrelatedneighborhoodstructuresforcombinatorialoptimizationproblems |