IDEAS home Printed from https://ideas.repec.org/p/hal/journl/halshs-02396784.html
   My bibliography  Save this paper

Using Column Generation To Solve A Coal Blending Problem

Author

Listed:
  • Daniel de Wolf

    (TVES - Territoires, Villes, Environnement & Société - ULR 4477 - ULCO - Université du Littoral Côte d'Opale - Université de Lille, ULCO - Université du Littoral Côte d'Opale)

  • Stéphane Auray

    (EQUIPPE - Economie Quantitative, Intégration, Politiques Publiques et Econométrie - Université de Lille, Sciences et Technologies - Université de Lille, Sciences Humaines et Sociales - PRES Université Lille Nord de France - Université de Lille, Droit et Santé, ULCO - Université du Littoral Côte d'Opale)

  • Yves Smeers

    (CORE - Center of Operation Research and Econometrics [Louvain] - UCL - Université Catholique de Louvain = Catholic University of Louvain, UCLouvain)

Abstract

In this paper, we formulate and solve a real life coal blending problem using a Column Generation Approach. The objective of the model is to prescribe optimal mixes of coal to produce coke. The problem is formulated as a mixed integer program. It involves various types of constraints arising from technical considerations of the blending process. The model also incorporates nonlinear constraints. It results in a large-scale problem that cannot be solved by classical operations research methods. Defining three heuristic methods based on column generation techniques, this paper proposes reasonable solutions for the industry.

Suggested Citation

  • Daniel de Wolf & Stéphane Auray & Yves Smeers, 2015. "Using Column Generation To Solve A Coal Blending Problem," Post-Print halshs-02396784, HAL.
    • Handle: RePEc:hal:journl:halshs-02396784
    DOI: 10.1051/ro/2014033
    Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-02396784
    as

    Download full text from publisher

    File URL: https://shs.hal.science/halshs-02396784/document
    Download Restriction: no
    File URL: https://libkey.io/10.1051/ro/2014033?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. François Vanderbeck, 2000. "On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm," Operations Research, INFORMS, vol. 48(1), pages 111-128, February.
    2. Sarker, Ruhul A. & Gunn, Eldon A., 1997. "A simple SLP algorithm for solving a class of nonlinear programs," European Journal of Operational Research, Elsevier, vol. 101(1), pages 140-154, August.
    3. Vanderbeck, F. & Wolsey, L. A., 1996. "An exact algorithm for IP column generation," LIDAM Reprints CORE 1242, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. DE WOLF, Daniel, 2003. "Using column generation to solve an industrial mixing problem," LIDAM Discussion Papers CORE 2003042, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Harvey J. Greenberg, 1995. "Analyzing the Pooling Problem," INFORMS Journal on Computing, INFORMS, vol. 7(2), pages 205-217, May.
    6. F J Vasko & D D Newhart & A D Strauss, 2005. "Coal blending models for optimum cokemaking and blast furnace operation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(3), pages 235-243, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. DE WOLF, Daniel, 2003. "Using column generation to solve an industrial mixing problem," LIDAM Discussion Papers CORE 2003042, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Michelle L. Blom & Christina N. Burt & Adrian R. Pearce & Peter J. Stuckey, 2014. "A Decomposition-Based Heuristic for Collaborative Scheduling in a Network of Open-Pit Mines," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 658-676, November.
    3. Sung, Inkyung & Lee, Taesik, 2016. "Optimal allocation of emergency medical resources in a mass casualty incident: Patient prioritization by column generation," European Journal of Operational Research, Elsevier, vol. 252(2), pages 623-634.
    4. Zheng Zhang & Brian T. Denton & Xiaolan Xie, 2020. "Branch and Price for Chance-Constrained Bin Packing," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 547-564, July.
    5. Amy Cohn, 2006. "Composite-variable modeling for service parts logistics," Annals of Operations Research, Springer, vol. 144(1), pages 17-32, April.
    6. Jans, Raf, 2010. "Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems," European Journal of Operational Research, Elsevier, vol. 204(2), pages 251-254, July.
    7. Daniel Villeneuve & Jacques Desrosiers & Marco Lübbecke & François Soumis, 2005. "On Compact Formulations for Integer Programs Solved by Column Generation," Annals of Operations Research, Springer, vol. 139(1), pages 375-388, October.
    8. Marc Peeters & Zeger Degraeve, 2004. "The Co-Printing Problem: A Packing Problem with a Color Constraint," Operations Research, INFORMS, vol. 52(4), pages 623-638, August.
    9. Belií«n, Jeroen & Demeulemeester, Erik, 2008. "A branch-and-price approach for integrating nurse and surgery scheduling," European Journal of Operational Research, Elsevier, vol. 189(3), pages 652-668, September.
    10. Subhash C. Sarin & Hanif D. Sherali & Seon Ki Kim, 2014. "A branch‐and‐price approach for the stochastic generalized assignment problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(2), pages 131-143, March.
    11. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    12. Guglielmo Lulli & Suvrajeet Sen, 2004. "A Branch-and-Price Algorithm for Multistage Stochastic Integer Programming with Application to Stochastic Batch-Sizing Problems," Management Science, INFORMS, vol. 50(6), pages 786-796, June.
    13. Degraeve, Z. & Jans, R.F., 2003. "A New Dantzig-Wolfe Reformulation And Branch-And-Price Algorithm For The Capacitated Lot Sizing Problem With Set Up Times," ERIM Report Series Research in Management ERS-2003-010-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    14. Valerio de Carvalho, J. M., 2002. "LP models for bin packing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 141(2), pages 253-273, September.
    15. François Vanderbeck, 2000. "Exact Algorithm for Minimising the Number of Setups in the One-Dimensional Cutting Stock Problem," Operations Research, INFORMS, vol. 48(6), pages 915-926, December.
    16. Gamvros, Ioannis & Raghavan, S., 2012. "Multi-period traffic routing in satellite networks," European Journal of Operational Research, Elsevier, vol. 219(3), pages 738-750.
    17. Marjan van den Akker & Han Hoogeveen & Steef van de Velde, 2002. "Combining Column Generation and Lagrangean Relaxation to Solve a Single-Machine Common Due Date Problem," INFORMS Journal on Computing, INFORMS, vol. 14(1), pages 37-51, February.
    18. Gökalp Erbeyoğlu & Ümit Bilge, 2016. "PSO-based and SA-based metaheuristics for bilinear programming problems: an application to the pooling problem," Journal of Heuristics, Springer, vol. 22(2), pages 147-179, April.
    19. Belien, Jeroen & Demeulemeester, Erik, 2006. "Scheduling trainees at a hospital department using a branch-and-price approach," European Journal of Operational Research, Elsevier, vol. 175(1), pages 258-278, November.
    20. Yifu Chen & Christos T. Maravelias, 2020. "Preprocessing algorithm and tightening constraints for multiperiod blend scheduling: cost minimization," Journal of Global Optimization, Springer, vol. 77(3), pages 603-625, July.

    More about this item

    Keywords

    Column generation; coal blending;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:hal:journl:halshs-02396784. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.