Opened 7 years ago

Last modified 4 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)

clusterGA.hl (67.4 KB) - added by pkuelzer 3 years ago.
Causes crash of HL when executing
communicationGA.hl (61.7 KB) - added by pkuelzer 3 years ago.

Download all attachments as: .zip

Change History (120)

comment:1 Changed 7 years ago by abeham

  • Status changed from new to accepted

r6646

  • created branch

comment:2 Changed 7 years ago by abeham

r6650

  • Added plugin, problem stub and evaluator

comment:3 Changed 7 years ago by abeham

r6651

  • syncing

comment:4 Changed 7 years ago by abeham

r6657

  • updated problem
  • added equality comparer for integer vectors

comment:5 Changed 7 years ago by abeham

r6658

  • updated project files

comment:6 Changed 7 years ago by abeham

r6878

  • updated branch from trunk

comment:7 Changed 7 years ago by abeham

r6889

  • 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 7 years ago by abeham

r6890

  • changed !QAPMoveEvaluatorTest slightly

comment:9 Changed 7 years ago by abeham

r6955:6957

  • removed GeneralizedQAP branch
  • readded new simpler branch
  • removed unnecessary files from import

comment:10 Changed 7 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 7 years ago by abeham

r7311: updated GQAP

comment:12 Changed 7 years ago by abeham

r7312: added views project

comment:13 Changed 7 years ago by abeham

r7319: worked on GQAP (added operators, assignment view)

comment:14 Changed 7 years ago by abeham

r7345

  • added first version of GRASP+PR algorithm

comment:15 Changed 7 years ago by abeham

r7363

  • worked on GQAP

comment:16 Changed 7 years ago by abeham

r7364

  • added ICrossover interface

comment:17 Changed 7 years ago by abeham

r7373: Worked on GQAP

comment:18 Changed 7 years ago by abeham

r7407: worked on GQAP

comment:19 Changed 7 years ago by abeham

r7412: worked on GQAP and GRASP+PR

comment:20 Changed 7 years ago by abeham

r7413

  • 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 7 years ago by abeham

r7415: improved results output of GQAP

comment:22 Changed 7 years ago by abeham

r7418

  • Added shaking operator based on n-moves
  • Added pareto analyzer regarding flowdistance and installation qualities

comment:23 Changed 7 years ago by abeham

r7419

  • reworked parameterization (one interface for every parameter resp. parameter group)
  • unified parameter descriptions

comment:24 Changed 7 years ago by abeham

r7420

  • fixed parameterizing of local improvement operators

comment:25 Changed 7 years ago by abeham

r7423

  • worked on path relinking operator

comment:26 Changed 7 years ago by abeham

r7425

  • worked on path relinking

comment:27 Changed 7 years ago by abeham

r7432

  • updated gqap (finished path-relinking)
  • fixed some bugs

comment:28 Changed 7 years ago by abeham

r7437

  • 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 7 years ago by abeham

r7438

  • 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 7 years ago by abeham

r7443

  • worked on generic instance provider
  • added CTAP instances

comment:31 Changed 7 years ago by abeham

r7444

  • fixed build

comment:32 Changed 7 years ago by abeham

r7445

  • updated problem instance provider

comment:33 Changed 7 years ago by abeham

r7448

  • 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 7 years ago by abeham

r7465

  • 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 7 years ago by abeham

r7466

  • included TSLIB's ATSP and CVRP problems as well

comment:36 Changed 7 years ago by abeham

r7470

  • Removed incompatible problem linhp318.tsp (contains fixed edges)
  • Fixed AssemblyInfo for TSPLIB
  • Added unit tests
  • Worked on assignment / solution view

comment:37 Changed 7 years ago by abeham

r7471

  • Added a button to recalculate the quality

comment:38 Changed 7 years ago by abeham

r7478: simplified GRASP+PR operator graph, replaced IMerger with an IPopulationReducer

comment:39 Changed 7 years ago by abeham

r7480

  • 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 7 years ago by abeham

r7482

  • 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 7 years ago by abeham

r7483: updated project file

comment:42 Changed 7 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 7 years ago by abeham

