Home  << 1 2 >> 
AlvarezMiranda, E., & Pereira, J. (2017). Designing and constructing networks under uncertainty in the construction stage: Definition and exact algorithmic approach. Comput. Oper. Res., 81, 178–191.
Abstract: The present work proposes a novel Network Optimization problem whose core is to combine both network design and network construction scheduling under uncertainty into a single twostage robust optimization model. The firststage decisions correspond to those of a classical network design problem, while the secondstage decisions correspond to those of a network construction scheduling problem (NCS) under uncertainty. The resulting problem, which we will refer to as the TwoStage Robust Network Design and Construction Problem (2SRNDC), aims at providing a modeling framework in which the design decision not only depends on the design costs (e.g., distances) but also on the corresponding construction plan (e.g., time to provide service to costumers). We provide motivations, mixed integer programming formulations, and an exact algorithm for the 2SRNDC. Experimental results on a large set of instances show the effectiveness of the model in providing robust solutions, and the capability of the proposed algorithm to provide good solutions in reasonable running times. (C) 2017 Elsevier Ltd. All rights reserved.

AlvarezMiranda, E., & Pereira, J. (2019). On the complexity of assembly line balancing problems. Comput. Oper. Res., 108, 182–186.
Abstract: Assembly line balancing is a family of combinatorial optimization problems that has been widely studied in the literature due to its simplicity and industrial applicability. Most line balancing problems are NPhard as they subsume the bin packing problem as a special case. Nevertheless, it is common in the line balancing literature to cite [A. Gutjahr and G. Nemhauser, An algorithm for the line balancing problem, Management Science 11 (1964) 308315] in order to assess the computational complexity of the problem. Such an assessment is not correct since the work of Gutjahr and Nemhauser predates the concept of NPhardness. This work points at over 50 publications since 1995 with the aforesaid error. (C) 2019 Elsevier Ltd. All rights reserved.
Keywords: Line balancing; Complexity; Bin packing

AlvarezMiranda, E., Pereira, J., & Vila, M. (2023). Analysis of the simple assembly line balancing problem complexity. Comput. Oper. Res., 159, 106323.
Abstract: The simple assembly line balancing problem (SALBP) involves the determination of the assignment of elementary assembly operations to the workstations of the assembly line for the manufacture of a final product, with the objective of maximising assembly efficiency. In addition to its practicality, the SALBP can be considered as an extension of the bin packing problem (BPP) to account for the precedence relations between items. These constraints introduce an ordering component to the problem, which increases the complexity of SALBP resolution. However, previous studies indicated that precedence constraints do not play an important role in the capacity of stateoftheart procedures to solve benchmark instances to optimality. In this study, we analysed the influences of different features of an SALBP instance on the performance of stateoftheart solution methods for the abovementioned problem. First, we provide an alternative proof of complexity for the SALBP that uses precedence constraints to demonstrate its nondeterministic polynomial time (NP)complete status, followed by a new set of benchmark instances directed towards an empirical analysis of the different features of SALBP instances. The experimental results revealed that the packing features of the SALBP are a major source of the perceived difficulty for any instance; however, precedence constraints play a role in the performance of these solution procedures. Specifically, the number of precedence constraints plays an important role in the results obtained from stateoftheart methods. In addition to the analysis, certain issues that were identified in the publicly available implementations of the stateoftheart method for resolving this problem were addressed in this study.

