Opened 6 years ago

Last modified 3 weeks ago

#1614 accepted feature request

Implement Generalized Quadratic Assignment Problem

Reported by: abeham Owned by: abeham
Priority: highest Milestone: HeuristicLab 3.3.16
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)

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

Download all attachments as: .zip

Change History (69)

comment:1 Changed 6 years ago by abeham

  • Status changed from new to accepted

r6646

  • created branch

comment:2 Changed 6 years ago by abeham

r6650

  • Added plugin, problem stub and evaluator

comment:3 Changed 6 years ago by abeham

r6651

  • syncing

comment:4 Changed 6 years ago by abeham

r6657

  • updated problem
  • added equality comparer for integer vectors

comment:5 Changed 6 years ago by abeham

r6658

  • updated project files

comment:6 Changed 6 years ago by abeham

r6878

  • updated branch from trunk

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

r6890

  • changed !QAPMoveEvaluatorTest slightly

comment:9 Changed 6 years ago by abeham

r6955:6957

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

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

r7311: updated GQAP

comment:12 Changed 6 years ago by abeham

r7312: added views project

comment:13 Changed 6 years ago by abeham

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

comment:14 Changed 6 years ago by abeham

r7345

  • added first version of GRASP+PR algorithm

comment:15 Changed 6 years ago by abeham

r7363

  • worked on GQAP

comment:16 Changed 6 years ago by abeham

r7364

  • added ICrossover interface

comment:17 Changed 6 years ago by abeham

r7373: Worked on GQAP

comment:18 Changed 6 years ago by abeham

r7407: worked on GQAP

comment:19 Changed 6 years ago by abeham

r7412: worked on GQAP and GRASP+PR

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

r7415: improved results output of GQAP

comment:22 Changed 5 years ago by abeham

r7418

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

comment:23 Changed 5 years ago by abeham

r7419

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

comment:24 Changed 5 years ago by abeham

r7420

  • fixed parameterizing of local improvement operators

comment:25 Changed 5 years ago by abeham

r7423

  • worked on path relinking operator

comment:26 Changed 5 years ago by abeham

r7425

  • worked on path relinking

comment:27 Changed 5 years ago by abeham

r7432

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

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

r7443

  • worked on generic instance provider
  • added CTAP instances

comment:31 Changed 5 years ago by abeham

r7444

  • fixed build

comment:32 Changed 5 years ago by abeham

r7445

  • updated problem instance provider

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

r7466

  • included TSLIB's ATSP and CVRP problems as well

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

r7471

  • 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

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 5 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 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

r7505

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

comment:44 Changed 5 years ago by abeham

r7523

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

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

r7539

  • 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

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

r7807

  • updated extension methods and operators that use them

comment:54 Changed 5 years ago by abeham

r7813

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

comment:55 Changed 5 years ago by abeham

r7833

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

r9114: adapted to intvector changes

comment:60 Changed 3 years ago by abeham

r11505: updated to trunk changes

comment:61 Changed 2 years ago by abeham

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

comment:62 Changed 21 months ago by abeham

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

comment:63 Changed 20 months 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 19 months ago by pkuelzer

Causes crash of HL when executing

Changed 19 months ago by pkuelzer

comment:64 Changed 19 months ago by pkuelzer

Exception:

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

-ScaledQualityDifferenceAnalyzer

comment:65 Changed 12 months ago by abeham

  • Milestone changed from HeuristicLab 3.3.14 to HeuristicLab 3.3.15

comment:66 Changed 3 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 3 weeks ago by abeham

  • Milestone changed from HeuristicLab 3.3.15 to HeuristicLab 3.3.16
Note: See TracTickets for help on using tickets.