Exploiting consecutive ones structure in the set partitioning problem.
Brown, Gerald G.
MetadataShow full item record
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.