r7505

  • added instances of Cordeau et al. as given by L. Moccia
  • added operators for tabu search

comment:44 Changed 7 years ago by abeham

r7523

  • sorted operators
  • added crossover defined by Cordeau et al.
  • fixed a few bugs

comment:45 Changed 7 years ago by abeham

r7538

  • Fixed plugin dependencies
  • Updated GQAP view
  • Changed instances infrastructure
    • Changed interface types into classes
    • Removed the library specific instance classes

comment:46 Changed 7 years ago by abeham

r7539

  • fixed a discovery bug

comment:47 Changed 7 years ago by abeham

r7548: changed according to architects review

comment:48 Changed 7 years ago by abeham

r7552: removed class diagram

comment:49 Changed 7 years ago by abeham

r7561: cleaned up branch, removed instances which were integrated into the trunk

comment:50 Changed 7 years ago by abeham

r7593

  • 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 7 years ago by abeham

r7595: updated SlackMinimizationSolutionCreator

comment:52 Changed 7 years ago by abeham

r7679: updated SlackMinimizationSolutionCreator

comment:53 Changed 7 years ago by abeham

r7807

  • updated extension methods and operators that use them

comment:54 Changed 7 years ago by abeham

r7813

  • moved extension methods to trunk and added reference to HeuristicLab.Random

comment:55 Changed 7 years ago by abeham

r7833

  • made GRASP+PR an IStorableContent
  • fixed bug in GreedyRandomizedSolutionCreator

comment:56 Changed 7 years ago by abeham

r7935: fixed issues mentioned in unit tests

comment:57 Changed 7 years ago by abeham

r7940: fixed a dependency

comment:58 Changed 7 years ago by abeham

r7970: restructured architecture to allow for different evaluator with different penalty strategies

comment:59 Changed 6 years ago by abeham

r9114: adapted to intvector changes

comment:60 Changed 4 years ago by abeham

r11505: updated to trunk changes

comment:61 Changed 3 years ago by abeham

  • Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.13

comment:62 Changed 3 years ago by abeham

  • Milestone changed from HeuristicLab 3.3.13 to HeuristicLab 4.x Backlog

comment:63 Changed 3 years ago by abeham

  • Milestone changed from HeuristicLab 4.x Backlog to HeuristicLab 3.3.14

r13418:

  • fixed some references
  • fixed versions and year
  • updated sln file to more recent vstudio
  • updated to .NET 4.5

Changed 3 years ago by pkuelzer

Causes crash of HL when executing

Changed 3 years ago by pkuelzer

comment:64 Changed 3 years ago by pkuelzer

Exception:

-CordeauCrossover -DiscreteCrossover (CommunicationGa.hl) -SinglePointCrossover (CommunicationGa.hl)

-ScaledQualityDifferenceAnalyzer

comment:65 Changed 2 years ago by abeham

  • Milestone changed from HeuristicLab 3.3.14 to HeuristicLab 3.3.15

comment:66 Changed 20 months 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 18 months ago by abeham

  • Milestone changed from HeuristicLab 3.3.15 to HeuristicLab 3.3.16

comment:68 Changed 16 months ago by abeham

Consider r6801 from #1649 as part of this ticket

comment:69 Changed 16 months ago by abeham

  • Version changed from 3.3.5 to branch

comment:70 Changed 13 months ago by abeham

  • Summary changed from Implement Generalized Quadratic Assignment Problem to Implement Generalized Quadratic Assignment Problem (GQAP)

r15490:

  • branched optimization
  • adapted references
  • renamed plugin

comment:71 Changed 13 months ago by abeham

r15491:

  • branched integer vector encoding

comment:72 Changed 13 months ago by abeham

r15492:

  • distributed code from artificial common plugin
  • removed common plugin

comment:73 Changed 12 months 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

Last edited 12 months ago by abeham (previous) (diff)

comment:74 Changed 12 months ago by abeham

r15506: finished wiring

comment:75 Changed 12 months ago by abeham

r15507:

  • 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 12 months ago by abeham

