too much memory used/ no optimization happen

[Nardine Basta]

Hello,

I have a problem with my code. I always get too out of memory error.

I tried simplifying the data... the outcome is no optimization at all. it simple gave me straight ones to the ho variable.

I am sure there is sthg wrong with the structure that i cannot see due to my lack of experience in this domain.

any help is highly appreciated

# algorithm to predict vehicles destination and compare it with the

#real life ones for validation

param T := 744;

set ID;     # location ids

set Veh;   #drivers

set socialSphere within  {Veh,ID};

set Destinations within {Veh,ID,1..T};

set home within {Veh,ID};

set work within {Veh,ID};

set study within {Veh,ID};

set leisure within {Veh,ID}; 

 

param attHome{Veh,ID} >= 0;#the weight of the attraction between a vehicle and a locatoion of type home.

param attWork{Veh,ID} >= 0;

param attStudy{Veh,ID} >= 0;

param attLeisure{Veh,ID} >= 0;

#indicates the importance variation of each location type with time

var ho {1..T} >= 0;

var wo {1..T} >= 0;

var st {1..T} >= 0;

var le {1..T} >= 0;

#calculate the attraction of a driver to each of the locations 

#in its social sphere according to the type of the location

var locAttraction{v in Veh,e in ID,t in 1..T}=

(if (v,e) in home        

then ho [t]*attHome[v,e]

else if (v,e) in work

then wo [t]*attWork[v,e]

else if (v,e) in study 

then st [t]*attStudy[v,e]

else if (v,e) in leisure

then le [t]*attLeisure[v,e] 

else 0

);

#getting the score of the maximumlocation

var maxLoc{v in Veh,t in 1..T}=max {e in ID} locAttraction[v,e,t];

#trying to get the location having the maximum score (substitute of argmax)

# that at the same time matches the real life location

var chosenLoc{v in Veh,e in ID,t in 1..T}=

(if   (v,e,t) in Destinations

then (if ( (v,e) in socialSphere  and locAttraction[v,e,t] = maxLoc[v,t] and Destination[v,t]=e)

then 1 else 0));

#since more than one locaation can have the same attraction. 

#it is cheking that for each vehicle there is at least one match

# with the real of a maximum soredd location with the real life location

var matching{v in Veh,t in 1..T}=

(if (

(sum{e in ID } chosenLoc[v,e,t] ) >0  )         

then 1 else 0);

#maximising the number of matches, i.e vehcles whose chosen location

# match the real life ones

maximize Total_match:

sum {v in Veh, t in 1..T} matching[v,t] ;

     

# since the possible the algorith favours one type of attracion rather than 

#the other, attractions should sum up to one to ease the comparaison.

subject to Time {t in 1..T}:

ho [t]+wo [t]+st [t]+le [t]=1;

[Victor Zverovich]

What are the dimensions of sets ID and Veh? Out of memory can be caused by {Veh,ID,1..T} being too big.

HTH,

Victor

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

[Nardine Basta]

thank you for replying.

I managed the out of memory error. I am now in the stage of no optimization. I get straight ones for the ho variable.

the attHome[v,e] attribute that is multiplied by the ho variable is always bigger than attWork[v,e], attStudy[v,e], and attLeisure[v,e].

which mean that the optimization is not so much affected by the objective function as much as by the parameter that directly multiplies it (that is my interpretation of the problem)

I kindly ask for an advice on what my might be the reason 

thank you in advance

[Robert Fourer]

By applying "max" and "if" to variables in your var definitions, you are creating a large number of nonlinearities that solvers cannot handle well. To get good results you will need to think about reformulating this problem as a linear mixed-integer program. For maxLoc it will probably work to specify

var maxLoc {v in Veh, t in 1..T};
subj to maxLocDefn {v in Veh, t in 1..T, e in ID}: maxLoc[v,t] >= locAttraction[v,e,t];

This is linear and at least it will force maxLoc[v,t] >= max {e in ID} locAttraction[v,e,t]. For vars chosenLoc and matching, you should define them as binary variables and then use linear constraints to force them to be 0 or 1 as appropriate; as a start on learning how this is done, see section 20.2 "Zero-one variables and logical conditions" in the AMPL book (http://ampl.com/BOOK/CHAPTERS/23-integer.pdf#page=3).

Bob Fourer
am...@googlegroups.com

=======

[Nardine Basta]

Thank you so much for the detailed reply :)

On Monday, April 4, 2016 at 1:23:32 AM UTC+2, Nardine Basta wrote:

[Nardine Basta]

Hello,

I have linearized the model as below: I got the following error

Error at _cmdno 17 executing "solve" command

(file mobilitymodel2.run, line 88, offset 2652):

error processing constraint maxLocDefn[2,'-103667851#8',1]:

invalid subscript locAttraction[2,'-103667851#8',1]

your help is highly appreciated

# algorithm to predict vehicles destination and compare it with the

#real life ones for validation

param T := 744;

set ID;     # location ids

set Veh;   #drivers

set socialSphere within  {Veh,ID};

set Destinations within {Veh,ID,1..T};

set hasaDest within {Veh,1..T}; #vehicle has a record in the real life destinations at this time slot

set home within {Veh,ID};

set work within {Veh,ID};

set study within {Veh,ID};

set leisure within {Veh,ID}; 

 

param Destination{Veh,1..T} >= 0;

param attHome{Veh,ID} >= 0;#the weight of the attraction between a vehicle and a locatoion of type home.

param attWork{Veh,ID} >= 0;

param attStudy{Veh,ID} >= 0;

param attLeisure{Veh,ID} >= 0;

#indicates the importance variation of each location type with time

var ho {1..T} >= 0;

var wo {1..T} >= 0;

var st {1..T} >= 0;

var le {1..T} >= 0;

#calculate the attraction of a driver to each of the locations 

#in its social sphere according to the type of the location

/*

(if (v,e) in home        

then ho [t]*attHome[v,e]

else if (v,e) in work

then wo [t]*attWork[v,e]

else if (v,e) in study 

then st [t]*attStudy[v,e]

else if (v,e) in leisure

then le [t]*attLeisure[v,e] 

else 0

);*/

var locAttraction{v in Veh,e in Edges,t in 1..T: (v,e) in socialSphere and  (v,e) in hasaDest}=

ho [t]*attHome[v,e]+ wo [t]*attWork[v,e]+st [t]*attStudy[v,e]+le [t]*attLeisure[v,e] ;

# since the possible the algorithm favours one type of attracion rather than 

#the other, attractions should sum up to one to ease the comparaison.

subject to Time {t in 1..T}:

ho [t]+wo [t]+st [t]+le [t]=1;

#getting the score of the maximumlocation

#var maxLoc{v in Veh,t in 1..T}=max {e in Edges} locAttraction[v,e,t];

var maxLoc {v in Veh, t in 1..T:  (v,t) in hasaDest}; 

subj to maxLocDefn {v in Veh, e in Edges, t in 1..T: (v,e) in socialSphere }:

  maxLoc[v,t] >= locAttraction[v,e,t]; 

#trying to get the location having the maximum score (substitute of argmax)

# that at the same time matches the real life location

/*

var chosenLoc{v in Veh,e in Edges,t in 1..T}=

(if   (v,e,t) in Destinations

then (if ( (v,e) in socialSphere  and locAttraction[v,e,t] = maxLoc[v,t] and Destination[v,t]=e)

then 1 else 0));

*/

var chosenLoc{v in Veh,e in Edges,t in 1..T : (v,e) in socialSphere  and (v,t) in hasaDest};

 

#since more than one location can have the same attraction. 

#it is cheking that for each vehicle there is at most one match

subject to choosenLoc2{v in Veh, t in 1..T :  (v,t) in hasaDest }:

sum{e in Edges : (v,e) in socialSphere } chosenLoc[v,e,t]  <= 1;

subject to choosenLoc3 {v in Veh, e in Edges, f in Edges , t in 1..T 

: f<>e and (v,e) in socialSphere and (v,f) in socialSphere and  (v,t) in hasaDest }:

  (locAttraction[v,e,t] - locAttraction[v,f,t]) *

   (chosenLoc[v,e,t] - chosenLoc[v,f,t]) >= 0;

   

/*

subject to choosenLoc4{v in Veh,e in Edges,t in 1..T}:

locAttraction[v,e,t]*chosenLoc[v,e,t] = maxLoc[v,t]*chosenLoc[v,e,t];

*/

subject to choosenLoc4a{v in Veh,e in Edges,t in 1..T : (v,e) in socialSphere and  (v,t)in hasaDest }:

locAttraction[v,e,t] -maxLoc[v,t] <= 1*(1-chosenLoc[v,e,t] );

subject to choosenLoc4b{v in Veh,e in Edges,t in 1..T : (v,e) in socialSphere and  (v,t) in hasaDest}: 

locAttraction[v,e,t] - maxLoc[v,t] >= -1*(1-chosenLoc[v,e,t] );

#maximising the number of matches, i.e vehcles whose chosen location

# match the real life ones

/*

var matching{v in Veh,t in 1..T}=

(if (

(sum{e in Edges } chosenLoc[v,e,t] ) >0  )         

then 1 else 0);

maximize Total_match:

sum {v in Veh, t in 1..T} matching[v,t] ;

*/

maximize Total_match:

sum {v in Veh,e in Edges, t in 1..T  : (v,e) in socialSphere  and (v,e,t) in Destinations  } chosenLoc[v,e,t];

     

Thank you so much in advance :)

[Robert Fourer]

This error message is telling you that in constraint maxLocDefn[2,'-103667851#8',1] there is a reference to a variable locAttraction[2,'-103667851#8',1] that doesn't exist. You define the locAttraction variables with

var locAttraction {v in Veh, e in Edges, t in 1..T:
(v,e) in socialSphere and (v,e) in hasaDest} = ...

but you define the maxLocDefn constraints with

subj to maxLocDefn {v in Veh, e in Edges, t in 1..T:

(v,e) in socialSphere}: ...

so it seems likely that this error occurs because (2,'-103667851#8') is in socialSphere but it is not in hasaDest.

Bob Fourer
am...@googlegroups.com

=======

From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of Nardine Basta
Sent: Tuesday, April 12, 2016 1:59 PM
To: AMPL Modeling Language
Cc: 4...@ampl.com
Subject: Re: [AMPL 11803] too much memory used/ no optimization happen

I have linearized the model as below: I got the following error
Error at _cmdno 17 executing "solve" command
(file mobilitymodel2.run, line 88, offset 2652):
error processing constraint maxLocDefn[2,'-103667851#8',1]:
invalid subscript locAttraction[2,'-103667851#8',1]

...

var locAttraction{v in Veh,e in Edges,t in 1..T: (v,e) in socialSphere and (v,e) in hasaDest}=
ho [t]*attHome[v,e]+ wo [t]*attWork[v,e]+st [t]*attStudy[v,e]+le [t]*attLeisure[v,e] ;

...

[Nardine Basta]

Thank you so much for  your reply.

the problem is solved, however even after linearizing the model, no optimization happen, and I cannot figure out why. I kindly ask for ur help in figuring out where to look.

please, find attached the code, with the nonlinear statement commented and its linearization just below it along with the database tables.

 the only non linear constraint is to choosenLoc3, i tried running the code without it but still no optimization,  am not sure how significant its presence is as my expertise in limited programming is very limited. I am using this as a validation for my PhD theory.

Your help is highly appreciated

I again deeply thank you for ur support

[Robert Fourer]

To get help with this kind of problem, you will need to copy all of the message output that the solver produced when it ran, and paste it into an email to this forum. (Also if the message says "optimal solution found" then you should explain why you think that the solution is not really optimal.)

[Nardine Basta]

thank you so much for ur concern

I understood where the problem lies however i find some difficulties in solving it.:

based on the linearized code below: the problem is in   maxLoc[v,t] >= attractionperLoc[v,e,t]; 

when all the values of attractionperloc are zeros then the maxloc will be zero and thus the chosenloc for this location will be 1 while it should not since the attraction matches the maximum based  on the non linear statement below

/*

var chosenLoc{v in Veh,e in Edges,t in 1..T}=

(   if (  relAttraction[v,u,t] = maxLoc[v,t] and maxLoc[v,t]>0)

then 1 else 0);

*/

to solve the problem the the statement in red is added. However I failed to linearize and maxLoc[v,t]>0). 

your help is highly appreciated.

below the non linear commented statement followed by its linear form

I also kindly ask for ur opinion on how the solver will react to the constraint choosenLoc3

does it need to be simplified more? any hint how?

Thank you in advance

---------------------------------------------------------------the code

param T := 744;

#set ID;     # location ids

set Veh;   #drivers

set Edges;

set socialSphere within  {Veh,Edges};

set Destinations within {Veh,Edges,1..T};

set hasaDest within {Veh,1..T}; #vehicle has a record in the real life destinations at this time slot

 

param Destination{Veh,1..T} symbolic in Edges;

param family{Veh,Veh} default 0;#the weight of the attraction between a vehicle and a locatoion of type home.

param friend{Veh,Veh} default 0;

param coworker{Veh,Veh} default 0;

#indicates the importance variation of each location type with time

var fa {1..T} >= 0;

var fr {1..T} >= 0;

var co {1..T} >= 0;

var relAttraction{v in Veh,u in Veh,t in 1..T: v<>u}=

