Анализ задачи поиска кратчайшего пути с неполной информацией и обучением тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Кетков Сергей Сергеевич

• Кетков Сергей Сергеевич
• кандидат наук
• 2023

Оглавление диссертации кандидат наук Кетков Сергей Сергеевич

Contents

Introduction

General idea and optimization models|

Uncertainty in the distribution of arc costs (Model I

Uncertainty in the structure of the network (Model II

Model I: related literature and contributions Related literature

6

Our approach and contributions!

Model II: related literature and contributions

Related literature

Our approach and contributions!

1 Model I: problem formulation and solution approach

24

1.1 Problem formulation

Formulation of the one-stage problem

1

1.1.2 Formulation of the multi-stage problem

1.2 Construction of the ambiguity set from data|

1.3 Solution approach

1.3.1 MIP reformulation of the one-stage problem

1.3.2 MIP reformulation of the multi-stage problem|

2 Model I: computational study

54

2.1 Numerical analysis of the one-stage problem|

2.1.1 Performance measures and benchmark approaches

2.1.2 Construction of test instances

56

2.1.3 Results and discussion

2.2 Numerical analysis of the multi-stage problem|

2.2.1 Performance measures

2.2.2 Construction of test instances

2.2.3 Results and discussion

3 Model II: problem formulation and solution approach

3.1 Problem formulation

3.2 Computational complexity

3.3 Basic analysis of user's policies

3.4 Heuristic algorithm for the strategic user|

4 Model II: computational study

97

98

4.1 Preliminaries

4.2 Results and discussion

Conclusions References

105

A Model I: Supplementary material

A.1 Construction of the moment-based ambiguity set from data A.2 Results for the auxiliary probability constraints

122

Введение диссертации (часть автореферата) на тему «Анализ задачи поиска кратчайшего пути с неполной информацией и обучением»

Introduction

General idea and optimization models

The problem of finding the least cost path between two fixed nodes in a given network seems to be one of the most well-studied combinatorial optimization problems in the literature. For example, the standard deterministic shortest path problem (SPP) can be solved in polynomial time by using standard dynamic programming based algorithms of Dijkstra and Bellman-Ford [1, 2]. Alternatively, the shortest path problem can be vied as a linear programming (LP) problem, where each path between the source and the destination nodes in a given graph is encoded by a path-incidence vector. Traditionally, the decisionmaker aims at minimizing the total cost of a path subject to some path flow constraints [3].

Since the deterministic version of the SPP can be solved rather fast even for large-scale networks, the shortest path problem has been applied to more involved application contexts, where solving the SPP can be viewed as a sub-procedure; see, e.g., [4, 5]. Furthermore, in order to address some practically relevant situations, the SPP has been studied under various additional assumptions including path or resource constraints [6, 7], stochastic travel times [8, 9] and multiple objective criteria [10, 11].

The focus of the current thesis is one- and multi-stage versions of the shortest path problem, where either the arc costs or the structure of the network is subject to uncertainty. In both cases we formulate the problem as a dynamic or repetitive zero-sum game between two decision-makers, namely, a user and an attacker. The user traverses between two fixed nodes in a given network, whereas the attacker controls in some predefined way the arc costs or their probability distribution. One of the decision-makers has incomplete information about either the distribution of arc costs and/or the structure of the network and attempts to learn some additional information by repetitive interactions with the other decision-maker.

Uncertainty in the distribution of arc costs (Model I)

The first problem setting we consider is the shortest path problem, in which the arc costs/arc travel times are subject to uncertainty. This modeling assumption brings together a rather large amount of research and enjoys some justification from the practice of decision-making; see, e.g., [8, 9, 12]. Thus, arc travel times usually depend on uncertain factors such as road capacity variation or traffic conditions. Naturally, these factors affect the structure and quality of routing decisions. For example, it is argued in [13] that travel time uncertainty forces travelers to pick a more reliable path even with a larger expected travel time.

The modeling approach to travel time uncertainty depends on a concrete application but is typically based on the following two major principles. First, in robust optimization the arc costs/travel times are represented via uncertainty sets and a particular loss function is optimized under the worst-case possible realization of the uncertain parameters; see, e.g., [14, 15, 16]. In other words, a robust optimization problem can be usually formulated as a bi-level problem, where the loss function is minimized over a set of feasible decisions and then maximized over a set of uncertain problem parameters.

On the other hand, in stochastic programming the cost vector is assumed to obey some known probability distribution; see, e.g., [17, 18]. In this case the decision-maker may optimize some measure of risk under the specified distribution of uncertain problem parameters, e.g., its expected loss or conditional value-at-risk (CVaR); see, e.g.,

In general, both robust optimization and stochastic programming have a number of essential drawbacks. First, despite the fact that many robust optimization problems can be reformulated as single-level convex problems [15], robust solutions assume no distributional knowledge and, thus, potentially provide overly conservative decisions. Secondly, it can be argued that fitting a single candidate distribution to the available information potentially leads to biased optimization results with poor out-of-sample performance [20]. Finally, calculation of an expected value of the objective function may become computationally intractable even for problems of a relatively small size [21 .

In view of the discussion above, it is often the case that the decision-maker has some partial information about the distribution of arc costs/travel times. For example, the distribution of uncertain problem parameters can only be observable through a finite training data set; see, e.g., [22, 23]. The latter problem can be addressed with a distributionally robust optimization (DRO) approach, where the uncertainty is described by an ambiguity set or a family of probability distributions that are deemed possible under existing information; see, e.g., the related studies in [20, 23, 24, 25]. Given some family of admissible distributions, the decision-maker is supposed to optimize a measure of risk under the worst-case possible distribution of uncertain parameters. Put differently, the DRO approach attempts to balance between the lack of distributional information (as in robust optimization) and the complete knowledge of the underlying probability distribution (as in stochastic programming).

Most recent solution approaches to single-stage DRO problems rely on the duality results for moments problems due to Isii [26] and Shapiro [27]. That is, under some assumptions on the geometry of ambiguity sets and functional properties of the objective function, DRO problems can be recast as single-level problems; see, e.g., [20, 22, 23].

It has also been shown that DRO may address dynamic or, equivalently, multi-stage optimization problems, where the decisions adapt to the uncertain outcomes as they unfold in stages; see, e.g., [24, 25, 28, 29]. In general, multistage DRO problems are computationally intractable since recourse decisions (or, equivalently, decisions affected by uncertainty) can be modeled as arbitrary functions of uncertain problem parameters [27, 30]. For this reason, most related studies consider approximations of the outlined problems, in which the recourse decisions are restricted to be some simple functions of the uncertain parameters observed up to the current stage [24, 25].

Summarizing the discussion above, in this thesis we consider both one- and multi-stage versions of the shortest path problem, where the cost vector is subject to distributional uncertainty. In our model the user seeks to minimize its expected loss by selecting a path between two fixed nodes in a given net-

work, whereas the attacker maximizes the user's objective function by choosing a probability distribution of the cost vector. Similar to the study of Wiesemann et al. [20], we assume that the family of admissible distributions in our setting is described by some first-order moment constraints with respect to subsets of arcs and individual probability constraints for particular arcs.

In the one-stage problem the user picks a path here-and-now, before a realization of the probability distribution selected by the attacker. On the other hand, in the multi-stage version of the shortest path problem we attempt to address a dynamic revelation of distributional information to the user by introducing some auxiliary distributional constraints the can be verified at particular nodes of the user's path. Our results for Model I can be found in [31] and [32].

Uncertainty in the structure of the network (Model II)

In this model we assume that the cost vector is deterministic, but the attacker has incomplete knowledge about the existence and precise costs of particular arcs in the network. As for Model I, Model II can be considered both in one-and multi-stage problem settings.

For a single decision epoch the problem can be viewed as a standard shortest path interdiction problem,; see, e.g., [4]. In this problem the attacker seeks a set of arcs, which removal subject to some budgetary constraint maximizes the cost of the shortest path between two specified nodes in the network. At the same time, the user is assumed to move along the shortest path in the currently interdicted network. If the attacker is allowed to block at most k arcs, then the outlined problem is often referred to as the k-most vital arcs problem [33 .

By observing the user's path, the attacker may potentially update its information about the structure of the network and the costs of the arcs traversed by the user. However, in the aforementioned one-stage model the information collected by the attacker cannot be used to refine the attacker's decision. In order to resolve this problem, we consider a repeated interaction between the user and the attacker, where the user attempts to minimize its cumulative loss over multiple decision epochs and the attacker sequentially blocks a set of k-most

vital arcs in the network currently known to it. In other words, we assume that the attacker follows a greedy policy in each decision epoch and both decision-makers are able to adjust their decisions through multiple decision epochs.

Despite the fact that rather effective exact solution approaches for the shortest path interdiction problem exist in the literature; see, e.g., [4, 34], the problem is known to be NP-hard. We demonstrate that the two-stage problem in our setting is NP-hard, even if the attacker's problem in decision epoch is polyno-mially solvable and the attacker has no initial information about the network's structure and costs. In this regard, the focus of this thesis is on several heuristic algorithms for the multi-stage problem and their numerical comparison. Our results for Model II can be found in

Model I: related literature and contributions

Заключение диссертации по теме «Другие cпециальности», Кетков Сергей Сергеевич

Conclusions

In this thesis we consider the shortest path problem with different forms of uncertainty. The problem is posed as a zero-sum game between two decisionmakers, namely, a user and an attacker. The user traverses between two fixed

nodes in the network, while the attacker controls either the arc costs in the given network or their probability distribution. The goal of the user is to minimize its cumulative (expected) loss over one or multiple decision epochs, while the attacker aims at maximizing the user's objective function (either in one or multiple decision epochs).

In the first model, Model I, the structure of the underlying network is assumed to be deterministic, while the arc costs/are travel times are subject to uncertainty. We assume that the distribution of the cost vector is not available to the user but can only be observed through a finite training data set. Based on the available data, we construct an ambiguity set or a family of probability distributions, which contains the unknown distribution with any required confidence level.

The distributional family in our setting is formed by linear expectation constraints with respect to some subsets of arcs and individual probability constraints with respect to particular arcs. It can also be argued that our distributional constraints can be constructed from incomplete or partially observable data. For instance, the user may exploit observations of a total cost with respect to some subsets of arcs or interval-censored observations with respect to particular arcs. In addition, the proposed family of probability distributions can be formed by leveraging standard measure concentration inequalities.

We consider one- and multi-stage formulations of the distributionally robust shortest path problem (DRSPP), where the user attempts to minimize its expected loss under the worst-case distribution of the uncertain problem parameters. In the one-stage formulation the user picks a path here-and-now before the realization of uncertainty. For this problem we propose equivalent robust and linear mixed-integer programming (MIP) reformulations. In particular, the problem without the first-order moment constraints is proved to be polynomially solvable and a closed form of the worst-case distribution is identified. Also, we demonstrate numerically that our approach is competitive against some basic robust and distributionally robust optimization techniques.

On the other hand, in the multi-stage formulation of DRSPP we assume that

both the user and the attacker are able to adjust their decisions at each node of the user's path. Specifically, while traversing through the network, the user may verify some auxiliary distributional constraints associated with the arcs emanated from the current user's position. The outlined constraint verification procedure is modeled via a list of auxiliary constraints. For each constraint in the list the attacker decides whether this constraint is satisfied or not and reveals its response to the user at the respective node of the user's path.

With respect to the multi-stage problem, we design two classes of non-anticipativity constraints (for acyclic and general graphs, repsectively) enforcing that the user's decision at some particular node cannot depend on future attacker's responses. Furthermore, by using some properties of the related one-stage formulation and linear programming duality the multi-stage DRSPP is reformulated as a one potentially large linear MIP problem. From the application perspective, we illustrate that the auxiliary distributional constraints can be constructed and verified by using some information from Bluetooth sensors. Finally, we conduct a numerical study where the one- and multi-stage problem formulations are compared on several classes of synthetic network instances. It turns out that using adaptive decisions is practically relevant only for networks of a relatively small size, in which high quality adaptive decisions can be obtained within a reasonable time.

Concerning the future research directions for Model I, it would be interesting to explore some other types of objective criteria both in the one- and multi-stage formulations; see, e.g., [28]. Furthermore, it seems to be rather interesting to develop a methodology that handles uncertainty not only in the distribution of uncertain problem parameters but also in the training data set obtained from the unknown distribution. Admittedly, the outlined problem setting may lead to more advanced optimization models that cannot be solved at hand using off-the-shelf MIP solvers.

In the second model, Model II, we consider uncertainty in the structure of the network assuming the arc costs/travel times are deterministic. Specifically, we introduce a multi-stage network game between a user and an attacker, where

the attacker has incomplete initial information about the network structure and costs. In particular, the attacker is assumed to act in a greedy manner by blocking at most k arcs known to it for the duration of one decision epoch. By observing the paths selected by the user in each decision epoch, the attacker learns about the existence and precise costs of the associated arcs and, thus, can adjust its actions in the subsequent decision epochs.

In contrast to the related interdiction models in [5, 89], we analyze the user's perspective and assume that the user aims at minimizing its cumulative loss over some finite time horizon. Specifically, we first show that the user's problem is computationally hard even for two decision epochs assuming that the attacker's problem in each decision epoch is polynomially solvable. Then we derive basic constructive properties of optimal user's policies for two decision epochs when the attacker has no initial information about the network structure. Furthermore, based on these observations, we design a heuristic algorithm for a strategic user in a general setting with an arbitrary time horizon and any initial information available to the attacker.

In other words, in contrast to Model I, where we attempt to solve the multistage problem exactly, in Model II we focus on heuristic algorithms for the associated multi-stage problem. Our computational experiments demonstrate that the proposed heuristic algorithm typically outperforms the greedy user's policy, i.e., the policy where the user selects the shortest available path in each decision epoch. Meanwhile, the outlined computational results are consistent with respect to several classes of synthetic network instances, various sets of initial information available to the attacker as well as different types of the feedback received by the attacker from the user.

The insights (both from theoretical and practical perspectives) from our results can be summarized as follows. First, our heuristic algorithm is based on a two-step look-ahead idea. Thus, whenever the attacker is greedy, the user can significantly improve its performance over multiple decision epochs in a rather simple manner, i.e., by considering only two consecutive decision epochs instead of the one for the greedy policy. Furthermore, for the aforementioned

two consecutive epochs it may be sufficient for the user to consider two simple decision strategies. Either the user should follow a myopic shortest-path based policy or seek only two alternative paths that have some arcs in common with the shortest path in the network. Also, for the latter case the pair of user's paths often needs to be arc-disjoint, which is also rather intuitive from the real-life perspective (e.g., in "infiltration" or "smuggling" scenarios).

Another interesting observation (with possible practical implications) from our computational study is that strategic user's decisions are more beneficial when the attacker has more resources. In other words, the more arcs can be blocked by the attacker in each decision epoch, the faster it forces the greedy user to reveal new network information (which subsequently can be exploited to improve the attacker's decisions). From the practical perspective, the increase in the attacker's resources may force the user to switch to strategic decisions. On the other hand, for instances where the attacker's resources are limited greedy user's decisions can be close to optimal, which implies that the user may simplify its decisions over multiple epochs.

With respect to future research directions for Model II, it would be interesting to explore non-deterministic policies from the user's perspective; see, e.g., [93, 113]. Moreover, in our study we assume that the user observes the blocking decision before choosing a path and knows the attacker's budget. Therefore, one may explore the user's problem with these assumptions relaxed.

Список литературы диссертационного исследования кандидат наук Кетков Сергей Сергеевич, 2023 год

References

[1] E. W. Dijkstra, "A note on two problems in connexion with graphs," Numerische mathematik, vol. 1, no. 1, pp. 269-271, 1959.

[2] R. Bellman, "On a routing problem," Quarterly of applied mathematics, vol. 16, no. 1, pp. 87-90, 1958.

[3] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network flows. Cambridge, Mass.: Alfred P. Sloan School of Management, Massachusetts, 1988.

[4] E. Israeli and R. K. Wood, "Shortest-path network interdiction," Networks, vol. 40, no. 2, pp. 97-111, 2002.

[5] J. S. Borrero, O. A. Prokopyev, and D. Saure, "Sequential shortest path interdiction with incomplete information," Decision Analysis, vol. 13, no. 1, pp. 68-98, 2015.

[6] S. Irnich and G. Desaulniers, "Shortest path problems with resource constraints," in Column generation, pp. 33-65, Springer, 2005.

[7] D. Villeneuve and G. Desaulniers, "The shortest path problem with forbidden paths," European Journal of Operational Research, vol. 165, no. 1, pp. 97-107, 2005.

[8] B. Y. Chen, W. H. Lam, A. Sumalee, Q. Li, H. Shao, and Z. Fang, "Finding reliable shortest paths in road networks under uncertainty," Networks and Spatial Economics, vol. 13, no. 2, pp. 123-148, 2013.

[9] M. Shahabi, A. Unnikrishnan*, and S. D. Boyles, "Robust optimization strategy for the shortest path problem under uncertain link travel cost distribution," Computer-Aided Civil and Infrastructure Engineering, vol. 30, no. 6, pp. 433-448, 2015.

[10] E. Q. V. Martins, "On a multicriteria shortest path problem," European Journal of Operational Research, vol. 16, no. 2, pp. 236-245, 1984.

[11] F. Guerriero and R. Musmanno, "Label correcting methods to solve multicriteria shortest path problems," Journal of Optimization Theory and Applications, vol. 111, no. 3, pp. 589-613, 2001.

[12] D. Bertsimas and M. Sim, "Robust discrete optimization and network flows," Mathematical Programming, vol. 98, no. 1-3, pp. 49-71, 2003.

[13] D. Brownstone, A. Ghosh, T. F. Golob, C. Kazimi, and D. Van Amelsfort, "Drivers' willingness-to-pay to reduce travel time: evidence from the san

diego i-15 congestion pricing project," Transportation Research Part A: Policy and Practice, vol. 37, no. 4, pp. 373-387, 2003.

[14] A. Ben-Tal and A. Nemirovski, "Robust optimization-methodology and applications," Mathematical Programming, vol. 92, no. 3, pp. 453-480, 2002.

[15] A. Ben-Tal, L. El Ghaoui, and A. Nemirovski, Robust optimization, vol. 28. Princeton University Press, 2009.

[16] D. Bertsimas, D. B. Brown, and C. Caramanis, "Theory and applications of robust optimization," SIAM review, vol. 53, no. 3, pp. 464-501, 2011.

[17] A. Ruszczynski and A. Shapiro, "Stochastic programming models," Handbooks in Operations Research and Management Science, vol. 10, pp. 1-64, 2003.

[18] A. Shapiro, D. Dentcheva, and A. Ruszczynski, Lectures on stochastic programming: modeling and theory. SIAM, 2009.

[19] R. T. Rockafellar, S. Uryasev, et al., "Optimization of conditional value-at-risk," Journal of Risk, vol. 2, pp. 21-42, 2000.

[20] W. Wiesemann, D. Kuhn, and M. Sim, "Distributionally robust convex optimization," Operations Research, vol. 62, no. 6, pp. 1358-1376, 2014.

[21] A. Shapiro and A. Nemirovski, "On complexity of stochastic programming problems," in Continuous optimization, pp. 111-146, Springer, 2005.

[22] P. M. Esfahani and D. Kuhn, "Data-driven distributionally robust optimization using the wasserstein metric: Performance guarantees and tractable reformulations," Mathematical Programming, vol. 171, no. 1-2, pp. 115-166, 2018.

[23] E. Delage and Y. Ye, "Distributionally robust optimization under moment uncertainty with application to data-driven problems," Operations Research, vol. 58, no. 3, pp. 595-612, 2010.

[24] J. Goh and M. Sim, "Distributionally robust optimization and its tractable approximations," Operations Research, vol. 58, no. 4-part-1, pp. 902-917, 2010.

[25] D. Bertsimas, M. Sim, and M. Zhang, "Adaptive distributionally robust optimization," Management Science, vol. 65, no. 2, pp. 604-618, 2018.

[26] K. Isii, "On sharpness of tchebycheff-type inequalities," Annals of the Institute of Statistical Mathematics, vol. 14, no. 1, pp. 185-197, 1962.

[27] A. Shapiro, "On duality theory of conic linear problems," in Semi-infinite Programming, pp. 135-165, Springer, 2001.

[28] G. A. Hanasusanto, D. Kuhn, and W. Wiesemann, "K-adaptability in two-stage distributionally robust binary programming," Operations Research Letters, vol. 44, no. 1, pp. 6-11, 2016.

[29] R. Jiang and Y. Guan, "Risk-averse two-stage stochastic program with distributional ambiguity," Operations Research, vol. 66, no. 5, pp. 13901405, 2018.

[30] M. Dyer and L. Stougie, "Computational complexity of stochastic programming problems," Mathematical Programming, vol. 106, no. 3, pp. 423-432, 2006.

[31] S. S. Ketkov, O. A. Prokopyev, and E. P. Burashnikov, "An approach to the distributionally robust shortest path problem," Computers & Operations Research, vol. 130, p. 105212, 2021.

[32] S. S. Ketkov, "On the multi-stage shortest path problem under distributional uncertainty," arXiv preprint arXiv:2205.09200, 2022.

[33] H. Corley and Y. S. David, "Most vital links and nodes in weighted networks," Operations Research Letters, vol. 1, no. 4, pp. 157-160, 1982.

[34] K. M. Sullivan and J. C. Smith, "Exact algorithms for solving a Euclidean maximum flow network interdiction problem," Networks, vol. 64, no. 2, pp. 109-124, 2014.

[35] S. S. Ketkov and O. A. Prokopyev, "On greedy and strategic evaders in sequential interdiction settings with incomplete information," Omega, vol. 92, p. 102161, 2020.

[36] G. Yu and J. Yang, "On the robust shortest path problem," Computers & Operations Research, vol. 25, no. 6, pp. 457-468, 1998.

[37] V. Gabrel and C. Murat, "Robust shortest path problems," hal-00179975, 2007.

[38] M. Minoux, "Robust network optimization under polyhedral demand uncertainty is np-hard," Discrete Applied Mathematics, vol. 158, no. 5, pp. 597-603, 2010.

[39] T. Dokka and M. Goerigk, "An experimental comparison of uncertainty sets for robust shortest path problems," arXiv preprint arXiv:1704.08470, 2017.

[40] P. Zielinski, "The computational complexity of the relative robust shortest path problem with interval data," European Journal of Operational Research, vol. 158, no. 3, pp. 570-576, 2004.

[41] R. Montemanni and L. M. Gambardella, "An exact algorithm for the robust shortest path problem with interval data," Computers & Operations Research, vol. 31, no. 10, pp. 1667-1680, 2004.

[42] V. Gabrel, C. Murat, and L. Wu, "New models for the robust shortest path problem: complexity, resolution and generalization," Annals of Operations Research, vol. 207, no. 1, pp. 97-120, 2013.

[43] M. Minoux, "On robust maximum flow with polyhedral uncertainty sets," Optimization Letters, vol. 3, no. 3, pp. 367-376, 2009.

[44] C. Buchheim and J. Kurtz, "Min-max-min robust combinatorial optimization," Mathematical Programming, vol. 163, no. 1-2, pp. 1-23, 2017.

[45] D. Bertsimas and I. Dunning, "Multistage robust mixed-integer optimization with adaptive partitions," Operations Research, vol. 64, no. 4, pp. 980-998, 2016.

[46] D. Bertsimas and A. Georghiou, "Design of near optimal decision rules in multistage adaptive mixed-integer optimization," Operations Research, vol. 63, no. 3, pp. 610-627, 2015.

[47] K. Postek and D. d. Hertog, "Multistage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set," INFORMS Journal on Computing, vol. 28, no. 3, pp. 553-574, 2016.

[48] W. Romeijnders and K. Postek, "Piecewise constant decision rules via branch-and-bound based scenario detection for integer adjustable robust optimization," INFORMS Journal on Computing, vol. 33, no. 1, pp. 390400, 2021.

[49] J. A. Sefair and J. C. Smith, "Dynamic shortest-path interdiction," Networks, vol. 68, no. 4, pp. 315-330, 2016.

[50] R. W. Hall, "Travel outcome and performance: the effect of uncertainty on accessibility," Transportation Research Part B: Methodological, vol. 17, no. 4, pp. 275-290, 1983.

[51] Y. M. Nie and X. Wu, "Shortest path problem considering on-time arrival probability," Transportation Research Part B: Methodological, vol. 43, no. 6, pp. 597-613, 2009.

[52] A. Chen and Z. Zhou, "The a-reliable mean-excess traffic equilibrium model with stochastic travel times," Transportation Research Part B: Methodological, vol. 44, no. 4, pp. 493-513, 2010.

[53] Y. Pan, L. Sun, and M. Ge, "Finding reliable shortest path in stochastic time-dependent network," Procedia-Social and Behavioral Sciences, vol. 96, pp. 451-460, 2013.

[54] B. Verweij, S. Ahmed, A. J. Kleywegt, G. Nemhauser, and A. Shapiro, "The sample average approximation method applied to stochastic routing problems: a computational study," Computational Optimization and Applications, vol. 24, no. 2, pp. 289-333, 2003.

[55] G. Bergsma and R. Spliet, "The sample average approximation method applied to routing problems with random travel times," Bachelor Thesis Quantitative Logistics & Operations Research, 2018.

[56] S. Samaranayake, S. Blandin, and A. Bayen, "A tractable class of algorithms for reliable routing in stochastic networks," Transportation Research Part C: Emerging Technologies, vol. 20, no. 1, pp. 199-217, 2012.

[57] E. Nikolova, J. A. Kelner, M. Brand, and M. Mitzenmacher, "Stochastic shortest paths via quasi-convex maximization," in European Symposium on Algorithms, pp. 552-563, Springer, 2006.

[58] I. Murthy and S. Sarkar, "Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function," European Journal of Operational Research, vol. 103, no. 1, pp. 209-229, 1997.

[59] I. Murthy and S. Sarkar, "Stochastic shortest path problems with piecewise-linear concave utility functions," Management Science, vol. 44, no. 11-part-2, pp. S125-S136, 1998.

[60] C. Gavriel, G. Hanasusanto, and D. Kuhn, "Risk-averse shortest path

problems," in 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), pp. 2533-2538, IEEE, 2012.

[61] Y. Zhang, S. Song, Z.-J. M. Shen, and C. Wu, "Robust shortest path problem with distributional uncertainty," IEEE Transactions on Intelligent Transportation Systems, vol. 19, no. 4, pp. 1080-1090, 2017.

[62] J. Cheng, J. Leung, and A. Lisser, "New reformulations of distribution-ally robust shortest path problem," Computers & Operations Research, vol. 74, pp. 196-204, 2016.

[63] Z. Wang, K. You, S. Song, and Y. Zhang, "Wasserstein distributionally robust shortest path problem," European Journal of Operational Research, vol. 284, no. 1, pp. 31-43, 2020.

[64] X. Yu and S. Shen, "Multistage distributionally robust mixed-integer programming with decision-dependent moment-based ambiguity sets," Mathematical Programming, pp. 1-40, 2020.

[65] J. Zou, S. Ahmed, and X. A. Sun, "Stochastic dual dynamic integer programming," Mathematical Programming, vol. 175, no. 1-2, pp. 461-502, 2019.

[66] G. Bayraksan and D. K. Love, "Data-driven stochastic programming using phi-divergences," in The Operations Research Revolution, pp. 1-19, INFORMS, 2015.

[67] V. Kreinovich, G. Xiang, S. A. Starks, L. Longpre, M. Ceberio, R. Araiza, J. Beck, R. Kandathi, A. Nayak, R. Torres, et al., "Towards combining probabilistic and interval uncertainty in engineering calculations: algorithms for computing statistics under interval uncertainty, and their computational complexity," Reliable Computing, vol. 12, no. 6, pp. 471-501, 2006.

[68] S. Bubeck, N. Cesa-Bianchi, and S. M. Kakade, "Towards minimax policies for online linear optimization with bandit feedback," in Conference on Learning Theory, pp. 41-1, 2012.

[69] E. D. Miller-Hooks and H. S. Mahmassani, "Least expected time paths in stochastic, time-varying transportation networks," Transportation Science, vol. 34, no. 2, pp. 198-215, 2000.

[70] L. Fu and L. R. Rilett, "Expected shortest paths in dynamic and stochastic traffic networks," Transportation Research Part B: Methodological, vol. 32, no. 7, pp. 499-516, 1998.

[71] A. Haghani, M. Hamedi, K. F. Sadabadi, S. Young, and P. Tarnoff, "Data collection of freeway travel time ground truth with bluetooth sensors," Transportation Research Record, vol. 2160, no. 1, pp. 60-68, 2010.

[72] M. Asudegi and A. Haghani, "Optimal number and location of node-based sensors for collection of travel time data in networks," Transportation research record, vol. 2338, no. 1, pp. 35-43, 2013.

[73] T. Vo, An investigation of bluetooth technology for measuring travel times on arterial roads: a case study on spring street. PhD thesis, Georgia Institute of Technology, 2011.

[74] N. B. Dimitrov and D. P. Morton, "Interdiction models and applications," in Handbook of operations research for homeland security, pp. 73-103, Springer, 2013.

[75] J. C. Smith and C. Lim, "Algorithms for network interdiction and fortification games," in Pareto optimality, game theory and equilibria (A. Chinchuluun, P. M. Pardalos, A. Migdalas, and L. Pitsoulis, eds.), pp. 609-644, Springer, 2008.

[76] J. C. Smith, M. Prince, and J. Geunes, "Modern network interdiction problems and algorithms," in Handbook of combinatorial optimization

(P. M. Pardalos, D.-Z. Du, and R. L. Graham, eds.), pp. 1949-1987, Springer, 2013.

[77] J. C. Smith and Y. Song, "A survey of network interdiction models and algorithms," European Journal of Operational Research, 2019. to appear.

[78] R. K. Wood, "Bilevel network interdiction models: Formulations and solutions," in Wiley Encyclopedia of Operations Research and Management Science (J. J. Cochran, L. A. C. Jr., P. Keskinocak, J. P. Kharoufeh, and J. C. Smith, eds.), pp. 1-11, John Wiley & Sons, Inc, 2010.

[79] R. J. Allain, "An evolving asymmetric game for modeling interdictor-smuggler problems," tech. rep., NAVAL POSTGRADUATE SCHOOL MONTEREY CA MONTEREY United States, 2016.

[80] D. P. Morton, F. Pan, and K. J. Saeger, "Models for nuclear smuggling interdiction," IIE Transactions, vol. 39, no. 1, pp. 3-14, 2007.

[81] F. Enayaty-Ahangar, C. E. Rainwater, and T. C. Sharkey, "A logic-based decomposition approach for multi-period network interdiction models," Omega, 2018. to appear.

[82] A. Malaviya, C. Rainwater, and T. Sharkey, "Multi-period network interdiction problems with applications to city-level drug enforcement," IIE Transactions, vol. 44, no. 5, pp. 368-380, 2012.

[83] G. G. Brown, W. M. Carlyle, J. Salmerón, and R. K. Wood, "Defending critical infrastructure," Interfaces, vol. 36, no. 6, pp. 530-544, 2006.

[84] G. G. Brown, W. M. Carlyle, R. C. Harney, E. M. Skroch, and R. K. Wood, "Interdicting a nuclear-weapons project," Operations Research, vol. 57, no. 4, pp. 866-877, 2009.

[85] F. Pan and D. P. Morton, "Minimizing a stochastic maximum-reliability path," Networks: An International Journal, vol. 52, no. 3, pp. 111-119, 2008.

[86] U. Janjarassuk and J. Linderoth, "Reformulation and sampling to solve a stochastic network interdiction problem," Networks, vol. 52, no. 3, pp. 120-132, 2008.

[87] M. V. Nehme, Two-person games for stochastic network interdiction: models, methods, and complexities. The University of Texas at Austin, 2009.

[88] H. Held and D. L. Woodruff, "Heuristics for multi-stage interdiction of stochastic networks," Journal of Heuristics, vol. 11, no. 5-6, pp. 483-500, 2005.

[89] J. S. Borrero, O. A. Prokopyev, and D. Saure, "Sequential interdiction with incomplete information and learning," Operations Research, vol. 67, no. 1, pp. 72-89, 2019.

[90] J. Zheng and D. A. Castanon, "Dynamic network interdiction games with imperfect information and deception," in 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), pp. 7758-7763, IEEE, 2012.

[91] A. Sanjab, W. Saad, and T. Basar, "Prospect theory for enhanced cyber-physical security of drone delivery systems: A network interdiction game," in 2017 IEEE International Conference on Communications (ICC), pp. 16, IEEE, 2017.

[92] A. Sanjab, W. Saad, and T. Basar, "A game of drones: Cyber-physical security of time-critical uav applications with cumulative prospect theory perceptions and valuations," arXiv preprint arXiv:1902.03506, 2019.

[93] A. Gutfraind, A. Hagberg, and F. Pan, "Optimal interdiction of unre-active markovian evaders," in International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 102-116, Springer, 2009.

[94] H. Xu and S. Mannor, "Distributionally robust markov decision processes," in Advances in Neural Information Processing Systems, pp. 25052513, 2010.

[95] L. Taccari, "Integer programming formulations for the elementary shortest path problem," European Journal of Operational Research, vol. 252, no. 1, pp. 122-130, 2016.

[96] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms. MIT press, 2009.

[97] C. E. Miller, A. W. Tucker, and R. A. Zemlin, "Integer programming formulation of traveling salesman problems," Journal of the ACM (JACM), vol. 7, no. 4, pp. 326-329, 1960.

[98] W. Hoeffding, "Probability inequalities for sums of bounded random variables," in The collected works of Wassily Hoeffding, pp. 409-426, Springer, 1994.

[99] G.-L. Chang, S. Y. Park, and J. Paracha, "Intelligent transportation system field demonstration: integration of variable speed limit control and travel time estimation for a recurrently congested highway," Transportation Research Record, vol. 2243, no. 1, pp. 55-66, 2011.

[100] M. De Berg, M. Van Kreveld, M. Overmars, and O. Schwarzkopf, "Computational geometry," in Computational geometry, pp. 1-17, Springer, 1997.

[101] D. Bertsimas, K. Natarajan, and C.-P. Teo, "Persistence in discrete optimization under data uncertainty," Mathematical Programming, vol. 108, no. 2-3, pp. 251-274, 2006.

[102] G. L. Nemhauser and L. A. Wolsey, Integer Programming and Combinatorial Optimization, vol. 191. Springer, 1988.

[103] D. Bertsimas, K. Natarajan, and C.-P. Teo, "Probabilistic combinatorial optimization: Moments, semidefinite programming, and asymptotic bounds," SIAM Journal on Optimization, vol. 15, no. 1, pp. 185-209, 2004.

[104] A. K. Gupta and S. Nadarajah, Handbook of beta distribution and its applications. CRC press, 2004.

[105] J. R. Birge and F. Louveaux, Introduction to stochastic programming. Springer Science & Business Media, 2011.

[106] A. Sinha, F. Fang, B. An, C. Kiekintveld, and M. Tambe, "Stackelberg security games: Looking beyond a decade of success.," in IJCAI, pp. 54945501, 2018.

[107] B. Colson, P. Marcotte, and G. Savard, "An overview of bilevel optimization," Annals of Operations Research, vol. 153, no. 1, pp. 235-256, 2007.

[108] R. K. Ahuja, K. Mehlhorn, J. Orlin, and R. E. Tarjan, "Faster algorithms for the shortest path problem," Journal of the ACM (JACM), vol. 37, no. 2, pp. 213-223, 1990.

[109] M. R. Garey and D. S. Johnson, Computers and intractability, vol. 29. wh freeman New York, 2002.

[110] C.-L. Li, S. Thomas McCormick, and D. Simchi-Levi, "Finding disjoint paths with different path-costs: Complexity and algorithms," Networks, vol. 22, no. 7, pp. 653-667, 1992.

[111] P. Erdos and A. Renyi, "On random graphs," Publicationes Mathematicae Debrecen, vol. 6, pp. 290-297, 1959.

[112] A.-L. Barabasi and R. Albert, "Emergence of scaling in random networks," Science, vol. 286, no. 5439, pp. 509-512, 1999.

[113] E. Delage, D. Kuhn, and W. Wiesemann, ""dice"-sion-making under uncertainty: When can a random decision reduce risk?," Management Science,, vol. 65, no. 7, pp. 3282-3301, 2019.