Search -
Exploiting Consecutive Ones Structure in the Set Partitioning Problem
Exploiting Consecutive Ones Structure in the Set Partitioning Problem Author:Mehmet Ayik This is a NAVAL POSTGRADUATE SCHOOL MONTEREY CA report procured by the Pentagon and made available for public release. It has been reproduced in the best form available to the Pentagon. It is not spiral-bound, but rather assembled with Velobinding in a soft, white linen cover. The Storming Media report number is A105783. The abstract provided by... more » the Pentagon follows: 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.« less