Strengthening the SDP Relaxation of AC Power Flows with Convex Envelopes, Bound Tightening, and Lifted Nonlinear Cuts

This paper considers state-of-the-art convex relaxations for the AC power flow equations and introduces new valid cuts based on convex envelopes and lifted nonlinear constraints. These valid linear inequalities strengthen existing semidefinite and quadratic programming relaxations and dominate existing cuts proposed in the litterature. Together with model intersections and bound tightening, the new linear cuts … Read more

The Ramping Polytope and Cut Generation for the Unit Commitment Problem

We present a perfect formulation for a single generator in the unit commitment problem, inspired by the dynamic programming approach taken by Frangioni and Gentile. This generator can have characteristics such as ramping constraints, time-dependent start-up costs, and start-up/shut-down ramping. To develop this perfect formulation we extend the result of Balas on unions of polyhedra … Read more

Algorithms over Arc-time Indexed Formulations for Single and Parallel Machine Scheduling Problems

This paper presents algorithms for single and parallel identical machine scheduling problems. While the overall algorithm can be viewed as a branch-cut-and-price over a very large extended formulation, a number of auxiliary techniques are necessary to make the column generation effective. Those techniques include a powerful fixing by reduced costs and a new proposed dual … Read more