论文标题
双向主体随机设施位置问题的分支机构切割算法
A branch-and-Benders-cut algorithm for a bi-objective stochastic facility location problem
论文作者
论文摘要
在许多现实世界优化问题中，一个以上的目标扮演着角色，输入参数会受到不确定性。在本文中，在灾难救济和公共设施位置的应用中，我们建模并解决了双目标随机设施的位置问题。所考虑的目标是成本和未发现的需求，而不同人口中心的需求尚不确定，但其概率分布已知。后一个信息用于生成一组场景。为了解决潜在的优化问题，我们应用了一种弯曲者的类型分解方法，该方法被称为随机编程的L形方法，并将其嵌入了最近开发的Bi-Optive Integer优化的分支机构和结合框架中。我们分析和比较不同的切割生成方案，并展示它们如何影响下限设置的计算，以确定最佳性能方法。最后，我们将分支机构切割的方法与基于确定性等效公式的直截了当的分支和结合实现进行了比较。
In many real-world optimization problems, more than one objective plays a role and input parameters are subject to uncertainty. In this paper, motivated by applications in disaster relief and public facility location, we model and solve a bi-objective stochastic facility location problem. The considered objectives are cost and uncovered demand, whereas the demand at the different population centers is uncertain but its probability distribution is known. The latter information is used to produce a set of scenarios. In order to solve the underlying optimization problem, 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 framework for bi-objective integer optimization. We analyze and compare different cut generation schemes and we show how they affect lower bound set computations, so as to identify the best performing approach. Finally, we compare the branch-and-Benders-cut approach to a straight-forward branch-and-bound implementation based on the deterministic equivalent formulation.
