1
$\begingroup$

this is a follow up on this question:

Check if two vertices of a graph are connected with an MILP constraint

Where Robert in fact provided me a nice idea to check if the solution has the two nodes connected.

In fact I'd like my problem to be actually constrained to select only solutions that have those two vertices connected, so I tought that adding the followin constraints would work:

let $y_a$ and $y_b$ be binary variables representing the two nodes to be connected, and $y_i,y_j,...$ binary variables associated to two generics nodes. maximize the sum:

$\sum_i y_i$ subject to:

$y_i=(a_ij)yj+a_ij(y_i)$ %% this is the if-then statement

$y_a=0$ %%the source node is set to 0

$y_b=0$ %%this was my idea to force that the destination is connected, but in fact it doesn't work

the problem is that imposing yb=0 does not imply that ya and yb are in fact connected as I tought before writing it up, since two separate graphs that are not connected would be a feasible solution.

What could I do to force this type of constraint?

Edit: an idea seems to be considering the problem of maximum flow, I'll update this question if I manage to find a working solution since I saw multiple other questions around the internet with no answers.

$\endgroup$
0
$\begingroup$

Yes, you can do this with flow. Suppose you have binary ($0-1$) variables $x_{ij}$ where $x_{ij} = 1$ means $\{i,j\}$ is an edge of the graph. Take new variables $y_{ij}$ with values in $\{-1,0,1\}$, and $y_{ji} = -y_{ij}$. We interpret $y_{ij}$ as the flow of a commodity from $i$ to $j$. Then in order to have $a$ connected to $b$, we impose constraints: $$ \eqalign{ y_{ij} \le x_{ij},\; -y_{ij} \le x_{ij} & \text{ for all } i,j\cr \sum_i y_{ij} - \sum_k y_{jk} = 0 & \text{ for all } j \ne a, b \cr \sum_i y_{ia} - \sum_k y_{ak} = 1\cr \sum_i y_{ib} - \sum_k y_{bk} = -1 }$$

$\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.