1
$\begingroup$

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.

$\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$
    – RobPratt
    Feb 7 '20 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$ Feb 7 '20 at 15:02
  • $\begingroup$ I had asked a similar question about two years ago: mathoverflow.net/questions/282302/… $\endgroup$ Feb 7 '20 at 19:25
  • $\begingroup$ you can find an answer also here: mathoverflow.net/a/282317/31310 $\endgroup$ Feb 7 '20 at 19:36
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

A NEW MIXED INTEGER LINEAR PROGRAMMING FORMULATION FOR THE MAXIMUM DEGREE BOUNDED CONNECTED SUBGRAPH PROBLEM

This paper helped me understand a lot on connectivity of subgraphs. A must look for those seeking an answer.

$\endgroup$
1
  • $\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$
    – RobPratt
    Feb 8 '20 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.