Opened 9 years ago

Closed 8 years ago

#1330 closed feature request (done)

Implement Quadratic Assignment Problem (QAP)

Reported by: swagner Owned by: abeham
Priority: high Milestone: HeuristicLab 3.3.4
Component: Problems.QuadraticAssignment Version: 3.3.4
Keywords: Cc:

Description


Change History (42)

comment:1 Changed 9 years ago by abeham

  • Status changed from new to accepted
  • Version changed from 3.3.2 to 3.3.3

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.

comment:2 Changed 9 years ago by abeham

r5558

  • Created branch for developing the QAP

comment:3 Changed 9 years ago by abeham

r5562

  • Worked on QAP
  • Added QAPLIB problems

r5563

  • Added working version of QAP

comment:4 Changed 9 years ago by abeham

r5583

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

comment:5 Changed 9 years ago by 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

comment:6 Changed 9 years ago by abeham

  • Summary changed from Port QAP from HeuristicLab 3.2 to HeuristicLab 3.3 to Implement Quadratic Assignment Problem (QAP)

comment:7 Changed 9 years ago by epitzer

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

comment:8 Changed 9 years ago by abeham

r5641

  • worked on visualization (and MDS)

comment:9 Changed 9 years ago by abeham

  • Milestone changed from HeuristicLab Backlog to HeuristicLab 3.3.4

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

comment:10 Changed 9 years ago by abeham

  • Component changed from ### Undefined ### to Problems.QuadraticAssignment

comment:11 Changed 9 years ago by abeham

r5723

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

comment:12 Changed 9 years ago by 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

comment:13 Changed 9 years ago by abeham

r5801

  • Added QAP evaluator for translocation moves

comment:14 Changed 9 years ago by abeham

r5811

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

comment:15 Changed 9 years ago by 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

comment:16 Changed 9 years ago by abeham

r5820

  • fixed a small bug in a view

comment:17 Changed 9 years ago by 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

comment:18 Changed 9 years ago by abeham

r5840

  • Removed unnecessary files

comment:19 Changed 9 years ago by abeham

r5855

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

comment:20 Changed 9 years ago by abeham

r5871

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

comment:21 Changed 9 years ago by 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) (#1430)
Last edited 9 years ago by abeham (previous) (diff)

comment:22 Changed 9 years ago by 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)

comment:23 Changed 9 years ago by 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
Last edited 9 years ago by abeham (previous) (diff)

comment:24 Changed 9 years ago by 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

comment:25 Changed 9 years ago by abeham

r5931

  • changes according to the review

comment:26 Changed 9 years ago by abeham

r5932

  • Finished further changes from review

comment:27 Changed 9 years ago by abeham

r5933

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

comment:28 Changed 9 years ago by abeham

  • Status changed from accepted to readytorelease

r5934

  • removed QAP branch

comment:29 Changed 9 years ago by 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.

comment:30 follow-up: Changed 9 years ago by 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

comment:31 Changed 9 years ago by abeham

r5939

  • fixed missing AssemblyInfo.cs

comment:32 in reply to: ↑ 30 Changed 9 years ago by 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.

comment:33 Changed 9 years ago by abeham

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

comment:34 Changed 9 years ago by abeham

  • Status changed from readytorelease to assigned

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.

comment:35 Changed 9 years ago by abeham

  • Status changed from assigned to accepted

r5947

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

comment:36 Changed 9 years ago by abeham

  • Status changed from accepted to readytorelease

comment:37 Changed 9 years ago by abeham

r5948

  • fixed an oversight in the last commit

comment:38 Changed 9 years ago by abeham

r5949

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

comment:39 Changed 9 years ago by abeham

r5950

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

comment:40 Changed 9 years ago by abeham

r5953

  • Added IStorableContent interface

comment:41 Changed 8 years ago by abeham

r6088

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

comment:42 Changed 8 years ago by swagner

  • Resolution set to done
  • Status changed from readytorelease to closed
  • Version changed from 3.3.3 to 3.3.4
Note: See TracTickets for help on using tickets.