Averbakh, I., & Pereira, J. (2021). Tree optimization based heuristics and metaheuristics in network construction problems. Comput. Oper. Res., 128, 105190.
Abstract: We consider a recently introduced class of network construction problems where edges of a transportation network need to be constructed by a server (construction crew). The server has a constant construction speed which is much lower than its travel speed, so relocation times are negligible with respect to construction times. It is required to find a construction schedule that minimizes a nondecreasing function of the times when various connections of interest become operational. Most problems of this class are strongly NPhard on general networks, but are often treeefficient, that is, polynomially solvable on trees. We develop a generic local search heuristic approach and two metaheuristics (Iterated Local Search and Tabu Search) for solving treeefficient network construction problems on general networks, and explore them computationally. Results of computational experiments indicate that the methods have excellent performance.
Keywords: Network design; Scheduling; Network construction; Heuristics; Metaheuristics; Local search

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., Mondschein, S., Canessa, G., & RojasZalazar, D. (2020). Operating room scheduling under waiting time constraints: the Chilean GES plan. Ann. Oper. Res., 286(12), 501–527.
Abstract: In 2000, Chile introduced profound health reforms to achieve a more equitable and fairer system (GES plan). The reforms established a maximum waiting time between diagnosis and treatment for a set of diseases, described as an opportunity guarantee within the reform. If the maximum waiting time is exceeded, the patient is referred to another (private) facility and receives a voucher to cover the additional expenses. This voucher is paid by the health provider that had to do the procedure, which generally is a public hospital. In general, this reform has improved the service for patients with GES pathologies at the expense of patients with nonGES pathologies. These new conditions create a complicated planning scenario for hospitals, in which the hospital's OR Manager must balance the fulfillment of these opportunity guarantees and the timely service of patients not covered by the guarantee. With the collaboration of the Instituto de Neurocirugia, in Santiago, Chile, we developed a mathematical model based on stochastic dynamic programming to schedule surgeries in order to minimize the cost of referrals to the private sector. Given the large size of the state space, we developed an heuristic to compute good solutions in reasonable time and analyzed its performance. Our experimental results, with both simulated and real data, show that our algorithm performs close to optimum and improves upon the current practice. When we compared the results of our heuristic against those obtained by the hospital's OR manager in a simulation setting with real data, we reduced the overtime from occurring 21% of the time to zero, and the nonGES average waiting list's length from 71 to 58 patients, without worsening the average throughput.
Keywords: Scheduling; Operating theater; Operating room scheduling

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

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.

ColiniBaldeschi, R., Cominetti, R., Mertikopoulos, P., & Scarsini, M. (2020). When Is Selfish Routing Bad? The Price of Anarchy in Light and Heavy Traffic. Oper. Res., 68(2), 411–434.
Abstract: This paper examines the behavior of the price of anarchy as a function of the traffic inflow in nonatomic congestion games with multiple origin/destination (O/D) pairs. Empirical studies in realworld networks show that the price of anarchy is close to 1 in both light and heavy traffic, thus raising the following question: can these observations be justified theoretically? We first show that this is not always the case: the price of anarchy may remain a positive distance away from 1 for all values of the traffic inflow, even in simple threelink networks with a single O/D pair and smooth, convex costs. On the other hand, for a large class of cost functions (including all polynomials) and inflow patterns, the price of anarchy does converge to 1 in both heavy and light traffic, irrespective of the network topology and the number of O/D pairs in the network. We also examine the rate of convergence of the price of anarchy, and we show that it follows a power law whose degree can be computed explicitly when the network's cost functions are polynomials.

Cominetti, R., Correa, J., & Olver, N. (2022). LongTerm Behavior of Dynamic Equilibria in Fluid Networks. Oper. Res., 70(1), 516–526.
Abstract: A fluid queuing network constitutes one of the simplest models in which to study flow dynamics over a network. In this model we have a single sourcesink pair, and each link has a pertimeunit capacity and a transit time. A dynamic equilibrium (or equilibrium flow over time) is a flow pattern over time such that no flow particle has incentives to unilaterally change its path. Although the model has been around for almost 50 years, only recently results regarding existence and characterization of equilibria have been obtained. In particular, the longterm behavior remains poorly understood. Our main result in this paper is to show that, under a natural (and obviously necessary) condition on the queuing capacity, a dynamic equilibrium reaches a steady state (after which queue lengths remain constant) in finite time. Previously, it was not even known that queue lengths would remain bounded. The proof is based on the analysis of a rather nonobvious potential function that turns out to be monotone along the evolution of the equilibrium. Furthermore, we show that the steady state is characterized as an optimal solution of a certain linear program. When this program has a unique solution, which occurs generically, the longterm behavior is completely predictable. On the contrary, if the linear program has multiple solutions, the steady state is more difficult to identify as it depends on the whole temporal evolution of the equilibrium.
Keywords: flows over time; dynamic equilibria; steady state

