Opened 6 years ago
Last modified 8 months ago
#1614 accepted feature request
Implement Generalized Quadratic Assignment Problem
Reported by: | abeham | Owned by: | abeham |
---|---|---|---|
Priority: | highest | Milestone: | HeuristicLab 3.3.15 |
Component: | Problems.QuadraticAssignment | Version: | 3.3.5 |
Keywords: | Cc: |
Description
Solutions to the QAP specify the assignment of exactly one facility to exactly one location such that no facility or location remains unassigned.
The Generalized QAP (GQAP) loosens this restriction and instead introduces a capacity at each location and a required capacity for each facility. Multiple facilities can then be assigned to the same location as long as there is enough free capacity.
Attachments (2)
Change History (67)
comment:1 Changed 6 years ago by abeham
- Status changed from new to accepted
comment:2 Changed 6 years ago by abeham
- Added plugin, problem stub and evaluator
comment:3 Changed 6 years ago by abeham
- syncing
comment:4 Changed 6 years ago by abeham
- updated problem
- added equality comparer for integer vectors
comment:5 Changed 6 years ago by abeham
- updated project files
comment:6 Changed 5 years ago by abeham
- updated branch from trunk
comment:7 Changed 5 years ago by abeham
- put TestRandom class into HeuristicLab.Tests and removed the duplicates
- readded QAPLIB unit test which disappeared after the last merge
- readded deep cloning test which also disappeared
comment:8 Changed 5 years ago by abeham
- changed !QAPMoveEvaluatorTest slightly
comment:9 Changed 5 years ago by abeham
- removed GeneralizedQAP branch
- readded new simpler branch
- removed unnecessary files from import
comment:10 Changed 5 years ago by abeham
- Milestone changed from HeuristicLab 3.3.6 to HeuristicLab 3.3.x Backlog
I decided to pull this from the next release and include this most probably in 3.3.7.
comment:11 Changed 5 years ago by abeham
r7311: updated GQAP
comment:12 Changed 5 years ago by abeham
r7312: added views project
comment:13 Changed 5 years ago by abeham
r7319: worked on GQAP (added operators, assignment view)
comment:14 Changed 5 years ago by abeham
- added first version of GRASP+PR algorithm
comment:15 Changed 5 years ago by abeham
- worked on GQAP
comment:16 Changed 5 years ago by abeham
- added ICrossover interface
comment:17 Changed 5 years ago by abeham
r7373: Worked on GQAP
comment:18 Changed 5 years ago by abeham
r7407: worked on GQAP
comment:19 Changed 5 years ago by abeham
r7412: worked on GQAP and GRASP+PR
comment:20 Changed 5 years ago by abeham
- renamed AssemblyInfo frame files to proper name
- fixed discovery of move operators
- fixed a bug in the move evaluator
- fixed a bug in the DiscreteLocationCrossover
comment:21 Changed 5 years ago by abeham
r7415: improved results output of GQAP
comment:22 Changed 5 years ago by abeham
- Added shaking operator based on n-moves
- Added pareto analyzer regarding flowdistance and installation qualities
comment:23 Changed 5 years ago by abeham
- reworked parameterization (one interface for every parameter resp. parameter group)
- unified parameter descriptions
comment:24 Changed 5 years ago by abeham
- fixed parameterizing of local improvement operators
comment:25 Changed 5 years ago by abeham
- worked on path relinking operator
comment:26 Changed 5 years ago by abeham
- worked on path relinking
comment:27 Changed 5 years ago by abeham
- updated gqap (finished path-relinking)
- fixed some bugs
comment:28 Changed 5 years ago by abeham
- Allowed to view the solution of a certain point in the pareto chart
- Added multi crossovers and manipulators
- Added population diversity analyzer
- Fixed a few bugs
comment:29 Changed 5 years ago by abeham
- Add BestKnownSolutions parameter
- Assignment view
- Clicking on an equipment highlights all related equipments
- Clicking on a location highlights other locations that contain equipment to which relations exist
- Showing installation costs when nothing is selected
- Analyzers were present double times
- Fixed GRASP to check EnabledByDefault
comment:30 Changed 5 years ago by abeham
- worked on generic instance provider
- added CTAP instances
comment:31 Changed 5 years ago by abeham
- fixed build
comment:32 Changed 5 years ago by abeham
- updated problem instance provider
comment:33 Changed 5 years ago by abeham
- Added Transpose() extension method for double[,] matrices
- Added IProblemInstanceConsumer<T> interface
- Implemented general ProblemView which auto-detects all instances a problem can consume
- Added ability of IProblemInstanceProvider to directly feed a consumer
- Implemented general view for problem instance providers
- Fixed a few bugs
comment:34 Changed 5 years ago by abeham
- Added TSPLIB instances (TSP, ATSP, CVRP)
- Improved parser for TSPLIB file format
- Added ProblemInstanceProvider as an abstract base class which handles the feeding of consumers
comment:35 Changed 5 years ago by abeham
- included TSLIB's ATSP and CVRP problems as well
comment:36 Changed 5 years ago by abeham
- Removed incompatible problem linhp318.tsp (contains fixed edges)
- Fixed AssemblyInfo for TSPLIB
- Added unit tests
- Worked on assignment / solution view
comment:37 Changed 5 years ago by abeham
- Added a button to recalculate the quality
comment:38 Changed 5 years ago by abeham
r7478: simplified GRASP+PR operator graph, replaced IMerger with an IPopulationReducer
comment:39 Changed 5 years ago by abeham
- Fixed a parameter type in the GQAP
- Fixed loading of ICTAP instances (only the upper triangular matrix is required for the distances)
- Fixed a bug in the reducer that causes the loss of diversity
comment:40 Changed 5 years ago by abeham
- Added a property ReferencePublication
- Added a custom combobox that can display a tooltip for each item
- Added tooltip for the different providers stating link and reference publication
comment:41 Changed 5 years ago by abeham
r7483: updated project file
comment:42 Changed 5 years ago by abeham
r7484: fixed a few bugs in the combobox and made it look and behave like the standard combobox
comment:43 Changed 5 years ago by abeham
- added instances of Cordeau et al. as given by L. Moccia
- added operators for tabu search
comment:44 Changed 5 years ago by abeham
- sorted operators
- added crossover defined by Cordeau et al.
- fixed a few bugs
comment:45 Changed 5 years ago by abeham
- Fixed plugin dependencies
- Updated GQAP view
- Changed instances infrastructure
- Changed interface types into classes
- Removed the library specific instance classes
comment:46 Changed 5 years ago by abeham
- fixed a discovery bug
comment:47 Changed 5 years ago by abeham
r7548: changed according to architects review
comment:48 Changed 5 years ago by abeham
r7552: removed class diagram
comment:49 Changed 5 years ago by abeham
r7561: cleaned up branch, removed instances which were integrated into the trunk
comment:50 Changed 5 years ago by abeham
- Investigation in different solution creator that result in feasible solutions even for 95% fill level instances
- Added option for all solution creators to produce the least infeasible solution if no feasible solution could be found
- Added maximum tries parameter to all creators
comment:51 Changed 5 years ago by abeham
r7595: updated SlackMinimizationSolutionCreator
comment:52 Changed 5 years ago by abeham
r7679: updated SlackMinimizationSolutionCreator
comment:53 Changed 5 years ago by abeham
- updated extension methods and operators that use them
comment:54 Changed 5 years ago by abeham
- moved extension methods to trunk and added reference to HeuristicLab.Random
comment:55 Changed 5 years ago by abeham
- made GRASP+PR an IStorableContent
- fixed bug in GreedyRandomizedSolutionCreator
comment:56 Changed 5 years ago by abeham
r7935: fixed issues mentioned in unit tests
comment:57 Changed 5 years ago by abeham
r7940: fixed a dependency
comment:58 Changed 5 years ago by abeham
r7970: restructured architecture to allow for different evaluator with different penalty strategies
comment:59 Changed 4 years ago by abeham
r9114: adapted to intvector changes
comment:60 Changed 2 years ago by abeham
r11505: updated to trunk changes
comment:61 Changed 21 months ago by abeham
- Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.13
comment:62 Changed 17 months ago by abeham
- Milestone changed from HeuristicLab 3.3.13 to HeuristicLab 4.x Backlog
comment:63 Changed 16 months ago by abeham
- Milestone changed from HeuristicLab 4.x Backlog to HeuristicLab 3.3.14
- fixed some references
- fixed versions and year
- updated sln file to more recent vstudio
- updated to .NET 4.5
Changed 15 months ago by pkuelzer
comment:64 Changed 15 months ago by pkuelzer
Exception:
-CordeauCrossover -DiscreteCrossover (CommunicationGa.hl) -SinglePointCrossover (CommunicationGa.hl)
-ScaledQualityDifferenceAnalyzer
comment:65 Changed 8 months ago by abeham
- Milestone changed from HeuristicLab 3.3.14 to HeuristicLab 3.3.15
r6646