search

heal-research / HeuristicLab

HeuristicLab - An environment for heuristic and evolutionary optimization
https://dev.heuristiclab.com
GNU General Public License v3.0
39 stars 16 forks source link

Additional Algorithms for the Generalized Quadratic Assignment Problem (GQAP) #1614

Open HeuristicLab-Trac-Bot opened 13 years ago

HeuristicLab-Trac-Bot commented 13 years ago

Issue migrated from trac ticket # 1614

milestone: HeuristicLab 3.3.x Backlog | component: Algorithms | priority: highest

2011-08-09 09:36:42: @abeham created the issue

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.

HeuristicLab-Trac-Bot commented 13 years ago

2011-08-09 09:38:04: @abeham changed status from new to accepted

HeuristicLab-Trac-Bot commented 13 years ago

2011-08-09 09:38:04: @abeham commented

r6646

  • created branch
HeuristicLab-Trac-Bot commented 13 years ago

2011-08-10 18:09:40: @abeham commented

r6650

  • Added plugin, problem stub and evaluator
HeuristicLab-Trac-Bot commented 13 years ago

2011-08-11 06:41:32: @abeham commented

r6651

  • syncing
HeuristicLab-Trac-Bot commented 13 years ago

2011-08-12 17:31:30: @abeham commented

r6657

  • updated problem
  • added equality comparer for integer vectors
HeuristicLab-Trac-Bot commented 13 years ago

2011-08-12 22:08:54: @abeham commented

r6658

  • updated project files
HeuristicLab-Trac-Bot commented 13 years ago

2011-10-05 22:30:58: @abeham commented

r6878

  • updated branch from trunk
HeuristicLab-Trac-Bot commented 13 years ago

2011-10-07 22:45:09: @abeham commented

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
HeuristicLab-Trac-Bot commented 13 years ago

2011-10-07 23:21:17: @abeham commented

r6890

  • changed !QAPMoveEvaluatorTest slightly
HeuristicLab-Trac-Bot commented 12 years ago

2011-11-07 11:14:37: @abeham commented

r6955 (not migrated) to r6957

  • removed GeneralizedQAP branch
  • readded new simpler branch
  • removed unnecessary files from import
HeuristicLab-Trac-Bot commented 12 years ago

2011-11-29 12:29:52: @abeham changed milestone from HeuristicLab 3.3.6 to HeuristicLab 3.3.x Backlog

HeuristicLab-Trac-Bot commented 12 years ago

2011-11-29 12:29:52: @abeham commented

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

HeuristicLab-Trac-Bot commented 12 years ago

2012-01-11 09:16:36: @abeham commented

r7311: updated GQAP

HeuristicLab-Trac-Bot commented 12 years ago

2012-01-11 09:19:22: @abeham commented

r7312: added views project

HeuristicLab-Trac-Bot commented 12 years ago

2012-01-11 17:47:39: @abeham commented

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

HeuristicLab-Trac-Bot commented 12 years ago

2012-01-17 15:23:37: @abeham commented

r7345

  • added first version of GRASP+PR algorithm
HeuristicLab-Trac-Bot commented 12 years ago

2012-01-18 16:55:17: @abeham commented

r7363

  • worked on GQAP
HeuristicLab-Trac-Bot commented 12 years ago

2012-01-18 16:56:07: @abeham commented

r7364

  • added ICrossover interface
HeuristicLab-Trac-Bot commented 12 years ago

2012-01-19 17:33:35: @abeham commented

r7373: Worked on GQAP

HeuristicLab-Trac-Bot commented 12 years ago

2012-01-24 17:23:30: @abeham commented

r7407: worked on GQAP

HeuristicLab-Trac-Bot commented 12 years ago

2012-01-25 18:32:53: @abeham commented

r7412: worked on GQAP and GRASP+PR

HeuristicLab-Trac-Bot commented 12 years ago

2012-01-26 00:37:08: @abeham commented

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
HeuristicLab-Trac-Bot commented 12 years ago

2012-01-26 14:51:24: @abeham commented

r7415: improved results output of GQAP

HeuristicLab-Trac-Bot commented 12 years ago

2012-01-27 02:01:56: @abeham commented

r7418

  • Added shaking operator based on n-moves
  • Added pareto analyzer regarding flowdistance and installation qualities
HeuristicLab-Trac-Bot commented 12 years ago

2012-01-27 13:24:56: @abeham commented

r7419

  • reworked parameterization (one interface for every parameter resp. parameter group)
  • unified parameter descriptions
HeuristicLab-Trac-Bot commented 12 years ago

2012-01-27 13:35:19: @abeham commented

r7420

  • fixed parameterizing of local improvement operators
HeuristicLab-Trac-Bot commented 12 years ago

2012-01-27 16:32:38: @abeham commented

r7423

  • worked on path relinking operator
HeuristicLab-Trac-Bot commented 12 years ago

2012-01-27 18:41:09: @abeham commented

r7425

  • worked on path relinking
HeuristicLab-Trac-Bot commented 12 years ago

2012-01-31 15:17:25: @abeham commented

r7432

  • updated gqap (finished path-relinking)
  • fixed some bugs
HeuristicLab-Trac-Bot commented 12 years ago

2012-02-01 00:14:15: @abeham commented

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
HeuristicLab-Trac-Bot commented 12 years ago

2012-02-01 13:29:07: @abeham commented

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
HeuristicLab-Trac-Bot commented 12 years ago

2012-02-03 10:02:08: @abeham commented

r7443

  • worked on generic instance provider
  • added CTAP instances
HeuristicLab-Trac-Bot commented 12 years ago

2012-02-03 10:11:31: @abeham commented

r7444

  • fixed build
HeuristicLab-Trac-Bot commented 12 years ago

2012-02-03 16:19:31: @abeham commented

r7445

  • updated problem instance provider
HeuristicLab-Trac-Bot commented 12 years ago

2012-02-03 18:22:54: @abeham commented

r7448

  • Added Transpose() extension method for double[,] matrices
  • Added IProblemInstanceConsumer 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
HeuristicLab-Trac-Bot commented 12 years ago

2012-02-10 23:18:10: @abeham commented

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
HeuristicLab-Trac-Bot commented 12 years ago

2012-02-13 16:35:31: @abeham commented

r7466

  • included TSLIB's ATSP and CVRP problems as well
HeuristicLab-Trac-Bot commented 12 years ago

2012-02-15 17:28:50: @abeham commented

r7470

  • Removed incompatible problem linhp318.tsp (contains fixed edges)
  • Fixed AssemblyInfo for TSPLIB
  • Added unit tests
  • Worked on assignment / solution view
HeuristicLab-Trac-Bot commented 12 years ago

2012-02-15 19:25:12: @abeham commented

r7471

  • Added a button to recalculate the quality
HeuristicLab-Trac-Bot commented 12 years ago

2012-02-16 16:00:18: @abeham commented

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

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-17 14:03:55: @abeham commented

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
HeuristicLab-Trac-Bot commented 12 years ago

2012-02-17 21:23:53: @abeham commented

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
HeuristicLab-Trac-Bot commented 12 years ago

2012-02-17 21:33:21: @abeham commented

r7483: updated project file

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-17 23:14:46: @abeham commented

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

HeuristicLab-Trac-Bot commented 12 years ago

2012-02-22 22:43:22: @abeham commented

r7505

  • added instances of Cordeau et al. as given by L. Moccia
  • added operators for tabu search
HeuristicLab-Trac-Bot commented 12 years ago

2012-02-24 23:27:22: @abeham commented

r7523

  • sorted operators
  • added crossover defined by Cordeau et al.
  • fixed a few bugs
HeuristicLab-Trac-Bot commented 12 years ago

2012-03-01 15:15:53: @abeham commented

r7538

  • Fixed plugin dependencies
  • Updated GQAP view
  • Changed instances infrastructure
    • Changed interface types into classes
    • Removed the library specific instance classes
HeuristicLab-Trac-Bot commented 12 years ago

2012-03-01 15:52:33: @abeham commented

r7539

  • fixed a discovery bug
HeuristicLab-Trac-Bot commented 12 years ago

2012-03-05 16:30:44: @abeham commented

r7548: changed according to architects review

HeuristicLab-Trac-Bot commented 12 years ago

2012-03-05 20:39:12: @abeham commented

r7552: removed class diagram