Message Boards Message Boards

1
|
8059 Views
|
11 Replies
|
4 Total Likes
View groups...
Share
Share this post:

Linear Programming and Optimization

Posted 8 years ago

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. Truck1 is waiting 19 hours at port1, 19 hours at port2, 14 hours at port3 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?

enter image description here

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"}}]
POSTED BY: Okkes Dulgerci
11 Replies

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

POSTED BY: Frank Kampas

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

POSTED BY: Frank Kampas
Posted 8 years ago

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?

POSTED BY: Diego Zviovich

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 https://reference.wolfram.com/language/tutorial/ConstrainedOptimizationLinearProgramming.html and the function itself 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.

POSTED BY: Todd Rowland
Posted 8 years ago

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.

POSTED BY: Okkes Dulgerci

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}]
POSTED BY: Todd Rowland
Posted 8 years ago

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,

POSTED BY: Okkes Dulgerci

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.)

POSTED BY: Todd Rowland

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)

POSTED BY: Todd Rowland
Posted 8 years ago

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..

enter image description here

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}}
POSTED BY: Okkes Dulgerci

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

https://www.youtube.com/watch?v=F9UKIN16HA0

POSTED BY: Frank Kampas
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract