Novel Mixed Integer Programming Approaches to Unit Commitment and Tool Switching Problems

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 to explicitly price the risk associated with uncertainty in large power systems scheduling problems. The uncertainty associated with renewable generation (e.g. solar and wind) is highlighting the need for changes in how power production is scheduled. It is known that symmetry in the integer programming formulations can slow down the solution process due to the redundancy in the search space caused by permutations. In the second chapter, we show that having symmetry in the unit commitment problem caused by having identical generating units could lead to a computational burden even for a small-scale problem. We present an effective method to exploit symmetry in the formulation introduced by identical (often co-located) generators. We propose a cut-generation approach coupled with aggregation method to remove symmetry without sacrificing feasibility or optimality. In the third chapter, we focus on the Job Sequencing and Tool Switching Problem (SSP), which is a well-known combinatorial optimization problem in the domain of Flexible Manufacturing Systems (FMS). We propose a new integer linear programming approach with symmetry-breaking and tightening cuts that provably outperformed the existing methodology described in the literature.