Improving banch-and-price algorithms and applying them to Stochastic programs
Silva, Eduardo Ferreira
Wood, P. Kevin
MetadataShow full item record
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.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Ryoo, Moo Bong (Monterey, California: Naval Postgraduate School, 1990-03);This thesis compares the efficiency of a constraint branch-and-bound method against the conventional variable branch-and-bound method in solving set partitioning problems. Because of the difficulties encountered in writing ...
Smith, Douglas R. (Monterey, California. Naval Postgraduate School, 1979-11); NPS-52-79-004Many important problems in operations research, artificial intelligence, combinatorial algorithms, and other areas seem to require search in order to find an optimal solution. A branch and bound procedure, which imposes a ...
An analysis of the Procurement Administrative Lead Time (PALT) for the procurement process at the Naval Postgraduate School Lodge, Terry C. (Monterey, California: U.S. Naval Postgraduate School, 1986-12);This thesis examines the environment within the Naval Postgraduate School's Small Purchase Branch. The intent of the study is to analyze the procurement process, ascertain the factors which contribute to the overall ...