After a blackout event, power system restoration is an essential activity for grid resilience; operators restart generators, re-establish transmission paths, and restore loads. With a goal of restoring electric service in the shortest time, the core decisions in restoration planning are to partition the grid into subnetworks, each of which has an initial power source for black-start (called sectionalization problem), and then restart all generators in each network (called generator startup sequencing (GSS) problem) as soon as possible. Due to their complexity, the sectionalization and GSS problems are usually solved separately, often resulting in a suboptimal solution. Our paper develops models and computational methods to solve the two problems simultaneously. We first study the computational complexity of the GSS problem and develop an efficient integer linear programming formulation. We then integrate the GSS problem with the sectionalization problem and develop an integer linear programming formulation for the parallel power system restoration (PPSR) problem to find exact optimal solutions. To solve larger systems, we then develop bounding approaches that find good upper and lower bounds efficiently. Finally, to address computational challenges for very large power grids, we develop a randomized approach to find a high-quality feasible solution quickly. Our computational experiments demonstrate that the proposed approaches are able to find good solutions for PPSR in up to 2,000-bus systems. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: This research was supported by the Visiting Faculty Program of Argonne National Laboratory and the U.S. Department of Energy Advanced Grid Modeling Program [Grant DE-OE0000875].

The inequity aversion pricing problem aims to maximize revenue while providing prices to people connected in a social network such that connected people receive prices that are not too different. This problem is known to be NP-hard even when the number of prices offered is three. This paper provides an extended graph formulation for the problem whose LP-relaxation is shown to be very strong. We show that the extended graph relaxation is integral on a network without any cycle. We develop extended cycle inequalities and show that the extended cycle inequalities cut off all the fractional extreme points of the extended graph relaxation on a cycle. We generalize cycle inequalities to zero half cuts performing a Chvátal–Gomory procedure on a cycle. Computational experiments show that the extended graph relaxation results in an integer solution for most problem instances with very small gaps (less than 3%) from optimality for the remaining instances. The addition of zero half cuts reduces the integrality gap significantly on the few difficult instances. Summary of Contribution: The inequity aversion pricing problem aims to maximize revenue while providing prices to people connected in a social network such that connected people receive prices that are not too different. This paper provides an extended graph formulation of this practical revenue management problem whose LP-relaxation is shown to be very strong. The authors show that the extended graph relaxation is integral on a network without any cycle. They develop extended cycle inequalities and generalize them to zero-half cuts. Computational experiments show that the extended graph formulation results in an integer solution or a very small integrality gap. For difficult instances, the addition of zero half cuts significantly reduces the integrality gap.

Abstract We develop a polynomial size extended graph formulation of the graph partition problem which dominates the formulation introduced by Chopra and Rao's study, and show that the extended graph formulation is tight on a tree. We introduce exponentially many valid inequalities to the Chopra‐Rao formulation, which we call generalized arc inequalities (GAI), and develop a linear time algorithm to separate the most violated generalized arc inequality. We show that the polynomial size extended graph formulation is equivalent to the Chopra‐Rao formulation augmented by the exponentially many GAI.