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 200² and 200³. 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;
      }
    }
  }
}