Dynamic convexification within nested Benders decomposition using Lagrangian relaxation: An application to the strategic bidding problem

Gregory Steeger and Steffen Rebennack

European Journal of Operational Research, 2017, vol. 257, issue 2, 669-686

Abstract: Many decomposition algorithms like Benders decomposition and stochastic dual dynamic programming are limited to convex optimization problems. In this paper, we utilize a dynamic convexification method that makes use of Lagrangian relaxation to overcome this limitation and enables the modeling of non-convex multi-stage problems using decomposition algorithms. Though the algorithm is confined by the duality gap of the problem being studied, the computed upper bounds (for maximization problems) are at least as good as those found via a linear programming relaxation approach. We apply the method to the strategic bidding problem for a hydroelectric producer, in which we ask: What is the revenue-maximizing production schedule for a single price-maker hydroelectric producer in a deregulated, bid-based market? Because the price-maker’s future revenue function has a sawtooth shape, we model it using mixed-integer linear programming. To remedy the non-concavity issues associated with modeling the future revenue function as a mixed-integer linear program, we model the price-maker’s bidding decision utilizing both Benders decomposition and Lagrangian relaxation. We demonstrate the utility of our algorithm through an illustrative example and through three case studies in which we model electricity markets in El Salvador, Honduras, and Nicaragua.

Keywords: Lagrangian relaxation; Mixed-integer linear programming; Benders decomposition; Hydroelectric scheduling; Strategic bidding problem; Stochastic dual dynamic programming (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171630621X
Full text for ScienceDirect subscribers only

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:eee:ejores:v:257:y:2017:i:2:p:669-686

DOI: 10.1016/j.ejor.2016.08.006

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().