# Dynamic programming with large arrays

Last week we have finished our program which applies a local search. At this moment the program needs more than three hours for the largest instances.

The three hours are too long and we try to optimize it, our profiling (which is not that professional) shows that a series of five functions takes a lot of the running time.

The five functions loop over several arrays with size 2002 and 2003. Can someone help me with improving this functions? The mathematics is already optimized, only performances is important and I'm the only one who has to work with this part of the code.

Note that the multidimensional arrays are expressed as a one dimensional array. First it was expressed as an array of array, however this was quite slower (don't remember the numbers anymore).

The reason why I ask you is that I only have one week left to improve this code and therefore I have no time to try all options. Second, I'm really a newbie if we talk about performance and only have a small year of experience with C++11.

The constructor of the class creates the arrays:

Handling::Handling(size_t nCities)
//:
{
d_v = new int[nCities * nCities]();
d_h = new int[nCities * nCities]();
d_r = new int[nCities * nCities * nCities]();

d_a = new int[nCities * nCities * nCities]();
d_b = new int[nCities * nCities * nCities]();

d_min = new int[nCities * nCities * nCities]();
d_max = new int[nCities * nCities * nCities]();

d_policy  = new int[nCities]();
d_policy2 = new int[nCities]();

cout << "Handling constructed" << endl;
}


The functions are called (see function implementation below):

  int const N = tour.size();
int const M = tour.size() - 2;

// Step 1
for (int i = 1; i != M + 1 ; ++i)
d_h[i*N + i+2] = i + 1;

// Step 2
set_all_a(tour);
set_all_b(tour);
set_all_min(tour);
set_all_max(tour);
set_all_r(tour);


The first function:

void Handling::set_all_a(Tour &tour) const
{
int const N = tour.size();
int const M = tour.size() - 2;

// Calculate all a's
for (int i = 0; i != M; ++i)
{
// Information about city_i
Column const &col_i = tour[i+1];
City const &city_i  = get<Tour::CITY>(col_i);
int const cityi_to  = get<Tour::FROM_TO>(col_i);

for (int w = i + 2; w < M + 1; ++w)
{
//first update condition
// TODO we weten vanaf waar cityi_to > w, misschien uit de for loop halen
int o_iw = 0;
if (city_i.type() == Type::PICKUP)
o_iw = ((cityi_to > w) ? city_i.weight() : 0);  // was w + 1.. nu w  !!!        // TODO weg optimizen?

d_a[(i*N + i+1)*N + w] = o_iw;

for (int k = i + 2; k < w; ++k)
{
Column const &col_k = tour[k];          // Current colomn of tour
City const &city_k = get<Tour::CITY>(col_k);
int o_kw = 0;                   // strange o from paper

// TODO we weten vanaf waar to_k > w, loop naar buiten??
if (city_k.type() == Type::PICKUP)      // is the location a pickup?
{
int to_k = get<Tour::FROM_TO>(col_k);
o_kw = ((to_k > w ) ? city_k.weight() : 0);   // was w + 1.. nu w  !!!        // TODO weg optimizen?
}
d_a[(i*N + k)*N + w] = d_a[(i*N + k-1)*N + w] + o_kw;
}
}
}
}


The second function is quite similar to the first one and therefore not shown. The third function is:

void Handling::set_all_max(Tour &tour) const
{
int const N = tour.size();
int const M = tour.size() - 2;

for (int i = 0; i <= M; ++i)
{
for (int j = i + 1; j <= M + 1; ++j)
{
int max_from = i;
for (int idx = i + 1; idx < j; ++idx)
{
int from_to = get<Tour::FROM_TO>(tour[idx]);
if (from_to < max_from)
max_from = from_to;
}
--max_from;
d_max[i*N + j] = max_from;
}
}
}


The fourth function is again similar to the third question and therefore not given. The final function is:

void Handling::set_all_r(Tour &tour) const
{
int const N = tour.size();
int const M = tour.size() - 2;

for (int i = 0; i != M+1; ++i)
{
for (int k = i + 1; k != M + 2; ++k)
{
int const w_min = d_min[i*N + k];
int const w_max = d_max[i*N + k];

int const a1 = d_a[(i*N + k-1)*N + k];
int const a2 = d_a[(i*N + w_max+1)*N + k];

for (int j = k + 1; j != M + 3; ++j)
{
d_r[(i*N + k)*N + j]
= a1
+ d_b[(i*N + k)*N + j]
- d_b[(i*N + w_min-1)*N + j]
- a2;
}
}
}
}

• From the code you have provided there is nothing that jumps out as bad in terms of performance. BUT in reality that is impossible to know because we don't know the types of half the objects nor can we actually compile or test it. – Martin York Mar 25 '15 at 13:57
• But you do have three O(n^3) functions. These do approximately the same thing (three nested loops) but set up different variables. Can you combine their logic into a single function. – Martin York Mar 25 '15 at 13:59
• @LokiAstari, allmost all types are int, only the Tour and City are not primitive types. I guess this objects does not delay the program since these are only used in the outer loop. Next, what do you mean b combine them in one function? Is it not the case that we then get a worse memory cache? – Michiel uit het Broek Mar 26 '15 at 11:26
•  Is it not the case that we then get a worse memory cache? Maybe, Depends who big your cache is. The only way you could find out is by testing. But given the sizes and any modern machine I doubt it. – Martin York Mar 26 '15 at 17:42
• @LokiAstari thanks for your time so far. Can you help me further if I send you more code such that it executable for you? – Michiel uit het Broek Mar 27 '15 at 16:49