Maximum probabilistic all-or-nothing paths

doi:10.1016/j.ejor.2019.11.011

Maximum probabilistic all-or-nothing paths

2020-05-01

2

OA

AI

DOI：10.1016/j.ejor.2019.11.011

原文链接

查看原文

摘要

En 中文

We consider the problem of a maximum probabilistic all-or-nothing network path. Each arc is associated with a profit and a probability and the objective is to select a path with maximum value for the product of probabilities multiplied by the sum of arc profits. The problem can be motivated by applications including serial-system design or subcontracting of key project activities that may fail. When subcontracting such critical success activities, each must be completed on time, according to the specs, and in a satisfactory manner in order for the entire project to be deemed successful. We develop a dynamic programming (DP) method for this problem in the acyclic graph setting, under an independence assumption. Two different fully-polynomial approximation schemes are developed based on the DP formulations, one of which applies repeated rounding and scaling to the input data, while the other uses only rounding. In experiments we compare the DP approach with mixed-integer nonlinear programming (MINLP) using a branch-and-cut method, on synthetic randomly generated instances as well as realistic ones. (C) 2019 Elsevier B.V. All rights reserved.

Keyword:

Networks

Dynamic programming

Integer non-linear programming

FPTAS

Maximum probabilistic all-or-nothing paths

摘要

AI总结

期刊

机构