Exploiting consecutive ones structure in the set partitioning problem
Loading...
Authors
Ayik, Mehmet
Subjects
Advisors
Brown, Gerald G.
Owen, Guillermo
Date of Issue
2000-12
Date
2000
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
The Set Partitioning Problem (SPP) is one of the most extensively researched models in integer optimization, and is widely applied in operations research. SPP is used for crew scheduling, vehicle routing, stock cutting, production scheduling, and many other combinatorial problems. The power and generality of SPP come at a price: An SPP can be very difficult to solve. A real-world SPP often has columns, or rows, with long strings of consecutive ones. We exploit this with a new preprocessing reduction that can eliminate some variables. We also introduce a column-splitting technique to render a model that can be solved directly or used to bound SPP with Lagrangian relaxation or an exterior penalty method. We develop an SPP row- splitting method that yields a special model that Bender's decomposition may then solve faster than the monolithic SPP. We demonstrate these techniques with well-known test problems from airlines and other researchers. We also contribute a new U.S. Navy aircraft carrier long-term deployment scheduling model, using our new techniques to plan with weekly fidelity over a ten-year planning horizon. This improved time fidelity increases planned deployment coverage of areas of responsibility by about ten carrier weeks.
Type
Thesis
Description
Series/Report No
Department
Operations Research
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
xii, 158 p.;28 cm.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.