# Linear Programming and Optimization

**URL:** <https://community.wolfram.com/t/linear-programming-and-optimization/8139>\
**Category:** Questions\
**Tags:** equation-solving, optimization\
**Created:** [March 16, 2016, 10:41am UTC](https://community.wolfram.com/t/linear-programming-and-optimization/8139 "2016-03-16T10:41:40Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![scinar](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/scinar/32/39519_2.png) [@scinar](https://community.wolfram.com/u/scinar)\
**Post date:** [March 16, 2016, 10:41am UTC](https://community.wolfram.com/t/linear-programming-and-optimization/8139/1 "2016-03-16T10:41:40Z")

</div>

Hi All,

I am trying to solve a problem. Assume I have 6 trucks and all are at the port at the same time. They need to stop each of the 4 ports to unload their freight. There is waiting time for each truck at each port. Please see the picture. Truck\_1 is waiting 19 hours at port\_1, 19 hours at port\_2, 14 hours at port\_3 and 6 hours at port\_4. There cannot be 2 trucks at the the same port at the same time and trucks cannot be 2 different port at the same time. I want to minimize total unloading time. What should be my order for trucks?

 ![truck.png](https://global.discourse-cdn.com/wolfram/original/3X/8/0/80fc154c4045a4edf7283c281fc252b444924b27.png)

It seems I can use LinearProgramming, but no luck so far. Any suggestion? Here is the my Data. Thanks in advance..

```
n = {{19, 19, 14, 6}, {9, 13, 6, 20}, {13, 8, 7, 14}, {16, 10, 5, 
    9}, {3, 18, 14, 18}, {18, 3, 14, 5}};

TableForm[n, 
 TableHeadings -> {{"truck1", "truck2", "truck3", "truck4", "truck5", 
    "truck6"}, {"port1", "port2", "port3", "port4"}}]

```

---

<div class="post-metadata">

**Author:** ![rowland](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/rowland/32/36108_2.png) [@rowland](https://community.wolfram.com/u/rowland)\
**Post date:** [March 16, 2016, 3:52pm UTC](https://community.wolfram.com/t/linear-programming-and-optimization/8139/2 "2016-03-16T15:52:28Z")

</div>

You could use LinearProgramming, but I would advise against it.

The thing about linear programming is that you have to convert your problem into linear equations, and then into vectors, including the thing you want to optimize. You would start by expressing the thing you want to minimize, and you’ve done that step. It is the total. How do you convert that to a vector with Dot? The trick to know is that

```
Dot[v, Table[1, Length[v]]]== v.Table[1,Length[v]] == Total[v]

```

Then the next thing is to convert every constraint you’ve said into either an equality or an inequality. These inequalities need to be turned into vectors (like above). Finally, you read the documentation for the syntax. (A tutorial [Linear Optimization—Wolfram Documentation](https://reference.wolfram.com/language/tutorial/ConstrainedOptimizationLinearProgramming.html) and the function itself [LinearProgramming—Wolfram Documentation](https://reference.wolfram.com/language/ref/LinearProgramming.html) )

Once you realize you have to do a bunch of translation of your problem, you should realize it is better to use more user friendly functions (`NMinimize` perhaps see the tutorial) which do a bunch of the translation for you. Ideally it would be done using natural language (e.g. in Wolfram Alpha). This doesn’t even cover the question of how to know whether LinearProgramming will work, in the real world you only know for sure if it is a homework question. The higher level functions like NMinimize makes that sort of understanding unnecessary.

Lastly I would suggest considering a concrete approach to the problem by finding a way to enumerate solutions. For example, you have only 24 events, which could symbolically be written, for instance to unload truck 2 at port 4

```
Unload[truck[2], port[4]]

```

Of course `Permutations[Range[24]]` is way too big to go through but I would guess that a huge chunk could be eliminated as being inefficient orders.

---

<div class="post-metadata">

**Author:** ![scinar](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/scinar/32/39519_2.png) [@scinar](https://community.wolfram.com/u/scinar)\
**Post date:** [March 16, 2016, 6:34pm UTC](https://community.wolfram.com/t/linear-programming-and-optimization/8139/3 "2016-03-16T18:34:32Z")

</div>

Thanks for your quick reply. After I posted the problem I realized that I can use the `NMinimize`. But the problem is I could not set up equations and constraints.

---

<div class="post-metadata">

**Author:** ![rowland](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/rowland/32/36108_2.png) [@rowland](https://community.wolfram.com/u/rowland)\
**Post date:** [March 17, 2016, 2:17am UTC](https://community.wolfram.com/t/linear-programming-and-optimization/8139/4 "2016-03-17T02:17:47Z")

</div>

You probably have to still rely on the sorts of tricks used in LinearProgramming like using auxiliary variables to effectively perform Max (Maybe do a web search for tricks). Using NMinimize is much easier because the constraints can be much more flexible.

For instance, t11, t12, …t14, …, t64 could represent the times that the ith truck starts at port I. Every sentence in the original question corresponds to equations. You could write them all by hand, but doing it with some code would be more reliable.

t11\>=0 && (t11 \<= t12 +n[[1,2]] || t12\<=n[[1,1]])

are just some of the constraints.

You could represent the total time by `Max[t11+n[[1,]],...,t64+n[[6,4]]]` but it is better to borrow a trick from LinearProgramming and create an auxiliary variable total with `total>= tij+n[[I,j]]` for each I,j and then minimize just total.

Here is a short version with just two trucks and two ports.

```
NMinimize[{total,
  t11 >= 0 && t12 >= 0 && t21 >= 0 && 
   t22 >= 0 && (t11 + 19 <= t12 || 
     t12 + 19 <= t11) && (t21 + 9 <= t22 || 
     t22 + 13 <= t21) && (t11 + 19 <= t21 || 
     t21 + 9 <= t11) && (t12 + 19 <= t22 || t22 + 13 <= t12) && 
   total >= t11 + 19 && total >= t12 + 19 && total >= t21 + 9 && 
   total >= t22 + 13}, {t11, t12, t21, t22, total}]

```

---

<div class="post-metadata">

**Author:** ![fkampas](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/fkampas/32/41217_2.png) [@fkampas](https://community.wolfram.com/u/fkampas)\
**Post date:** [March 17, 2016, 4:07pm UTC](https://community.wolfram.com/t/linear-programming-and-optimization/8139/5 "2016-03-17T16:07:39Z")

</div>

Don’t you need integer variables to prevent more than one truck from being at port at the same time?

---

<div class="post-metadata">

**Author:** ![scinar](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/scinar/32/39519_2.png) [@scinar](https://community.wolfram.com/u/scinar)\
**Post date:** [March 17, 2016, 4:40pm UTC](https://community.wolfram.com/t/linear-programming-and-optimization/8139/6 "2016-03-17T16:40:57Z")

</div>

Hi Todd, Thanks again for your reply. It solves for 3 trucks and 2 port

```
In[2]:= NMinimize[{total, 
  t11 >= 0 && t12 >= 0 && t21 >= 0 && t22 >= 0 && t31 >= 0 && 
   t32 >= 0 &&
   (t11 + n[[1, 1]] <= t12 || 
     t12 + n[[1, 2]] <= t11) && (t21 + n[[2, 1]] <= t22 || 
     t22 + n[[2, 2]] <= t21) &&
   (t31 + n[[3, 1]] <= t32 || t32 + n[[3, 2]] <= t31) &&
   
   (t11 + n[[1, 1]] <= t21 || t21 + n[[2, 1]] <= t11) &&
   (t11 + n[[1, 1]] <= t31 || t31 + n[[3, 1]] <= t11) &&
   
   (t21 + n[[2, 1]] <= t31 || t31 + n[[3, 1]] <= t21) &&
   
   (t12 + n[[1, 2]] <= t22 || t22 + n[[2, 2]] <= t12) &&
   (t12 + n[[1, 2]] <= t32 || t32 + n[[3, 2]] <= t12) &&
   
   (t22 + n[[2, 2]] <= t32 || t32 + n[[3, 2]] <= t22) &&
   
   total >= t11 + n[[1, 1]] && total >= t12 + n[[1, 2]] && 
   total >= t21 + n[[2, 1]] && total >= t22 + n[[2, 2]] && 
   total >= t31 + n[[3, 1]] && total >= t32 + n[[3, 2]]}, {t11, t12, 
  t21, t22, t31, t32, total}]

Out[2]= {41., {t11 -> 0., t12 -> 22., t21 -> 19., t22 -> 0., 
  t31 -> 28., t32 -> 13., total -> 41.}}

```

But when it comes 5 trucks and 4 port it takes hours, an I have to quit the program..

```
NMinimize[{total, 
   t11 >= 0 && t12 >= 0 && t13 >= 0 && t14 >= 0 && t21 >= 0 && 
    t22 >= 0 && t23 >= 0 && t24 >= 0 && t31 >= 0 && t32 >= 0 && 
    t33 >= 0 && t34 >= 0 && t41 >= 0 && t42 >= 0 && t43 >= 0 && 
    t44 >= 0 && t51 >= 0 && t52 >= 0 && t53 >= 0 && t54 >= 0 &&
    
    (t11 + n[[1, 1]] <= t12 || t12 + n[[1, 2]] <= t11) &&
    (t11 + n[[1, 1]] <= t13 || t13 + n[[1, 3]] <= t11) &&
    (t11 + n[[1, 1]] <= t14 || t14 + n[[1, 4]] <= t11) &&
    
    (t12 + n[[1, 2]] <= t13 || t13 + n[[1, 3]] <= t12) &&
    (t12 + n[[1, 2]] <= t14 || t14 + n[[1, 4]] <= t12) &&
    
    (t13 + n[[1, 3]] <= t14 || t14 + n[[1, 4]] <= t13) &&
    
    (t21 + n[[2, 1]] <= t22 || t22 + n[[2, 2]] <= t21) &&
    (t21 + n[[2, 1]] <= t23 || t23 + n[[2, 3]] <= t21) &&
    (t21 + n[[2, 1]] <= t24 || t24 + n[[2, 4]] <= t21) &&
    
    (t22 + n[[2, 2]] <= t23 || t23 + n[[2, 3]] <= t22) &&
    (t22 + n[[2, 2]] <= t24 || t24 + n[[2, 4]] <= t22) &&
    
    (t23 + n[[2, 3]] <= t24 || t24 + n[[2, 4]] <= t23) &&
    
    (t31 + n[[3, 1]] <= t32 || t32 + n[[3, 2]] <= t31) &&
    (t31 + n[[3, 1]] <= t33 || t33 + n[[3, 3]] <= t31) &&
    (t31 + n[[3, 1]] <= t34 || t34 + n[[3, 4]] <= t31) &&
    
    (t32 + n[[3, 2]] <= t33 || t33 + n[[3, 3]] <= t32) &&
    (t32 + n[[3, 2]] <= t34 || t34 + n[[3, 4]] <= t32) &&
    
    (t33 + n[[3, 3]] <= t34 || t34 + n[[3, 4]] <= t33) &&
    
    (t41 + n[[4, 1]] <= t42 || t42 + n[[4, 2]] <= t41) &&
    (t41 + n[[4, 1]] <= t43 || t43 + n[[4, 3]] <= t41) &&
    (t41 + n[[4, 1]] <= t44 || t44 + n[[4, 4]] <= t41) &&
    
    (t42 + n[[4, 2]] <= t43 || t43 + n[[4, 3]] <= t42) &&
    (t42 + n[[4, 2]] <= t44 || t44 + n[[4, 4]] <= t42) &&
    
    (t43 + n[[4, 3]] <= t44 || t44 + n[[4, 4]] <= t43) &&
    
    (t51 + n[[5, 1]] <= t52 || t52 + n[[5, 2]] <= t51) &&
    (t51 + n[[5, 1]] <= t53 || t53 + n[[5, 3]] <= t51) &&
    (t51 + n[[5, 1]] <= t54 || t54 + n[[5, 4]] <= t51) &&
    
    (t52 + n[[5, 2]] <= t53 || t53 + n[[5, 3]] <= t52) &&
    (t52 + n[[5, 2]] <= t54 || t54 + n[[5, 4]] <= t52) &&
    
    (t53 + n[[5, 3]] <= t54 || t54 + n[[5, 4]] <= t53) &&
    
    
    (t11 + n[[1, 1]] <= t21 || t21 + n[[2, 1]] <= t11) &&
    (t11 + n[[1, 1]] <= t31 || t31 + n[[3, 1]] <= t11) &&
    (t11 + n[[1, 1]] <= t41 || t41 + n[[4, 1]] <= t11) &&
    (t11 + n[[1, 1]] <= t51 || t51 + n[[5, 1]] <= t11) &&
    
    (t21 + n[[2, 1]] <= t31 || t31 + n[[3, 1]] <= t21) &&
    (t21 + n[[2, 1]] <= t41 || t41 + n[[4, 1]] <= t21) &&
    (t21 + n[[2, 1]] <= t51 || t51 + n[[5, 1]] <= t21) &&
    
    (t31 + n[[3, 1]] <= t41 || t41 + n[[4, 1]] <= t31) &&
    (t31 + n[[3, 1]] <= t51 || t51 + n[[5, 1]] <= t31) &&
    
    (t41 + n[[4, 1]] <= t51 || t51 + n[[5, 1]] <= t41) &&
    
    (t12 + n[[1, 2]] <= t22 || t22 + n[[2, 2]] <= t12) &&
    (t12 + n[[1, 2]] <= t32 || t32 + n[[3, 2]] <= t12) &&
    (t12 + n[[1, 2]] <= t42 || t42 + n[[4, 2]] <= t12) &&
    (t12 + n[[1, 2]] <= t52 || t52 + n[[5, 2]] <= t12) &&
    
    (t22 + n[[2, 2]] <= t32 || t32 + n[[3, 2]] <= t22) &&
    (t22 + n[[2, 2]] <= t42 || t42 + n[[4, 2]] <= t22) &&
    (t22 + n[[2, 2]] <= t52 || t52 + n[[5, 2]] <= t22) &&
    
    (t32 + n[[3, 2]] <= t42 || t42 + n[[4, 2]] <= t32) &&
    (t32 + n[[3, 2]] <= t52 || t52 + n[[5, 2]] <= t32) &&
    
    (t42 + n[[4, 2]] <= t52 || t52 + n[[5, 2]] <= t42) &&
    
    (t13 + n[[1, 3]] <= t23 || t23 + n[[2, 3]] <= t13) &&
    (t13 + n[[1, 3]] <= t33 || t33 + n[[3, 3]] <= t13) &&
    (t13 + n[[1, 3]] <= t43 || t43 + n[[4, 3]] <= t13) &&
    (t13 + n[[1, 3]] <= t53 || t53 + n[[5, 3]] <= t13) &&
    
    (t23 + n[[2, 3]] <= t33 || t33 + n[[3, 3]] <= t23) &&
    (t23 + n[[2, 3]] <= t43 || t43 + n[[4, 3]] <= t23) &&
    (t23 + n[[2, 3]] <= t53 || t53 + n[[5, 3]] <= t23) &&
    
    (t33 + n[[3, 3]] <= t43 || t43 + n[[4, 3]] <= t33) &&
    (t33 + n[[3, 3]] <= t53 || t53 + n[[5, 3]] <= t33) &&
    
    (t43 + n[[4, 3]] <= t53 || t53 + n[[5, 3]] <= t43) &&
    
    (t14 + n[[1, 4]] <= t24 || t24 + n[[2, 4]] <= t14) &&
    (t14 + n[[1, 4]] <= t34 || t34 + n[[3, 4]] <= t14) &&
    (t14 + n[[1, 4]] <= t44 || t44 + n[[4, 4]] <= t14) &&
    (t14 + n[[1, 4]] <= t54 || t54 + n[[5, 4]] <= t14) &&
    
    (t24 + n[[2, 4]] <= t34 || t34 + n[[3, 4]] <= t24) &&
    (t24 + n[[2, 4]] <= t44 || t44 + n[[4, 4]] <= t24) &&
    (t24 + n[[2, 4]] <= t54 || t54 + n[[5, 4]] <= t24) &&
    
    (t34 + n[[3, 4]] <= t44 || t44 + n[[4, 4]] <= t34) &&
    (t34 + n[[3, 4]] <= t54 || t54 + n[[5, 4]] <= t34) &&
    
    (t44 + n[[4, 4]] <= t54 || t54 + n[[5, 4]] <= t44) &&
    
    total >= t11 + n[[1, 1]] && total >= t12 + n[[1, 2]] && 
    total >= t13 + n[[1, 3]] && total >= t14 + n[[1, 4]] && 
    total >= t21 + n[[2, 1]] && total >= t22 + n[[2, 2]] && 
    total >= t23 + n[[2, 3]] && total >= t24 + n[[2, 4]] && 
    total >= t31 + n[[3, 1]] && total >= t32 + n[[3, 2]] && 
    total >= t33 + n[[3, 3]] && total >= t34 + n[[3, 4]] && 
    total >= t41 + n[[4, 1]] && total >= t42 + n[[4, 2]] && 
    total >= t43 + n[[4, 3]] && total >= t44 + n[[4, 4]] && 
    total >= t51 + n[[5, 1]] && total >= t52 + n[[5, 2]] && 
    total >= t53 + n[[5, 3]] && total >= t54 + n[[5, 4]]}, {t11, t12, 
   t13, t14, t21, t22, t23, t24, t31, t32, t33, t34, t41, t42, t43, 
   t44, t51, t52, t53, t54, total}] // Timing

```

I don’t know what to do.. And there should be easy way to set up equations and constraints, doing by hand is very painful and easy to make mistakes..

Regards,

---

<div class="post-metadata">

**Author:** ![rowland](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/rowland/32/36108_2.png) [@rowland](https://community.wolfram.com/u/rowland)\
**Post date:** [March 18, 2016, 1:40pm UTC](https://community.wolfram.com/t/linear-programming-and-optimization/8139/7 "2016-03-18T13:40:52Z")

</div>

Just wanted to say that I am thinking about this, but for the moment I can answer Frank’s question.

That this is confusing is an obvious drawback, but we encode the constraint that two things don’t happen at once with

```
Not happen at the same time
->
Or[start time of A + time spent doing A <= start time of B, 
      start time of B + time spent doing B <= start time of A]

```

This is the source of the problem, possibly. The obvious way to make this a LinearProgramming problem creates 2^n different regions and 2^24 is pretty big.

(I should admit that I am not an expert.)

---

<div class="post-metadata">

**Author:** ![fkampas](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/fkampas/32/41217_2.png) [@fkampas](https://community.wolfram.com/u/fkampas)\
**Post date:** [March 18, 2016, 1:59pm UTC](https://community.wolfram.com/t/linear-programming-and-optimization/8139/8 "2016-03-18T13:59:11Z")

</div>

I believe that binary variables are more efficient than Or constraints for this sort of problem, when done by linear programming.  
For example, the linear programming approach to Sudoku has 9 binary variables for each cell

---

<div class="post-metadata">

**Author:** ![dzviovich](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/dzviovich/32/27395_2.png) [@dzviovich](https://community.wolfram.com/u/dzviovich)\
**Post date:** [March 18, 2016, 5:05pm UTC](https://community.wolfram.com/t/linear-programming-and-optimization/8139/9 "2016-03-18T17:05:29Z")

</div>

Is the problem statement such that trucks need to visit first port 1 then port 2 then port 3 and finally port 4 in that order?

---

<div class="post-metadata">

**Author:** ![rowland](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/rowland/32/36108_2.png) [@rowland](https://community.wolfram.com/u/rowland)\
**Post date:** [March 18, 2016, 5:14pm UTC](https://community.wolfram.com/t/linear-programming-and-optimization/8139/10 "2016-03-18T17:14:25Z")

</div>

Diego, no the order is unknown. If the order was known, the NMinimize expression that Okkes Dulgerci was using would return pretty quickly.

Frank, that sounds like a good idea. I don’t know exactly how to implement it. But the LinearProgramming function does allow Integers, and it has a better chance to deal with all of the possibilities with your idea. My only reluctance is that the real number algorithms are more reliable than the discrete ones. (as far as I know)

---

<div class="post-metadata">

**Author:** ![scinar](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/scinar/32/39519_2.png) [@scinar](https://community.wolfram.com/u/scinar)\
**Post date:** [March 18, 2016, 5:57pm UTC](https://community.wolfram.com/t/linear-programming-and-optimization/8139/11 "2016-03-18T17:57:19Z")

</div>

Thanks for you comments. Yes Diego, there is no specific order.. Actually my original data is the below one.. 20 trucks and 4 ports. I know this is harder than my previous data..

 ![pic.png](https://global.discourse-cdn.com/wolfram/original/3X/e/8/e893183a9d023a66bd906f6398349e4a5c7e16b0.png)

and here is the data:

```
n={{36.67, 23.33, 18.33, 12.33}, {20., 33.33, 30.83, 10.33}, {16.67, 
  60.83, 22.08, 16.13}, {26.67, 53.33, 24.33, 11.93}, {53.33, 43.33, 
  11.33, 14.33}, {60., 13.33, 14.58, 23.13}, {43.33, 33.33, 9.58, 
  16.13}, {36.67, 23.33, 27.08, 16.53}, {20., 28.33, 21.58, 
  24.73}, {33.33, 38.33, 29.08, 12.33}, {28.33, 68.33, 6.08, 
  11.13}, {45., 78.33, 30.33, 10.73}, {46.67, 38.33, 21.83, 
  15.73}, {53.33, 13.33, 13.33, 12.33}, {73.33, 23.33, 12.08, 
  18.13}, {13.33, 28.33, 19.58, 10.73}, {33.33, 33.33, 21.83, 
  21.93}, {26.67, 28.33, 27.58, 7.33}, {23.33, 18.33, 14.83, 
  6.93}, {33.33, 40.83, 30.08, 12.33}}

```

---

<div class="post-metadata">

**Author:** ![fkampas](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/fkampas/32/41217_2.png) [@fkampas](https://community.wolfram.com/u/fkampas)\
**Post date:** [March 18, 2016, 6:09pm UTC](https://community.wolfram.com/t/linear-programming-and-optimization/8139/12 "2016-03-18T18:09:34Z")

</div>

this looks it might be useful. it’s a staff scheduling problem done with LP

https://www.youtube.com/embed/F9UKIN16HA0?feature=oembed&wmode=opaque