Exploiting Consecutive Ones Structure in the Set Partitioning Problem
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 2000
- Accession Number
- ADA387501
Entities
People
- Mehmet Ayik
Organizations
- Naval Postgraduate School