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

DOI10.1287/OPRE.2022.2353MaRDI QIDQ6196734zbMATH OpenOpenAlexFDO

Authors Hosseinali Salemi, Danial Davarnia

Publication date 15 March 2024

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.06650

zbMATH Keywords

Benders decompositiondecision diagramsmixed integer programsunit commitment

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

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 has been lacking. More broadly, the question which problem structures admit a DD representation is still open in the DDs 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 to the outcome of modern solvers.

Recommendations

• Outer approximation for integer nonlinear programs via decision diagrams
• On Mixed-Integer Programming Formulations for the Unit Commitment Problem
• Incorporating bounds from decision diagrams into integer programming
• Decomposition based on decision diagrams
• Theoretical insights and algorithmic tools for decision diagram-based optimization

This page was built for publication: On the Structure of Decision Diagram–Representable Mixed-Integer Programs with Application to Unit Commitment

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6196734)