Publication:
Improving banch-and-price algorithms and applying them to Stochastic programs

Loading...
Thumbnail Image
Authors
Silva, Eduardo Ferreira
Subjects
branch-and-price
integer programming
stochastic programming
generalized assignment problem
facility-location problem
Advisors
Wood, P. Kevin
Date of Issue
2004-09
Date
September 2004
Publisher
Monterey, California. Naval Postgraduate School
Language
Abstract
The first phase of this research demonstrates improvements in the performance of branch-and-price algorithms (B and P) for solving integer programs by (i) stabilizing dual variables during column generation, (ii) performing strong branching, (iii) inserting multiple near-optimal columns from each subproblem, (iv) heuristically improving feasible integer solutions, and by applying several other techniques. Computational testing on generalized-assignment problems shows that solution times decrease over "nave" B and P by as much as 96%; and, some problems that could not be solved by standard branch and bound on the standard model formulation have become easy. In the second phase, this research shows how to solve a class of difficult, stochastic mixed-integer programs using B and P.A new, column-oriented formulation of a stochastic facility-location problem (SFLP), using a scenario representation of uncertainty, provides a vehicle for demonstrating this method's viability. Computational results show that B and P can be orders of magnitude faster than solving the original problem by branch and bound, and this can be true even for single-scenario problems; i.e., for deterministic problems. B and P also solves SFLP exactly when random parameters are modeled through certain continuous probability distributions. In practice, these problems solve more quickly than comparable scenario-based problems.
Type
Description
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
xvi, 81 p. ; 28 cm.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
Copyright is reserved by the copyright owner.
Collections