12
$\begingroup$

Is there an efficient way to model the connectivity of two nodes in an arbitrary undirected graph? I would like to have a binary variable representing this connectivity: 1 if there exists a path between these two nodes and 0 otherwise. Let us assume I have a set of binary variables over edges indicating that edge is active or not. By using these variables (and possibly some more), I would like create the connectivity constraints which are aimed to be linear in terms of other variables, or any auxiliary variable which might be introduced.

$\endgroup$
  • 2
    $\begingroup$ Hi Mertcan Yetkin, welcome to OR.SE. I think your question would benefit from a bit more background on what you are trying to achieve here. From what I understand you have a graph and a pair (or small number) of nodes. Then you want to develop a model that tells you whether two nodes are connected by a path and some additional constraints. If you are only interested in the fact that two nodes are connected, you can compute that beforehand. So, could you provide some more background on the underlying question. $\endgroup$ – JakobS Jun 18 '19 at 8:16
  • 1
    $\begingroup$ Hey Jacob, I edited the question based on your comments. I would like to get a dynamic representation of the connectivity based on the binary variables over edges as I explained in the question. Therefore, the connectivity ends up more complex than a pre-processing over the nodes. $\endgroup$ – Mertcan Yetkin Jun 18 '19 at 17:40
10
$\begingroup$

From the question and the comments I gather that you really only have one pair between with connectivity could be established (by activating edges) and whether this is the case or not should be indicated by a binary variable.

How about sending one unit of flow between the two nodes? In, say, the source node you send the one unit either along an exisiting/activated edge, or along an artificial edge (on which you have your "indicator" variable with a small penalty in the objective function: when you must use the indicator, there is no connectivity between the pairs, otherwise it is).

$\endgroup$
  • $\begingroup$ Thanks for your answer. If I understood correctly, you suggest solving a type of single commodity flow problem with some artificial edges. My only concern with this is that I would like to have a set of constraints linking to a binary variable for connectivity in a much larger problem (which has some other objective). In other words, I am going to use the connectivity variables in some other constraint before solving the optimization problem. In more detail, I would like to dynamically choose the connectivity depending on other constraints, rather than solving an optimization problem. $\endgroup$ – Mertcan Yetkin Jun 19 '19 at 15:21
  • 1
    $\begingroup$ Now I am puzzled. I thought the connectivity should be part of the optimization. If you just need to check up front whether there is a path between two nodes then this information would not be variable but constant. Do you solve two optimization problems, one after other? Alternatingly? Help! $\endgroup$ – Marco Lübbecke Jun 20 '19 at 17:55
  • $\begingroup$ I am sorry for misunderstanding. It is part of the optimization, but I would like to have this information before solving an optimization problem. Based on my understanding, in your explanation, I require the solution of some problem to be able to decide whether two nodes are connected or not. I would like to determine this inside a problem with some constraints (for instance forcing the two nodes to be connected, or not connected), so that the connectivity would be dynamic and I can have other constraints on these connectivity variables to form a broader formulation involving other decisions. $\endgroup$ – Mertcan Yetkin Jun 21 '19 at 15:44
  • 1
    $\begingroup$ @Simon the extra variable "consumes" the flow for the case that the flow cannot be routed into the target, i.e., the extra variable reflects "not connected" $\endgroup$ – Marco Lübbecke Jul 3 '19 at 12:26
  • 1
    $\begingroup$ I think I understood your approach correctly and that we're not contradicting eachother. In your solution, you even explicitly state that this additional variable must be part of the objective for it to work properly. The difficulty might lie in determining the weight of said variable - if other parts of the model participate in the objective in the opposite way. $\endgroup$ – Simon Jul 3 '19 at 13:20
5
$\begingroup$

Hint: Connectivity is an equivalence relation on the set of nodes, so it has three properties. You can model each of these properties with linear constraints.

$\endgroup$
  • 1
    $\begingroup$ Thanks for your answer, it seems to me that it would require modeling of connectivity for the each pair of nodes (to form the equivalence classes). Let's say I am only interested in a single pair of nodes (or a very small subset of nodes). $\endgroup$ – Mertcan Yetkin Jun 17 '19 at 21:12
2
$\begingroup$

So assuming you have a graph that you can compute something like all_paths .

Then for the the given start and end node you can create a constraint such that you have at least one of these in your solution.

i.e.

sum_i_j x_i_j >= 1

$\endgroup$
2
$\begingroup$

Have a look at the Floyd-Warshall algorithm. This classic shortest-path algorithm produces $n^2$ min-constraints, each min-constraint over $n$ variables and a constant $M$, larger than the diameter of the graph. It calculates all shortest paths, between all nodes. You can then look at the distance of the two nodes you're interested in. If they belong to different, disconnected components, their distance will be $M$.

This is the corresponding implementation in pseudo-code:

for i from 1 to |V|
    for j from 1 to |V|
        dist[i, j] = min(dist[i, k]+dist[k, j] for k=1..|V|, M)

Some solvers support min-constraints directly, e.g. Gurobi does with general min constraints. You can also linearize a min-constraint $y = \min_i(x_i)$ manually, by introducing a couple of binary indicator variables $z$:

$ x_i - M(1-z_i) \leq y \leq x_i \qquad \forall x_i \\ \sum z_i = 1 \\ z \in \{0,1\}^n $

$\endgroup$
2
$\begingroup$

Marco suggests using a flow-based mechanism to check whether you can send a unit of flow from source to sink (e.g. set all edge costs to one, set a supply of 1 at one node, a demand of 1 at the other, set all edge capacities to 1 and run a maxflow. If the problem is feasible, you have edge connectivity). By the max-flow min-cut duality, you could do the same thing using cuts, but you'll pay a price in terms of how many constraints you need.

Here's a suggestion - it may not be correct or complete, as I don't have time to think it through properly. For your graph $G=\{N,E\}$, partition your node set $N$ into two parts $\{T, N \setminus T\}, T\subset N$ that separate your node pair $i,j$. Define a binary decision variable $u_{ij}=1$ if edge $\{i,j\}$ is in your solution. Define another decision variable $z_{ij}=1$ if node $i$ is connected to node $j$ and 0 otherwise (this is your original request). Consider the constraint $$ \sum_{\{k,l\} \in \{T, N \setminus T\}}u_{kl} \ge z_{ij}, \forall \, \text{cutsets} \,T, \forall \, \{i,j\} \in \{T, N \setminus T\} $$

I think this does what you want. The LHS says that if there's a way "across" from $T$ to the other side and reach your desired node, at least one of the $u$'s will be one so the RHS can grow from 0 to 1 and properly indicate that you have connectivity. The last ingredient is setting up the objective function by adding something like $\sum_{\{i,j\} \in E} z_{ij}$ with the appropriate sign in front, depending on your overall objective, in order to encourage the $z$'s to be 1. Just remember that the number of cutsets $T$ grows exponentially with the cardinality of $N$ (so, something like cutting planes may be needed as well).

$\endgroup$

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.