brian bovril

914 Reputation

16 Badges

18 years, 170 days

MaplePrimes Activity


These are replies submitted by brian bovril

@vv too easy. I presume. As a constraint

 min(a,b) >= c   <==>  a>=c, b>=c.

@vv I was kind of hoping for a LPSolve solution, (you did mention you had one but it was incomplete). Anyways, what you've done is great.

I did use your TSP code for the first part, because in effect it was a TSP problem (1 path starting and ending at the depot). the second and third parts were not.

For what its worth I managed  "sledgehammer to crush a walnut code" to solve the problem [with the assistance of Carl Love and Tom], but I get memory overload for N=14...
Tours_CL_Dataframe_2.mw

 

@Kitonum I have just posted another question on this theme
http://www.mapleprimes.com/questions/221834-Convert-Max-To-ILP-Constraint?sq=221834

@Kitonum 

thanks. I was tired when I wrote the original Q. I change what i want, slightly.

Trying this input:

(seq(seq(Max(add(d[s[i]]*x[s[i],s[i+1]], i=1..nops(s)-1)), s=t)<=K, t=Tour2));
I get for the second partition:
Max(d[1]*x[1, 2]), Max(d[1]*x[1, 3]+d[3]*x[3, 4])<=K

But what i want is

max(d[1]*x[1, 2] , d[1]*x[1, 3]+d[3]*x[3, 4] )<=K

for all indices in Tour2


 

@tomleslie and Carl, thanks

@vv
http://www.mapleprimes.com/questions/221764-Combinations-Of-The-Contents-Of-The-Partitions

Here is a question and answer which doesn't violate the triangle inequality.

VRP_IP_DC1.mw
 

 

2. Given the following cij matrix, determine the shortest vehicle routes and their lengths to distribute goods from one warehouse, denoted 1 below, to the eight customers, denoted 2 9 below, when:

a)  all vehicles have a capacity of 200 units.
b)  all vehicles have a capacity of 100 units.
c)  all vehicles have a capacity of 70 units.

The Depot is located at (40,40).

restart:

"maple init loaded..."

(1)

city :=  [[40,40], [22,22], [36,26], [21, 45], [45,35], [55,20], [55,45], [26,59] ,[55,65]]; N:=nops(city):

[[40, 40], [22, 22], [36, 26], [21, 45], [45, 35], [55, 20], [55, 45], [26, 59], [55, 65]]

(2)

#c := array(1..N,1..N,[evalf(seq([seq(((city[i][1]-city[j][1])^2 + (city[i][2]-city[j][2])^2)^(1/2)                                     ,j=1..N)],i=1..N))]);

N:=9:

c:= Matrix(
   N$2, shape= symmetric, scan= triangular,
   [0, op]~([[26,15,20,7 ,25,16,24,29],
                [15,23,26,33,40,38,54],
                   [24,13,20,27,35,43],
                      [26,42,34,15,39],
                         [18,14,31,32],
                            [25,49,45],
                               [32,20],
                                  [30]]
)):

d:=<0, 18,26,11,30,21,16,29,37>:

P:=plots[pointplot](city, color=red, thickness=2, connect=false):
T:=plots[textplot]([seq([op(city[i]),i],i=1..9)],align=right, font=[TIMES,ROMAN,15]):
S:=plots[textplot]([40,40,"Depot"]):
plots[display](T,P,S);

 

Triangle inequality holds:

seq(seq([i,j,c[i,j]+c[j,N],c[i,N],c[i,j]+c[j,N]>=c[i,N],is(c[i,j]+c[j,N]>=c[i,N])],i=1..N ),j=1..N )[1..5];

[1, 1, 29, 29, 29 <= 29, true], [2, 1, 55, 54, 54 <= 55, true], [3, 1, 44, 43, 43 <= 44, true], [4, 1, 49, 39, 39 <= 49, true], [5, 1, 36, 32, 32 <= 36, true]

(3)

a)  Vehicle capacity < 200        note: only 1 route will be needed (TSP)

 

            K:=200: n := sqrt(numelems(c)): N:={seq(1..n)};

{1, 2, 3, 4, 5, 6, 7, 8, 9}

(4)

z:=add(add( c[i,j]*x[i,j],j=N ),i=N); #expression to be minimized, (2.2)
 

