Originally posted by: csfab

Hello everyone, everything good?

I work with a school project, in which we have 11802 GPS coordinates, and we calculate an array of distances. Lots of entries, almost 140 million. And CPLEX gives memory error.

I tried to put the .dat file already with the calculated distances, this is equivalent to 415 MB, I currently put a .dat file with the latitude and longitude entries and it still gives memory problem.

The model is as follows:

 

//Parametros
int n = ...;
range cidades = 1..n;

float latitude[i in cidades] = ...;
float longitude[i in cidades] = ...;

float PI;

execute
{
PI=Math.PI;
}

float pointsRadianlat[i in cidades] = latitude[i]*PI/180;
float pointsRadianlong[i in cidades] = longitude[i]*PI/180;
float earthRadiusKms = 6376.5;

tuple arco {
    int i;
    int j;
}

setof(arco) arcos = {<i,j> | i,j  in cidades: i!=j};

float distancias[arcos];

execute compute_distances {
//writeln(n,"points");

    for(var e in arcos)
        {
        if (0.8*earthRadiusKms*Math.acos(Math.cos(pointsRadianlat[e.i])*Math.sin(pointsRadianlat[e.j])
            +Math.cos(pointsRadianlat[e.i])*Math.cos(pointsRadianlat[e.j])*Math.cos(pointsRadianlong[e.j]-pointsRadianlong[e.i]))/10000 < 0.5)
        
        distancias[e]=0.8*earthRadiusKms*Math.acos(Math.cos(pointsRadianlat[e.i])*Math.sin(pointsRadianlat[e.j])
            +Math.cos(pointsRadianlat[e.i])*Math.cos(pointsRadianlat[e.j])*Math.cos(pointsRadianlong[e.j]-pointsRadianlong[e.i]))/1000
        
        else            
        
            distancias[e]=100000;;
    
          writeln("distance from ",e.i," to ",e.j," = ",distancias[e]);      
        
            
  }
}

int o = 2;
int d = 5000;

//Variaveis de Decisao
dvar boolean rota[arcos];

//Expressoes
dexpr float caminho = sum(<i,j> in arcos: i!=j) distancias[<i,j>]*rota[<i,j>];

//Funcao Objetico
minimize
  caminho;

//Restricoes

subject to{

sum(j in cidades: j!=o && j!=d) rota[<o,j>] == 1;
          

Coneccao:  
forall(w in cidades: w!=o && w!=d)
  sum(<i,w> in arcos) rota[<i,w>] - sum(<w,j> in arcos) rota[<w,j>] == 0;

sum(i in cidades: i!=d && i!=o) rota[<i,d>] == 1;

      
 
}

execute Resultados {
    writeln("Rotas: ");
        for (var c in arcos)
            if(rota[c]==1){
            writeln ("Ruas: " + ' '+c + ' ' + ' '+ ' '+ "(" + (latitude[c.i]+' ' + ' ' + longitude[c.i])+")"
            + ' ' +  "(" + (latitude[c.j]+' ' + ' ' + longitude[c.j])+")");        
        }
            
    writeln("Distancia total percorrida: ", cplex.getObjValue()+' '+"km");
    }
 

Can you help me?

 

The goal is:

Given two points, called the origin = o, and destination = d, of the distance matrix.

What is the shortest distance that connects these two points, I do not want to consider in a straight line, but the corners that connect each one of them;

 

 

 

#CPLEXOptimizers
#DecisionOptimization

Is the distance symmetric? If so, then you can save half of the data since you only have to specify data for the case i<j. The other case is symmetric.

Also, would it be acceptable to store the data as int instead of float? If you store distance in meters and round to meters that may be enough. Storing data as int rather than float may further reduce the memory consumption.

Finally, it looks like you could attack this problem directly using a shortest path algorithm?

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: csfab

Hi Daniel.

The problem is symmetrical yes, I'll try to put it int!

How do I use a shorter path algorithm in CPLEX?

#CPLEXOptimizers
#DecisionOptimization

There is no shortest path algorithm in CPLEX. But you can take any textbook and implement the algorithm that is described there. Or find an implementation on the internet. I am sure there are plenty of implementations around.

#CPLEXOptimizers
#DecisionOptimization