Operations Research, Systems Engineering and Industrial Engineering Commons^™

Exploiting Symmetry In Linear And Integer Linear Programming, Ethan Jedidiah Deakins

Doctoral Dissertations

This thesis explores two algorithmic approaches for exploiting symmetries in linear and integer linear programs. The first is orbital crossover, a novel method of crossover designed to exploit symmetry in linear programs. Symmetry has long been considered a curse in combinatorial optimization problems, but significant progress has been made. Up until recently, symmetry exploitation in linear programs was not worth the upfront cost of symmetry detection. However, recent results involving a generalization of symmetries, equitable partitions, has made the upfront cost much more manageable.

The motivation for orbital crossover is that many highly symmetric integer linear programs exist, and …

Novel Mixed Integer Programming Approaches To Unit Commitment And Tool Switching Problems, Najmaddin Akhundov

Doctoral Dissertations

In the first two chapters, we discuss mixed integer programming formulations in Unit Commitment Problem. First, we present a new reformulation to capture the uncertainty associated with renewable energy. Then, the symmetrical property of UC is exploited to develop new methods to improve the computational time by reducing redundancy in the search space. In the third chapter, we focus on the Tool Switching and Sequencing Problem. Similar to UC, we analyze its symmetrical nature and present a new reformulation and symmetry-breaking cuts which lead to a significant improvement in the solution time. In chapter one, we use convex hull pricing …

Optimization Methods For Day Ahead Unit Commitment, Jonathan David Schrock

Doctoral Dissertations

This work examines a variety of optimization techniques to better solve the day ahead unit commitment problem. The first method looks at the impact of almost identical generators on the problem and how to exploit that fact for computational gain. The second work seeks to improve the fidelity of the problem by better modeling the impact of pumped storage hydropower. Lastly, the relationship between the length of the planning horizon and the quality of the solutions is investigated.