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

dc.contributor.advisorWood, P. Kevin
dc.contributor.authorSilva, Eduardo Ferreira
dc.contributor.departmentOperations Research (OR)
dc.dateSeptember 2004
dc.description.abstractThe 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.en_US
dc.description.distributionstatementApproved for public release; distribution is unlimited.
dc.description.serviceLieutenant Commander, Brazilian Navyen_US
dc.format.extentxvi, 81 p. ; 28 cm.en_US
dc.publisherMonterey, California. Naval Postgraduate Schoolen_US
dc.rightsCopyright is reserved by the copyright owner.en_US
dc.subject.authorinteger programmingen_US
dc.subject.authorstochastic programmingen_US
dc.subject.authorgeneralized assignment problemen_US
dc.subject.authorfacility-location problemen_US
dc.subject.lcshStochastic programmingen_US
dc.titleImproving banch-and-price algorithms and applying them to Stochastic programsen_US
etd.thesisdegree.disciplineOperations Researchen_US
etd.thesisdegree.grantorNaval Postgraduate School (U.S.)en_US
etd.thesisdegree.namePh. D. in Operations Researchen_US
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
357.95 KB
Adobe Portable Document Format