I have the optimization problem given below

max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$


$\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$

$\quad 2)\quad x_{ij} \in {0,1}$

$\quad 3)\ \ \sum_{j=1}^{M} x_{ij}R_{ij} \geq R^b_{i} \quad \forall i$

$\quad 4)\ \ \sum_{i=1}^{N} x_{ij}R_{ij} \leq R^u_{j} \quad \forall j$

$\quad 5)\ \ \sum_{i=1}^{N} x_{ij}\leq N_{eq} \quad \forall j$

The parameters $N, M, R_{ij},R^b_{i},R^u_{j}, N_{eq}$ are given.

It is clear the problem is binary LP. I would like to construct a network flow problem.

I will set up a network flow problem as follows. There will be four layers. The first layer is a single node we call the source. The second layer consists of $N$ nodes. The third layer has $M$ nodes. The final layer is one node we call the sink. For each edge, we give a lower bound , upper bound and and a profit, say, $[lb,ub,p]$. One arc enters the source node and we label it as $[N,N,0]$. We label each arc from the source node to each edge in the second layer as $[1,1,0]$. We also label each arc from a node $i$ in the second layer to a node $j$ in the third layer as $[0,1,R_{ij}]$. Arcs from each node in the third layer to the sink node are labeled by $[0,N_{eq},0]$.

Note that this construction does not consider constraint (3) and (4). To consider constraint (3), arcs that does not satisfy $R_{ij}\geq R^b_{i}$ are labeled as $[0,0,R_{ij}]$, not $[0,1,R_{ij}]$ as mentioned above because we want to force its variable $x_{ij}$ to be zero.

My questions are:

Q1: If we ignore constraint (4), is the network flow problem correct?.

Q2: Considering constraint (4), how can I reconstruct the network flow problem?.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.