Joint IMA and Digital Technology Center (DTC) Talk

Time: 3:30 pm, April 28 (Monday)
Place: 402 Walter Library

Speaker: Dr. Herve Kerivin, IMA postdoctoral associate

Title: Partition inequalities and the network design problem with connectivity requirements

Abstract. The network design problem with connectivity requirements models a wide variety of celebrated combinatorial optimization problems including the minimum spanning tree, Steiner tree, and survivable network design problems. It has applications to the design of reliable communication and transportation networks. Informally given requirements for the number of edge-disjoint paths between every pair of nodes, it consists in designing a minimum cost network that satisfies these requirements.

A way to formulate this problem is to use the well-known custset model which is based on the so-called cut inequalities. This formulation is known to be weak, that is the objective value of the linear programming relaxation is typically significantly less than the objective value of the integer program. Strong formulations are very useful in developing exact algorithm solution methods (i.e., branch-and-cut) since their use rapidly accelerates these solution techniques.

Partition inequalities generalize cut inequalities, and arise as valid inequalities or facets for optimization problems related to the network design problem with connectivity requirements. These inequalities have received special attention over the past twenty years as people investigated the polyhedral structure of the problem. This talk will give an overview of research on the partition inequalities, with a particular emphasis on their associated separation problem.