Opened 10 years ago
Closed 10 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 10 years ago by abeham
- Status changed from new to accepted
- Version changed from 3.3.2 to 3.3.3
comment:2 Changed 10 years ago by abeham
- Created branch for developing the QAP
comment:3 Changed 10 years ago by abeham
comment:4 Changed 10 years ago by abeham
- Worked on QAP
- Added solution and analyzer
- Added crude solution view
- Overwrote instances with those from new QAPLIB site (Pennsylvania)
comment:5 Changed 10 years ago by abeham
- 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 10 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 10 years ago by epitzer
fixed pre-build event to also update AssemblyInfo.cs from frame file (r5627)
comment:8 Changed 10 years ago by abeham
- worked on visualization (and MDS)
comment:9 Changed 10 years ago by abeham
- Milestone changed from HeuristicLab Backlog to HeuristicLab 3.3.4
- 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 10 years ago by abeham
- Component changed from ### Undefined ### to Problems.QuadraticAssignment
comment:11 Changed 10 years ago by abeham
- Moved MDS into Analysis
- Added test with some simple examples
comment:12 Changed 10 years ago by abeham
- 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 10 years ago by abeham
- Added QAP evaluator for translocation moves
comment:14 Changed 10 years ago by abeham
- Adapted QAP to new problem base class structure
- Fixed a bug in a view
- Merged changes from Optimization plugin into branch
comment:15 Changed 10 years ago by abeham
- 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 10 years ago by abeham
- fixed a small bug in a view
comment:17 Changed 10 years ago by abeham
- 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 10 years ago by abeham
- Removed unnecessary files
comment:19 Changed 10 years ago by abeham
- Fixed calculation of normalized stress value
- Fixed a few bugs
comment:20 Changed 10 years ago by abeham
- Fixed normalized stress value
- Changed method name and signature of MDS
- Adapted unit tests
- Adapted QAP View
comment:21 Changed 10 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)
comment:22 Changed 10 years ago by abeham
comment:23 Changed 10 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
comment:24 Changed 10 years ago by abeham
- 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 10 years ago by abeham
- changes according to the review
comment:26 Changed 10 years ago by abeham
- Finished further changes from review
comment:27 Changed 10 years ago by abeham
- Merged QAP from branch into trunk
- Merged MDS from branch into trunk
- Merged Swap2 moves from branch into trunk
comment:28 Changed 10 years ago by abeham
- Status changed from accepted to readytorelease
- removed QAP branch
comment:29 Changed 10 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: ↓ 32 Changed 10 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.
- 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 10 years ago by abeham
- fixed missing AssemblyInfo.cs
comment:32 in reply to: ↑ 30 Changed 10 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 10 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 10 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 10 years ago by abeham
- Status changed from assigned to accepted
- 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 10 years ago by abeham
- Status changed from accepted to readytorelease
comment:37 Changed 10 years ago by abeham
- fixed an oversight in the last commit
comment:38 Changed 10 years ago by abeham
- some remaining problems with benchmark data, two instances had quality values and solutions that did not go together
comment:39 Changed 10 years ago by abeham
- Added three solution files that were not included in the tarball, but are available on the website
comment:40 Changed 10 years ago by abeham
- Added IStorableContent interface
comment:41 Changed 10 years ago by abeham
- Fixed an issue were a TSP move evaluator could be selected in the QAP
comment:42 Changed 10 years ago by swagner
- Resolution set to done
- Status changed from readytorelease to closed
- Version changed from 3.3.3 to 3.3.4
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.