Additional Algorithms for the Generalized Quadratic Assignment Problem (GQAP)

[abeham]

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.

[abeham]

r6646

• created branch

[abeham]

r6650

• Added plugin, problem stub and evaluator

[abeham]

r6651

• syncing

[abeham]

r6657

• updated problem
• added equality comparer for integer vectors

[abeham]

r6658

• updated project files

[abeham]

r6878

• updated branch from trunk

[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

[abeham]

r6890

• changed !QAPMoveEvaluatorTest slightly

[abeham]

r6955:6957

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

[abeham]

I decided to pull this from the next release and include this most probably in 3.3.7.

[abeham]

r7311: updated GQAP

[abeham]

r7312: added views project

[abeham]

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

[abeham]

r7345

• added first version of GRASP+PR algorithm

[abeham]

r7363

• worked on GQAP

[abeham]

r7364

• added ICrossover interface

[abeham]

r7373: Worked on GQAP

[abeham]

r7407: worked on GQAP

[abeham]

r7412: worked on GQAP and GRASP+PR

[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

[abeham]

r7415: improved results output of GQAP

[abeham]

r7418

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

[abeham]

r7419

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

[abeham]

r7420

• fixed parameterizing of local improvement operators

[abeham]

r7423

• worked on path relinking operator

[abeham]

r7425

• worked on path relinking

[abeham]

r7432

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

[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

[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

[abeham]

r7443

• worked on generic instance provider
• added CTAP instances

[abeham]

r7444

• fixed build

[abeham]

r7445

• updated problem instance provider

[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

[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

[abeham]

r7466

• included TSLIB's ATSP and CVRP problems as well

[abeham]

r7470

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

[abeham]

r7471

• Added a button to recalculate the quality

[abeham]

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

[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

[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

[abeham]

r7483: updated project file

[abeham]

r7484: fixed a few bugs in the combobox and made it look and behave like the standard combobox

[abeham]

r7505

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

[abeham]

r7523

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

[abeham]

r7538

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

[abeham]

r7539

• fixed a discovery bug

[abeham]

r7548: changed according to architects review

[abeham]

r7552: removed class diagram

[abeham]

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

[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

[abeham]

r7595: updated SlackMinimizationSolutionCreator

[abeham]

r7679: updated SlackMinimizationSolutionCreator

[abeham]

r7807

• updated extension methods and operators that use them

[abeham]

r7813

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

[abeham]

r7833

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

[abeham]

r7935: fixed issues mentioned in unit tests

[abeham]

r7940: fixed a dependency

[abeham]

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

[abeham]

r9114: adapted to intvector changes

[abeham]

r11505: updated to trunk changes

[abeham]

r13418:

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

[pkuelzer]

Causes crash of HL when executing

[pkuelzer]

Exception:

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

-ScaledQualityDifferenceAnalyzer

[gkronber]

Priority highest? How do we proceed with this ticket. Will it be included in the next release (3.3.15)?

[abeham]

Consider r6801 from #1649 as part of this ticket

[abeham]

r15490:

• branched optimization
• adapted references
• renamed plugin

[abeham]

r15491:

• branched integer vector encoding

[abeham]

r15492:

• distributed code from artificial common plugin
• removed common plugin

[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

[abeham]

r15506: finished wiring

[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

[abeham]

r15510:

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

[abeham]

r15511: Improved performance by switching from Dictionary to Array

[abeham]

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

[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

[abeham]

r15555: finished checking the implementation against the paper

[abeham]

r15558: fixed bugs

[abeham]

r15562: added additional algorithms

[abeham]

r15563:

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

[abeham]

r15564:

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

[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)

[abeham]

r15574: Added CPLEX algorithms

[abeham]

r15575:

• Added two LocalSolver models (binary and integer)

[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)

[abeham]

r15579: Added the new instances as problem instance assembly

[abeham]

r15602: Branched Optimization.Views plugin

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

[abeham]

r15604: fixed data type of inputs in FY model

[abeham]

r15605: merged trunk into branch

[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

[abeham]

r15616:

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

[abeham]

r15629: fixed cloning in ILS

[abeham]

r15633: changed localsolver algorithms to run analyzer at the end

[abeham]

r15634: run analyzer at the end of CPLEX

[abeham]

r15676:

• Refactored RLD view, added additional classes

r15677: renamed branch

[abeham]

r15688: Adapted references to restructured trunk

[abeham]

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

[abeham]

r15699: corrected RLD view to gracefully handle runs in which the convergence graph result is missing or contains bad values

[abeham]

r15700:

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

[abeham]

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

r15702: branched fitness landscape analysis from #2457

[abeham]

r15703: Corrected namespace of random search and fixed problem that convergence graph doesn't get updated when terminating normally

[abeham]

r15704:

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

[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

[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

[abeham]

r15719:

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

[abeham]

r15720: merged analysis and analysis views from #2457

[abeham]

r15721:

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

[abeham]

r15736: fixed some things

[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).

[abeham]

r15758: Added LocalSolver model based on lists

[abeham]

r15890: Added console app for irace parameter optimization

[abeham]

r15904: fix loading of problem instance

[abeham]

r16076: pending updates

[abeham]

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.

[abeham]

r16103: the exclusion of runs leads to somewhat unexpected results

[abeham]

r16728: updated to new persistence and .NET 4.6.1

• merged changes in #3000
• merged changes in #2936

[abeham]

r16733: added simpler variant of RLD view

[abeham]

r16961: fixed compilation errors