source: trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/BoundsCalculators/GilmoreLawlerBoundCalculator.cs @ 8910

Last change on this file since 8910 was 8910, checked in by abeham, 9 years ago

#1841:

  • Corrected best known solutions in new taillard and microarray instances
  • Improved computation of an average fitness in the QAP
File size: 2.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using HeuristicLab.Data;
24using HeuristicLab.Encodings.PermutationEncoding;
25using HeuristicLab.Problems.LinearAssignment;
26
27namespace HeuristicLab.Problems.QuadraticAssignment {
28  public static class GilmoreLawlerBoundCalculator {
29    public static double CalculateLowerBound(DoubleMatrix weights, DoubleMatrix distances) {
30      Permutation tmp;
31      return CalculateLowerBound(weights, distances, out tmp);
32    }
33
34    public static double CalculateLowerBound(DoubleMatrix weights, DoubleMatrix distances, out Permutation solution) {
35      int N = weights.Rows;
36      DoubleMatrix sortedWeights = SortEachRowExceptDiagonal(weights), sortedDistances = SortEachRowExceptDiagonal(distances);
37
38      DoubleMatrix costs = new DoubleMatrix(N, N);
39      for (int i = 0; i < N; i++) {
40        for (int j = 0; j < N; j++) {
41          for (int k = 0; k < N - 1; k++)
42            costs[i, j] += sortedWeights[i, k] * sortedDistances[j, N - 2 - k];
43          costs[i, j] += sortedWeights[i, N - 1] * sortedDistances[j, N - 1];
44        }
45      }
46
47      double result;
48      solution = new Permutation(PermutationTypes.Absolute, LinearAssignmentProblemSolver.Solve(costs, out result));
49      return result;
50    }
51
52    private static DoubleMatrix SortEachRowExceptDiagonal(DoubleMatrix matrix) {
53      var result = new DoubleMatrix(matrix.Rows, matrix.Columns);
54
55      double[] row = new double[matrix.Rows - 1];
56      for (int i = 0; i < matrix.Rows; i++) {
57        int counter = 0;
58        for (int j = 0; j < matrix.Columns; j++)
59          if (i != j) row[counter++] = matrix[i, j];
60        Array.Sort(row);
61        for (int k = 0; k < matrix.Columns - 1; k++)
62          result[i, k] = row[k];
63        result[i, matrix.Columns - 1] = matrix[i, i];
64      }
65      return result;
66    }
67  }
68}
Note: See TracBrowser for help on using the repository browser.