TY - JOUR

T1 - Cutting plane algorithms for solving a stochastic edge-partition problem

AU - Taşkin, Z. Caner

AU - Smith, J. Cole

AU - Ahmed, Shabbir

AU - Schaefer, Andrew J.

N1 - Funding Information:
The authors are grateful to two anonymous referees, Osman Özaltın and Semra Ağralı, whose remarks helped improve the presentation of the paper. The authors gratefully acknowledge the support of the Air Force Office of Scientific Research under Grants F49620-03-1-0377 and FA9550-07-1-0404, and the support of the National Science Foundation under Grants CMII-0620780 and CMMI-0758234.

PY - 2009/11

Y1 - 2009/11

N2 - We consider the edge-partition problem, which is a graph theoretic problem arising in the design of 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 stochastic version of the edge-partition problem in which we assign nodes to subgraphs in a first stage, realize a set of edge weights from 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.

AB - We consider the edge-partition problem, which is a graph theoretic problem arising in the design of 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 stochastic version of the edge-partition problem in which we assign nodes to subgraphs in a first stage, realize a set of edge weights from 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.

KW - Constraint programming

KW - Edge-partition

KW - Integer programming

KW - Stochastic optimization

UR - http://www.scopus.com/inward/record.url?scp=68349095142&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=68349095142&partnerID=8YFLogxK

U2 - 10.1016/j.disopt.2009.05.004

DO - 10.1016/j.disopt.2009.05.004

M3 - Article

AN - SCOPUS:68349095142

VL - 6

SP - 420

EP - 435

JO - Discrete Optimization

JF - Discrete Optimization

SN - 1572-5286

IS - 4

ER -