Home  << 1 >> 
Barrera, J., HomemDeMello, T., Moreno, E., Pagnoncelli, B. K., & Canessa, G. (2016). Chanceconstrained problems and rare events: an importance sampling approach. Math. Program., 157(1), 153–189.
Abstract: We study chanceconstrained problems in which the constraints involve the probability of a rare event. We discuss the relevance of such problems and show that the existing samplingbased algorithms cannot be applied directly in this case, since they require an impractical number of samples to yield reasonable solutions. We argue that importance sampling (IS) techniques, combined with a Sample Average Approximation (SAA) approach, can be effectively used in such situations, provided that variance can be reduced uniformly with respect to the decision variables. We give sufficient conditions to obtain such uniform variance reduction, and prove asymptotic convergence of the combined SAAIS approach. As it often happens with IS techniques, the practical performance of the proposed approach relies on exploiting the structure of the problem under study; in our case, we work with a telecommunications problem with Bernoulli input distributions, and show how variance can be reduced uniformly over a suitable approximation of the feasibility set by choosing proper parameters for the IS distributions. Although some of the results are specific to this problem, we are able to draw general insights that can be useful for other classes of problems. We present numerical results to illustrate our findings.

Canessa, G., Gallego, J. A., Ntaimo, L., & Pagnoncelli, B. K. (2019). An algorithm for binary linear chanceconstrained problems using IIS. Comput. Optim. Appl., 72(3), 589–608.
Abstract: We propose an algorithm based on infeasible irreducible subsystems to solve binary linear chanceconstrained problems with random technology matrix. By leveraging on the problem structure we are able to generate good quality upper bounds to the optimal value early in the algorithm, and the discrete domain is used to guide us efficiently in the search of solutions. We apply our methodology to individual and joint binary linear chanceconstrained problems, demonstrating the ability of our approach to solve those problems. Extensive numerical experiments show that, in some cases, the number of nodes explored by our algorithm is drastically reduced when compared to a commercial solver.

Canessa, G., Moreno, E., & Pagnoncelli, B. K. (2021). The riskaverse ultimate pit problem. Optim. Eng., 22, 2655–2678.
Abstract: In this work, we consider a riskaverse ultimate pit problem where the grade of the mineral is uncertain. We derive conditions under which we can generate a set of nested pits by varying the risk level instead of using revenue factors. We propose two properties that we believe are desirable for the problem: risk nestedness, which means the pits generated for different risk aversion levels should be contained in one another, and additive consistency, which states that preferences in terms of order of extraction should not change if independent sectors of the mine are added as precedences. We show that only an entropic risk measure satisfies these properties and propose a twostage stochastic programming formulation of the problem, including an efficient approximation scheme to solve it. We illustrate our approach in a small selfconstructed example, and apply our approximation scheme to a realworld section of the Andina mine, in Chile.
Keywords: Ultimate pit; Mining; Riskaverse optimization; Integer programming

Kosowski, A., Li, B., Nisse, N., & Suchan, K. (2015). kChordal Graphs: From Cops and Robber to Compact Routing via Treewidth. Algorithmica, 72(3), 758–777.
Abstract: Cops and robber games, introduced by Winkler and Nowakowski (in Discrete Math. 43(23), 235239, 1983) and independently defined by Quilliot (in J. Comb. Theory, Ser. B 38(1), 8992, 1985), concern a team of cops that must capture a robber moving in a graph. We consider the class of kchordal graphs, i.e., graphs with no induced (chordless) cycle of length greater than k, ka parts per thousand yen3. We prove that k1 cops are always sufficient to capture a robber in kchordal graphs. This leads us to our main result, a new structural decomposition for a graph class including kchordal graphs. We present a polynomialtime algorithm that, given a graph G and ka parts per thousand yen3, either returns an induced cycle larger than k in G, or computes a treedecomposition of G, each bag of which contains a dominating path with at most k1 vertices. This allows us to prove that any kchordal graph with maximum degree Delta has treewidth at most (k1)(Delta1)+2, improving the O(Delta(Delta1) (k3)) bound of Bodlaender and Thilikos (Discrete Appl. Math. 79(13), 4561, 1997. Moreover, any graph admitting such a treedecomposition has small hyperbolicity). As an application, for any nvertex graph admitting such a treedecomposition, we propose a compact routing scheme using routing tables, addresses and headers of size O(klog Delta+logn) bits and achieving an additive stretch of O(klog Delta). As far as we know, this is the first routing scheme with O(klog Delta+logn)routing tables and small additive stretch for kchordal graphs.
Keywords: Treewidth; Chordality; Compact routing; Cops and robber games

Li, B., Moataz, F. Z., Nisse, N., & Suchan, K. (2018). Minimum size treedecompositions. Discret Appl. Math., 245, 109–127.
Abstract: We study in this paper the problem of computing a treedecomposition of a graph with width at most k and minimum number of bags. More precisely, we focus on the following problem: given a fixed k >= 1, what is the complexity of computing a treedecomposition of width at most k with minimum number of bags in the class of graphs with treewidth at most k? We prove that the problem is NPcomplete for any fixed k >= 4 and polynomial for k <= 2; for k = 3, we show that it is polynomial in the class of trees and 2connected outerplanar graphs. (C) 2017 Elsevier B.V. All rights reserved.
Keywords: Treedecomposition; Treewidth; NPhard

Reus, L., Pagnoncelli, B., & Armstrong, M. (2019). Better management of production incidents in mining using multistage stochastic optimization. Resour. Policy, 63, 13 pp.
Abstract: Among the many sources of uncertainty in mining are production incidents: these can be strikes, environmental issues, accidents, or any kind of event that disrupts production. In this work, we present a strategic mine planning model that takes into account these types of incidents, as well as random prices. When confronted by production difficulties, mines which have contracts to supply customers have a range of flexibility options including buying on the spot market, or taking material from a stockpile if they have one. Earlier work on this subject was limited in that the optimization could only be carried out for a few stages (up to 5 years) and in that it only analyzed the riskneutral case. By using decomposition schemes, we are now able to solve largescale versions of the model efficiently, with a horizon of up to 15 years. We consider decision trees with up to 615 scenarios and implement risk aversion using Conditional ValueatRisk, thereby detecting its effect on the optimal policy. The results provide a “roadmap” for mine management as to optimal decisions, taking future possibilities into account. We present extensive numerical results using the new sddp.jl library, written in the Julia language, and discuss policy implications of our findings.