26*x[1, 2]+15*x[1, 3]+20*x[1, 4]+7*x[1, 5]+25*x[1, 6]+16*x[1, 7]+24*x[1, 8]+29*x[1, 9]+26*x[2, 1]+15*x[2, 3]+23*x[2, 4]+26*x[2, 5]+33*x[2, 6]+40*x[2, 7]+38*x[2, 8]+54*x[2, 9]+15*x[3, 1]+15*x[3, 2]+24*x[3, 4]+13*x[3, 5]+20*x[3, 6]+27*x[3, 7]+35*x[3, 8]+43*x[3, 9]+20*x[4, 1]+23*x[4, 2]+24*x[4, 3]+26*x[4, 5]+42*x[4, 6]+34*x[4, 7]+15*x[4, 8]+39*x[4, 9]+7*x[5, 1]+26*x[5, 2]+13*x[5, 3]+26*x[5, 4]+18*x[5, 6]+14*x[5, 7]+31*x[5, 8]+32*x[5, 9]+25*x[6, 1]+33*x[6, 2]+20*x[6, 3]+42*x[6, 4]+18*x[6, 5]+25*x[6, 7]+49*x[6, 8]+45*x[6, 9]+16*x[7, 1]+40*x[7, 2]+27*x[7, 3]+34*x[7, 4]+14*x[7, 5]+25*x[7, 6]+32*x[7, 8]+20*x[7, 9]+24*x[8, 1]+38*x[8, 2]+35*x[8, 3]+15*x[8, 4]+31*x[8, 5]+49*x[8, 6]+32*x[8, 7]+30*x[8, 9]+29*x[9, 1]+54*x[9, 2]+43*x[9, 3]+39*x[9, 4]+32*x[9, 5]+45*x[9, 6]+20*x[9, 7]+30*x[9, 8]

(5)

  conx:= seq( add(x[i,j], i=N minus {j})=1,j=N); #expression 2.3

x[2, 1]+x[3, 1]+x[4, 1]+x[5, 1]+x[6, 1]+x[7, 1]+x[8, 1]+x[9, 1] = 1, x[1, 2]+x[3, 2]+x[4, 2]+x[5, 2]+x[6, 2]+x[7, 2]+x[8, 2]+x[9, 2] = 1, x[1, 3]+x[2, 3]+x[4, 3]+x[5, 3]+x[6, 3]+x[7, 3]+x[8, 3]+x[9, 3] = 1, x[1, 4]+x[2, 4]+x[3, 4]+x[5, 4]+x[6, 4]+x[7, 4]+x[8, 4]+x[9, 4] = 1, x[1, 5]+x[2, 5]+x[3, 5]+x[4, 5]+x[6, 5]+x[7, 5]+x[8, 5]+x[9, 5] = 1, x[1, 6]+x[2, 6]+x[3, 6]+x[4, 6]+x[5, 6]+x[7, 6]+x[8, 6]+x[9, 6] = 1, x[1, 7]+x[2, 7]+x[3, 7]+x[4, 7]+x[5, 7]+x[6, 7]+x[8, 7]+x[9, 7] = 1, x[1, 8]+x[2, 8]+x[3, 8]+x[4, 8]+x[5, 8]+x[6, 8]+x[7, 8]+x[9, 8] = 1, x[1, 9]+x[2, 9]+x[3, 9]+x[4, 9]+x[5, 9]+x[6, 9]+x[7, 9]+x[8, 9] = 1

(6)

conK:= add(add(d[i]*add(x[i, j], j = N minus {i}), i = N minus {j})) <= K; #expression 2.4

18*x[2, 1]+18*x[2, 3]+18*x[2, 4]+18*x[2, 5]+18*x[2, 6]+18*x[2, 7]+18*x[2, 8]+18*x[2, 9]+26*x[3, 1]+26*x[3, 2]+26*x[3, 4]+26*x[3, 5]+26*x[3, 6]+26*x[3, 7]+26*x[3, 8]+26*x[3, 9]+11*x[4, 1]+11*x[4, 2]+11*x[4, 3]+11*x[4, 5]+11*x[4, 6]+11*x[4, 7]+11*x[4, 8]+11*x[4, 9]+30*x[5, 1]+30*x[5, 2]+30*x[5, 3]+30*x[5, 4]+30*x[5, 6]+30*x[5, 7]+30*x[5, 8]+30*x[5, 9]+21*x[6, 1]+21*x[6, 2]+21*x[6, 3]+21*x[6, 4]+21*x[6, 5]+21*x[6, 7]+21*x[6, 8]+21*x[6, 9]+16*x[7, 1]+16*x[7, 2]+16*x[7, 3]+16*x[7, 4]+16*x[7, 5]+16*x[7, 6]+16*x[7, 8]+16*x[7, 9]+29*x[8, 1]+29*x[8, 2]+29*x[8, 3]+29*x[8, 4]+29*x[8, 5]+29*x[8, 6]+29*x[8, 7]+29*x[8, 9]+37*x[9, 1]+37*x[9, 2]+37*x[9, 3]+37*x[9, 4]+37*x[9, 5]+37*x[9, 6]+37*x[9, 7]+37*x[9, 8] <= 200

