Advanced search
Publication Cover
Mining Technology
Transactions of the Institutions of Mining and Metallurgy
Volume 130, 2021 - Issue 1
Journal homepage
196
Views
1
CrossRef citations to date
0
Altmetric
Articles

An efficient algorithm for the precedence constraint knapsack problem with reference to large-scale open-pit mining pushback design

Nayan MaitiDepartment of Mining Engineering, Indian Institute of Technology Kharagpur, Kharagpur, IndiaView further author information
,
Pranjal PathakDepartment of Mining Engineering, Indian Institute of Technology Kharagpur, Kharagpur, IndiaView further author information
&
Biswajit SamantaDepartment of Mining Engineering, Indian Institute of Technology Kharagpur, Kharagpur, IndiaCorrespondence[email protected]
View further author information
Pages 8-21 | Received 02 Sep 2020, Accepted 15 Dec 2020, Published online: 14 Jan 2021

References

  • Bienstock D, Zuckerberg M. 2010. Solving LP relaxations of large-scale precedence constrained problems. In: Eisenbrand F, Shepherd FB, editor. Integer programming and combinatorial optimization, June 9–11. Lausanne, Switzerland: Springer; p. 1–14.
  • Boland N, Bley A, Fricke C, Froyland G, Sotirov R. 2012. Clique-based facets for the precedence constrained knapsack problem. Math Program. 133(1–2):481–511.
  • Boyd EA. 1993. Polyhedral results for the precedence-constrained knapsack problem. Discrete Appl Math. 41(3):185–201.
  • Byun J, Dimitrakopoulos R. 2013. An efficient algorithm for the LP relaxation of the maximal closure problem with a capacity constrain. Cahiers du GERAD, G-2013-60.
  • Caccetta L, Hill SP. 2003. An application of branch and cut to open pit mine scheduling. J Glob Optim. 27(2–3):349–365.
  • Chandran BG, Hochbaum DS. 2009. A computational study of the pseudoflow and push-relabel algorithms for the maximum flow problem. Oper Res. 57(2):358–376.
  • Chicoisne R, Espinoza D, Goycoolea M, Moreno E, Rubio E. 2012. A new algorithm for the open-pit mine production scheduling problem. Oper Res. 60(3):517–528.
  • Dagdelen K. 1985. Optimum multi-period open pit mine production scheduling by Lagrangian parameterization [unpublished PhD thesis]. Colorado School of Mines, Golden, Colorado, p. 1–325.
  • Elkington T, Durham R. 2011. Integrated open pit pushback selection and production capacity optimization. J Min Sci. 47(2):177–190.
  • Espinoza D, Goycoolea M, Moreno E, Newman A. 2013. MineLib: a library of open pit mining problems. Ann Oper Res. 206 (1): 93–114.
  • Gallo G, Grigoriadis MD, Tarjan RE. 1989. A fast parametric maximum flow algorithm and applications. SIAM J Comput. 18(1):30–55.
  • Hiriart-Urruty JB, Lemaréchal C. 1993. Convex analysis and minimization algorithms, Vols. 1 and 2. Berlin: Springer Verlag.
  • Hochbaum DS, Chen A. 2000. Performance analysis and best implementations of old and new algorithms for the open-pit mining problem. Oper Res. 48(6):894–914.
  • Lerchs H, Grossman I. 1965. Optimum design of open-pit mines. CIM Bull. 12:47–54.
  • Meagher C, Dimitrakopoulos R, Avis D. 2014. Optimized open pit mine design, pushbacks and the gap problem – a review. J Min Sci. 50(3):508–526.
  • Meagher C, Sabour SA, Dimitrakopoulos R. 2009. Pushback design of open pit mines under geological and market uncertainties. In Orebody modelling and strategic mine planning. p. 297–304.
  • Osanloo M, Gholamnejad J, Karimi B. 2008. Long-term open pit mine production planning: a review of models and algorithms. Int J Min Reclam Environ. 22(1):3–35.
  • Park K, Park S. 1997. Lifting cover inequalities for the precedence-constrained knapsack problem. Discrete Appl Math. 72(3):219–241.
  • Picard JC. 1976. Maximal closure of a graph and applications to combinatorial problems. Manage Sci. 22(11):1268–1272.
  • Tachefine B, Soumis F. 1997. Maximal closure on a graph with resource constraints. Comput Oper Res. 24(10):981–990.
  • Tolwinski B. 1998. Scheduling production for open pit mines. International Symposium Computer Applications in the Minerals Industries; UK. p. 651–662.
  • Zhao X, Luh P. 2002. New bundle methods for solving Lagrangian relaxation dual problems. J Optim Theory Appl. 113(2):373–397.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.