A branch-and-Benders-cut algorithm for bi-objective integer programming: Application to a stochastic facility location problem
Sprache des Vortragstitels:
Recent Advances in Multi-Objective Optimization (RAMOO 2019)
Sprache des Tagungstitel:
Motivated by applications in disaster relief and public facility location under demand uncer- tainty, we develop a branch-and-Benders-cut algorithm for bi-objective two-stage stochastic programming, where the integer variables only appear in the first stage. As test case we use a bi-objective stochastic facility location problem. The considered objectives are cost and uncov- ered demand, whereas the demands at the different population centers are uncertain but their probability distributions are known. The latter information is used to produce a set of scenarios. We apply a Benders? type decomposition approach which is known as the L-shaped method for stochastic programming and we embed it into a recently developed branch-and-bound frame- work for bi-objective integer optimization. We analyze and compare different optimality cut generation strategies and we show how they affect the lower bound set computation scheme. Finally, we compare the branch-and-Benders-cut approach to a straightforward branch-and- bound implementation based on a deterministic equivalent formulation of the original two-stage stochastic program.
Sprache der Kurzfassung:
Hauptvortrag / Eingeladener Vortrag auf einer Tagung