Suppose we have a network (shown in the image above), and the maximum transfer rate between two computers is written on each link. We want to maximize the transfer rate from computer $o$ to computer $n$ and we have to satisfy these conditions:
No link is allowed to proceed its maximum capacity.
Each link can transfer data in either direction but not at the same time.
We can't save or waste flow in any node, in other words whatever enters each node has to leave.
What I am really stuck on right now is how can I write the 3rd condition in my linear program, could someone please help me, because we don't know the direction beforehand.
What this is equating to is that when we use an edge of a node to transfer data into it, we have to use at least one outgoing edge from that node.
A partial model to the problem:
Let $N_{out, in}$ represent the nodes in the network with $out$ being an index that tells us the outgoing node, and $in$ being the index denoting the incoming node that node $out$ is going towards with $out\in\{a,b,c,d,e,o\}$ and $in\in\{a,b,c,d,e,n\}$.
Next, lets have $C_{out,in}$ denote the weight of the edge that connects the two nodes together.
Since we can only use one edge at a time, $N$ is binary for all edges. Thus, we can represent this with a model as the following:
$$\text{Maximize } z = \sum_{out}\sum_{in}C_{out,in}\cdot N_{out,in}$$
Subject to:
$$N_{oa} + N_{ob} + N_{oc} = 1$$
$$\sum_{in}N_{out,in}\le 1 \text{$\quad$} \forall out$$
$$\sum_{out}N_{out,in}\le 1 \text{$\quad$} \forall in$$
$$N_{dn} + N_{en} = 1 $$
$$N_{out, in}\in\{0,1\}\text{ }\forall out,in$$
Lastly, we’ll need a modified Miller-Tucker-Zemlin constraint to eliminate sub-tours, but we’ll leave that as an exercise for the reader, as the explanation and partial model is enough to answer the question presented. One thing to notice is that this networking problem is a variation of the Traveling Salesman problem.
Here’s a PowerPoint presentation that gives additional detail on sub-tour elimination of the TSP.