|   | 
Details
   web
Records
Author (up) Acuna, V.; Ferreira, C.E.; Freire, A.S.; Moreno, E.
Title Solving the maximum edge biclique packing problem on unbalanced bipartite graphs Type
Year 2014 Publication Discrete Applied Mathematics Abbreviated Journal Discret Appl. Math.
Volume 164 Issue Pages 2-12
Keywords Maximum edge biclique packing; Branch-and-price; Metabolic networks; Product bundling
Abstract A biclique is a complete bipartite graph. Given an (L, R)-bipartite graph G = (V, E) and a positive integer k, the maximum edge biclique packing (num') problem consists in finding a set of at most k bicliques, subgraphs of G, such that the bicliques are vertex disjoint with respect to a subset of vertices S, where S E {V, L, R}, and the number of edges inside the bicliques is maximized. The maximum edge biclique (mEs) problem is a special case of the MEBP problem in which k = 1. Several applications of the MEB problem have been studied and, in this paper, we describe applications of the MEBP problem in metabolic networks and product bundling. In these applications the input graphs are very unbalanced (i.e., IRI is considerably greater than ILI), thus we consider carefully this property in our models. We introduce a new formulation for the MEB problem and a branch-and-price scheme, using the classical branch rule by Ryan and Foster, for the MEBP problem. Finally, we present computational experiments with instances that come from the described applications and also with randomly generated instances. (C) 2011 Elsevier B.V. All rights reserved.
Address [Acuna, V.] Univ Lyon 1, F-69622 Villeurbanne, France, Email: afreire@ime.usp.br
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0166-218x ISBN Medium
Area Expedition Conference
Notes WOS:000332427400002 Approved
Call Number UAI @ eduardo.moreno @ Serial 361
Permanent link to this record
 

 
Author (up) Barrera, J.; Beaupuits, P.; Moreno, E.; Moreno, R.; Munoz, F.D.
Title Planning resilient networks against natural hazards: Understanding the importance of correlated failures and the value of flexible transmission assets Type
Year 2021 Publication Electric Power System Research Abbreviated Journal Electr. Power Syst. Res.
Volume 197 Issue Pages
Keywords
Abstract 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.
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0378-7796 ISBN Medium
Area Expedition Conference
Notes Approved
Call Number UAI @ eduardo.moreno @ Serial 1365
Permanent link to this record
 

 
Author (up) Barrera, J.; Cancela, H.; Moreno, E.
Title Topological optimization of reliable networks under dependent failures Type
Year 2015 Publication Operations Research Letters Abbreviated Journal Oper. Res. Lett.
Volume 43 Issue 2 Pages 132-136
Keywords Common-cause failure; Dependent failure; Reliable network design; Sample average approximation
Abstract We address the design problem of a reliable network. Previous work assumes that link failures are independent. We discuss the impact of dropping this assumption. We show that under a common-cause failure model, dependencies between failures can affect the optimal design. We also provide an integer-programming formulation to solve this problem. Furthermore, we discuss how the dependence between the links that participate in the solution and those that do not can be handled. Other dependency models are discussed as well. (C) 2014 Elsevier B.V. All rights reserved.
Address [Barrera, Javiera; Moreno, Eduardo] Univ Adolfo Ibanez, Fac Sci & Engn, Santiago, Chile, Email: javiera.barrera@uai.cl;
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0167-6377 ISBN Medium
Area Expedition Conference
Notes WOS:000351968300003 Approved
Call Number UAI @ eduardo.moreno @ Serial 480
Permanent link to this record
 

 
Author (up) Barrera, J.; Carrasco, R.A.; Moreno, E.
Title Real-time fleet management decision support system with security constraints Type
Year 2020 Publication TOP Abbreviated Journal TOP
Volume 28 Issue 3 Pages 728-748
Keywords Fleet management; Real-time control; Data analytics; GPS tracking; Decision support system; Conflict detection and resolution
Abstract Intelligent transportation, and in particular, fleet management, has been a forefront concern for a plethora of industries. This statement is especially true for the production of commodities, where transportation represents a central element for operational continuity. Additionally, in many industries, and in particular those with hazardous environments, fleet control must satisfy a wide range of security restrictions to ensure that risks are kept at bay and accidents are minimum. Furthermore, in these environments, any decision support tool must cope with noisy and incomplete data and give recommendations every few minutes. In this work, a fast and efficient decision support tool is presented to help fleet managers oversee and control ore trucks, in a mining setting. The main objective of this system is to help managers avoid interactions between ore trucks and personnel buses, one of the most critical security constraints in our case study, keeping a minimum security distance between the two at all times. Furthermore, additional algorithms are developed and implemented, so that this approach can work with real-life noisy GPS data. Through the use of historical data, the performance of this decision support system is studied, validating that it works under the real-life conditions presented by the company. The experimental results show that the proposed approach improved truck and road utilization significantly while allowing the fleet manager to control the security distance required by their procedures.
Address [Barrera, Javiera; Carrasco, Rodrigo A.; Moreno, Eduardo] Univ Adolfo Ibanez, Fac Engn & Sci, Santiago, Chile, Email: javiera.barrera@uai.cl;
Corporate Author Thesis
Publisher Springer Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1134-5764 ISBN Medium
Area Expedition Conference
Notes WOS:000534967700001 Approved
Call Number UAI @ eduardo.moreno @ Serial 1200
Permanent link to this record
 

 
Author (up) Barrera, J.; Homem-De-Mello, T.; Moreno, E.; Pagnoncelli, B.K.; Canessa, G.
Title Chance-constrained problems and rare events: an importance sampling approach Type
Year 2016 Publication Mathematical Programming Abbreviated Journal Math. Program.
Volume 157 Issue 1 Pages 153-189
Keywords Chance-constrained programming; Sample average approximation; Importance sampling; Rare-event simulation
Abstract We study chance-constrained problems in which the constraints involve the probability of a rare event. We discuss the relevance of such problems and show that the existing sampling-based algorithms cannot be applied directly in this case, since they require an impractical number of samples to yield reasonable solutions. We argue that importance sampling (IS) techniques, combined with a Sample Average Approximation (SAA) approach, can be effectively used in such situations, provided that variance can be reduced uniformly with respect to the decision variables. We give sufficient conditions to obtain such uniform variance reduction, and prove asymptotic convergence of the combined SAA-IS approach. As it often happens with IS techniques, the practical performance of the proposed approach relies on exploiting the structure of the problem under study; in our case, we work with a telecommunications problem with Bernoulli input distributions, and show how variance can be reduced uniformly over a suitable approximation of the feasibility set by choosing proper parameters for the IS distributions. Although some of the results are specific to this problem, we are able to draw general insights that can be useful for other classes of problems. We present numerical results to illustrate our findings.
Address [Barrera, Javiera; Moreno, Eduardo] Univ Adolfo Ibanez, Fac Sci & Engn, Santiago, Chile, Email: javiera.barrera@uai.cl
Corporate Author Thesis
Publisher Springer Heidelberg Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0025-5610 ISBN Medium
Area Expedition Conference
Notes WOS:000375568400007 Approved
Call Number UAI @ eduardo.moreno @ Serial 613
Permanent link to this record
 

 
Author (up) Barrera, J.; Moreno, E.; Varas, S.
Title A decomposition algorithm for computing income taxes with pass-through entities and its application to the Chilean case Type
Year 2020 Publication Annals Of Operations Research Abbreviated Journal Ann. Oper. Res.
Volume 286 Issue 1-2 Pages 545-557
Keywords Income taxes; Markov processes; Networks; Algorithms
Abstract Income tax systems with “pass-through” entities transfer a firm's income to shareholders, which are taxed individually. In 2014, a Chilean tax reform introduced this type of entity and changed to an accrual basis that distributes incomes (but not losses) to shareholders. A crucial step for the Chilean taxation authority is to compute the final income of each individual given the complex network of corporations and companies, usually including cycles between them. In this paper, we show the mathematical conceptualization and the solution to the problem, proving that there is only one way to distribute income to taxpayers. Using the theory of absorbing Markov chains, we define a mathematical model for computing the taxable income of each taxpayer, and we propose a decomposition algorithm for this problem. This approach allows us to compute the solution accurately and to efficiently use computational resources. Finally, we present some characteristics of Chilean taxpayers' network and the computational results of the algorithm using this network.
Address [Barrera, Javiera; Moreno, Eduardo] Univ Adolfo Ibanez, Fac Engn & Sci, Santiago, Chile, Email: javiera.barrera@uai.cl;
Corporate Author Thesis
Publisher Springer Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0254-5330 ISBN Medium
Area Expedition Conference
Notes WOS:000511564300023 Approved
Call Number UAI @ eduardo.moreno @ Serial 1102
Permanent link to this record
 

 
Author (up) Canessa, G.; Moreno, E.; Pagnoncelli, B.K.
Title The risk-averse ultimate pit problem Type
Year 2021 Publication Optimization And Engineering Abbreviated Journal Optim. Eng.
Volume Early access Issue Pages 24 pp
Keywords Ultimate pit; Mining; Risk-averse optimization; Integer programming
Abstract 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 precedences. 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 section of the Andina mine, in Chile.
Address [Canessa, Gianpiero] Univ Adolfo Ibanez, PhD Program Ind Engn & Operat Res, Diagonal Las Torres 2640, Santiago 7941169, Chile, Email: canessa@kth.se
Corporate Author Thesis
Publisher Springer Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1389-4420 ISBN Medium
Area Expedition Conference
Notes WOS:000557140000001 Approved
Call Number UAI @ eduardo.moreno @ Serial 1219
Permanent link to this record
 

 
Author (up) Chicoisne, R.; Espinoza, D.; Goycoolea, M.; Moreno, E.; Rubio, E.
Title A New Algorithm for the Open-Pit Mine Production Scheduling Problem Type
Year 2012 Publication Operations Research Abbreviated Journal Oper. Res.
Volume 60 Issue 3 Pages 517-528
Keywords
Abstract For the purpose of production scheduling, open-pit mines are discretized into three-dimensional arrays known as block models. Production scheduling consists of deciding which blocks should be extracted, when they should be extracted, and what to do with the blocks once they are extracted. Blocks that are close to the surface should be extracted first, and capacity constraints limit the production in each time period. Since the 1960s, it has been known that this problem can be cast as an integer programming model. However, the large size of some real instances (3-10 million blocks, 15-20 time periods) has made these models impractical for use in real planning applications, thus leading to the use of numerous heuristic methods. In this article we study a well-known integer programming formulation of the problem that we refer to as C-PIT. We propose a new decomposition method for solving the linear programming relaxation (LP) of C-PIT when there is a single capacity constraint per time period. This algorithm is based on exploiting the structure of the precedence-constrained knapsack problem and runs in O(mn log n) in which n is the number of blocks and m a function of the precedence relationships in the mine. Our computations show that we can solve, in minutes, the LP relaxation of real-sized mine-planning applications with up to five million blocks and 20 time periods. Combining this with a quick rounding algorithm based on topological sorting, we obtain integer feasible solutions to the more general problem where multiple capacity constraints per time period are considered. Our implementation obtains solutions within 6% of optimality in seconds. A second heuristic step, based on local search, allows us to find solutions within 3% in one hour on all instances considered. For most instances, we obtain solutions within 1-2% of optimality if we let this heuristic run longer. Previous methods have been able to tackle only instances with up to 150,000 blocks and 15 time periods.
Address [Chicoisne, Renaud; Espinoza, Daniel] Univ Chile, Dept Ind Engn, Santiago 8370439, Chile, Email: renaud.chicoisne@gmail.com;
Corporate Author Thesis
Publisher Informs Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0030-364x ISBN Medium
Area Expedition Conference
Notes WOS:000306645500003 Approved
Call Number UAI @ eduardo.moreno @ Serial 223
Permanent link to this record
 

 
Author (up) Cortes, C.E.; Jara-Moroni, P.; Moreno, E.; Pineda, C.
Title Stochastic transit equilibrium Type
Year 2013 Publication Transportation Research Part B-Methodological Abbreviated Journal Transp. Res. Pt. B-Methodol.
Volume 51 Issue Pages 29-44
Keywords Transit equilibrium; Stochastic models; Hyperpaths; Congested networks; Simulation
Abstract We present a transit equilibrium model in which boarding decisions are stochastic. The model incorporates congestion, reflected in higher waiting times at bus stops and increasing in-vehicle travel time. The stochastic behavior of passengers is introduced through a probability for passengers to choose boarding a specific bus of a certain service. The modeling approach generates a stochastic common-lines problem, in which every line has a chance to be chosen by each passenger. The formulation is a generalization of deterministic transit assignment models where passengers are assumed to travel according to shortest hyperpaths. We prove existence of equilibrium in the simplified case of parallel lines (stochastic common-lines problem) and provide a formulation for a more general network problem (stochastic transit equilibrium). The resulting waiting time and network load expressions are validated through simulation. An algorithm to solve the general stochastic transit equilibrium is proposed and applied to a sample network; the algorithm works well and generates consistent results when considering the stochastic nature of the decisions, which motivates the implementation of the methodology on a real-size network case as the next step of this research. (C) 2013 Elsevier Ltd. All rights reserved.
Address Univ Chile, Transport Div, Dept Civil Engn, Santiago, Chile, Email: ccortes@ing.uchile.cl;
Corporate Author Thesis
Publisher Pergamon-Elsevier Science Ltd Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0191-2615 ISBN Medium
Area Expedition Conference
Notes WOS:000318323000003 Approved
Call Number UAI @ eduardo.moreno @ Serial 279
Permanent link to this record
 

 
Author (up) Coudert, D.; Luedtke, J.; Moreno, E.; Priftis, K.
Title Computing and maximizing the exact reliability of wireless backhaul networks. Type
Year 2018 Publication Electronic Notes in Discrete Mathematics Abbreviated Journal Electron. Notes Discret. Math.
Volume 64 Issue Pages 85-94
Keywords
Abstract
Address
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 1571-0653 ISBN Medium
Area Expedition Conference
Notes Approved
Call Number UAI @ eduardo.moreno @ Serial 1297
Permanent link to this record
 

 
Author (up) Espinoza, D.; Goycoolea, M.; Moreno, E.
Title The precedence constrained knapsack problem: Separating maximally violated inequalities Type
Year 2015 Publication Discrete Applied Mathematics Abbreviated Journal Discret Appl. Math.
Volume 194 Issue Pages 65-80
Keywords Lifting; Shrinking; Precedence-constrained knapsack problem; Induced cover inequality; Induced clique inequality; Separation problem
Abstract 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. (C) 2015 Elsevier B.V. All rights reserved.
Address [Espinoza, Daniel] Univ Chile, Dept Ind Engn, Santiago, Chile, Email: daespino@dii.uchile.cl;
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0166-218x ISBN Medium
Area Expedition Conference
Notes WOS:000361772500005 Approved
Call Number UAI @ eduardo.moreno @ Serial 525
Permanent link to this record
 

 
Author (up) Espinoza, D.; Goycoolea, M.; Moreno, E.; Newman, A.
Title MineLib: a library of open pit mining problems Type
Year 2013 Publication Annals Of Operations Research Abbreviated Journal Ann. Oper. Res.
Volume 206 Issue 1 Pages 93-114
Keywords Mine scheduling; Mine planning; Open pit production scheduling; Surface mine production scheduling; Problem libraries; Open pit mining library
Abstract Similar to the mixed-integer programming library (MIPLIB), we present a library of publicly available test problem instances for three classical types of open pit mining problems: the ultimate pit limit problem and two variants of open pit production scheduling problems. The ultimate pit limit problem determines a set of notional three-dimensional blocks containing ore and/or waste material to extract to maximize value subject to geospatial precedence constraints. Open pit production scheduling problems seek to determine when, if ever, a block is extracted from an open pit mine. A typical objective is to maximize the net present value of the extracted ore; constraints include precedence and upper bounds on operational resource usage. Extensions of this problem can include (i) lower bounds on operational resource usage, (ii) the determination of whether a block is sent to a waste dump, i.e., discarded, or to a processing plant, i.e., to a facility that derives salable mineral from the block, (iii) average grade constraints at the processing plant, and (iv) inventories of extracted but unprocessed material. Although open pit mining problems have appeared in academic literature dating back to the 1960s, no standard representations exist, and there are no commonly available corresponding data sets. We describe some representative open pit mining problems, briefly mention related literature, and provide a library consisting of mathematical models and sets of instances, available on the Internet. We conclude with directions for use of this newly established mining library. The library serves not only as a suggestion of standard expressions of and available data for open pit mining problems, but also as encouragement for the development of increasingly sophisticated algorithms.
Address [Espinoza, Daniel] Univ Chile, Dept Ind Engn, Santiago Ctr, Santiago, Chile, Email: daespino@dii.uchile.cl;
Corporate Author Thesis
Publisher Springer Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0254-5330 ISBN Medium
Area Expedition Conference
Notes WOS:000320694000006 Approved
Call Number UAI @ eduardo.moreno @ Serial 290
Permanent link to this record
 

 
Author (up) Espinoza, D.; Moreno, E.
Title A primal-dual aggregation algorithm for minimizing conditional value-at-risk in linear programs Type
Year 2014 Publication Computational Optimization And Applications Abbreviated Journal Comput. Optim. Appl.
Volume 59 Issue 3 Pages 617-638
Keywords Conditional value at risk; Aggregation techniques; Approximation methods; Sample average approximation
Abstract Recent years have seen growing interest in coherent risk measures, especially in Conditional Value-at-Risk (). Since is a convex function, it is suitable as an objective for optimization problems when we desire to minimize risk. In the case that the underlying distribution has discrete support, this problem can be formulated as a linear programming (LP) problem. Over more general distributions, recent techniques, such as the sample average approximation method, allow to approximate the solution by solving a series of sampled problems, although the latter approach may require a large number of samples when the risk measures concentrate on the tail of the underlying distributions. In this paper we propose an automatic primal-dual aggregation scheme to exactly solve these special structured LPs with a very large number of scenarios. The algorithm aggregates scenarios and constraints in order to solve a smaller problem, which is automatically disaggregated using the information of its dual variables. We compare this algorithm with other common approaches found in related literature, such as an improved formulation of the full problem, cut-generation schemes and other problem-specific approaches available in commercial software. Extensive computational experiments are performed on portfolio and general LP instances.
Address [Espinoza, Daniel] Univ Chile, Dept Ind Engn, Santiago, Chile, Email: daespino@dii.uchile.cl;
Corporate Author Thesis
Publisher Springer Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0926-6003 ISBN Medium
Area Expedition Conference
Notes WOS:000344803000009 Approved
Call Number UAI @ eduardo.moreno @ Serial 424
Permanent link to this record
 

 
Author (up) Freire, A.S.; Moreno, E.; Vielma, J.P.
Title An integer linear programming approach for bilinear integer programming Type
Year 2012 Publication Operations Research Letters Abbreviated Journal Oper. Res. Lett.
Volume 40 Issue 2 Pages 74-77
Keywords Bilinear programming; Integer linear programming; Product bundling
Abstract We introduce a new Integer Linear Programming (ILP) approach for solving Integer Programming (IP) problems with bilinear objectives and linear constraints. The approach relies on a series of ILP approximations of the bilinear P. We compare this approach with standard linearization techniques on random instances and a set of real-world product bundling problems. (C) 2011 Elsevier B.V. All rights reserved.
Address [Moreno, Eduardo] Univ Adolfo Ibanez, Fac Sci & Engn, Santiago, Chile, Email: afreire@ime.usp.br
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0167-6377 ISBN Medium
Area Expedition Conference
Notes WOS:000301331700002 Approved
Call Number UAI @ eduardo.moreno @ Serial 201
Permanent link to this record
 

 
Author (up) Freire, A.S.; Moreno, E.; Yushimito, W.F.
Title A branch-and-bound algorithm for the maximum capture problem with random utilities Type
Year 2016 Publication European Journal Of Operational Research Abbreviated Journal Eur. J. Oper. Res.
Volume 252 Issue 1 Pages 204-212
Keywords Facility location; Branch and bound; Maximum capture; Random utility model
Abstract The MAXIMUM CAPTURE PROBLEM WITH RANDOM UTILITIES seeks to locate new facilities in a competitive market such that the captured demand of users is maximized, assuming that each individual chooses among all available facilities according to the well-know a random utility model namely the multinomial logit. The problem is complex mostly due to its integer nonlinear objective function. Currently, the most efficient approaches deal with this complexity by either using a nonlinear programing solver or reformulating the problem into a Mixed-Integer Linear Programing (MILP) model. In this paper, we show how the best MILP reformulation available in the literature can be strengthened by using tighter coefficients in some inequalities. We also introduce a new branch-and-bound algorithm based on a greedy approach for solving a relaxation of the original problem. Extensive computational experiments are presented, bench marking the proposed approach with other linear and non-linear relaxations of the problem. The computational experiments show that our proposed algorithm is competitive with all other methods as there is no method which outperforms the others in all instances. We also show a large-scale real instance of the problem, which comes from an application in park-and-ride facility location, where our proposed branch-and-bound algorithm was the most effective method for solving this type of problem. (C) 2015 Elsevier B.V. All rights reserved.
Address [Moreno, Eduardo; Yushimito, Wilfredo F.] Univ Adolfo Ibanez, Fac Sci & Engn, Santiago, Chile, Email: afreire@ime.usp.br;
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0377-2217 ISBN Medium
Area Expedition Conference
Notes WOS:000371939700018 Approved
Call Number UAI @ eduardo.moreno @ Serial 601
Permanent link to this record
 

 
Author (up) Lagos, G.; Espinoza, D.; Moreno, E.; Vielma, J.P.
Title Restricted risk measures and robust optimization Type
Year 2015 Publication European Journal Of Operational Research Abbreviated Journal Eur. J. Oper. Res.
Volume 241 Issue 3 Pages 771-782
Keywords Risk management; Stochastic programming; Uncertainty modeling
Abstract In this paper we consider characterizations of the robust uncertainty sets associated with coherent and distortion risk measures. In this context we show that if we are willing to enforce the coherent or distortion axioms only on random variables that are affine or linear functions of the vector of random parameters, we may consider some new variants of the uncertainty sets determined by the classical characterizations. We also show that in the finite probability case these variants are simple transformations of the classical sets. Finally we present results of computational experiments that suggest that the risk measures associated with these new uncertainty sets can help mitigate estimation errors of the Conditional Value-at-Risk. (C) 2014 Elsevier B.V. All rights reserved.
Address [Lagos, Guido] Georgia Inst Technol, H Milton Stewart Sch Ind & Syst Engn, Atlanta, GA 30332 USA, Email: glagos@gatech.edu;
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0377-2217 ISBN Medium
Area Expedition Conference
Notes WOS:000347605100018 Approved
Call Number UAI @ eduardo.moreno @ Serial 438
Permanent link to this record
 

 
Author (up) Letelier, O.R.; Espinoza, D.; Goycoolea, M.; Moreno, E.; Munoz, G.
Title Production Scheduling for Strategic Open Pit Mine Planning: A Mixed-Integer Programming Approach Type
Year 2020 Publication Operations Research Abbreviated Journal Oper. Res.
Volume 68 Issue 5 Pages 1425-1444
Keywords open pit mining; production scheduling; column generation; heuristics; cutting planes; integer programming applications
Abstract Given a discretized representation of an ore body known as a block model, the open pit mining production scheduling problem that we consider consists of defining which blocks to extract, when to extract them, and how or whether to process them, in such a way as to comply with operational constraints and maximize net present value. Although it has been established that this problem can be modeled with mixed-integer programming, the number of blocks used to represent real-world mines (millions) has made solving large instances nearly impossible in practice. In this article, we introduce a new methodology for tackling this problem and conduct computational tests using real problem sets ranging in size from 20,000 to 5,000,000 blocks and spanning 20 to 50 time periods. We consider both direct block scheduling and bench-phase scheduling problems, with capacity, blending, and minimum production constraints. Using new preprocessing and cutting planes techniques, we are able to reduce the linear programming relaxation value by up to 33%, depending on the instance. Then, using new heuristics, we are able to compute feasible solutions with an average gap of 1.52% relative to the previously computed bound. Moreover, after four hours of running a customized branch-and-bound algorithm on the problems with larger gaps, we are able to further reduce the average from 1.52% to 0.71%.
Address [Rivera Letelier, Orlando] Univ Adolfo Ibanez, Doctoral Program Ind Engn & Operat Res, Santiago 7941169, Chile, Email: orlando.rivera@uai.cl;
Corporate Author Thesis
Publisher Informs Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0030-364x ISBN Medium
Area Expedition Conference
Notes WOS:000574409100008 Approved
Call Number UAI @ alexi.delcanto @ Serial 1250
Permanent link to this record
 

 
Author (up) Ljubic, I.; Moreno, E.
Title Outer approximation and submodular cuts for maximum capture facility location problems with random utilities Type
Year 2018 Publication European Journal Of Operational Research Abbreviated Journal Eur. J. Oper. Res.
Volume 266 Issue 1 Pages 46-56
Keywords Combinatorial optimization; Branch-and-cut; Maximum capture; Random utility model; Competitive facility location
Abstract We consider a family of competitive facility location problems in which a “newcomer” company enters the market and has to decide where to locate a set of new facilities so as to maximize its market share. The multinomial logit model is used to estimate the captured customer demand. We propose a first branch-and-cut approach for this family of difficult mixed-integer non-linear problems. Our approach combines two types of cutting planes that exploit particular properties of the objective function: the first one are the outer-approximation cuts and the second one are the submodular cuts. The approach is computationally evaluated on three datasets from the recent literature. The obtained results show that our new branch-and-cut drastically outperforms state-of-the-art exact approaches, both in terms of the computing times, and in terms of the number of instances solved to optimality. (C) 2017 Elsevier B.V. All rights reserved.
Address [Ljubic, Ivana] ESSEC Business Sch, 3 Av Bernard Hirsch,BP 50105, F-95021 Cergy Pontoise, France, Email: ivana.ljubic@essec.edu;
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0377-2217 ISBN Medium
Area Expedition Conference
Notes WOS:000423646500005 Approved
Call Number UAI @ eduardo.moreno @ Serial 815
Permanent link to this record
 

 
Author (up) Matamala, M.; Moreno, E.
Title Minimum Eulerian circuits and minimum de Bruijn sequences Type
Year 2009 Publication Discrete Mathematics Abbreviated Journal Discret. Math.
Volume 306 Issue 17 Pages 5298-5304
Keywords Eulerian circuits; Labelled digraph; De Bruijn sequences
Abstract Given a digraph (directed graph) with a labeling on its arcs, We Study the problem of finding the Eulerian circuit of lexicographically minimum label. We prove that this problem is NP-complete in general, but if the labelling is locally injective (arcs going out from each vertex have different labels), we prove that it is solvable in linear time by giving an algorithm that Constructs this circuit. When this algorithm is applied to a de Bruijn graph, it obtains the de Bruijn sequences with lexicographically minimum label. (C) 2007 Elsevier B.V. All rights reserved.
Address [Moreno, Eduardo] Univ Adolfo Ibanez, Sch Engn, Santiago, Chile, Email: mmatamal@dim.uchile.cl
Corporate Author Thesis
Publisher Elsevier Science Bv Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0012-365x ISBN Medium
Area Expedition Conference
Notes WOS:000269600400007 Approved
Call Number UAI @ eduardo.moreno @ Serial 58
Permanent link to this record
 

 
Author (up) Matus, O.; Barrera, J.; Moreno, E.; Rubino, G.
Title On the Marshall-Olkin Copula Model for Network Reliability Under Dependent Failures Type
Year 2019 Publication IEEE Transactions On Reliability Abbreviated Journal IEEE Trans. Reliab.
Volume 68 Issue 2 Pages 451-461
Keywords Copula theory; failure analysis; network design; optimization methods; reliability
Abstract The Marshall-Olkin (MO) copulamodel has emerged as the standard tool for capturing dependence between components in failure analysis in reliability. In this model, shocks arise at exponential random times, that affect one or several components inducing a natural correlation in the failure process. However, because the number of parameter of the model grows exponentially with the number of components, MO suffers of the “curse of dimensionality.” MO models are usually intended to be applied to design a network before its construction; therefore, it is natural to assume that only partial information about failure behavior can be gathered, mostly from similar existing networks. To construct such an MO model, we propose an optimization approach to define the shock's parameters in the MO copula, in order to match marginal failures probabilities and correlations between these failures. To deal with the exponential number of parameters of this problem, we use a column-generation technique. We also discuss additional criteria that can be incorporated to obtain a suitable model. Our computational experiments show that the resulting MO model produces a close estimation of the network reliability, especially when the correlation between component failures is significant.
Address [Matus, Omar; Barrera, Javiera; Moreno, Eduardo] Univ Adolfo Ibanez, Fac Engn & Sci, Santiago 7941169, Chile, Email: omar.matus@edu.uai.cl;
Corporate Author Thesis
Publisher Ieee-Inst Electrical Electronics Engineers Inc Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0018-9529 ISBN Medium
Area Expedition Conference
Notes WOS:000470826100005 Approved
Call Number UAI @ eduardo.moreno @ Serial 1027
Permanent link to this record