Items tagged with optimization

Feed
Also available: optimization

Experts.

I'm trying to solve a Truck Routing Problem. I set in up in Maple and Excel, but I get a smaller minimum in the spreadsheet, than in Maple. Its like as if I havn't generated enough possible routes, even though i feel i've done an exaustive search. I realise the distance matrix violates the triangle inequality.  Any suggestions....

TRP_14x3.mw

Given

Tour2:=[[[1, 2, 3, 4]], [[1, 2], [1, 3, 4]], [[1, 3], [1, 2, 4]], [[1, 4], [1, 2, 3]], [[1, 2], [1, 3], [1, 4]]]:

Kitonums code

seq(max(seq(add(d[s[i]]*x[s[i],s[i+1]], i=1..nops(s)-1) , s=t))<=K, t=Tour2); produces

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

correctly. The problem is I want to pass this through LPSolve and it doesn't like it. So what I need is to convert it to a constraint it will accept. I found a method on stackexchange,

http://stackoverflow.com/questions/10792139/using-min-max-within-an-integer-linear-program

i'm not sure it even works.i would be great if a procedure could could convert the max's in the above expression, or change the code in bold.

max(6*x[1, 4],4*x[1, 2]+3*x[2, 3]), where x[i,j] are binary vars.
x4 >= 6*x[1, 4];
x4 >= 4*x[1, 2]+3*x[2, 3];
Objective:= x4;

 

Sirs.

Probably a brain fade, but I cant seem to code what i want.

constraints.mw
 

Tour2:=[[[1, 2, 3, 4]], [[1, 2], [1, 3, 4]], [[1, 3], [1, 2, 4]], [[1, 4], [1, 2, 3]], [[1, 2], [1, 3], [1, 4]]];M:=nops(Tour2):

[[[1, 2, 3, 4]], [[1, 2], [1, 3, 4]], [[1, 3], [1, 2, 4]], [[1, 4], [1, 2, 3]], [[1, 2], [1, 3], [1, 4]]]

(1)

interface(rtablesize=M):
  maxEnt:=max([seq(nops(Tour2[i]),i=1..M)]):
  Tours_Distances := Matrix
                     ( maxEnt,
                       M,
                       [ seq
                         ( [ seq
                             ( `if`( numelems(Tour2[i])>=j,
                                     d[i]*x[op(Tour2[i,j])]<=K,
                                    0
                                   ),
                               i=1..M
                             )
                           ],
                           j=1..maxEnt
                         )
                       ]
                     );

Tours_Distances := Matrix(3, 5, {(1, 1) = d[1]*x[1, 2, 3, 4] <= K, (1, 2) = d[2]*x[1, 2] <= K, (1, 3) = d[3]*x[1, 3] <= K, (1, 4) = d[4]*x[1, 4] <= K, (1, 5) = d[5]*x[1, 2] <= K, (2, 1) = 0, (2, 2) = d[2]*x[1, 3, 4] <= K, (2, 3) = d[3]*x[1, 2, 4] <= K, (2, 4) = d[4]*x[1, 2, 3] <= K, (2, 5) = d[5]*x[1, 3] <= K, (3, 1) = 0, (3, 2) = 0, (3, 3) = 0, (3, 4) = 0, (3, 5) = d[5]*x[1, 4] <= K})

(2)

convert( (2), 'list', 'nested' );

[[d[1]*x[1, 2, 3, 4] <= K, d[2]*x[1, 2] <= K, d[3]*x[1, 3] <= K, d[4]*x[1, 4] <= K, d[5]*x[1, 2] <= K], [0, d[2]*x[1, 3, 4] <= K, d[3]*x[1, 2, 4] <= K, d[4]*x[1, 2, 3] <= K, d[5]*x[1, 3] <= K], [0, 0, 0, 0, d[5]*x[1, 4] <= K]]

(3)

 

But what I want is:

