Implement Quadratic Assignment Problem (QAP)

[abeham]

The quadratic assignment problem is a well-known benchmark problem, should be built on HeuristicLab 3.3.3 and be integrated into the trunk, hopefully in time for 3.3.4.

[abeham]

r5558

• Created branch for developing the QAP

[abeham]

r5562

• Worked on QAP
• Added QAPLIB problems

r5563

• Added working version of QAP

[abeham]

r5583

• Worked on QAP
  • Added solution and analyzer
  • Added crude solution view
• Overwrote instances with those from new QAPLIB site (Pennsylvania)

[abeham]

r5598

• Updated solution view
• Made distance matrix a mandatory parameter (solution instances are small anyway)
• Added and set best known solution if available for a QAPLIB instance

[epitzer]

fixed pre-build event to also update AssemblyInfo.cs from frame file (r5627)

[abeham]

r5641

• worked on visualization (and MDS)

[abeham]

r5648

• Unified QAP visualization in solution and problem view
• Fixed bug in gradient-descent gradient calculation when performing multidimensional scaling
• Extended QAPLIB parsers to cover some file format variations
• Added unit tests to check if all QAPLIB instances import without error
• Changed BestKnownSolution to be an OptionalValueParameter

[abeham]

r5723

• Moved MDS into Analysis
• Added test with some simple examples

[abeham]

r5785

• Added Swap2 move to permutation (+tabu search operators)
• Added move evaluators for QAP (translocation/insertion missing)
• Merged trunk-changes from Optimization into QAP branch

[abeham]

r5801

• Added QAP evaluator for translocation moves

[abeham]

r5811

• Adapted QAP to new problem base class structure
• Fixed a bug in a view
• Merged changes from Optimization plugin into branch

[abeham]

r5814

• Added a test if the reported quality of the solution instances is similar to the evaluated qualities of these solutions
• Adapted parsing of the solution file and added another parameter whether the permutation should be treated as facility->location (HeuristicLab default) or location->facility.
• Adapted QuadraticAssignmentProblem to use that method that corresponds with the reported quality since there is no consistent encoding over all files
• Improved API documentation of the parsing methods

[abeham]

r5820

• fixed a small bug in a view

[abeham]

r5838

• Renamed the DistanceMatrix parameter to Distances
• Renamed the SwapMove to Swap2Move and renamed operators accordingly
• Integrated changes in HeuristicLab.Analysis.Views regarding description text box

[abeham]

r5840

• Removed unnecessary files

[abeham]

r5855

• Fixed calculation of normalized stress value
• Fixed a few bugs

[abeham]

r5871

• Fixed normalized stress value
• Changed method name and signature of MDS
• Adapted unit tests
• Adapted QAP View

[abeham]

I'm ready to integrate the branch. One thing to consider:

• Integrating multidimensional scaling into HeuristicLab.Analysis requires adding a reference to ALGLIB, because I'm using one of its algorithms.

Important changes:

• Added the QAP itself (HeuristicLab.Problems.QuadraticAssignment)
• Added Swap2 moves to the permutation encoding (HeuristicLab.Encodings.PermutationEncoding)
• Added the Kruskal-Shepard MDS algorithm (HeuristicLab.Analysis)
  • Added unit tests for the MDS algorithm (and a tests project for Analysis)
• Changed the BestKnownQuality parameter to be an OptionalValueParameter (HeuristicLab.Optimization)

[abeham]

r5873

• Fixed project references
• Moved Analysis.Tests project one level up
• Removed Optimization project as the changes have been merged into the trunk (cf. #1430)

[abeham]

Review with swagner:

• Multidimensional scaling
  • Add a scaling method that takes the number of iterations as parameter
  • Rename all occurrences of distance into dissimilarity
  • Add a PluginDependency to the ALGLIB plugin
• Permutation
  • Remove the exception of not generating some moves in the ExhaustiveSwap2MoveGenerator for relative undirected permutations
  • The StochasticSwap2SingleMoveGenerator exhibits a possible bias regarding the swapped indices
• Quadratic Assignment Problem
  • Remove the Coordinates parameter everywhere
  • Use a different base constructor and hand instances of the evaluator and solution creator
  • Align the name textbox and load instance combobox
  • Make sure to include the description icon
  • Views
    • Do not automatically synchronize changes to the visualization, but instead indicate that a redraw is necessary
    • Give the redraw button the refresh icon
    • Rename the QAPView to QAPControl
• General (reminder)
  • Check all license headers

[abeham]

r5930

• fixed a bug in the swap-2 move evaluator regarding asymmetric matrices and matrices with non-zero diagonals
• fixed a similar bug for evaluating inversion moves
• enhanced test cases
• Renamed !QAPSwapMoveEvaluator.cs to !QAPSwap2MoveEvaluator.cs

[abeham]

r5931

• changes according to the review

[abeham]

r5932

• Finished further changes from review

[abeham]

r5933

• Merged QAP from branch into trunk
• Merged MDS from branch into trunk
• Merged Swap2 moves from branch into trunk

[abeham]

r5934

• removed QAP branch

[mkommend]

Please add the new trunk projects to the HL 3.3 test project and run the unit test to ensure that everything works as expected. Additionally the builder test settings must also be adapted, but as far as I know this can only be done by gkronber or swagner.

[abeham]

Thanks for the reminder! Btw, the unit test complained that there was an unnecessary dependency to HeuristicLab.Optimization in HeuristicLab.Problems.QuadraticAssignment.Views. However, also remvoing that dependency in the project references resulted in a build error. Certainly that dependency is already satisfied through the reference to HeuristicLab.Problems.QuadraticAssignment, but so are others as well.

r5938

• Added HeuristicLab.Problems.QuadraticAssignment.Tests-3.3 project to solution
• Fixed assembly name in HeuristicLab.Analysis.Tests-3.3
• Added another test case to the MDS tests
• Referenced the two QAP plugins in the tests project
• Removed plugin dependency in HeuristicLab.Problems.QuadraticAssignment.Views to HeuristicLab.Optimization as the unit test complained about it

[abeham]

r5939

• fixed missing AssemblyInfo.cs

[mkommend]

Replying to abeham:

Thanks for the reminder! Btw, the unit test complained that there was an unnecessary dependency to HeuristicLab.Optimization in HeuristicLab.Problems.QuadraticAssignment.Views. However, also remvoing that dependency in the project references resulted in a build error. Certainly that dependency is already satisfied through the reference to HeuristicLab.Problems.QuadraticAssignment, but so are others as well.

I've already noticed this problem, but I don't know a solution for it. The cause is that the unit test can only check all linked assemblies. However the compiler needs additional assemblies to check for correct overrides, etc. but these assemblies are not linked to the resulting assembly and therefore the unit test complains about unnecessary project references.

[abeham]

Thanks for the answer! Understanding that I think it's okay that the dependency is given as a transitive dependency.

[abeham]

I just discovered a misinterpretation in the problem data and pulling this ticket again. The weights / flow matrix according to the evaluation formula on the QAPLIB page is the first matrix in the file. This is currently read as distance matrix.

[abeham]

r5947

• simplified parser
• correctly reading first matrix as weights (accessed by index of permutation) and second matrix as distances (accessed by value of permutation)

[abeham]

r5948

• fixed an oversight in the last commit

[abeham]

r5949

• some remaining problems with benchmark data, two instances had quality values and solutions that did not go together

[abeham]

r5950

• Added three solution files that were not included in the tarball, but are available on the website

[abeham]

r5953

• Added IStorableContent interface

[abeham]

r6088

• Fixed an issue were a TSP move evaluator could be selected in the QAP