Hi all,

I am working on a graph partitioning problem with the hard constraint that each partition must induce a connected subgraph. While I found a lot of work on graph partitioning, I did not find much about the connectivity issue: can anyone suggest me relevant literature?

In particular, I am looking for exact approaches and formulations.

Thanks a lot :-)

asked 15 Jan '13, 08:30

kr1zz's gravatar image

kr1zz
18615
accept rate: 25%

edited 26 Oct '13, 12:55

fbahr's gravatar image

fbahr ♦
3.5k313


Hi!

Sorry for the self-reference here, but you might want to read:

"Imposing Connectivity Constraints in Forest Planning Models" by R. C., M. Constantino, M. Goycoolea, J. P. Vielma and A. Weintraub, 2011.

you will find an exact approach there and references to other authors tackling the issue of connectivity.

Regards,
Rodolfo

link

answered 15 Jan '13, 09:22

Rodolfo%20Carvajal's gravatar image

Rodolfo Carv...
1062
accept rate: 25%

edited 15 Jan '13, 09:33

fbahr's gravatar image

fbahr ♦
3.5k313

Thank you Rodolfo, I found your paper very interesting, both the application and the algorithm. We also happened to consider a tree-based formulation,that's why I am looking for something different. However, I might exploit your strengthenings. Did you work on the problem because of a real need or was it just an academic investigation?

(21 Jan '13, 05:53) kr1zz

Another question: did you try any heuristic approach? Maybe to bootstrap the b&c?

(21 Jan '13, 06:07) kr1zz

And a third one: have you experimented with more than one patch?

(21 Jan '13, 06:27) kr1zz
1

I'm glad that you like the paper, @kr1zz! Regarding your questions:

  1. We worked on this problem because we think that there exists a bit of a gap between the people working in forestry and the people working in MIP/OR. In the case of connectivity in particular, some of the formulations are not able to scale well with the size of the instances (they use explicit enumeration of certain subsets or are arc-based formulations), so a formulation with a polynomial (and decent) number of variables with a constraint-generation approach was well suited to the problem.
(21 Jan '13, 20:43) Rodolfo Carv...
1

@kr1zz 2. We did try a very simple heuristic but it seems it didn't did well compared with CPLEX. Our focus was to show the strenght of the formulation and the ease to obtain good upper bounds. There is a lot of room for trying more ideas on the heuristic side. Whe did not try to bootstrap the b&c.

(21 Jan '13, 20:50) Rodolfo Carv...
1

@kr1zz

  1. No, we haven't done computational tests with multiple patches. But as you can see in the paper, the approach easily extends to that case.

I would love to know about any progress on your problem. Good luck!

(21 Jan '13, 20:54) Rodolfo Carv...
showing 5 of 6 show 1 more comments

Realize that a (sub)graph is connected if and only if it has a spanning tree. So, you can enforce that each partition induces a tree (say, by choosing edges).

Another common method for enforcing connectivity is through a flow formulation. For each partition, pick a 'source' node and require that each vertex in the graph receives at least one unit of flow from a source node. There can be considerable symmetry in this formulation when you have multiple partitions. One remedy is to require that a source node may only 'fuel' nodes with a larger index (after numbering the nodes 1,...,n). Equivalently, each partition has a unique 'representative' that roots the tree; it has the lowest index in its partition.

You can also use an exponentially-sized formulation based on cutsets. In each partition, there will be sets of vertices that will disconnect the partition. For each of these cutsets, require that at least one of its vertices is selected.

I suspect that there are many other ways to enforce connectivity. For more information, I would search for connectivity constraints in general -- not necessarily limited to graph partitioning.

link

answered 15 Jan '13, 09:43

Austin%20Buchanan's gravatar image

Austin Buchanan
689210
accept rate: 21%

1

Thank you Austin, in fact I am looking for other ways (and in case I find anything I'll post links :-) ). Now we are trying both approaches (which are closely related) in MIP formulations and yes, we have symmetry issues. They are due to the root and to the structure (chosen a set of nodes, there is more than one, possibly many, spaning trees). We are exploiting the remedy you suggest plus orbitopal constraints, which seem to work pretty well until the problem does not grow too much. Other ideas? What about Constraint Programming?

(21 Jan '13, 06:06) kr1zz

I would be very careful about combining symmetry-breaking approaches. Sometimes strategy A is appropriate and strategy B is appropriate, but A+B rules out optimal solutions.

In another strategy, do not try to break symmetry, but instead use a commercial solver with significant symmetry detection. You may try setting the symmetry parameter as high as possible in CPLEX or in Gurobi.

As for constraint programming--I would not be the person to ask.

(27 Jan '13, 12:35) Austin Buchanan
1

Do you know the number of elements in the partition in advance? Do you know that some nodes belong to a given partition element? What is the objective function?

(28 Jan '13, 07:27) jfpuget

@jfpuget the original problem featured cardinality constraints (i.e., up to C nodes per partition) and the number of partitions was given (so I had to allow the case were a node could be left unassigned to any partition), details can be found here and here. Now I would like to generalize the problem/try some variants.

(31 Jan '13, 04:33) kr1zz
1

The papers aren't freely available, I can't read them :-(

(10 Feb '13, 09:01) jfpuget

Thanks, I did not notice from within the university :(

However the second one is freely available here.

(14 Feb '13, 03:22) kr1zz
showing 5 of 6 show 1 more comments
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×2
×1
×1

Asked: 15 Jan '13, 08:30

Seen: 935 times

Last updated: 26 Oct '13, 12:55

OR-Exchange! Your site for questions, answers, and announcements about operations research.