d[1]*x[1,2]+d[2]*x[2,3]+d[3]*x[3,4]<=K,d[1]*x[1,2]<=K,d[1]*x[1,3]+d[3]*x[3,4]<=K;      #.....etc.

 

 

 

 

 

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

(4)

NULL


 

Download constraints.mw

 

I want to maximize a total profit (TP) function which is dependent on five independent variables (E,W,T, theta, tp). All these five variables can have non negative values. The TP function is given below- ( first TP is directly copied from maple worksheet and than copied again as a picture for clear viewing).

 

 TP = (p1*(Q-q)+p1*(1-theta)*(q-E)+s*E-c*Q-o-h*((1/6)*alpha*W^beta*a*p1^(-b)*tp^3/m-(1/2)*alpha*W^beta*a*p1^(-b)*tp^2+Q*tp)-(t1-tp)*h*((1/2*(-(2/3)*t1+m-(1/3)*tp))*W^beta*a*alpha*(t1-tp)*(-p1*(-1+theta))^(-b)+W*m)/m-(1/2)*h*(W+E)*(T-t1))/T-u*W

 

I am trying the maximize TP with respect to above five independent variables. I tried to solve  five equations ( representing first order partial derivative of TP with respect to each of the independent variables equated to zero) simultaneously by "solve" and "fsolve" command but both these commands fail to give any output. I have also tried three other commands in optimization package ( QPSolve, NLPSolve, Maximize) but all these three commands also doesn't give any output. I want to prove the concavity of TP function with respect to five independent variables, please guide how it can be done. ( I have computed the Hessian matrix but since five first order equations doesn't give output ( through fsolve command) so I am unable to compute Hessian at these first order optimiality condition solution.). The values of the paramters in the TP equation are -

[alpha = 50, beta = .7, c = 20, h = 4, m = .4, o = 10, p1 = 40, s = 10, u = 5, a = 15000, b = 2]

i use optimization package with constraint hello >= 0

Minimize(xx=0, {hello >= 0})

but solution only return the case when hello = 0

how about hello > 0?

i would like to find all possible set of solutions using this constraint

do i need to set upper bound, such as {hello <= 7, hello >=0}

can it return solution when hello = 1.1, 1.2, ...2, 2.1, 2.2, 2.3, ....7

hello, i have problem here.

> restart;
> with(linalg);
> NULL;
> fungsi1 := sum(d1[h]+b1[h], h = 1 .. 7);
> fungsi2 := sum(sum(d2[h, t]+b2[h, t], t = 1 .. 23), h = 1 .. 7);
> fungsi3 := sum(sum(d3[h, t]+b3[h, t], t = 1 .. 23), h = 1 .. 7);
> fungsi4 := sum(d4[k]+b4[k], k = 1 .. 3);
> fungsi := fungsi1+fungsi2+fungsi3+fungsi4;
> NULL;
> NULL;
> k1 := seq(sum(X[h, t], t = 1 .. 23) >= 9, h = 1 .. 6);
> k2 := seq(sum(Y[h, t], t = 1 .. 23) >= 2, h = 1 .. 6);
> k3 := seq(sum(Z[h, t], t = 1 .. 23) >= 2, h = 1 .. 6);
> NULL;
> k4 := seq(seq(X[h, t]+Y[h, t]+Z[h, t] <= 1, h = 1 .. 6), t = 1 .. 23);
> NULL;
> k5 := seq(seq(Z[h, t]+Z[h+1, t] <= 1, h = 1 .. 6), t = 1 .. 23);
> NULL;
> k6 := seq(sum(X[h, t]+Y[h, t]+Z[h, t], t = 1 .. 23) >= 5, h = 1 .. 7);
> k7 := seq(sum(X[h, t]+Y[h, t]+Z[h, t], t = 1 .. 23) <= 6, h = 1 .. 7);
> NULL;
> k8 := seq(sum(X[h, t], t = 1 .. 23)+b1[h]-d1[h] <= 15, h = 1 .. 6);
> k9 := seq(sum(Y[h, t], t = 1 .. 23)+b1[h]-d1[h] <= 4, h = 1 .. 6);
> k10 := seq(sum(Z[h, t], t = 1 .. 23)+b1[h]-d1[h] <= 4, h = 1 .. 6);
> NULL;
> k11 := seq(seq(Y[h, t]+Y[h+1, t]+b2[h, t]-d2[h, t] <= 1, t = 1 .. 23), h = 1 .. 6);
> NULL;
> k12 := seq(seq(Z[h, t]+Z[h+1, t]+b3[h, t]-d3[h, t] <= 1, t = 1 .. 23), h = 1 .. 6);
> NULL;
> k13 := sum(X[7, t], t = 1 .. 23)+b4[1]-d4[1] = 2;
> k14 := sum(Y[7, t], t = 1 .. 23)+b4[1]-d4[1] = 2;
> k15 := sum(Z[7, t], t = 1 .. 23)+b4[1]-d4[1] = 2;
> with(Optimization);
[ImportMPS, Interactive, LPSolve, LSSolve, Maximize, Minimize, 

  NLPSolve, QPSolve]
