Cutting plane algorithms for solving a stochastic edge-partition problem

Z. Caner Taşkin, J. Cole Smith, Shabbir Ahmed, Andrew J. Schaefer

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)420-435
Number of pages16
JournalDiscrete Optimization
Volume6
Issue number4
DOIs
StatePublished - Nov 2009
Externally publishedYes

Keywords

  • Constraint programming
  • Edge-partition
  • Integer programming
  • Stochastic optimization

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Cutting plane algorithms for solving a stochastic edge-partition problem'. Together they form a unique fingerprint.

Cite this