Abstract Given an undirected graph with positive weights on the edges we study a parametric biobjective graph clustering problem. We remove a subset of edges to break the graph into smaller pieces, that is, connected components, or clusters. We seek to maximize the number of clusters while minimizing the weight of the removed edges. We identify nested solutions that lie on the concave envelope of the efficient frontier, yielding a hierarchical family of clusters, in strongly polynomial time. We demonstrate the performance of our approach on a graph defined by the schedule of football teams within the National Collegiate Athletic Association, which has a known hierarchical structure, and on a set of synthetic graphs generated from a stochastic block model with embedded hierarchical structure.

We consider a robust optimization problem in an electric power system under uncertain demand and availability of renewable energy resources. Solving the deterministic alternating current (AC) optimal power flow (ACOPF) problem has been considered challenging since the 1960s due to its nonconvexity. Linear approximation of the AC power flow system sees pervasive use, but does not guarantee a physically feasible system configuration. In recent years, various convex relaxation schemes for the ACOPF problem have been investigated, and under some assumptions, a physically feasible solution can be recovered. Based on these convex relaxations, we construct a robust convex optimization problem with recourse to solve for optimal controllable injections (fossil fuel, nuclear, etc.) in electric power systems under uncertainty (renewable energy generation, demand fluctuation, etc.). We propose a cutting-plane method to solve this robust optimization problem, and we establish convergence and other desirable properties. Experimental results indicate that our robust convex relaxation of the ACOPF problem can provide a tight lower bound.

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.

We consider two types of convex approximations of two-stage totally unimodular integer recourse models. Although worst-case error bounds are available for these approximations, their actual performance has not yet been investigated, mainly because this requires solving the original recourse model. In this paper we assess the quality of the approximating solutions using Monte Carlo sampling, or more specifically, using the so-called multiple replications procedure. Based on numerical experiments for an integer newsvendor problem, a fleet allocation and routing problem, and a stochastic activity network investment problem, we conclude that the error bounds are reasonably sharp if the variability of the random parameters in the model is either small or large; otherwise, the actual error of using the convex approximations is much smaller than the error bounds suggest. Moreover, we conclude that the solutions obtained using the convex approximations are good only if the variability of the random parameters is medium to large. In case this variability is small, however, typically sampling methods perform best, even with modest sample sizes. In this sense, the convex approximations and sampling methods can be considered as complementary solution methods. Moreover, as required for our applications, we extend our approach to derive new error bounds dealing with deterministic second-stage side constraints and relatively complete recourse, and perfect dependencies in the right-hand side vector.

Oil and gas companies are drilling and developing fields in the Arctic Ocean, which is an environment with ice floes. These companies must protect their platforms from ice floe collisions. One proposal is to use a system that consists of autonomous underwater vehicles (AUVs) and docking stations. The AUVs measure the under-water topography of the ice floes, while the docking stations launch the AUVs and recharge their batteries. Given resource constraints, we optimize locations and quantities for the docking stations and the AUVs, as well as the AUV scheduling policies, to maximize security of the platform. We model the system using a multistage stochastic facility location problem to optimize the docking station locations, the AUV allocations, and the scheduling policies of the AUVs. A two-stage stochastic facility location problem and two efficient online scheduling heuristics provide lower bounds and upper bounds for the multistage model. Even though the model is motivated by an oil industry project, most of the modeling and optimization methods apply more broadly to two-dimensional radial detection.

We consider a multiperiod system operation problem with two conflicting objectives, minimizing cost and risk. Risk stems from uncertain disruptions to the system during operation. Whereas a general model would hedge against disruptions in each time period, we study special cases in which only a modest number of disruptions occur. To optimize for risk, we employ a convex approximation based on constraint sampling. We develop a stratified sampling scheme based on distributional information on the time of disruption. We establish that our scheme yields significant savings in sampling costs—up to an order of magnitude in the number of time periods—over naive sampling. Moreover, in the absence of distributional information, we exhibit a sampling strategy that has comparable performance to optimal stratification. We numerically demonstrate that stratification improves cost over naive sampling, improving the solution's proximity to the efficient frontier of the bicriteria problem.

Abstract We consider a stochastic network interdiction problem in which the goal is to detect an evader, who selects a maximum‐reliability path. Subject to a resource constraint, the interdictor installs sensors on a subset of the network's arcs to minimize the value of the evader's maximum‐reliability path, i.e., to maximize the detection probability. When this decision is made, the evader's origin–destination pair is known to the interdictor only through a probability distribution. Our model is framed as a stochastic mixed‐integer program and solved by an enhanced L‐shaped decomposition method. Our primary enhancement is via a valid inequality, which we call a step inequality. In earlier work [Morton et al., IIE Trans 39 (2007), 3–14], we developed step inequalities for the special case in which the evader encounters at most one sensor on an origin–destination path. Here, we generalize the step inequality to the case where the evader encounters multiple sensors. In this more general setting, the step inequality is tightly coupled to the decomposition scheme. An efficient separation algorithm identifies violated step inequalities and strengthens the linear programming relaxation of the L‐shaped method's master program. We apply this solution procedure with further computational enhancements to a collection of test problems. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008