r15510:

  • Fixed bugs in view
  • Made Evaluation object immutable
  • Fixed bug in Analyze
  • Fixed operators

comment:77 Changed 12 months ago by abeham

r15511: Improved performance by switching from Dictionary to Array

comment:78 Changed 12 months ago by abeham

r15512: Added unit test for approximate local search (from feasible solution)

comment:79 Changed 12 months ago by abeham

r15553:

  • 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 12 months ago by abeham

r15555: finished checking the implementation against the paper

comment:81 Changed 12 months ago by abeham

r15558: fixed bugs

comment:82 Changed 12 months ago by abeham

r15562: added additional algorithms

comment:83 Changed 12 months ago by abeham

r15563:

  • Added LAHC and pLAHC-s
  • Changed all algorithms to update high frequency results only every second

comment:84 Changed 12 months ago by abeham

r15564:

  • Fixed some bugs
  • Added OSGA
  • Updated ES (added recombination)
  • Reusing operators among algorihtms (RelocateEquipmentManipluator)
  • Rewrote DiscreteLocationCrossover

comment:85 Changed 12 months ago by abeham

r15572:

  • 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 12 months ago by abeham

r15574: Added CPLEX algorithms

comment:87 Changed 12 months ago by abeham

r15575:

  • Added two LocalSolver models (binary and integer)

comment:88 Changed 12 months 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 12 months ago by abeham

r15579: Added the new instances as problem instance assembly

comment:90 Changed 11 months ago by abeham

r15602: Branched Optimization.Views plugin

r15603: Implemented changed behavior to measure execution time (cf. #2869)

comment:91 Changed 11 months ago by abeham

r15604: fixed data type of inputs in FY model

comment:92 Changed 11 months ago by abeham

r15605: merged trunk into branch

comment:93 Changed 11 months ago by abeham

r15615:

  • 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 11 months ago by abeham

r15616:

  • Added missing Item and StorableClass attributes
  • Removed running analyzer on empty solutions in GRASP

comment:95 Changed 11 months ago by abeham

r15629: fixed cloning in ILS

comment:96 Changed 11 months ago by abeham

r15633: changed localsolver algorithms to run analyzer at the end

comment:97 Changed 11 months ago by abeham

r15634: run analyzer at the end of CPLEX

comment:98 Changed 11 months ago by abeham

r15676:

  • Refactored RLD view, added additional classes

r15677: renamed branch

comment:99 Changed 11 months ago by abeham

r15688: Adapted references to restructured trunk

comment:100 Changed 11 months ago by abeham

r15698: Added random search and fixed execution time counting for commercial solvers

comment:101 Changed 11 months 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 11 months ago by abeham

r15700:

  • Changed performance measure to stopwatch instead of datetime for precision reasons

comment:103 Changed 11 months ago by abeham

r15701: Several improvements to the run collection RLD view and additional robustification

r15702: branched fitness landscape analysis from #2457

comment:104 Changed 11 months 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 11 months ago by abeham

r15704:

  • fixed exception in case no solution could be found
  • fixed behavior in GRASP regarding infeasible solutions

comment:106 Changed 11 months ago by abeham

r15713:

  • 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 11 months ago by abeham

r15718:

  • 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 11 months ago by abeham

r15719:

  • branched analysis and analysis views
  • merged changes from #2457 into optimization and optimization.views

comment:109 Changed 11 months ago by abeham

r15720: merged analysis and analysis views from #2457

comment:110 Changed 11 months ago by abeham

r15721:

  • reverted r15603 by reverse merging
  • added expert system plugins from #2457

comment:111 Changed 10 months ago by abeham

r15736: fixed some things

comment:112 Changed 10 months 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 10 months ago by abeham

r15758: Added LocalSolver model based on lists

comment:114 Changed 8 months ago by abeham

r15890: Added console app for irace parameter optimization

comment:115 Changed 8 months ago by abeham

r15904: fix loading of problem instance

comment:116 Changed 4 months ago by abeham

r16076: pending updates

comment:117 Changed 4 months 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 4 months ago by abeham

r16103: the exclusion of runs leads to somewhat unexpected results

Note: See TracTickets for help on using tickets.