> CodeTools:-Usage(LPSolve(fungsi, {k1, k10, k11, k12, k13, k14, k15, k2, k3, k4, k5, k6, k7, k8, k9}, assume = {integer, nonnegative}));
Error, (in Optimization:-LPSolve) no feasible point found for LP subproblem

why it can be? please i need help. 

I was looking to see if anyone has come across a Maple routine for a savings algorithm - specifically, Clarke and Wright. In fact, any classical savings heuristic would also be interesting.

Any guidance would be truly appreciated.

If binary constraints are imposed on an optimization problem and LPSolve presents a solution, is it possible to extract the variables that have zero or one assigned to them? This would be most useful if there are many variables, for example...

If a solution is returned that looks like ...

[x[001]=0, x[101]=1, x[201]=0, x[301]=1, ....], how can I filter those solutions that equal zero?

Thanks for reading!

I was curious to know if one can extract a specific solution from a LPSolve routine. 

As an example, consider the following output to a constrained linear problem. The objective value is 8 and the decision variable values (binary) are given.

Sol := [8, [w[1, 1] = 1., x[0, 0, 1] = 0, x[0, 1, 1] = 1, x[0, 2, 1] = 0, x[1, 0, 1] = 0, x[1, 1, 1] = 0, x[1, 2, 1] = 1, x[2, 0, 1] = 0, x[2, 1, 1] = 0, x[2, 2, 1] = 0, y[0, 0] = 0., y[0, 1] = 0., y[1, 1] = 2.]]

I am interested to know if we can isolate any variable value from this solution. I know that Sol[1] will return 8, and Sol[2] will return the remaining terms. But what if I wanted, say, x[1,2,1] alone?

Thanks for reading!

guys, need your help. i've been trying to find 9 pamater which are psi1,psi2,psi3,m1,m2,m3,sigma1,sigma2,sigma3. I need to minimize one function. i have datas and several contraints. i will share this with you guys. Really need your help and i'll appreciate any suggestion. Thanks

data:

a(x):=qtopi[x];

this is my objective function:

fungsikerugian := sum((1-(1-(psi1*exp(-((x+1)/m1)^(m1/sigma1))+psi2*(1-exp(-((x+1)/m2)^(-m2/sigma2)))+psi3*exp(exp(-m3/sigma3)-exp((x+1-m3)/sigma3)))/(psi1*exp(-(x/m1)^(m1/sigma1))+psi2*(1-exp(-(x/m2)^(-m2/sigma2)))+psi3*exp(exp(-m3/sigma3)-exp((x-m3)/sigma3))))/a(x))^2, x = 0 .. 111);

these are my contraints

a := psi1+psi2+psi3 = 1;
         
b := 0 <= exp(-((x+1)/m1)^(m1/sigma1));
                          
