Dynamic convexification within nested Benders decomposition using Lagrangian relaxation: An application to the strategic bidding problem
Gregory Steeger and
European Journal of Operational Research, 2017, vol. 257, issue 2, 669-686
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)
References: View references in EconPapers View complete reference list from CitEc
Citations View citations in EconPapers (1) Track citations by RSS feed
Downloads: (external link)
Full text for ScienceDirect subscribers only
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:257:y:2017:i:2:p:669-686
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
Series data maintained by Dana Niculescu ().