[script] window.dataLayer = window.dataLayer || []; function gtag(){dataLayer.push(arguments);} gtag('js', new Date()); gtag('config', 'UA-1437536-2'); [/script]

Exact reliability optimization for series-parallel graphs using convex envelopes

Articles
Javiera Barrera, Eduardo Moreno, Gonzalo Muñoz, Pablo Romero
Networks, to appear.
Publication year: 2022

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

Articles
Javiera Barrera, Eduardo Moreno, Gonzalo Muñoz
Optimization Letters, to appear.
Publication year: 2022

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.

The risk-averse ultimate pit problem

Articles
Gianpiero Canessa, Eduardo Moreno, Bernardo K. Pagnoncelli
Optimization and Engineering 22, 2655-2678, 2021
Publication year: 2021

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

Articles
Javiera Barrera, Pauline Beaupuits, Eduardo Moreno, Rodrigo Moreno, Francisco D. Muñoz
Electric Power Systems Research 197, 107280, 2021
Publication year: 2021

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.

Generalized Adaptive Partition-based Method for Two-Stage Stochastic Linear Programs with Fixed Recourse

Articles
Cristian Ramirez-Pico, Eduardo Moreno
Mathematical Programming, to appear.
Publication year: 2021

Real-Time Fleet Management Decision Support System with Security Constraints

Articles
Javiera Barrera, Rodrigo A. Carrasco, Eduardo Moreno
TOP, 28(3):728-748, 2020
Publication year: 2020

Production scheduling for strategic open pit mine planning: A mixed integer programming approach

Articles
Orlando Rivera Letelier and Daniel Espinoza and Marcos Goycoolea and Eduardo Moreno and Gonzalo Muñoz
Operations Research, 68(5):1425-1444, 2020
Publication year: 2020

Practical performance of an open pit mine scheduling model considering blending and stockpiling

Articles
Mojtaba Rezakhah and Eduardo Moreno and Alexandra Newman
Computers and Operations Research, 115: 104638, 2020
Publication year: 2020

A decomposition algorithm for computing income taxes with pass-through entities and its application to the Chilean case

Articles
Javiera Barrera, Eduardo Moreno, Sebastian Varas K.
Annals of Operational Research, 286(1): 545–557, 2020
Publication year: 2020

On the Marshall-Olkin Copula Model for Network Reliability under Dependent Failures

Articles
Omar Matus and Javiera Barrera and Eduardo Moreno and Gerardo Rubino
IEEE Transactions on Reliability, 62(2): 451—461, 2019
Publication year: 2019

Outer approximation and submodular cuts for maximum capture facility location problems with random utilities

Articles
Ljubic, Ivana and Moreno, Eduardo
European Journal of Operational Research, 266(1): 46—56, 2018
Publication year: 2018

A study of the Bienstock-Zuckerberg algorithm: Applications in Mining and Resource Constrained Project Scheduling

Articles
Gonzalo Muñoz, Daniel Espinoza, Marcos Goycoolea, Eduardo Moreno, Maurice Queyranne, Orlando Rivera
Computational Optimization and Applications, 69(2): 501—534, 2018
Publication year: 2018

Traffic Engineering in Segment Routing Networks

Articles
Moreno, Eduardo and Beghelli, Alejandra and Cugini, Filippo
Computer Networks, 114: 23—31, 2017
Publication year: 2017

Linear Models for Stockpiling in Open-pit Mine Production Scheduling Problems

Articles
Moreno, Eduardo and Rezakhah, Mojtaba and Newman, Alexandra and Ferreira, Felipe
European Journal of Operational Research, 260(1): 212—221, 2017
Publication year: 2017

Integrated traffic-transit stochastic equilibrium model with park-and-ride facilities

Articles
Cristobal Pineda and Cristián Cortés and Pedro Jara-Moroni and Eduardo Moreno
Transportation Research Part C: Emerging Technologies, 71: 86—107, 2016
Publication year: 2016

Chance-constrained problems and rare events: an importance sampling approach

