Effective computational methods are important for practitioners and researchers working in strategic underground mine planning. We consider a class of problems that can be modeled as a resource-constrained project scheduling problem with optional activities; the objective maximizes net present value. We provide a computational review of math programming and constraint programming techniques for this problem, describe and implement novel problem-size reductions, and introduce an aggregated linear program that guides a list scheduling algorithm running over unaggregated instances. Practical, large-scale planning problems cannot be processed using standard optimization approaches. However, our strategies allow us to solve them to within about 5% of optimality in several hours, even for the most difficult instances. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms—Discrete. Funding: This work was supported by Alford Mining Systems, the Centro de Modelamiento Matemático [Grants ACE210010 and FB21005], ANID-Chile [BASAL funds for center of excellence and FONDEF Grant ID19-10164], and the supercomputing infrastructure of the NLHPC [Grant ECM-02].

Microgrids are frequently employed in remote regions, in part because access to a larger electric grid is impossible, difficult, or compromises reliability and independence. Although small microgrids often employ spot generation, in which a diesel generator is attached directly to a load, microgrids that combine these individual loads and augment generators with photovoltaic cells and batteries as a distributed energy system are emerging as a safer, less costly alternative. We present a model that seeks the minimum-cost microgrid design and ideal dispatched power to support a small remote site for one year with hourly fidelity under a detailed battery model; this mixed-integer nonlinear program (MINLP) is intractable with commercial solvers but loosely coupled with respect to time. A mixed-integer linear program (MIP) approximates the model, and a partitioning scheme linearizes the bilinear terms. We introduce a novel policy for loosely coupled MIPs in which the system reverts to equivalent conditions at regular time intervals; this separates the problem into subproblems that we solve in parallel. We obtain solutions within 5% of optimality in at most six minutes across 14 MIP instances from the literature and solutions within 5% of optimality to the MINLP instances within 20 minutes.

Abstract We embed a directed graph G(V, E) in a representation of a naval minefield; vertices V represent waypoints and edges E denote possible segments for ship transit. A new model identifies a simple s‐t path through the minefield that minimizes the risk of incurring unacceptable damage from threats, that is, mine detonations. Traditional “edge‐additive” models rely on shortest‐path algorithms that over‐accumulate risk along a path. Our “threat‐additive” approach accumulates risk based upon the path's closest point of approach to each mine. We formulate and solve this model (1) using an integer program (IP) and its stronger variant, and (2) via an A* search algorithm. Preprocessing routines are key to reducing run times. We investigate the relative merits, both with respect to solution quality and requisite computational effort, of two types of graphs, one based on a rectilinear scheme and one based on Voronoi diagrams. We find that graphs based on Voronoi diagrams provide higher quality solutions with less computational effort, and that the A* search procedure requires less computational effort than solving instances of our models as IPs.

The network‐diversion problem (ND) is defined on a directedor undirected graph G = (V,E) having non‐negative edge weights, a source vertex s, a sink vertex t, and a “diversion edge” . This problem, with intelligence‐gathering and war‐fighting applications, seeks a minimum‐weight, minimal s‐t cut in G such that . We present (a) a new NP‐completeness proof for ND on directed graphs, (b) the first polynomial‐time solution algorithm for a special graph topology, (c) an improved mixed‐integer programming formulation (MIP), and (d) useful valid inequalities for that MIP. The proof strengthens known results by showing, for instance, that ND is strongly NP‐complete on a directed graph even when is incident from s or into t, but not both, and even when G is acyclic; a corollary shows the NP‐completeness of a vertex‐deletion version of ND on undirected graphs. The polynomial‐time algorithm solves ND on s‐t planar graphs. Compared to a MIP from the literature, the new MIP, coupled with valid inequalities, reduces the average duality gap by 10–50% on certain classes of test problems. It can also reduce solution times by an order of magnitude. We successfully solve unweighted problems with roughly 90,000 vertices and 360,000 edges and weighted problems with roughly 10,000 vertices and 40,000 edges. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 000(00), 000–000 2013