source: branches/QAPGenerators/HeuristicLab.Problems.Instances.QAPGenerator/3.3/Generators/TaillardQAPInstanceGenerator.cs @ 14704

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using HeuristicLab.Core;

namespace HeuristicLab.Problems.Instances.QAPGenerator {
  public static class TaillardQAPInstanceGenerator {
    /// <summary>
    /// Generates two random symmetric matrices with independent uniformly distributed elements in the range [0;100[.
    /// The generated instances are referred to as Tai-a or taiXXa instances published in the literature.
    /// The instance generator is described in E. Taillard. 1991. Robust Taboo Search for the Quadratic Assignment Problem. Parallel Computing, Vol 17, pp. 443-455.
    /// </summary>
    /// <param name="N">The width and height of the matrices to generate, i.e. the size of the problem instance.</param>
    /// <param name="A">The flow matrix.</param>
    /// <param name="B">The distance matrix.</param>
    /// <param name="random">The random number generator to use, in case this is omitted Taillard's default PRNG and seed will be used.</param>
    public static void GenerateTaia(int N, out double[,] A, out double[,] B, IRandom random = null) {
      if (random == null) random = new Bratley(123456789);
      A = new double[N, N];
      B = new double[N, N];
      for (var i = 0; i < N - 1; i++) {
        for (var j = i + 1; j < N; j++) {
          A[i, j] = Math.Floor(100.0 * random.NextDouble());
          A[j, i] = A[i, j];
        }
      }
      for (var i = 0; i < N - 1; i++) {
        for (var j = i + 1; j < N; j++) {
          B[i, j] = Math.Floor(100.0 * random.NextDouble());
          B[j, i] = B[i, j];
        }
      }
    }

    /// <summary>
    /// The generated instances are referred to as Tai-b or taiXXb instances published in the literature.
    /// The instance generator is described in E. Taillard. 1995. Comparison of iterative searches for the quadratic assignment problem. Location Science, Vol 3, No. 2, pp. 87-105.
    /// </summary>
    /// <param name="N">The width and height of the matrices to generate, i.e. the size of the problem instance.</param>
    /// <param name="maxClusterDistance">The maximum radius of the disc that contains the clusters.</param>
    /// <param name="maxClusterSize">The maximum size of clustered locations.</param>
    /// <param name="maxClusterRadius">The maximum radius of the disc that contains the clustered locations.</param>
    /// <param name="minFlowExponent">The minimum exponent that determines the flows to other facilities.</param>
    /// <param name="maxFlowExponent">The maximum exponent that determines the flows to other facilities.</param>
    /// <param name="A">The flow matrix.</param>
    /// <param name="B">The distance matrix.</param>
    /// <param name="random">The random number generator to use, in case this is omitted Taillard's default PRNG and seed will be used.</param>
    public static void GenerateTaib(int N, int maxClusterDistance, int maxClusterSize, int maxClusterRadius, int minFlowExponent, int maxFlowExponent, out double[,] A, out double[,] B, IRandom random = null) {
      if (random == null) random = new Bratley(123456789);
      var locations = new double[N, 2];
      var loc = 0;
      while (loc < N) {
        var clusterDirection = random.NextDouble() * 2 * Math.PI;
        var clusterDistance = random.NextDouble() * maxClusterDistance;
        var clusterSize = random.Next(1, maxClusterSize);
        for (var i = 0; i < clusterSize; i++) {
          var locationDirection = random.NextDouble() * 2 * Math.PI;
          var locationDistance = random.NextDouble() * maxClusterRadius;
          locations[loc, 0] = clusterDistance * Math.Cos(clusterDirection) +
                              locationDistance * Math.Cos(locationDirection);
          locations[loc, 1] = clusterDistance * Math.Sin(clusterDirection) +
                              locationDistance * Math.Sin(locationDirection);
          loc++;
          if (loc == N) break;
        }
      }

      A = new double[N, N];
      for (var i = 0; i < N - 1; i++) {
        for (var j = i + 1; j < N; j++) {
          A[i, j] = Math.Sqrt((locations[i, 0] - locations[j, 0]) * (locations[i, 0] - locations[j, 0])
                              + (locations[i, 1] - locations[j, 1]) * (locations[i, 1] - locations[j, 1]));
          A[j, i] = A[i, j];
        }
      }

      B = new double[N, N];
      for (var i = 0; i < N - 1; i++) {
        for (var j = i + 1; j < N; j++) {
          B[i, j] = Math.Floor(Math.Pow(10, (maxFlowExponent - minFlowExponent) * random.NextDouble() + minFlowExponent));
          B[j, i] = B[i, j];
        }
      }
    }
  }
}