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.

A present trend in the study of the symmetric traveling salesman polytope is to use, as a relaxation of the polytope, the graphical traveling salesman polyhedron (GTSP). Following a parallel approach for the asymmetric traveling salesman polytope, we define the graphical asymmetric traveling salesman problem on a general digraph D and its associated polyhedron GATSP(D). We give basic polyhedral results and lifting theorems for GATSP(D) and we give a general condition for a facet-defining inequality for GTSP to yield a symmetric facet-defining inequality for GATSP. Using this approach we show that all known major families of facet-defining inequalities of GTSP define facets of GATSP. Finally, we discuss possible extension of these results to the asymmetric traveling salesman polytope.

We study facets of the k-partition polytope Pk,n, the convex hull of edges cut by r-partitions of a complete graph for r ⩽ k, k ⩾ 3. We generalize the hypermetric and cycle inequalities (see Deza and Laurent, 1992) from the cut polytope to Pk,n, k ⩾ 3. We give some sufficient conditions under which these are facet defining. We show the anti-web inequality introduced by Deza and Laurent (1992) to be facet defining for Pk,n, k ⩾ 3. We also give lifting procedures for constructing facets of Pk,r from facets of Pk,n for r ⩾ n + 1 and facets of Pk,r from facets of Pk−1,n for r ⩾ n + 1.

The graph partitioning polytope $P( G )$ is the convex hull of the incidence vectors of all partitions of a graph G. The authors show that $P( G )$ is completely defined by cycle inequalities if G is series-parallel and by cycle, 3-wheel, and repeated 2-sums of 3-wheel and cycle inequalities if G is a 4-wheel free graph.

This paper studies the polyhedron $P_k ( G )$ definedd by the convex hull of k-edge-connected spanning subgraphs of a given graph G where multiple copies of an edge are allowed. A complete inequality description of $P_k ( G )$ when k is odd and G is an outer planar graph is given. A family of facet-defining inequalities of $P_k ( G )$ that have the same support graph but coefficients that depend on $k \in \{ 4r - 2, 4r - 1, 4r + 1,r \in t\{ 1,2, \ldots \} \}$ is described.

In this paper we report computational experience with a branch and cut solver for the Steimer tree problem on a graph. The problem instances include complete graphs, randomly generated sparse graphs and grid graphs. The edge weights are either randomly generated or are the Euclidean distance between the endnodes that are placed at random on the plane. The effect of changing various problem parameters on solution time is studied. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

In this paper the problem of finding a minimum weight equivalent subgraph of a directed graph is considered. The associated equivalent subgraph polyhedron $P ( G )$ is studied. Several families of facet-defining inequalities are described for this polyhedron. A related problem of designing networks that satisfy certain survivability conditions, as introduced in [M. Grötschel and C. L. Monma, SIAM Journal on Discrete Mathematics, 3 (1990), pp. 502–523] is also studied. The low connectivity case is formulated on directed graphs, and the directed formulation is shown to give a better LP-relaxation than the undirected one. It is shown how facet-defining inequalities of $P ( G )$ give facet-defining inequalities in this case. Computational results are presented for some randomly generated problems.

The families of minimal directed cuts and minimal equivalent subgraphs of a directed graph form a pair of blocking clutters. A directed graph is series-parallel if the undirected graph obtained on ignoring directions is series-parallel. It is shown that the minimal equivalent subgraph inequalities completely describe the directed cut polyhedron, and that the minimal directed cut inequalities completely describe the equivalent subgraph polyhedron on strongly connected series-parallel graphs.

Abstract Given a graph G = (V,E) and a set N ⊆ V, we consider the problem of finding a minimum‐weight multiway cut that separates each pair of nodes in N. In this paper we give an integer programming formulation of this problem and study the associated polyhedron. We give some computational results to support the strength of our facets. We also give some efficiently solvable instances.