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$


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

  • $\begingroup$ I dont understand quite well your problem, as the index $k$ appears to be a power??. Or this is just another ranging index?? $\endgroup$ – Brethlosze Jun 8 '17 at 19:18
  • $\begingroup$ Besides, you have a contradiction in the $=K$ constraints, following the $=1$ constraints... Are you missing or exceeding some indexes in there?? $\endgroup$ – Brethlosze Jun 8 '17 at 19:20
  • $\begingroup$ Also there is an $ili$ symbol.. what is that!..... $\endgroup$ – Brethlosze Jun 8 '17 at 19:22
  • $\begingroup$ $k$ is the commodity. so we have $K$ commodity of vehicles I edited typos, thanks @hyprfrco $\endgroup$ – 0038lana Jun 10 '17 at 6:57
  • $\begingroup$ Ok if you have to decide between 0 and 1, you are no longer linear, you are discrete, do you know that, right? $\endgroup$ – Brethlosze Jun 10 '17 at 10:35

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.