c := 1 >= exp(-((x+1)/m1)^(m1/sigma1));
                       
d := 0 <= 1-exp(-((x+1)/m2)^(-m2/sigma2));
                        
e := 1 >= 1-exp(-((x+1)/m2)^(-m2/sigma2));
                 
f := 0 <= exp(exp(-m3/sigma3)-exp((x+1-m3)/sigma3));
                  
g := 1 >= exp(exp(-m3/sigma3)-exp((x+1-m3)/sigma3));
            
h := 0 <= exp(-(x/m1)^(m1/sigma1));
                        
i := 1 >= exp(-(x/m1)^(m1/sigma1));
                     
j := 0 <= 1-exp(-(x/m2)^(-m2/sigma2));
                           
k := 1 >= 1-exp(-(x/m2)^(-m2/sigma2));
                      
l := 0 <= exp(exp(-m3/sigma3)-exp((x-m3)/sigma3));
                   
m := 1 >= exp(exp(-m3/sigma3)-exp((x-m3)/sigma3));
               
n := 0 <= 1-(psi1*exp(-((x+1)/m1)^(m1/sigma1))+psi2*(1-exp(-((x+1)/m2)^(-m2/sigma2)))+psi3*exp(exp(-m3/sigma3)-exp((x+1-m3)/sigma3)))/(psi1*exp(-(x/m1)^(m1/sigma1))+psi2*(1-exp(-(x/m2)^(-m2/sigma2)))+psi3*exp(exp(-m3/sigma3)-exp((x-m3)/sigma3)));

o := 1 >= 1-(psi1*exp(-((x+1)/m1)^(m1/sigma1))+psi2*(1-exp(-((x+1)/m2)^(-m2/sigma2)))+psi3*exp(exp(-m3/sigma3)-exp((x+1-m3)/sigma3)))/(psi1*exp(-(x/m1)^(m1/sigma1))+psi2*(1-exp(-(x/m2)^(-m2/sigma2)))+psi3*exp(exp(-m3/sigma3)-exp((x-m3)/sigma3)));
 
i use this to solve that but seems to not going anywhere
NLPSolve(fungsikerugian, {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o}, assume = nonnegative);
 
Thanks

I wish to apply several i-j constraints to an optimization problem that involves minimizing a function x[i,j]. 

Does anyone know of a simple way to exclude values for i and j? For instance, how do we specify the conditions, i not equal to j, i is not equal to 1, etc.?

Thanks in advance!

 

 

Can somebody suggest an efficient way to specify / input a large list of binary variables in the LPSolve command, for example:

> LPSolve(objective function, constraints, binaryvariables={ x[0,0,1], .x[0,0,2], ...., x[i,j,k]}

Is it possible to assign a name to the set rather than input each element, x[i,j,k], manually?

Thanks in advance!

Friends in Maple

I have a Vehicle Routing Problem I wish to cast as a integer model. VRP is a kind of TSP and knapsack problem hybrid  I would be grateful if someone can finish it. answers included. This isn't homework BTW.

VRP_IP.mw

Dear all

I would like to minimuze the following function 4 x ^2 + 4 x y  under constraint  16=x^2 y  and both x , y  nonnegative real number 

this is my code

with(Optimization)

Minimize(4*x^2+4*x*y, {x^2*y = 16}, assume = nonnegative)

 

The result obtained from this code is strange

because when i do directly the computation without maple by substituting y =16/x^2 and simple derivation i get the minimum is at x=2 and so y=4 and therefore the minimum is 48

But as i say using my code I obtained a different solution

whats is the problem occurs in this situation

Many thanks

 

Hello

I know there are other methods to solve this classic probem, but I wanted to cast it as a linear program. I wonder if an expert can look at my IP coding and please correct my error.

TSP_IP.mw

sorry its a mishmash of 1D and 2D inputs

1 2 3 4 5 6 7 Last Page 1 of 15