Cominetti, R., Quattropani, M., & Scarsini, M. (2022). The BuckPassing Game. Math. Oper. Res., Early Access.
Abstract: We consider two classes of games in which players are the vertices of a directed graph. Initially, nature chooses one player according to some fixed distribution and gives the player a buck. This player passes the buck to one of the player's outneighbors in the graph. The procedure is repeated indefinitely. In one class of games, each player wants to minimize the asymptotic expected frequency of times that the player receives the buck. In the other class of games, the player wants to maximize it. The PageRank game is a particular case of these maximizing games. We consider deterministic and stochastic versions of the game, depending on how players select the neighbor to which to pass the buck. In both cases, we prove the existence of pure equilibria that do not depend on the initial distribution; this is achieved by showing the existence of a generalized ordinal potential. If the graph on which the game is played admits a Hamiltonian cycle, then this is the outcome of priorfive Nash equilibrium in the minimizing game. For the minimizing game, we then use the price of anarchy and stability to measure fairness of these equilibria.

Cominetti, R., Scarsini, M., Schroder, M., & StierMoses, N. (2022). Approximation and Convergence of Large Atomic Congestion Games. Math. Oper. Res., Early Access.
Abstract: We consider the question of whether and in what sense, Wardrop equilibria provide a good approximation for Nash equilibria in atomic unsplittable congestion games with a large number of small players. We examine two different definitions of small players. In the first setting, we consider games in which each player's weight is small. We prove that when the number of players goes to infinity and their weights to zero, the random flows in all (mixed) Nash equilibria for the finite games converge in distribution to the set of Wardrop equilibria of the corresponding nonatomic limit game. In the second setting, we consider an increasing number of players with a unit weight that participate in the game with a decreasingly small probability. In this case, the Nash equilibrium flows converge in total variation toward Poisson random variables whose expected values are War drop equilibria of a different nonatomic game with suitably defined costs. The latter can be viewed as symmetric equilibria in a Poisson game in the sense of Myerson, establishing a plausible connection between the Wardrop model for routing games and the stochastic fluctuations observed in real traffic. In both settings, we provide explicit approximation bounds, and we study the convergence of the price of anarchy. Beyond the case of congestion games, we prove a general result on the convergence of large games with random players toward Poisson games.

de Mateo, F., Coelli, T., & O'Donnell, C. (2006). Optimal paths and costs of adjustment in dynamic DEA models: with application to chilean department stores. Ann. Oper. Res., 145(1), 211–227.
Abstract: In this paper we propose a range of dynamic data envelopment analysis (DEA) models which allow information on costs of adjustment to be incorporated into the DEA framework. We first specify a basic dynamic DEA model predicated on a number or simplifying assumptions. We then outline a number of extensions to this model to accommodate asymmetric adjustment costs, nonstatic output quantities, nonstatic input prices, and nonstatic costs of adjustment, technological change, quasifixed inputs and investment budget constraints. The new dynamic DEA models provide valuable extra information relative to the standard static DEA modelsthey identify an optimal path of adjustment for the input quantities, and provide a measure of the potential cost savings that result from recognising the costs of adjusting input quantities towards the optimal point. The new models are illustrated using data relating to a chain of 35 retail department stores in Chile. The empirical results illustrate the wealth of information that can be derived from these models, and clearly show that static models overstate potential cost savings when adjustment costs are nonzero.
Keywords: cost of adjustment; dynamic DEA; path of adjustment

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.

