# Graph partitioning with connectivity constraints

 3 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 190●1●8 accept rate: 25% fbahr ♦ 4.5k●5●15

 5 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 answered 15 Jan '13, 09:22 Rodolfo Carv... 136●2 accept rate: 20% fbahr ♦ 4.5k●5●15 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: 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 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
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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: