Opened 10 years ago

Closed 10 years ago

#1497 closed feature request (done)

Implement local search operator for QAP

Reported by: abeham Owned by: abeham
Priority: high Milestone: HeuristicLab 3.3.5
Component: Problems.QuadraticAssignment Version: 3.3.5
Keywords: Cc:

Description

For use in VNS implement a best-improvement local search operator that is problem-specific and fast.

Change History (6)

comment:1 Changed 10 years ago by abeham

  • Status changed from new to accepted

comment:2 Changed 10 years ago by abeham

r6086

  • Added problem-specific local improvement operator (best improvement local search using swap2 moves)
    • Adapted ExhaustiveSwap2MoveGenerator to yield moves
  • Added a parameter BestKnownSolutions to collect possible optimal invariants
    • Adapted BestQAPSolutionAnalyzer to collect optimal invariants
  • Added a function to the QAP Evaluator that calculates the impact of a certain allele

comment:3 Changed 10 years ago by abeham

  • Priority changed from medium to high

comment:4 Changed 10 years ago by abeham

  • Owner changed from abeham to svonolfe
  • Status changed from accepted to reviewing
  • Version changed from branch to 3.3.4

r6342

  • merged to trunk

comment:5 Changed 10 years ago by svonolfe

  • Owner changed from svonolfe to abeham
  • Status changed from reviewing to readytorelease

I think the change is very valuable and improves the runtime efficiency of VNS a lot. The relevant changes to the VNS algorithm have already been incorporated in r6042, so this is ready for release.

For other problems we probably have to implement stochastic variants if the exhaustive move generator produces too many moves.

comment:6 Changed 10 years ago by swagner

  • Resolution set to done
  • Status changed from readytorelease to closed
  • Version changed from 3.3.4 to 3.3.5
Note: See TracTickets for help on using tickets.