What do you really mean? In a given graph, the path between two nodes exists or not. Do you want to use the constraint to "force" using two specific nodes and some path between them?

In my problem I have a directed graph. Each edge is associated with a weight. I have to choose a set of edges which minimized the total weight. However, I have to sets of nodes, source nodes and destination nodes. The problem states that there must exists a path from each source node to each destination node (this actually define which edges I should choose). I'm looking for a way to define this constrain in liner programming.

Thanks,

Oren

So, it seems to me you just want to solve a shortest path problem for each pair "source node-destination node" (or is it a transportation problem?).

The shortest path problem as LP

https://en.wikipedia.org/wiki/Shortest_path_problem#Linear_programming_formulation

In the shortest path problem there is a single path (the shortest) from the source node to the target node. However, I don't want to limit the number of existing path.

Oren

OK, once again. You have a set a source nodes, a set of destination nodes and (I guess) also a set of intermediate nodes. You want to find a collection of paths which

1) connect each source node with each destination node via some intermediate nodes (the number of paths is the number of source nodes multiplied by the number of destination nodes)

2) the total weight/length of all the paths is minimal.

Right?

I'm not interested in the 2nd part. I need the 1st path as a constraint. Leta say that my algorithms choose sets of source, destination and intermediate nodes (and therefore, a set of edges). In order of the problem to be feasible there must be a path between each destination node and each source node.

תצייר קו כאילוץ!

I think I understand now. But I'm not sure if it is possible just by adding a set of appropriate constraints to a LP problem. The path in LP (the shortest path in particular) is modelled as variables corresponding to nodes which take values 1. The shortest path problem is in fact  the problem of minimal flow cost where one unit of some commodity is transferred from a single source to the single destination. So you can check all the pairs "source-destination" in a loop by solving the shortest path problem for them. You can also check in the "one source-many destinations" mode. I mean that eg. if you have 5 sources and 4 destinations, you can solve a min flow cost for each source (loop in 5 steps). You assign a capacity of 4 units to a source, demands of 1 unit each to  all the destinations and find min flow cost. If there exists a path to each destination then the solution exists (one unit flow occurs). But how to describe the existence of connections "each source-each destination" as LP constraints? I doubt if it is possible, at least basing on the "flow approach".

Maybe if I define my problem as a multi-source - multi-destination max flow problem and add a constraint stating that the flow of each edge in the selected graph must be greater than zero. I think that in this case there must exist at least one path from every source node to every destination node.

Yes, max flow is better than min flow cost/shortest path because obviously it "engages" many arcs and you want to force using all the arcs. But I doubt if it is right in any case.  If by "directed graph" you mean a graph in which all the arcs are unidirectional (the flow is possible in one direction only) then see the example below (2 sources,  2 intermediate,  2 destinations)

s1-----> i1-------->d1

               |

              v

s2-----> i2 -------->d2

The paths that exist are s1-i1-d1,s1-i1-i2-d2,s2-i2-d2. The path s2-i2-i1-d1 doesn't exist but  flows along all the arcs are possible (provided capacities, demands and limits on arc large enough).

May be linear sequence of edges with certain cost less than a certain maximum value.

I've read through your question, answers, and responses and am still unclear w.r.t. exactly what you want to do, But, if you want to have a path existing between nodes, I would think that you would define that in the variable space as xij, the path between source I and destination j, and then have your optimization model select which paths are optimal. I am not seeing that as something that needs to be constrained. But without more clarity for the model, I am not sure what you are exactly wanting....

Same as David Rogers I do not understanhd what to inted to do.

Could you clarify please?