(7)

  conV:= seq(add(x[i, k], i = N)-add(x[k, j], j = N) = 0, k = N); #expression 2.6

x[2, 1]+x[3, 1]+x[4, 1]+x[5, 1]+x[6, 1]+x[7, 1]+x[8, 1]+x[9, 1]-x[1, 2]-x[1, 3]-x[1, 4]-x[1, 5]-x[1, 6]-x[1, 7]-x[1, 8]-x[1, 9] = 0, x[1, 2]+x[3, 2]+x[4, 2]+x[5, 2]+x[6, 2]+x[7, 2]+x[8, 2]+x[9, 2]-x[2, 1]-x[2, 3]-x[2, 4]-x[2, 5]-x[2, 6]-x[2, 7]-x[2, 8]-x[2, 9] = 0, x[1, 3]+x[2, 3]+x[4, 3]+x[5, 3]+x[6, 3]+x[7, 3]+x[8, 3]+x[9, 3]-x[3, 1]-x[3, 2]-x[3, 4]-x[3, 5]-x[3, 6]-x[3, 7]-x[3, 8]-x[3, 9] = 0, x[1, 4]+x[2, 4]+x[3, 4]+x[5, 4]+x[6, 4]+x[7, 4]+x[8, 4]+x[9, 4]-x[4, 1]-x[4, 2]-x[4, 3]-x[4, 5]-x[4, 6]-x[4, 7]-x[4, 8]-x[4, 9] = 0, x[1, 5]+x[2, 5]+x[3, 5]+x[4, 5]+x[6, 5]+x[7, 5]+x[8, 5]+x[9, 5]-x[5, 1]-x[5, 2]-x[5, 3]-x[5, 4]-x[5, 6]-x[5, 7]-x[5, 8]-x[5, 9] = 0, x[1, 6]+x[2, 6]+x[3, 6]+x[4, 6]+x[5, 6]+x[7, 6]+x[8, 6]+x[9, 6]-x[6, 1]-x[6, 2]-x[6, 3]-x[6, 4]-x[6, 5]-x[6, 7]-x[6, 8]-x[6, 9] = 0, x[1, 7]+x[2, 7]+x[3, 7]+x[4, 7]+x[5, 7]+x[6, 7]+x[8, 7]+x[9, 7]-x[7, 1]-x[7, 2]-x[7, 3]-x[7, 4]-x[7, 5]-x[7, 6]-x[7, 8]-x[7, 9] = 0, x[1, 8]+x[2, 8]+x[3, 8]+x[4, 8]+x[5, 8]+x[6, 8]+x[7, 8]+x[9, 8]-x[8, 1]-x[8, 2]-x[8, 3]-x[8, 4]-x[8, 5]-x[8, 6]-x[8, 7]-x[8, 9] = 0, x[1, 9]+x[2, 9]+x[3, 9]+x[4, 9]+x[5, 9]+x[6, 9]+x[7, 9]+x[8, 9]-x[9, 1]-x[9, 2]-x[9, 3]-x[9, 4]-x[9, 5]-x[9, 6]-x[9, 7]-x[9, 8] = 0

(8)

            binaryvariables={ seq(seq(x[i,j],i=N minus {j}),j=N)}; #expression 2.7
 

