2
$\begingroup$

I have the optimization problem given below

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

s.t

$\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?.

Thanks,

$\endgroup$

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.