CODEWITHSUNDEEP
pythonalgorithmgraph-theory
Eric Contreras
Eric Contreras

Reputation: 41

Optimize flow in a graph with multiple sources and sinks without capacity constraints on edges

I’m working on a flow optimization problem within a graph that represents an energy network. Here are the specifics:

  1. Graph Structure: I have an undirected graph representing a network of streets or connections between nodes.
  2. Sources and Sinks: There are multiple sources (energy nodes) and multiple sinks (demand nodes).
  3. Energy Flow: I need to route energy from each source to its respective sinks.
  4. Edge Restriction: Each edge in the graph can only be used by one source. In other words, once an edge is assigned to a source, no other source can use it.
  5. No Capacity Constraints: Edges have no capacity limits, so there are no restrictions on the amount of flow each edge can carry.

Objective: The goal is to find paths such that:

Each sink is covered by at least one source. Overlap between paths from different sources is minimized.

I started with a backtracking approach, creating paths from each source to its sinks while trying to avoid overlaps. However, this approach is slow and struggles with larger graphs, especially when ensuring minimal overlap.

Ideally, I’d like an efficient solution that scales well for larger graphs, ensuring that each sink is covered by a source without overlap on edges and that minimizes the total path lengths.

Upvotes: 4

Views: 93

Answers (1)

borisd
borisd

Reputation: 11

You can view this as a multi-commodity flow problem (if the energy going to different sinks cannot be mixed) or some kind of network design problem (if it can be mixed). Since there is no capacity on nodes or edges and the cost of a solution does not depend on the energy sent on the nodes, it seems that the problem reduces to creating a collection of trees from each source, the union of the trees covering all the sinks.

I suggest modeling it as a Mixed Integer Linear Program (MILP) and trying a MILP solver such as Gurobi, Cplex, Highs, or CBC... depending on whether you can grab an academic license for the commercial ones (Gurobi, Cplex) or not.

Assuming that the undirected arcs are duplicated to get a directed symmetric graph with arc set $A$, you can use the following decision variables to model the trees:

  • x_{i,u,v} is equal to 1 if arc (u,v) is associated with the source i, 0 otherwise

Then we have to minimize the total cost: \min \sum_i\sum_{(u,v) \in A} c_{u,v}x_{i,u,v}.

Each sink must receive energy: \sum_i \sum_{(u,j) \in A} x_{i,u,j} = 1 \quad\forall~sink~j

For non-source nodes, energy can go out only if energy comes in: \sum_{(u,v) \in A} x_{i,u,v} \ge x_{i,v,u} \quad\forall~node~v~\forall~source~i

Each edge can be used by only one source: \sum_i x_{i,u,v}+x_{i,v,u} \le 1 \qaud\forall~(u,v) \in A~\forall~source~i

All variables are binary.

It is a first draft. You might add another term in the objective function to minimize the overlap (I assume that is the number of nodes where several paths cross).

Upvotes: 0

Related Questions