Industrial
and
EIN 6918: Graduate Seminar
Spring 2008
February 7, 2008
3PM, MAEB 211
Cutting Plane Algorithms
for Solving a Robust Edge-Partition Problem
Zeki Taskin
Department of Industrial and Systems Engineering
Abstract
The edge-partition problem is inspired by a telecommunication network design problem arising in Synchronous Optical Networks. The deterministic edge-partition problem considers an undirected graph with weighted edges, and simultaneously assigns nodes and edges to subgraphs such that each edge appears in exactly one subgraph, and such that no edge is assigned to a subgraph unless both of its incident nodes are also assigned to that subgraph. Additionally, there are limitations on the number of nodes and on the sum of edge weights that can be assigned to each subgraph. In this paper, we consider a robust version of the edge-partition problem in which we assign nodes to subgraphs in a first stage, realize a set of edge weights from among a finite set of alternatives, and then assign edges to subgraphs. We first prescribe a two-stage cutting plane approach with integer variables in both stages, and examine computational difficulties associated with the proposed cutting planes. As an alternative, we prescribe a hybrid integer programming/constraint programming algorithm capable of solving a suite of test instances within practical computational limits.