Most power grid systems are operated to be N-1 secure, meaning that the system can withstand the failure of any one component. There is increasing interest in more stringent security standards, where the power grid must be able to survive the (nearly) simultaneous failure of k components (i.e., N-k). However, this improved reliability criterion significantly increases the number of contingency scenarios that must be considered when solving the unit commitment problem. Additional computational complexity is introduced when taking into account transmission switching. This relatively inexpensive method of redirecting power flows in the grid has been proposed as a way of introducing flexibility to better survive failure events. We present an algorithm for solving the unit commitment problem that simultaneously addresses both the challenges of the N-k security requirement and the use of transmission switching during operation. We analyze the algorithmic performance and present computational results for the IEEE24 and RTS-96 test systems for k = 1 and 2. We also include a discussion of how this approach might be extended to solve problems with k ≥ 3. The online supplement, and data, are available at https://doi.org/10.1287/ijoc.2017.0751 .