Can anyone assist me to find out what should be the ILP formulation of a case when I try to label vertices by say $0$, $1$ and $2$ and want the subgraph of graph $(V,E)$ made by same vertex set but edge set being those which have at least one end point as $1$ or $2$, to be connected. I don't need objective functions, just want to know how to show this as a constraint.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Your title says induced subgraph, but your description says the same vertex set. Are vertices with label 0 and no neighbors with label 1 or 2 supposed to be included? $\endgroup$– RobPrattCommented Feb 7, 2020 at 13:03
-
$\begingroup$ @RobPratt No, those vertices need not be included. But based on some other constraints I am getting all the vertices. So, to simplify I have told that people need not worry about reduced vertices and vertex set remains same. $\endgroup$– Himanshu KhandelwalCommented Feb 7, 2020 at 15:02
-
$\begingroup$ I had asked a similar question about two years ago: mathoverflow.net/questions/282302/… $\endgroup$– Manfred WeisCommented Feb 7, 2020 at 19:25
-
$\begingroup$ you can find an answer also here: mathoverflow.net/a/282317/31310 $\endgroup$– Manfred WeisCommented Feb 7, 2020 at 19:36
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Imposing contiguity constraints in political districting models, by Hamidreza Validi, Austin Buchanan, and Eugene Lykhovyd, is a very recent paper (January 27, 2020) that provides a good survey of integer linear programming models for connectivity in the context of political districting.
$\begingroup$
$\endgroup$
1
This paper helped me understand a lot on connectivity of subgraphs. A must look for those seeking an answer.
-
$\begingroup$ The paper seems to suggest that, for large enough instances, a polynomial formulation yields faster solve times than an exponential formulation. This is not necessarily true if the exponential constraints are generated dynamically only when they are violated. As a famous example, consider the Miller-Tucker-Zemlin and Dantzig-Fulkerson-Johnson formulations for the traveling salesman problem. $\endgroup$– RobPrattCommented Feb 8, 2020 at 15:36