Abstract: We propose an algorithm based on infeasible irreducible subsystems to solve binary linear chance-constrained 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 chance-constrained 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.

Abstract: Cops and robber games, introduced by Winkler and Nowakowski (in Discrete Math. 43(2-3), 235-239, 1983) and independently defined by Quilliot (in J. Comb. Theory, Ser. B 38(1), 89-92, 1985), concern a team of cops that must capture a robber moving in a graph. We consider the class of k-chordal graphs, i.e., graphs with no induced (chordless) cycle of length greater than k, ka parts per thousand yen3. We prove that k-1 cops are always sufficient to capture a robber in k-chordal graphs. This leads us to our main result, a new structural decomposition for a graph class including k-chordal graphs. We present a polynomial-time 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 tree-decomposition of G, each bag of which contains a dominating path with at most k-1 vertices. This allows us to prove that any k-chordal graph with maximum degree Delta has treewidth at most (k-1)(Delta-1)+2, improving the O(Delta(Delta-1) (k-3)) bound of Bodlaender and Thilikos (Discrete Appl. Math. 79(1-3), 45-61, 1997. Moreover, any graph admitting such a tree-decomposition has small hyperbolicity). As an application, for any n-vertex graph admitting such a tree-decomposition, 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 k-chordal graphs.

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 risk-neutral case. By using decomposition schemes, we are now able to solve large-scale 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 Value-at-Risk, 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.