fa [t]*family[v,u]+ fr [t]*friend[v,u]+co [t]*coworker[v,u] ;

# since the possible  algorithm favours one type of attracion rather than 

#the other with time, attractions variables to be tuned should sum up to one to ease the comparaison.

subject to Time {t in 1..T}:

fa [t]+fr [t]+co [t]=1;

#sum of the social ties between v and u who are now  at the location s. 

var attractionperLoc{v in Veh,e in Edges,t in 1..T : (v,e) in socialSphere  and (v,t) in hasaDest}=

sum {u in Veh: v<>u and (u,t) in hasaDest and e= Destination[u,t]}relAttraction[v,u,t] ;

#getting the score of the maximumlocation

#var maxLoc{v in Veh,t in 1..T}=max {e in Edges} relAttraction[v,u,t];

var maxLoc {v in Veh, t in 1..T:  (v,t) in hasaDest}>= 0; 

subj to maxLocDefn {v in Veh, e in Edges, t in 1..T: (v,e) in socialSphere and (v,t) in hasaDest}:

  maxLoc[v,t] >= attractionperLoc[v,e,t]; 

then the chosen loction will be 1 in this case while it should not 

#trying to get the location having the maximum score (substitute of argmax)

# that at the same time matches the real life location

/*

var chosenLoc{v in Veh,e in Edges,t in 1..T}=

(   if (  relAttraction[v,u,t] = maxLoc[v,t] and maxLoc[v,t]>0)

then 1 else 0);

*/

var chosenLoc{v in Veh,e in Edges,t in 1..T };

 

#since more than one location can have the same attraction. 

#it is cheking that for each vehicle there is at most one match

subject to choosenLoc2{v in Veh, t in 1..T :  (v,t) in hasaDest }:

sum{e in Edges : (v,e) in socialSphere } chosenLoc[v,e,t]  <= 1;

subject to choosenLoc3 {v in Veh, e in Edges, f in Edges , t in 1..T 

: f<>e and (v,e) in socialSphere and (v,f) in socialSphere and  (v,t) in hasaDest }:

  (attractionperLoc[v,e,t] - attractionperLoc[v,f,t]) *

   (chosenLoc[v,e,t] - chosenLoc[v,f,t]) >= 0;

   

/*

subject to choosenLoc4{v in Veh,e in Edges,t in 1..T}:

relAttraction[v,u,t]*chosenLoc[v,e,t] = maxLoc[v,t]*chosenLoc[v,e,t];

*/

subject to choosenLoc4a{v in Veh,e in Edges,t in 1..T : (v,e) in socialSphere and  (v,t)in hasaDest }:

attractionperLoc[v,e,t] -maxLoc[v,t] <= 1*(1-chosenLoc[v,e,t] );

subject to choosenLoc4b{v in Veh,e in Edges,t in 1..T : (v,e) in socialSphere and  (v,t) in hasaDest}: 

attractionperLoc[v,e,t] - maxLoc[v,t] >= -1*(1-chosenLoc[v,e,t] );

#maximising the number of matches, i.e vehcles whose chosen location

# match the real life ones

maximize Total_match:

sum {v in Veh,e in Edges, t in 1..T  : (v,e) in socialSphere  and (v,e,t) in Destinations  } chosenLoc[v,e,t];

     

[Robert Fourer]

Because you write "then 1 else 0" this is actually an "if and only if" condition, so it can be written as two conditions

relAttraction[v,u,t] = maxLoc[v,t] and maxLoc[v,t] > 0 implies chosenLoc[v,e,t] = 1
relAttraction[v,u,t] <> maxLoc[v,t] or maxLoc[v,t] = 0 implies chosenLoc[v,e,t] = 0

or equivalently the other way around,

chosenLoc[v,e,t] = 1 implies relAttraction[v,u,t] = maxLoc[v,t] and maxLoc[v,t] > 0
chosenLoc[v,e,t] = 0 implies relAttraction[v,u,t] <> maxLoc[v,t] or maxLoc[v,t] = 0

which may be more helpful in seeing how to write the linearization. The first of the above two conditions is relatively easy since it breaks into two separate implications (one for each side of the "and") but the second is harder and will most likely require a separate zero-one variable for each side of the "or".

