solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看133次
Network Design with Probabilistic Capacities. (arXiv:1705.05916v1 [math.OC])
来源于:arXiv
We consider a network design problem with random arc capacities and give a
formulation with a probabilistic capacity constraint on each cut of the
network. To handle the exponentially-many probabilistic constraints a
separation procedure that solves a nonlinear minimum cut problem is introduced.
For the case with independent arc capacities, we exploit the supermodularity of
the set function defining the constraints and generate cutting planes based on
the supermodular covering knapsack polytope. For the general correlated case,
we give a reformulation of the constraints that allows to uncover and utilize
the submodularity of a related function. The computational results indicate
that exploiting the underlying submodularity and supermodularity arising with
the probabilistic constraints provides significant advantages over the
classical approaches. 查看全文>>