7
$\begingroup$

I would like to create a constraint with AMPL that checks whether I am able to reach from one node $v$ to all other nodes of a set but I don't really know how to formulate it (especially in AMPL (+CPLEX)).

(I am not interested in finding the shortest paths just a path per pair of nodes $(v,*)$ (Floyd-Warshall))

Basically the main goal of my optimisation is to split graphs into two subgraphs even so this extends the question itself (the objective function is untested and highly experimental): For a connected graph $G=(V,E_V)$ I'd like to find two connected subgraphs $SG1=(U,E_U)$ and $SG2=(W,E_W)$ $$ \begin{split} & \min |\text{card}(U)-\text{card}(W)|\cdot\text{card}\left(N^+_{E_V}(U)\cap N^+_{E_V}(W)\right)\\ & \exists v\in U: N^+_{E_U}(v)=U \text{ therefore the first subgraph is connected}\\ & \exists v\in W: N^+_{E_W}(v)=W \text{ the second subgraph is connected}\\ & U\cap W=\emptyset\\ & N^+_{E} \text{ is the set of nodes that is reachable for a given set of edges} \end{split} $$

Improve this question
$\endgroup$
3
  • $\begingroup$ To clarify: In your model, do you have decision variables that turn edges on/off? And you're trying to write constraints that check whether the resulting network is connected? $\endgroup$
    – LarrySnyder610
    Commented Feb 17, 2020 at 16:05
  • $\begingroup$ One moment will add (I think) the details you asked for. $\endgroup$
    – baxbear
    Commented Feb 17, 2020 at 16:40
  • $\begingroup$ cs.stackexchange.com/q/159983/755 $\endgroup$
    – D.W.
    Commented Sep 14, 2023 at 6:22

3 Answers 3

Reset to default
5
$\begingroup$

I am aware of models that model such constraints using a network-flow-type approach. The basic idea is to create a source node that send "flow" of an imaginary product for which all nodes have a demand of 1. There are no costs for the flows.

In your case the problem is trickier because you would need two source nodes, and maybe two types of imaginary products, and maybe you have a constraint that each node needs one type or the other—but hopefully you can make use of this idea.

I would also suggest doing an online search for "connectivity constraints". There are other approaches in the literature.

Improve this answer
$\endgroup$
3
$\begingroup$

One possible solution (not necessarily quick or efficient) is a lazy constraint approach:

  • Solve your problem, ignoring the connection requirement
  • Examine the solution and find the subgraph $H$ that is connected to $v$.
  • If $H=G$, you are finished.
  • Otherwise, add a constraint that at least one of the edges between $H$ and not-$H$ is connected, and repeat.

This post by Bob Fourer gives an example of the same approach as applied to a TSP.

Improve this answer
$\endgroup$
1
$\begingroup$

You may have a look at this presentation about network flows implementations in AMPL. In the presentation, the authors talked about new AMPL implementations of "arc" and "node" especially on page 8 they mentioned keywords like from and to that I think will help you design your constraints in AMPL. There is also AMPL book chapter about network linear programs that you can read more about the topic. I hope it works for you.

Improve this answer
$\endgroup$
2
  • $\begingroup$ If I'm not mistaken, I think these AMPL features just make it easier to define models on networks. I think the OP is asking about constraints that check for connectedness, given that the structure of the network itself may be determined by decision variables. $\endgroup$
    – LarrySnyder610
    Commented Feb 17, 2020 at 16:04
  • 1
    $\begingroup$ @LarrySnyder610 You are right Dr. Snyder before the question has been changed, I thought the mentioned keywords could be helpful in writing the necessary constraints in AMPL. But now, my answer is away from being a solution. I will just delete the answer if I can not find modify it. $\endgroup$
    – Oguz Toragay
    Commented Feb 17, 2020 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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