Before you go to all the trouble of figuring this out, however, you may want to ask yourself whether both of these conditions are actually needed. In many formulations it turns out that only the "if" or the "only if" side is needed to give a correct formulation. Also you should consider whether the formulation would remain correct if the = is replaced by a >= or a <= since that will simplify the linearization. (I don't know the answers since they depend on the details of your model.)

Bob Fourer
am...@googlegroups.com

P.S.: Your constraint choosenLoc3 involves variables times variables and hence is quadratic. I doubt it will work well with any solver. However since it only involves continuous variables times binary variables, it can be linearized using the ideas described by Paul Rubin at http://orinanobworld.blogspot.com/2010/10/binary-variables-and-quadratic-terms.html.

[Nardine Basta]

i am not sure what i did is correct.

in my case if maxLoc[v,t] then for sure chosenLoc[v,e,t] = 0

else if(relAttraction[v,u,t]=maxLoc[v,t] then chosenLoc[v,e,t] = 1

else chosenLoc[v,e,t] = 0

so i treated these as two separate constrains and added the following 3 constraints

1- 100*maxLoc[v,t]>=chosenLoc[v,e,t]

2- attractionperLoc[v,e,t] -maxLoc[v,t] <= 100*(1-chosenLoc[v,e,t] );

 

3-attractionperLoc[v,e,t] - maxLoc[v,t] >= -100*(1-chosenLoc[v,e,t] );

thank you

[Robert Fourer]

You write "... else if(relAttraction[v,u,t]=maxLoc[v,t] then chosenLoc[v,e,t] = 1 ..." but relAttraction[v,u,t] does not appear in any of your constraints. So I think there is something that needs to be fixed here. Also it's not clear what you mean by "if maxLoc[v,t] then for sure chosenLoc[v,e,t] = 0".

Once you have the constraint statements corrected, consider that chosenLoc[v,e,t] is either going to be 1, or it is going to be 0. So first try setting it to 1 in all your constraints, and consider whether the constraints have the effect that you want; then do the same for setting it to 0.

Bob Fourer
am...@googlegroups.com

[Nardine Basta]

thank you so much for your concern.I have two versions of the code to solve to almost similar problems, relattr appears in my before ast reply. However to clarify. I will stick to my first version of code.

chosenloc is a binary to replace the argmax function

what i mean by  if maxLoc[v,t] then for sure chosenLoc[v,e,t] = 0

 chosenlocis a binary to mark the locattr that have a value equals to the maximum.

if maxloc[v,t]  which signifies the maximum location attraction = 0 then all attractions for this vehicle are zero and no locations should be chosen 

thus in this case chosenloc=0

if it is not zero then

if locAttraction[v,e,t]= maxLoc[v,t]

then chosenLoc[v,e,t] =1

else

chosenLoc[v,e,t] = 0

so i am trying to linearize the following

 if (  locAttraction[v,f,t] = maxLoc[v,t] and maxLoc[v,t]>0)

then 1 else 0);

by doing the following:

1- 100*maxLoc[v,t]>=chosenLoc[v,e,t]

2- locAttraction[v,e,t] -maxLoc[v,t] <= 100*(1-chosenLoc[v,e,t] );

 

3-locAttraction[v,e,t] - maxLoc[v,t] >= -100*(1-chosenLoc[v,e,t] );

is this correct or there is a case that i am missing.

thank you

[Robert Fourer]

Either chosenLoc[v,e,t] is going to be 1 or it is going to be 0. If chosenLoc[v,e,t] is 1, then the constraints become

100 * maxLoc[v,t] >= 1
locAttraction[v,e,t] - maxLoc[v,t] <= 0
locAttraction[v,e,t] - maxLoc[v,t] >= 0

which simplifies to

maxLoc[v,t] >= 0.01

locAttraction[v,e,t] = maxLoc[v,t]

Similarly you can analyze the case where chosenLoc[v,e,t] is 0 -- in that case it turns out that all of the constraints are trivial. Thus the effect of the constraints is to say that

chosenLoc[v,e,t] = 1 implies

maxLoc[v,t] >= 0.01 and locAttraction[v,e,t] = maxLoc[v,t]

which is logically equivalent to saying that

maxLoc[v,t] < 0.01 or locAttraction[v,e,t] <> maxLoc[v,t] implies
chosenLoc[v,e,t] = 0

If that is not what you want, then you'll need to revise the formulation -- maybe you need to add some constraints that will be nontrivial when chosenLoc[v,e,t] = 0. If you do revise the formulation, then you can make this same kind of analysis to see whether it is correct for your model.

Bob Fourer
am...@googlegroups.com

=======

From: am...@googlegroups.com [mailto:am...@googlegroups.com] On Behalf Of Nardine Basta
Sent: Monday, April 25, 2016 10:56 PM
To: AMPL Modeling Language
Cc: 4...@ampl.com