Home  << 1 2 >> 
Acuna, V., Ferreira, C. E., Freire, A. S., & Moreno, E. (2014). Solving the maximum edge biclique packing problem on unbalanced bipartite graphs. Discret Appl. Math., 164, 2–12.
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 branchandprice 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.

Barrera, J., Cancela, H., & Moreno, E. (2015). Topological optimization of reliable networks under dependent failures. Oper. Res. Lett., 43(2), 132–136.
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 commoncause failure model, dependencies between failures can affect the optimal design. We also provide an integerprogramming 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.

Barrera, J., Carrasco, R. A., & Moreno, E. (2020). Realtime fleet management decision support system with security constraints. TOP, 28(3), 728–748.
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 reallife noisy GPS data. Through the use of historical data, the performance of this decision support system is studied, validating that it works under the reallife 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.

Barrera, J., HomemDeMello, T., Moreno, E., Pagnoncelli, B. K., & Canessa, G. (2016). Chanceconstrained problems and rare events: an importance sampling approach. Math. Program., 157(1), 153–189.
Abstract: We study chanceconstrained problems in which the constraints involve the probability of a rare event. We discuss the relevance of such problems and show that the existing samplingbased 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 SAAIS 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.

Barrera, J., Moreno, E., & Varas, S. (2020). A decomposition algorithm for computing income taxes with passthrough entities and its application to the Chilean case. Ann. Oper. Res., 286(12), 545–557.
Abstract: Income tax systems with “passthrough” 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.
Keywords: Income taxes; Markov processes; Networks; Algorithms

Canessa, G., Moreno, E., & Pagnoncelli, B. K. (2021). The riskaverse ultimate pit problem. Optim. Eng., Early access, 24 pp.
Abstract: In this work, we consider a riskaverse 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 twostage stochastic programming formulation of the problem, including an efficient approximation scheme to solve it. We illustrate our approach in a small selfconstructed example, and apply our approximation scheme to a realworld section of the Andina mine, in Chile.
Keywords: Ultimate pit; Mining; Riskaverse optimization; Integer programming

Chicoisne, R., Espinoza, D., Goycoolea, M., Moreno, E., & Rubio, E. (2012). A New Algorithm for the OpenPit Mine Production Scheduling Problem. Oper. Res., 60(3), 517–528.
Abstract: For the purpose of production scheduling, openpit mines are discretized into threedimensional 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 (310 million blocks, 1520 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 wellknown integer programming formulation of the problem that we refer to as CPIT. We propose a new decomposition method for solving the linear programming relaxation (LP) of CPIT when there is a single capacity constraint per time period. This algorithm is based on exploiting the structure of the precedenceconstrained 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 realsized mineplanning 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 12% 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.

Cortes, C. E., JaraMoroni, P., Moreno, E., & Pineda, C. (2013). Stochastic transit equilibrium. Transp. Res. Pt. BMethodol., 51, 29–44.
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 invehicle 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 commonlines 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 commonlines 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 realsize network case as the next step of this research. (C) 2013 Elsevier Ltd. All rights reserved.

Coudert, D., Luedtke, J., Moreno, E., & Priftis, K. (2018). Computing and maximizing the exact reliability of wireless backhaul networks. In Electronic Notes in Discrete Mathematics (Vol. 64, pp. 85–94). 
Espinoza, D., & Moreno, E. (2014). A primaldual aggregation algorithm for minimizing conditional valueatrisk in linear programs. Comput. Optim. Appl., 59(3), 617–638.
Abstract: Recent years have seen growing interest in coherent risk measures, especially in Conditional ValueatRisk (). 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 primaldual 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, cutgeneration schemes and other problemspecific approaches available in commercial software. Extensive computational experiments are performed on portfolio and general LP instances.

Espinoza, D., Goycoolea, M., & Moreno, E. (2015). The precedence constrained knapsack problem: Separating maximally violated inequalities. Discret Appl. Math., 194, 65–80.
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.

Espinoza, D., Goycoolea, M., Moreno, E., & Newman, A. (2013). MineLib: a library of open pit mining problems. Ann. Oper. Res., 206(1), 93–114.
Abstract: Similar to the mixedinteger 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 threedimensional 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.

Freire, A. S., Moreno, E., & Vielma, J. P. (2012). An integer linear programming approach for bilinear integer programming. Oper. Res. Lett., 40(2), 74–77.
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 realworld product bundling problems. (C) 2011 Elsevier B.V. All rights reserved.

Freire, A. S., Moreno, E., & Yushimito, W. F. (2016). A branchandbound algorithm for the maximum capture problem with random utilities. Eur. J. Oper. Res., 252(1), 204–212.
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 wellknow 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 MixedInteger 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 branchandbound 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 nonlinear 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 largescale real instance of the problem, which comes from an application in parkandride facility location, where our proposed branchandbound algorithm was the most effective method for solving this type of problem. (C) 2015 Elsevier B.V. All rights reserved.

Lagos, G., Espinoza, D., Moreno, E., & Vielma, J. P. (2015). Restricted risk measures and robust optimization. Eur. J. Oper. Res., 241(3), 771–782.
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 ValueatRisk. (C) 2014 Elsevier B.V. All rights reserved.

Letelier, O. R., Espinoza, D., Goycoolea, M., Moreno, E., & Munoz, G. (2020). Production Scheduling for Strategic Open Pit Mine Planning: A MixedInteger Programming Approach. Oper. Res., 68(5), 1425–1444.
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 mixedinteger programming, the number of blocks used to represent realworld 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 benchphase 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 branchandbound algorithm on the problems with larger gaps, we are able to further reduce the average from 1.52% to 0.71%.

Ljubic, I., & Moreno, E. (2018). Outer approximation and submodular cuts for maximum capture facility location problems with random utilities. Eur. J. Oper. Res., 266(1), 46–56.
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 branchandcut approach for this family of difficult mixedinteger nonlinear problems. Our approach combines two types of cutting planes that exploit particular properties of the objective function: the first one are the outerapproximation 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 branchandcut drastically outperforms stateoftheart 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.

Matamala, M., & Moreno, E. (2009). Minimum Eulerian circuits and minimum de Bruijn sequences. Discret. Math., 306(17), 5298–5304.
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 NPcomplete 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.
Keywords: Eulerian circuits; Labelled digraph; De Bruijn sequences

Matus, O., Barrera, J., Moreno, E., & Rubino, G. (2019). On the MarshallOlkin Copula Model for Network Reliability Under Dependent Failures. IEEE Trans. Reliab., 68(2), 451–461.
Abstract: The MarshallOlkin (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 columngeneration 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.

Moreno, E., Beghelli, A., & Cugini, F. (2017). Traffic engineering in segment routing networks. Comput. Netw., 114, 23–31.
Abstract: Segment routing (SR) has been recently proposed as an alternative traffic engineering (TE) technology enabling relevant simplifications in control plane operations. In the literature, preliminary investigations on SR have focused on label encoding algorithms and experimental assessments, without carefully addressing some key aspects of SR in terms of the overall network TE performance. In this study, ILP models and heuristics are proposed and successfully utilized to assess the TE performance of SRbased packet networks. Results show that the default SR behavior of exploiting equal cost multiple paths (ECMP) may lead to several drawbacks, including higher network resource utilization with respect to cases where ECMP is avoided. Moreover, results show that, by properly performing segment list computations, it is possible to achieve very effective TE solutions by just using a very limited number of stacked labels, thus successfully exploiting the benefits of the SR technology. (C) 2017 Elsevier B.V. All rights reserved.
Keywords: Segment routing; Integer Linear Programming; Heuristic