Articles
Javiera Barrera and Tito Homem-de-Mello and Eduardo Moreno and Bernardo K. Pagnoncelli and Gianpiero Canessa
Mathematical Programming, 157(1): 153—189, 2016
Publication year: 2016

Availability-driven optimal design of shared path protection in WDM networks

Articles
Marco Tarifeño-Gajardo and Alejandra Beghelli and Eduardo Moreno
Networks, 68(3): 224—237, 2016
Publication year: 2016

A branch-and-bound algorithm for the maximum capture problem with random utilities

Articles
Alexandre S. Freire and Eduardo Moreno and Wilfredo F. Yushimito
European Journal of Operational Research, 252(1): 204—212, 2016
Publication year: 2016

Topological optimization of reliable networks under dependent failures

Articles
Javiera Barrera and Hector Cancela and Eduardo Moreno
Operations Research Letters, 43: 132—136, 2015
Publication year: 2015

The precedence constrained knapsack problem: Separating maximally violated inequalities

Articles
Daniel Espinoza and Marcos Goycoolea and Eduardo Moreno
Discrete Applied Mathematics, 194: 65—80, 2015
Publication year: 2015

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

Articles
Guido Lagos and Daniel Espinoza and Eduardo Moreno and Juan Pablo Vielma
European Journal of Operational Research, 241: 771—782, 2015
Publication year: 2015

Solving the maximum edge biclique packing problem on unbalanced bipartite graphs

Articles
Vicente Acuña and Alexandre Freire and Carlos E. Ferreira and Eduardo Moreno
Discrete Applied Mathematics, 164(1): 2—12, 2014
Publication year: 2014

A primal-dual aggregation algorithm for minimizing Conditional-Value-at-Risk in linear programs

Articles
Daniel Espinoza and Eduardo Moreno
Computational Optimization and Applications, 59: 617—638, 2014
Publication year: 2014

Stochastic Transit Equilibrium

Articles
Cristian E. Cortes and Pedro Jara-Moroni and Eduardo Moreno and Cristobal Pineda
Transportation Research Part B, 51: 29—44, 2013
Publication year: 2013

MineLib: A Library of Open Pit Mining Problems

Articles
Daniel Espinoza and Marcos Goycoolea and Eduardo Moreno and Alexandra N. Newman
Annals of Operations Research, 206(1): 91—114, 2013
Publication year: 2013

An Integer Linear Programming Approach for Bilinear Integer Programming

Articles
Alexandre S. Freire and Eduardo Moreno and Juan Pablo Vielma
Operations Research Letters, 40(2): 74—77, 2012
Publication year: 2012

A New Algorithm for the Open-pit Mine Scheduling Problem

Articles
Renaud Chicoisne and Daniel Espinoza and Marcos Goycoolea and Eduardo Moreno and Enrique Rubio
Operations Research, 60(3): 517—528, 2012
Publication year: 2012

Minimal Eulerian circuits and Minimal de Bruijn sequences

Articles
Mart’in Matamala and Eduardo Moreno
Discrete Mathematics, 309(17): 5298—5304, 2009
Publication year: 2009

Minimal Eulerian Circuit in a Labeled Digraph

Articles
Eduardo Moreno and Mart’in Matamala
Lecture Notes in Computer Science, 3887: 737—744, 2006
Publication year: 2006

De Bruijn Sequences and De Bruijn Graphs for a general language

Articles
Eduardo Moreno
Information Processing Letters, 96(6): 214—219, 2005
Publication year: 2005

On the theorem of Fredricksen and Maiorana about de Bruijn sequences

Articles
Eduardo Moreno
Advances in Applied Mathematics, 33(2): 413—415, 2004
Publication year: 2004

Minimal de Bruijn Sequence in a Language with Forbidden Subtrings

Articles
Eduardo Moreno, Martin Matamala
Lecture Notes in Computer Science, 3353: 168—176, 2004
Publication year: 2004

Dynamic of cyclic automata over $Z^2$

Articles
Martín Matamala and Eduardo Moreno
Theoretical Computer Science, 322(2): 369—381, 2004
Publication year: 2004