Publication:
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.date.accessioned2012-08-22T15:30:45Z
dc.date.available2012-08-22T15:30:45Z
dc.date.issued2004-09
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.description.urihttp://archive.org/details/improvingbanchan109459958
dc.format.extentxvi, 81 p. ; 28 cm.en_US
dc.identifier.urihttps://hdl.handle.net/10945/9958
dc.publisherMonterey, California. Naval Postgraduate Schoolen_US
dc.rightsCopyright is reserved by the copyright owner.en_US
dc.subject.authorbranch-and-priceen_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
dspace.entity.typePublication
etd.thesisdegree.disciplineOperations Researchen_US
etd.thesisdegree.grantorNaval Postgraduate School (U.S.)en_US
etd.thesisdegree.levelDoctoralen_US
etd.thesisdegree.namePh. D. in Operations Researchen_US
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
04Sep_Silva_PhD.pdf
Size:
357.95 KB
Format:
Adobe Portable Document Format
Collections