Gonzalez, E., Epstein, L. D., & Godoy, V. (2012). Optimal number of bypasses: minimizing cost of calls to wireless phones under Calling Party Pays. Ann. Oper. Res., 199(1), 179–191.
Abstract: In telecommunications, Calling Party Pays is a billing formula that prescribes that the person who makes the call pays its full cost. Under CPP landline to wireless phone calls have a high cost for many organizations. They can reduce this cost at the expense of installing wireless bypasses to replace landline to wireless traffic with wirelesstowireless traffic, when the latter is cheaper than the former. Thus, for a given timehorizon, the cost of the project is a tradeoff between traffic towireless and the number of bypasses. We present a method to determine the number of bypasses that minimizes the expected cost of the project. This method takes into account hourly varying traffic intensity. Our method takes advantage of parallels with inventory models for rental items. Examples illustrate the economic value of our approach.

Lagos, F., Boland, N., & Savelsbergh, M. (2022). Dynamic discretization discovery for solving the Continuous Time Inventory Routing Problem with OutandBack Routes. Comput. Oper. Res., 141, 105686.
Abstract: In time dependent models, the objective is to find the optimal times (continuous) at which activities occur and resources are utilized. These models arise whenever a schedule of activities needs to be constructed. A common approach consists of discretizing the planning time and then restricting the decisions to those time points. However, this approach leads to very large formulations that are intractable in practice. In this work, we study the Continuous Time Inventory Routing Problem with OutandBack Routes (CIRPOB). In this problem, a company manages the inventory of its customers, resupplying a single product from a single facility during a finite time horizon. The product is consumed at a constant rate (product per unit of time) by each customer. The customers have local storage capacity. The goal is to find the minimum cost delivery plan with outandback routes only that ensures that none of the customers run out of product during the planning period. We study the Dynamic Discovery Discretization algorithm (DDD) to solve the CIRPOB by using partially constructed timeexpanded networks. This method iteratively discovers time points needed in the network to find optimal continuous time solutions. We test this method by using randomly generated instances in which we find provable optimal solutions.
Keywords: NETWORK DESIGN; CUT ALGORITHM; DECOMPOSITION; POLICIES

Lespay, H., & Suchan, K. (2022). Territory Design for the MultiPeriod Vehicle Routing Problem with Time Windows. Comput. Oper. Res., 145, 105866.
Abstract: This study introduces the Territory Design for the MultiPeriod Vehicle Routing Problem with Time Windows (TDMPVRPTW) problem, motivated by a realworld application at a food company's distribution center. This problem deals with the design of contiguous and compact territories for delivery of orders from a depot to a set of customers, with time windows, over a multiperiod planning horizon. Customers and their demands vary over time. The problem is modeled as a mixedinteger linear program (MILP) and solved by a proposed heuristic. The heuristic solutions are compared with the proposed MILP solutions on a set of small artificial instances and the food company's solutions on a set of realworld instances. Computational results show that the proposed algorithm can yield highquality solutions within moderate running times. A methodology is proposed in which the territories computed by the proposed heuristic on the past demand of one month are used for the operational routing during the following month, in which the demand is known only one day in advance. An evaluation shows that the territories obtained with our methodology would have led to levels of service significantly better than the ones that were experienced by the company, using a significantly lower number of vehicles to execute the deliveries.

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%.

Moreno, S., Pereira, J., & Yushimito, W. (2020). A hybrid Kmeans and integer programming method for commercial territory design: a case study in meat distribution. Ann. Oper. Res., 286(12), 87–117.
Abstract: The objective of territorial design for a distribution company is the definition of geographic areas that group customers. These geographic areas, usually called districts or territories, should comply with operational rules while maximizing potential sales and minimizing incurred costs. Consequently, territorial design can be seen as a clustering problem in which clients are geographically grouped according to certain criteria which usually vary according to specific objectives and requirements (e.g. costs, delivery times, workload, number of clients, etc.). In this work, we provide a novel hybrid approach for territorial design by means of combining a Kmeansbased approach for clustering construction with an optimization framework. The Kmeans approach incorporates the novelty of using tour length approximation techniques to satisfy the conditions of a pork and poultry distributor based in the region of Valparaiso in Chile. The resulting method proves to be robust in the experiments performed, and the Valparaiso case study shows significant savings when compared to the original solution used by the company.
Keywords: Territorial design; Clustering; Kmeans; Integer programming; Case study
