Opened 9 years ago
Last modified 20 months ago
#1614 accepted feature request
Additional Algorithms for the Generalized Quadratic Assignment Problem (GQAP)
Reported by: | abeham | Owned by: | abeham |
---|---|---|---|
Priority: | highest | Milestone: | HeuristicLab 3.3.x Backlog |
Component: | Algorithms | Version: | branch |
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 (123)
comment:1 Changed 9 years ago by abeham
- Status changed from new to accepted
comment:2 Changed 9 years ago by abeham
- Added plugin, problem stub and evaluator
comment:3 Changed 9 years ago by abeham
- syncing
comment:4 Changed 9 years ago by abeham
- updated problem
- added equality comparer for integer vectors
comment:5 Changed 9 years ago by abeham
- updated project files
comment:6 Changed 9 years ago by abeham
- updated branch from trunk
comment:7 Changed 9 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 9 years ago by abeham
- changed !QAPMoveEvaluatorTest slightly
comment:9 Changed 9 years ago by abeham
- removed GeneralizedQAP branch
- readded new simpler branch
- removed unnecessary files from import
comment:10 Changed 9 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 9 years ago by abeham
r7311: updated GQAP
comment:12 Changed 9 years ago by abeham
r7312: added views project
comment:13 Changed 9 years ago by abeham
r7319: worked on GQAP (added operators, assignment view)
comment:14 Changed 9 years ago by abeham
- added first version of GRASP+PR algorithm
comment:15 Changed 9 years ago by abeham
- worked on GQAP
comment:16 Changed 9 years ago by abeham
- added ICrossover interface
comment:17 Changed 9 years ago by abeham
r7373: Worked on GQAP
comment:18 Changed 9 years ago by abeham
r7407: worked on GQAP
comment:19 Changed 9 years ago by abeham
r7412: worked on GQAP and GRASP+PR
comment:20 Changed 9 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 9 years ago by abeham
r7415: improved results output of GQAP
comment:22 Changed 9 years ago by abeham
- Added shaking operator based on n-moves
- Added pareto analyzer regarding flowdistance and installation qualities
comment:23 Changed 9 years ago by abeham
- reworked parameterization (one interface for every parameter resp. parameter group)
- unified parameter descriptions
comment:24 Changed 9 years ago by abeham
- fixed parameterizing of local improvement operators
comment:25 Changed 9 years ago by abeham
- worked on path relinking operator
comment:26 Changed 9 years ago by abeham
- worked on path relinking
comment:27 Changed 9 years ago by abeham
- updated gqap (finished path-relinking)
- fixed some bugs
comment:28 Changed 9 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 9 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 9 years ago by abeham
- worked on generic instance provider
- added CTAP instances
comment:31 Changed 9 years ago by abeham
- fixed build
comment:32 Changed 9 years ago by abeham
- updated problem instance provider
comment:33 Changed 9 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 9 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 9 years ago by abeham
- included TSLIB's ATSP and CVRP problems as well
comment:36 Changed 9 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 9 years ago by abeham
- Added a button to recalculate the quality
comment:38 Changed 9 years ago by abeham
r7478: simplified GRASP+PR operator graph, replaced IMerger with an IPopulationReducer
comment:39 Changed 9 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 9 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 9 years ago by abeham
r7483: updated project file
comment:42 Changed 9 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 9 years ago by abeham
- added instances of Cordeau et al. as given by L. Moccia
- added operators for tabu search
comment:44 Changed 9 years ago by abeham
- sorted operators
- added crossover defined by Cordeau et al.
- fixed a few bugs
comment:45 Changed 9 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 9 years ago by abeham
- fixed a discovery bug
comment:47 Changed 9 years ago by abeham
r7548: changed according to architects review
comment:48 Changed 9 years ago by abeham
r7552: removed class diagram
comment:49 Changed 9 years ago by abeham
r7561: cleaned up branch, removed instances which were integrated into the trunk
comment:50 Changed 9 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 9 years ago by abeham
r7595: updated SlackMinimizationSolutionCreator
comment:52 Changed 9 years ago by abeham
r7679: updated SlackMinimizationSolutionCreator
comment:53 Changed 9 years ago by abeham
- updated extension methods and operators that use them
comment:54 Changed 9 years ago by abeham
- moved extension methods to trunk and added reference to HeuristicLab.Random
comment:55 Changed 9 years ago by abeham
- made GRASP+PR an IStorableContent
- fixed bug in GreedyRandomizedSolutionCreator
comment:56 Changed 9 years ago by abeham
r7935: fixed issues mentioned in unit tests
comment:57 Changed 9 years ago by abeham
r7940: fixed a dependency
comment:58 Changed 9 years ago by abeham
r7970: restructured architecture to allow for different evaluator with different penalty strategies
comment:59 Changed 8 years ago by abeham
r9114: adapted to intvector changes
comment:60 Changed 6 years ago by abeham
r11505: updated to trunk changes
comment:61 Changed 6 years ago by abeham
- Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.13
comment:62 Changed 5 years ago by abeham
- Milestone changed from HeuristicLab 3.3.13 to HeuristicLab 4.x Backlog
comment:63 Changed 5 years 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 5 years ago by pkuelzer
comment:64 Changed 5 years ago by pkuelzer
Exception:
-CordeauCrossover -DiscreteCrossover (CommunicationGa.hl) -SinglePointCrossover (CommunicationGa.hl)
-ScaledQualityDifferenceAnalyzer
comment:65 Changed 5 years ago by abeham
- Milestone changed from HeuristicLab 3.3.14 to HeuristicLab 3.3.15
comment:66 Changed 4 years ago by gkronber
Priority highest? How do we proceed with this ticket. Will it be included in the next release (3.3.15)?
comment:67 Changed 4 years ago by abeham
- Milestone changed from HeuristicLab 3.3.15 to HeuristicLab 3.3.16
comment:68 Changed 3 years ago by abeham
comment:69 Changed 3 years ago by abeham
- Version changed from 3.3.5 to branch
comment:70 Changed 3 years ago by abeham
- Summary changed from Implement Generalized Quadratic Assignment Problem to Implement Generalized Quadratic Assignment Problem (GQAP)
- branched optimization
- adapted references
- renamed plugin
comment:71 Changed 3 years ago by abeham
- branched integer vector encoding
comment:72 Changed 3 years ago by abeham
- distributed code from artificial common plugin
- removed common plugin
comment:73 Changed 3 years ago by abeham
r15504: refactored code
- change problem to derive from basic problem
- using a combined instance class instead of individual parameters
TODO: wiring of the encoding name
comment:74 Changed 3 years ago by abeham
r15506: finished wiring
comment:75 Changed 3 years ago by abeham
- fixed some bugs introduced in last commit (project file, tests)
- fixed ApproximateLocalSearch due to change in move evaluator that outputs an absolute quality of the move and not a delta
- added evaluated solution counting to approximate local search
- GRASP+PR: restructured main loop and combined iteration initialization with variable creator outside
comment:76 Changed 3 years ago by abeham
- Fixed bugs in view
- Made Evaluation object immutable
- Fixed bug in Analyze
- Fixed operators
comment:77 Changed 3 years ago by abeham
r15511: Improved performance by switching from Dictionary to Array
comment:78 Changed 3 years ago by abeham
r15512: Added unit test for approximate local search (from feasible solution)
comment:79 Changed 3 years ago by abeham
- Implementing basic algorithm according to paper (rechecking all operators)
- Checking implementation with paper
- Improved speed of move generator
- Improved speed of randomized solution creator
comment:80 Changed 3 years ago by abeham
r15555: finished checking the implementation against the paper
comment:81 Changed 3 years ago by abeham
r15558: fixed bugs
comment:82 Changed 3 years ago by abeham
r15562: added additional algorithms
comment:83 Changed 3 years ago by abeham
- Added LAHC and pLAHC-s
- Changed all algorithms to update high frequency results only every second
comment:84 Changed 3 years ago by abeham
- Fixed some bugs
- Added OSGA
- Updated ES (added recombination)
- Reusing operators among algorihtms (RelocateEquipmentManipluator)
- Rewrote DiscreteLocationCrossover
comment:85 Changed 3 years ago by abeham
- fixed a bug in GRASP where solutions in the elite set would be mutated
- introduced termination criteria when reaching best-known quality
- tweaked generating random numbers in StochasticNMoveSingleMoveGenerator
- changed DiscreteLocationCrossover to use an allele from one of the parents instead of introducing a mutation in case no feasible insert location is found
- changed OSGA maxselpress to 500
- slight change to contexts, introduced single-objectiveness much earlier in the class hierachy
- limited ContextAlgorithm to SingleObjectiveBasicProblems (doesn't matter here)
comment:86 Changed 3 years ago by abeham
r15574: Added CPLEX algorithms
comment:87 Changed 3 years ago by abeham
- Added two LocalSolver models (binary and integer)
comment:88 Changed 3 years ago by abeham
r15578: Added program to generate new benchmark instances based on QAPLIB (same flow matrices, clustered distance matrices and randomly chosen installation costs, demands, and capacities)
comment:89 Changed 3 years ago by abeham
r15579: Added the new instances as problem instance assembly
comment:90 Changed 3 years ago by abeham
comment:91 Changed 3 years ago by abeham
r15604: fixed data type of inputs in FY model
comment:92 Changed 3 years ago by abeham
r15605: merged trunk into branch
comment:93 Changed 3 years ago by abeham
- fixed a bug in the run collection RLD view when BestKnownQuality is set to double.NaN
- fixed a bug in evolution strategy's solution not being a storable class
comment:94 Changed 3 years ago by abeham
- Added missing Item and StorableClass attributes
- Removed running analyzer on empty solutions in GRASP
comment:95 Changed 3 years ago by abeham
r15629: fixed cloning in ILS
comment:96 Changed 3 years ago by abeham
r15633: changed localsolver algorithms to run analyzer at the end
comment:97 Changed 3 years ago by abeham
r15634: run analyzer at the end of CPLEX
comment:98 Changed 3 years ago by abeham
comment:99 Changed 3 years ago by abeham
r15688: Adapted references to restructured trunk
comment:100 Changed 3 years ago by abeham
r15698: Added random search and fixed execution time counting for commercial solvers
comment:101 Changed 3 years ago by abeham
r15699: corrected RLD view to gracefully handle runs in which the convergence graph result is missing or contains bad values
comment:102 Changed 3 years ago by abeham
- Changed performance measure to stopwatch instead of datetime for precision reasons
comment:103 Changed 3 years ago by abeham
comment:104 Changed 3 years ago by abeham
r15703: Corrected namespace of random search and fixed problem that convergence graph doesn't get updated when terminating normally
comment:105 Changed 3 years ago by abeham
- fixed exception in case no solution could be found
- fixed behavior in GRASP regarding infeasible solutions
comment:106 Changed 3 years ago by abeham
- added additional constraint to benchmark data generator and updated one instance that was affected by this
- added fitness landscape characteristics for the GQAP
- fixed RLD analysis view to compensate for empty convergence graphs
- fixed CPLEX solvers not using the obj value when the solver terminates (callback is not called if proven optimal solution is found)
- added code for local solver to also check on final quality
comment:107 Changed 3 years ago by abeham
- Scale directed walk fitness values
- Performance improvements to RLD view
- Changed CPLEX to use a single thread only
- Set the context to null when algorithm is stopped
comment:108 Changed 3 years ago by abeham
comment:109 Changed 3 years ago by abeham
comment:110 Changed 3 years ago by abeham
comment:111 Changed 3 years ago by abeham
r15736: fixed some things
comment:112 Changed 3 years ago by abeham
The instance map should present the points by giving each algorithm a unique color and thus showing the best algorithm for a certain target. Some tie-breaking should be done in case there are multiple best (e.g. consider the ERT values instead of the ranks).
comment:113 Changed 3 years ago by abeham
r15758: Added LocalSolver model based on lists
comment:114 Changed 3 years ago by abeham
r15890: Added console app for irace parameter optimization
comment:115 Changed 3 years ago by abeham
r15904: fix loading of problem instance
comment:116 Changed 2 years ago by abeham
r16076: pending updates
comment:117 Changed 2 years ago by abeham
- Component changed from Problems.QuadraticAssignment to Algorithms
- Milestone changed from HeuristicLab 3.3.16 to HeuristicLab 3.3.x Backlog
- Summary changed from Implement Generalized Quadratic Assignment Problem (GQAP) to Additional Algorithms for the Generalized Quadratic Assignment Problem (GQAP)
Trunk integration of the GQAP has been moved to #2936 and its own branch
This ticket and its associated branch hold some additional algorithms that can be used to solve the GQAP. These were tested and published at GECCO 2018.
comment:118 Changed 2 years ago by abeham
r16103: the exclusion of runs leads to somewhat unexpected results
comment:119 Changed 22 months ago by abeham
comment:120 Changed 22 months ago by abeham
r16733: added simpler variant of RLD view
comment:121 Changed 20 months ago by abeham
r16961: fixed compilation errors
r6646