Maximum probabilistic all-or-nothing paths

Noam Goldberg

doi:10.1016/j.ejor.2019.11.011

Return

Maximum probabilistic all-or-nothing paths

2020-05-01

Noam Goldberg

Michaël Poss *

DOI：10.1016/j.ejor.2019.11.011

Original

Save

View PDF

Abstract

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.

Keywords:

Networks

Dynamic programming

Integer non-linear programming

FPTAS

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.