I am having problem understanding how to relax multiple constrains in linear programming. I know how to relax just one constrain of LP, but I have problem understanding how to constrain for example, two or three constrains.
Can someone show me how would objective function look like on this example:
\begin{align} \min \ \sum\limits_{1 \leq k \leq K}&\sum\limits_{(i,j)\in E} c_{ij}x_{ij}^k \label{11}\\ \sum\limits_{1\leq k\leq K}x_{ij}^k & = y_{ij} \label{22}\\ \sum\limits_{1\leq j\leq n}y_{ij} &= 1, \ \forall i = 2, ..., n \label{33} \\ \sum\limits_{1\leq i\leq n}y_{ij} &= 1, \ \forall j = 2, ..., n \label{44}\\ \sum\limits_{1\leq j\leq n}y_{1j} &= K \label{55}\\ \sum\limits_{1\leq i\leq n}y_{i1} &= K \label{66}\\ \sum\limits_{2\leq i \leq n}\sum\limits_{1\leq j \leq n} d_ix_{ij}^k &\leq u, \ \forall k=1,2,...,K \label{77}\\ \sum\limits_{i \in Q}\sum\limits_{j \in Q} y_{ij}& \leq |Q|-1, \ \forall Q \subset \{2,...,n\} \label{88} \\ y_{ij} = 0 \ \text{or}& \ 1,\ \forall (i,j) \in E \label{99}\\ x_{ij}^k = 0 \ \text{or}& \ 1,\ \forall (i,j)\in E, \ \forall k=1,2,...,K \label{1010} \end{align}
So for example if we relax constrains $\sum\limits_{1\leq j\leq n}y_{ij} = 1, \ \forall i = 1, 2, ..., n $
$\sum\limits_{2\leq i \leq n}\sum\limits_{1\leq j \leq n} d_ix_{ij}^k \leq u, \ \forall k=1,2,...,K$
and
$\sum\limits_{i \in Q}\sum\limits_{j \in Q} y_{ij} \leq |Q|-1, \ \forall Q \subset \{2,...,n\} $
we are left with assignment problem which is easy to solve. Can anyone show me how would objective function look like after relaxing these contrains?
This program is known as vehicle routing.
Thank youu