Maximum probabilistic all-or-nothing paths

Noam Goldberg and Michael Poss

European Journal of Operational Research, 2020, vol. 283, issue 1, 279-289

Abstract: 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.

Keywords: Networks; Dynamic programming; Integer non-linear programming; FPTAS (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719309221
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:283:y:2020:i:1:p:279-289

DOI: 10.1016/j.ejor.2019.11.011

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().