Eduardo Moreno
Professor
Faculty of Engineering and Science
Universidad Adolfo Ibáñez
Publications
Filter by type:
Generalized Adaptive Partition-based Method for Two-Stage Stochastic Linear Programs with Fixed Recourse
Exact reliability optimization for series-parallel graphs using convex envelopes
Given its wide spectrum of applications, the classical problem of all-terminal network reliability evaluation remains a highly relevant problem in network design. The associated optimization problem—to find a network with the best possible reliability under multiple constraints—presents an even more complex challenge, which has been addressed in the scientific literature but usually under strong assumptions over failures probabilities and/or the network topology. In this work, we propose a novel reliability optimization framework for network design with failures probabilities that are independent but not necessarily identical. We leverage the linear-time evaluation procedure for network reliability in the series-parallel graphs of Satyanarayana and Wood (1985) to formulate the reliability optimization problem as a mixed-integer nonlinear optimization problem. To solve this nonconvex problem, we use classical convex envelopes of bilinear functions, introduce custom cutting planes, and propose a new family of convex envelopes for expressions that appear in the evaluation of network reliability. Furthermore, we exploit the refinements produced by spatial branch-and-bound to locally strengthen our convex relaxations. Our experiments show that, using our framework, one can efficiently obtain optimal solutions in challenging instances of this problem.
Convex envelopes for ray-concave functions
Convexification based on convex envelopes is ubiquitous in the non-linear optimization literature. Thanks to considerable efforts of the optimization community for decades, we are able to compute the convex envelopes of a considerable number of functions that appear in practice, and thus obtain tight and tractable approximations to challenging problems. We contribute to this line of work by considering a family of functions that, to the best of our knowledge, has not been considered before in the literature. We call this family ray-concave functions. We show sufficient conditions that allow us to easily compute closed-form expressions for the convex envelope of ray-concave functions over arbitrary polytopes. With these tools, we are able to provide new perspectives to previously known convex envelopes and derive a previously unknown convex envelope for a function that arises in probability contexts.
Resource-constrained project scheduling problems (RCPSP) are at the heart of many production planning problems across a plethora of applications. Although the problem has been studied since the early 1960s, most developments and test instances are limited to problems with less than 300 jobs, far from the thousands present in real-life scenarios. Furthermore, the RCPSP with discounted cost (DC) is critical in many of these settings, which require decision makers to evaluate the net present value of the finished tasks, but the non-linear cost function makes the problem harder to solve or analyze.
In this work, we propose a novel approximation algorithm for the RCPSP-DC. Our main contribution is that, through the use of geometrically increasing intervals, we can construct an approximation algorithm, keeping track of precedence constraints, usage of multiple resources, and time requirements. To our knowledge, this is the first approximation algorithm for this problem. Finally, through experimental analysis over real instances, we report the empirical performance of our approach, showing that our technique allows us to solve sizeable underground mining problems within reasonable time frames and gaps much smaller than the theoretically computed ones.
The risk-averse ultimate pit problem
In this work, we consider a risk-averse 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 prec- edences. We show that only an entropic risk measure satisfies these properties and propose a two-stage stochastic programming formulation of the problem, including an efficient approximation scheme to solve it. We illustrate our approach in a small self-constructed example, and apply our approximation scheme to a real-world sec- tion of the Andina mine, in Chile.
Planning Resilient Networks against Natural Hazards: Understanding the Importance of Correlated Failures and the Value of Flexible Transmission Assets
Natural hazards cause major power outages as a result of spatially-correlated failures of network components. However, these correlations between failures of individual elements are often ignored in probabilistic planning models for optimal network design. We use different types of planning models to demonstrate the impact of ignoring correlations between component failures and the value of flexible transmission assets when power systems are exposed to natural hazards. We consider a network that is hypothetically located in northern Chile, a region that is prone to earthquakes. Using a simulation model, we compute the probabilities of spatially-correlated outages of transmission and substations based on information about historical earthquakes in the area. We determine optimal network designs using a deterministic reliability criterion and probabilistic models that either consider or disregard correlations among component failures. Our results show that the probability of a simultaneous failure of two transmission elements exposed to an earthquake can be up to 15 times higher than the probability simultaneous failure of the same two elements when we only consider independent component failures. Disregarding correlations of component failures changes the optimal network design significantly and increases the expected levels of curtailed demand in scenarios with spatially-correlated failures. We also find that, in some cases, it becomes optimal to invest in HVDC instead of AC transmission lines because the former gives the system operator the flexibility to control power flows in meshed transmission networks. This feature is particularly valuable to systems exposed to natural hazards, where network topologies in post-contingency operating conditions might differ significantly from pre-contingency ones.
Real-Time Fleet Management Decision Support System with Security Constraints
Production scheduling for strategic open pit mine planning: A mixed integer programming approach
Practical performance of an open pit mine scheduling model considering blending and stockpiling
A decomposition algorithm for computing income taxes with pass-through entities and its application to the Chilean case
On the Marshall-Olkin Copula Model for Network Reliability under Dependent Failures
Outer approximation and submodular cuts for maximum capture facility location problems with random utilities
Dataset available at https://github.com/borelian/j.ejor.2017.09.023
A study of the Bienstock-Zuckerberg algorithm: Applications in Mining and Resource Constrained Project Scheduling
Traffic Engineering in Segment Routing Networks
Linear Models for Stockpiling in Open-pit Mine Production Scheduling Problems
A two-stage stochastic model for open pit mine planning under geological uncertainty
Integrated traffic-transit stochastic equilibrium model with park-and-ride facilities
Chance-constrained problems and rare events: an importance sampling approach
Availability-driven optimal design of shared path protection in WDM networks
A branch-and-bound algorithm for the maximum capture problem with random utilities
Topological optimization of reliable networks under dependent failures
The precedence constrained knapsack problem: Separating maximally violated inequalities
We consider the problem of separating maximally violated inequalities for the precedence constrained knapsack problem. Though we consider maximally violated constraints in a very general way, special emphasis is placed on induced cover inequalities and induced clique inequalities. Our contributions include a new partial characterization of maximally violated inequalities, a new safe shrinking technique, and new insights on strengthening and lifting. This work follows on the work of Boyd (1993), Park and Park (1997), van de Leensel et al. (1999) and Boland et al. (2011). Computational experiments show that our new techniques and insights can be used to significantly improve the performance of cutting plane algorithms for this problem.
Restricted Risk Measures and Robust Optimization
Solving the maximum edge biclique packing problem on unbalanced bipartite graphs
A primal-dual aggregation algorithm for minimizing Conditional-Value-at-Risk in linear programs
Stochastic Transit Equilibrium
MineLib: A Library of Open Pit Mining Problems
An Integer Linear Programming Approach for Bilinear Integer Programming
A New Algorithm for the Open-pit Mine Scheduling Problem
Robust planning for an open-pit mining problem under ore-grade uncertainty
Grafos: Fundamentos y Algoritmos
Minimal Eulerian circuits and Minimal de Bruijn sequences
Minimal Eulerian Circuit in a Labeled Digraph
De Bruijn Sequences and De Bruijn Graphs for a general language
On the theorem of Fredricksen and Maiorana about de Bruijn sequences
Minimal de Bruijn Sequence in a Language with Forbidden Subtrings
