Lagrangian Methods and Dynamic Programming-Based MIP Formulations for the Unit Commitment Problem

Tiziano Bacci (), Antonio Frangioni () and Claudio Gentile ()
Additional contact information
Tiziano Bacci: Istituto di Analisi dei Sistemi ed Informatica “A. Ruberti”, C.N.R
Antonio Frangioni: Università di Pisa
Claudio Gentile: Istituto di Analisi dei Sistemi ed Informatica “A. Ruberti”, C.N.R

Chapter Chapter 14 in Optimization Essentials, 2024, pp 417-468 from Springer

Abstract: Abstract Exactly solving hard optimization problems, in particular those mixing both nonlinear components and combinatorial ones, crucially requires the ability to derive tight bounds on the optimal value, which are obtained via relaxations. A fundamental trade-off exists between the tightness of the bound, which is important to avoid the explosion of the number of nodes in branch-and-bound (B&B) approaches and better drive the heuristics and the branching decisions, and the cost of the solution of the continuous relaxation. This is in particular true because “strong” relaxations (providing tight bounds) are also very often “large” ones, i.e., with a very large—often exponential—number of variables and/or constraints. Navigating this trade-off is crucial to develop overall efficient solution algorithms, especially since apparently minor aspects may have a disproportionate large impacts depending on the fine details of the computational environment in which the algorithm is implemented. This chapter provides an extensive illustration of this process using as test bed the Unit Commitment problem in electrical power production. In particular we will review several Mixed-Integer NonLinear formulations of (some of the most common variants of) the problem, with different trade-offs between size and “tightness”, as well as algorithms for the efficient solutions of single-unit versions of the problem that motivate Lagrangian approaches. We will then compare the different variants, mostly in terms of their running time versus the quality of the provided bound, in the context of a state-of-the-art software implementation, highlighting the several nontrivial choices that have to be navigated in order to choose the best approach for each given application.

Date: 2024
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-981-99-5491-9_14

Ordering information: This item can be ordered from
http://www.springer.com/9789819954919

DOI: 10.1007/978-981-99-5491-9_14

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().