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

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 on which … Read more

A Polynomial-time Algorithm with Tight Error Bounds for Single-period Unit Commitment Problem

This paper proposes a Lagrangian dual based polynomial-time approximation algorithm for solving the single-period unit commitment problem, which can be formulated as a mixed integer quadratic programming problem and proven to be NP-hard. Tight theoretical bounds for the absolute errors and relative errors of the approximate solutions generated by the proposed algorithm are provided. Computational … Read more

New MINLP Formulations for the Unit Commitment Problems with Ramping Constraints

The Unit Commitment (UC) problem in electrical power production requires to optimally operate a set of power generation units over a short time horizon (one day to a week). Operational constraints of each unit depend on its type (e.g., thermal, hydro, nuclear, …), and can be rather complex. For thermal units, typical ones concern minimum … Read more

A Polyhedral Study of the Semi-Continuous Knapsack Problem

We study the convex hull of the feasible set of the semi-continuous knapsack problem, in which the variables belong to the union of two intervals. Besides being important in its own right, the semi-continuous knapsack problem arises in a number of other contexts, e.g. it is a relaxation of general mixed-integer programming. We show how … Read more