Home << 1 >>
List View
 | 
Citations
 | 
Details
   web
Records
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) 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) 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) Munoz, G.; Espinoza, D.; Goycoolea, M.; Moreno, E.; Queyranne, M.; Rivera Letelier, O.
Title A study of the Bienstock-Zuckerberg algorithm: applications in mining and resource constrained project scheduling Type
Year 2018 Publication Computational Optimization And Applications Abbreviated Journal Comput. Optim. Appl.
Volume 69 Issue 2 Pages 501-534
Keywords Column generation; Dantzig-Wolfe; Optimization; RCPSP
Abstract We study a Lagrangian decomposition algorithm recently proposed by Dan Bienstock and Mark Zuckerberg for solving the LP relaxation of a class of open pit mine project scheduling problems. In this study we show that the Bienstock-Zuckerberg (BZ) algorithm can be used to solve LP relaxations corresponding to a much broader class of scheduling problems, including the well-known Resource Constrained Project Scheduling Problem (RCPSP), and multi-modal variants of the RCPSP that consider batch processing of jobs. We present a new, intuitive proof of correctness for the BZ algorithm that works by casting the BZ algorithm as a column generation algorithm. This analysis allows us to draw parallels with the well-known Dantzig-Wolfe decomposition (DW) algorithm. We discuss practical computational techniques for speeding up the performance of the BZ and DW algorithms on project scheduling problems. Finally, we present computational experiments independently testing the effectiveness of the BZ and DW algorithms on different sets of publicly available test instances. Our computational experiments confirm that the BZ algorithm significantly outperforms the DW algorithm for the problems considered. Our computational experiments also show that the proposed speed-up techniques can have a significant impact on the solve time. We provide some insights on what might be explaining this significant difference in performance.
Address [Munoz, Gonzalo] Columbia Univ, Ind Engn & Operat Res, New York, NY USA, Email: marcos.goycoolea@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 0926-6003 ISBN Medium
Area Expedition Conference
Notes WOS:000426295000009 Approved
Call Number UAI @ eduardo.moreno @ Serial 835
Permanent link to this record
 
 
Author (up) Rivera Letelier, O.; 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
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
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 0030-364X ISBN Medium
Area Expedition Conference
Notes Approved
Call Number UAI @ eduardo.moreno @ Serial 1052
Permanent link to this record
 
 
Author (up) Rozas Andaur, J.M.; Ruz, G.A.; Goycoolea, M.
Title Predicting Out-of-Stock Using Machine Learning: An Application in a Retail Packaged Foods Manufacturing Company Type
Year 2021 Publication Electronics Abbreviated Journal Electronics
Volume 10 Issue 22 Pages 2787
Keywords out of stock; machine learning; classification algorithms; imbalance data; supply chain management; decision support; retail industry application
Abstract For decades, Out-of-Stock (OOS) events have been a problem for retailers and manufacturers. In grocery retailing, an OOS event is used to characterize the condition in which customers do not find a certain commodity while attempting to buy it. This paper focuses on addressing this problem from a manufacturer’s perspective, conducting a case study in a retail packaged foods manufacturing company located in Latin America. We developed two machine learning based systems to detect OOS events automatically. The first is based on a single Random Forest classifier with balanced data, and the second is an ensemble of six different classification algorithms. We used transactional data from the manufacturer information system and physical audits. The novelty of this work is our use of new predictor variables of OOS events. The system was successfully implemented and tested in a retail packaged foods manufacturer company. By incorporating the new predictive variables in our Random Forest and Ensemble classifier, we were able to improve their system’s predictive power. In particular, the Random Forest classifier presented the best performance in a real-world setting, achieving a detection precision of 72% and identifying 68% of the total OOS events. Finally, the incorporation of our new predictor variables allowed us to improve the performance of the Random Forest by 0.24 points in the F-measure.
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 2079-9292 ISBN Medium
Area Expedition Conference
Notes Approved
Call Number UAI @ alexi.delcanto @ Serial 1487
Permanent link to this record