IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v274y2019i1d10.1007_s10479-018-2827-x.html
   My bibliography  Save this article

On the complexity of the Unit Commitment Problem

Author

Listed:
  • Pascale Bendotti

    (Sorbonne Université, LIP6-CNRS (Laboratoire d’Informatique de Paris 6)
    EDF R&D)

  • Pierre Fouilhoux

    (Sorbonne Université, LIP6-CNRS (Laboratoire d’Informatique de Paris 6))

  • Cécile Rottner

    (Sorbonne Université, LIP6-CNRS (Laboratoire d’Informatique de Paris 6)
    EDF R&D)

Abstract

This article analyzes how the Unit Commitment Problem (UCP) complexity evolves with respect to the number n of units and T of time periods. A classical reduction from the knapsack problem shows that the UCP is NP-hard in the ordinary sense even for $$T=1$$ T = 1 . The main result of this article is that the UCP is strongly NP-hard. When the constraints are restricted to minimum up and down times, the UCP is shown to be polynomial for a fixed n. When either a unitary cost or amount of power is considered, the UCP is polynomial for $$T=1$$ T = 1 and strongly NP-hard for arbitrary T. The pricing subproblem commonly used in a UCP decomposition scheme is also shown to be strongly NP-hard for a subset of units.

Suggested Citation

  • Pascale Bendotti & Pierre Fouilhoux & Cécile Rottner, 2019. "On the complexity of the Unit Commitment Problem," Annals of Operations Research, Springer, vol. 274(1), pages 119-130, March.
    • Handle: RePEc:spr:annopr:v:274:y:2019:i:1:d:10.1007_s10479-018-2827-x
    DOI: 10.1007/s10479-018-2827-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-018-2827-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-018-2827-x?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Jonathan F. Bard, 1988. "Short-Term Scheduling of Thermal-Electric Generators Using Lagrangian Relaxation," Operations Research, INFORMS, vol. 36(5), pages 756-766, October.
    2. Antonio Frangioni & Claudio Gentile, 2006. "Solving Nonlinear Single-Unit Commitment Problems with Ramping Constraints," Operations Research, INFORMS, vol. 54(4), pages 767-775, August.
    3. Antonio Frangioni, 2005. "About Lagrangian Methods in Integer Optimization," Annals of Operations Research, Springer, vol. 139(1), pages 163-193, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Luis Montero & Antonio Bello & Javier Reneses, 2022. "A Review on the Unit Commitment Problem: Approaches, Techniques, and Resolution Methods," Energies, MDPI, vol. 15(4), pages 1-40, February.
    2. Layon Mescolin de Oliveira & Ivo Chaves da Silva Junior & Ramon Abritta, 2022. "Search Space Reduction for the Thermal Unit Commitment Problem through a Relevance Matrix," Energies, MDPI, vol. 15(19), pages 1-16, September.
    3. L. Alvarado-Barrios & A. Rodríguez del Nozal & A. Tapia & J. L. Martínez-Ramos & D. G. Reina, 2019. "An Evolutionary Computational Approach for the Problem of Unit Commitment and Economic Dispatch in Microgrids under Several Operation Modes," Energies, MDPI, vol. 12(11), pages 1-23, June.

    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. L. A. C. Roque & D. B. M. M. Fontes & F. A. C. C. Fontes, 2014. "A hybrid biased random key genetic algorithm approach for the unit commitment problem," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 140-166, July.
    2. Ogbe, Emmanuel & Li, Xiang, 2017. "A new cross decomposition method for stochastic mixed-integer linear programming," European Journal of Operational Research, Elsevier, vol. 256(2), pages 487-499.
    3. Luis Montero & Antonio Bello & Javier Reneses, 2022. "A Review on the Unit Commitment Problem: Approaches, Techniques, and Resolution Methods," Energies, MDPI, vol. 15(4), pages 1-40, February.
    4. C. Gentile & G. Morales-España & A. Ramos, 2017. "A tight MIP formulation of the unit commitment problem with start-up and shut-down constraints," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(1), pages 177-201, March.
    5. Pérez-Iribarren, E. & González-Pino, I. & Azkorra-Larrinaga, Z. & Gómez-Arriarán, I., 2020. "Optimal design and operation of thermal energy storage systems in micro-cogeneration plants," Applied Energy, Elsevier, vol. 265(C).
    6. Tadahiro Taniguchi & Koki Kawasaki & Yoshiro Fukui & Tomohiro Takata & Shiro Yano, 2015. "Automated Linear Function Submission-Based Double Auction as Bottom-up Real-Time Pricing in a Regional Prosumers’ Electricity Network," Energies, MDPI, vol. 8(7), pages 1-26, July.
    7. Guanglei Wang & Hassan Hijazi, 2018. "Mathematical programming methods for microgrid design and operations: a survey on deterministic and stochastic approaches," Computational Optimization and Applications, Springer, vol. 71(2), pages 553-608, November.
    8. Fatma Kılınç-Karzan, 2016. "On Minimal Valid Inequalities for Mixed Integer Conic Programs," Mathematics of Operations Research, INFORMS, vol. 41(2), pages 477-510, May.
    9. Xu, Qingyang & Sun, Feihu & Cai, Qiran & Liu, Li-Jing & Zhang, Kun & Liang, Qiao-Mei, 2022. "Assessment of the influence of demand-side responses on high-proportion renewable energy system: An evidence of Qinghai, China," Renewable Energy, Elsevier, vol. 190(C), pages 945-958.
    10. Adriaan Weijde & Benjamin Hobbs, 2011. "Locational-based coupling of electricity markets: benefits from coordinating unit commitment and balancing markets," Journal of Regulatory Economics, Springer, vol. 39(3), pages 223-251, June.
    11. Claudio Gambella & Joe Naoum-Sawaya & Bissan Ghaddar, 2018. "The Vehicle Routing Problem with Floating Targets: Formulation and Solution Approaches," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 554-569, August.
    12. de Queiroz, A.R. & Mulcahy, D. & Sankarasubramanian, A. & Deane, J.P. & Mahinthakumar, G. & Lu, N. & DeCarolis, J.F., 2019. "Repurposing an energy system optimization model for seasonal power generation planning," Energy, Elsevier, vol. 181(C), pages 1321-1330.
    13. Tonbari, Mohamed El & Ahmed, Shabbir, 2023. "Consensus-based Dantzig-Wolfe decomposition," European Journal of Operational Research, Elsevier, vol. 307(3), pages 1441-1456.
    14. Löschenbrand, Markus & Wei, Wei & Liu, Feng, 2018. "Hydro-thermal power market equilibrium with price-making hydropower producers," Energy, Elsevier, vol. 164(C), pages 377-389.
    15. Sanjay Dominik Jena & Jean-François Cordeau & Bernard Gendron, 2017. "Lagrangian Heuristics for Large-Scale Dynamic Facility Location with Generalized Modular Capacities," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 388-404, August.
    16. Zhong, Haiwang & Xia, Qing & Chen, Yuguo & Kang, Chongqing, 2015. "Energy-saving generation dispatch toward a sustainable electric power industry in China," Energy Policy, Elsevier, vol. 83(C), pages 14-25.
    17. Wim Ackooij & Jérôme Malick, 2016. "Decomposition algorithm for large-scale two-stage unit-commitment," Annals of Operations Research, Springer, vol. 238(1), pages 587-613, March.
    18. Igor Litvinchev & Socorro Rangel & Jania Saucedo, 2010. "A Lagrangian bound for many-to-many assignment problems," Journal of Combinatorial Optimization, Springer, vol. 19(3), pages 241-257, April.
    19. Antonio Frangioni & Claudio Gentile & Enrico Grande & Andrea Pacifici, 2011. "Projected Perspective Reformulations with Applications in Design Problems," Operations Research, INFORMS, vol. 59(5), pages 1225-1232, October.
    20. Maturana, Jorge & Riff, Maria-Cristina, 2007. "Solving the short-term electrical generation scheduling problem by an adaptive evolutionary approach," European Journal of Operational Research, Elsevier, vol. 179(3), pages 677-691, June.

    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:spr:annopr:v:274:y:2019:i:1:d:10.1007_s10479-018-2827-x. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.