binaryvariables = {x[1, 2], x[1, 3], x[1, 4], x[1, 5], x[1, 6], x[1, 7], x[1, 8], x[1, 9], x[2, 1], x[2, 3], x[2, 4], x[2, 5], x[2, 6], x[2, 7], x[2, 8], x[2, 9], x[3, 1], x[3, 2], x[3, 4], x[3, 5], x[3, 6], x[3, 7], x[3, 8], x[3, 9], x[4, 1], x[4, 2], x[4, 3], x[4, 5], x[4, 6], x[4, 7], x[4, 8], x[4, 9], x[5, 1], x[5, 2], x[5, 3], x[5, 4], x[5, 6], x[5, 7], x[5, 8], x[5, 9], x[6, 1], x[6, 2], x[6, 3], x[6, 4], x[6, 5], x[6, 7], x[6, 8], x[6, 9], x[7, 1], x[7, 2], x[7, 3], x[7, 4], x[7, 5], x[7, 6], x[7, 8], x[7, 9], x[8, 1], x[8, 2], x[8, 3], x[8, 4], x[8, 5], x[8, 6], x[8, 7], x[8, 9], x[9, 1], x[9, 2], x[9, 3], x[9, 4], x[9, 5], x[9, 6], x[9, 7], x[9, 8]}

(9)

conu:= seq(seq(u[i]-u[j]+n*x[i,j] <= n-1, i=N minus {1,j}), j=N minus {1}): #vv code to avoid subtours
Sol := Optimization[LPSolve](z, {conx,  conK,conV,  conu},

                         binaryvariables={ seq(seq(x[i,j],i=N minus {j}),j=N)} ); #vv's code

[164, [u[2] = HFloat(-2.9999999635148717), u[3] = HFloat(-1.9999999791759384), u[4] = HFloat(-3.999999961965951), u[5] = HFloat(0.0), u[6] = HFloat(-0.9999999845110354), u[7] = HFloat(-6.999999897944883), u[8] = HFloat(-4.99999995990077), u[9] = HFloat(-5.999999925825029), x[1, 2] = 0, x[1, 3] = 0, x[1, 4] = 0, x[1, 5] = 0, x[1, 6] = 0, x[1, 7] = 1, x[1, 8] = 0, x[1, 9] = 0, x[2, 1] = 0, x[2, 3] = 1, x[2, 4] = 0, x[2, 5] = 0, x[2, 6] = 0, x[2, 7] = 0, x[2, 8] = 0, x[2, 9] = 0, x[3, 1] = 0, x[3, 2] = 0, x[3, 4] = 0, x[3, 5] = 0, x[3, 6] = 1, x[3, 7] = 0, x[3, 8] = 0, x[3, 9] = 0, x[4, 1] = 0, x[4, 2] = 1, x[4, 3] = 0, x[4, 5] = 0, x[4, 6] = 0, x[4, 7] = 0, x[4, 8] = 0, x[4, 9] = 0, x[5, 1] = 1, x[5, 2] = 0, x[5, 3] = 0, x[5, 4] = 0, x[5, 6] = 0, x[5, 7] = 0, x[5, 8] = 0, x[5, 9] = 0, x[6, 1] = 0, x[6, 2] = 0, x[6, 3] = 0, x[6, 4] = 0, x[6, 5] = 1, x[6, 7] = 0, x[6, 8] = 0, x[6, 9] = 0, x[7, 1] = 0, x[7, 2] = 0, x[7, 3] = 0, x[7, 4] = 0, x[7, 5] = 0, x[7, 6] = 0, x[7, 8] = 0, x[7, 9] = 1, x[8, 1] = 0, x[8, 2] = 0, x[8, 3] = 0, x[8, 4] = 1, x[8, 5] = 0, x[8, 6] = 0, x[8, 7] = 0, x[8, 9] = 0, x[9, 1] = 0, x[9, 2] = 0, x[9, 3] = 0, x[9, 4] = 0, x[9, 5] = 0, x[9, 6] = 0, x[9, 7] = 0, x[9, 8] = 1]]

(10)

  X:=eval(Matrix(n, symbol=x),{Sol[2][], seq(x[i,i]=0,i=1..n)});

ord:=1: k:=1: to n do k:=max[index](X[k]); ord:=ord,k od:'order'=ord; #vv's code
trace(Sol);

order = (1, 7, 9, 8, 4, 2, 3, 6, 5, 1)

(11)

f:=[1,7,9,8,4,2,3,6,5,1]

[1, 7, 9, 8, 4, 2, 3, 6, 5, 1]

(12)

add(c[f[i],f[i+1]],i=1..nops(f)-1); #z

164

(13)

add(d[f[i+1]],i=1..nops(f)-1); #capacity

188

(14)

 

b) Require capacity<=100. Two routes are needed to minimize cost z.  The answers are z=198.......

 

f:=[1,4,8,9,7,1]

[1, 4, 8, 9, 7, 1]

