On the Structure of Decision Diagram–Representable Mixed-Integer Programs with Application to Unit Commitment

Hosseinali Salemi () and Danial Davarnia ()
Additional contact information
Hosseinali Salemi: Department of Industrial and Manufacturing Systems Engineering, Iowa State University, Ames, Iowa 50011
Danial Davarnia: Department of Industrial and Manufacturing Systems Engineering, Iowa State University, Ames, Iowa 50011

Operations Research, 2023, vol. 71, issue 6, 1943-1959

Abstract: Over the past decade, decision diagrams (DDs) have been used to model and solve integer programming and combinatorial optimization problems. Despite successful performance of DDs in solving various discrete optimization problems, their extension to model mixed-integer programs (MIPs), such as those appearing in energy applications, is lacking. More broadly, the question of which problem structures admit a DD representation is still open in the DD community. In this paper, we address this question by introducing a geometric decomposition framework based on rectangular formations that provides both necessary and sufficient conditions for a general MIP to be representable by DDs. As a special case, we show that any bounded mixed-integer linear program admits a DD representation through a specialized Benders decomposition technique. The resulting DD encodes both integer and continuous variables and, therefore, is amenable to the addition of feasibility and optimality cuts through refinement procedures. As an application for this framework, we develop a novel solution methodology for the unit commitment problem (UCP) in the wholesale electricity market. Computational experiments conducted on a stochastic variant of the UCP show a significant improvement of the solution time for the proposed method when compared with the outcome of modern solvers.

Keywords: Special Issue on Computational Advances in Short-Term Power System Operations; decision diagrams; Benders decomposition; mixed-integer programs; unit commitment (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2353 (application/pdf)

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:inm:oropre:v:71:y:2023:i:6:p:1943-1959

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().