(15)

add(c[f[i],f[i+1]],i=1..nops(f)-1)

101

(16)

add(d[f[i+1]],i=1..nops(f)-1)

93

(17)

f:=[1,2,3,6,5,1]

[1, 2, 3, 6, 5, 1]

(18)

add(c[f[i],f[i+1]],i=1..nops(f)-1)

86

(19)

add(d[f[i+1]],i=1..nops(f)-1)

95

(20)

now, how to get these results programmatically: (?)

K:=100: #with new K, repeat above procedure. Hardly surprisingly, it doesnt work,

 

c) Require capacity <=70. Three routes are needed to minimize cost z. Answer z=223.....

f:=[1,7,9,1]

[1, 7, 9, 1]

(21)

add(c[f[i],f[i+1]],i=1..nops(f)-1)

65

(22)

add(d[f[i+1]],i=1..nops(f)-1)

53

(23)

f:=[1,2,3,6,1]

[1, 2, 3, 6, 1]

(24)

add(c[f[i],f[i+1]],i=1..nops(f)-1)

86

(25)

add(d[f[i+1]],i=1..nops(f)-1)

65

(26)

f:=[1,5,4,8,1]

[1, 5, 4, 8, 1]

(27)

add(c[f[i],f[i+1]],i=1..nops(f)-1)

72

(28)

add(d[f[i+1]],i=1..nops(f)-1)

70

(29)

NULL


 

Download VRP_IP_DC1.mw

 

 

@vv 

What is the role of the node 0? I have replaced node 0 with 1, since as you previously point out 0 is not indexable in a matrix.
- Is it in N? in C? N={1..9}
- What is c[0, j]  ?   Or is it not defined/necessary? I see you are reading this from the .dk insert. c is the distance matrix. I made it c[1,j] for my problem,
- Are (some) (0,j), (i,0) in A? I have changed it to  (1,j), (i,1).

I have reposted the problem (with proper question and answers supplied) at

http://www.mapleprimes.com/questions/220689-How-To-Solve-A-VRP-

 

 

@Carl Love thanks for your efforts on my problem.

I wonder if using the DataFrame structure, the 6th index only could be displayed ( minimum of +tour dists which in this case is 98), so it displays [6,[[1,2,3,4,5]],[98],98,[85],85]]] . At the moment I have to guess the range where the mimima of +tour dists is.

I tried

MM[min(MM[`+tour dists`])];

AND/OR

given

MM[MM[`+tour dists`] >=~ 90 and MM[`+tour dists`] <=~ 120];

sort the resulting output in Ascending order of `+tour dists' ie  [6,[[1,2,3,4,5]],[98],98,[85],85]]] is at the top. Thankyou

PS I'm aware if I right click on the DataFrame output I can get Data Manipulation menu, but it doesnt quite do what I want....

@Carl Love Sorry to bother you. I tried to do add an uneven length list but I got this error. I hope you can fix it

Tours_CL_between.mw

 

@Carl Love thanks, I'll examine it tomorrow. It's bedtime in the antipodes.

@Carl Love Thankyou, it works perfectly. How do you do it?!

This is to reflect that changing the order of the nodes changes the distance traversed. from my previous post:

tour_length([1,2,3,4]),tour_length([1,2,4,3]),tour_length([1,3,2,4])=85,88,73

inspired by:

http://www.mapleprimes.com/questions/220689-How-To-Solve-A-VRP-

where I was unable to write the ILP constraints properly. Hence my need for the sledgehammer exhaustive approach above. With the new distance matrix:

VRP_IP_DC1.mw

You can be the first to answer this question!

@Carl Love thanks for your effort.

Sorry to bug you further. How do I return the row numbers of the matrix <LimitDist(56)[]>;

[[1, 4], [1, 5], [1, 2, 3]] = inds 4

 

@tomleslieJust what I wanted! I salute you Sir and Carl Love too.

BTW this problem is inspired by an earlier unanswered question,

http://www.mapleprimes.com/questions/220689-How-To-Solve-A-VRP-

where I was unable to write the ILP constraints properly. Hence my need for the sledgehammer approach above.

@rlopez the OP asked specifically about output of Std. Error w.r.t. NonlinearFit.

 "the summarize option is not available when the model expression is not linear in the parameters"

only

?LinearFit

The summarize option returns a summary for the regression:

Edit.
 

First 7 8 9 10 11 12 13 Last Page 9 of 26