net.sf.cpsolver.exam.heuristics
Class ExamTabuSearch

java.lang.Object
  net.sf.cpsolver.exam.heuristics.ExamTabuSearch

All Implemented Interfaces:

NeighbourSelection, ValueSelection

public class ExamTabuSearch
extends Object
implements NeighbourSelection, ValueSelection

Tabu search algorithm.

If used as NeighbourSelection, the most improving (re)assignment of a value to a variable is returned (all variables and all their values are enumerated). If there are more than one of such assignments, one is selected randomly. A returned assignment can cause unassignment of other existing assignments. The search is stopped (selectNeighbour(Solution) returns null) after TabuSearch.MaxIdle idle (not improving) iterations.

If used as ValueSelection, the most improving (re)assignment of a value to a given variable is returned (all values of the given variable are enumerated). If there are more than one of such assignments, one is selected randomly. A returned assignment can cause unassignment of other existing assignments.

To avoid cycling, a tabu is maintainded during the search. It is the list of the last n selected values. A selection of a value that is present in the tabu list is only allowed when it improves the best ever found solution.

The minimum size of the tabu list is TabuSearch.MinSize, maximum size is TabuSearch.MaxSize (tabu list is not used when both sizes are zero). The current size of the tabu list starts at MinSize (and is reset to MinSize every time a new best solution is found), it is increased by one up to the MaxSize after TabuSearch.MaxIdle / (MaxSize - MinSize) non-improving iterations.

Conflict-based Statistics ConflictStatistics (CBS) can be used instead of (or together with) tabu list, when CBS is used as a solver extension.

Version:

ExamTT 1.1 (Examination Timetabling)
Copyright (C) 2008 Tomáš Müller
muller@unitime.org
Lazenska 391, 76314 Zlin, Czech Republic

This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

Constructor Summary

ExamTabuSearch(DataProperties properties)
TabuSearch.MaxIdle ... maximum number of idle iterations (default is 10000) TabuSearch.MinSize ... minimum size of the tabu list TabuSearch.MaxSize ... maximum size of the tabu list Value.ValueWeight ... weight of a value (i.e., Value.toDouble()) Value.ConflictWeight ... weight of a conflicting value (see Model.conflictValues(Value)), it is also weighted by the past occurrences when conflict-based statistics is used

Method Summary

void	init(Solver solver) Initialization
Neighbour	selectNeighbour(Solution solution) Neighbor selection
Value	selectValue(Solution solution, Variable variable) Value selection

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ExamTabuSearch

public ExamTabuSearch(DataProperties properties)
               throws Exception

• TabuSearch.MaxIdle ... maximum number of idle iterations (default is 10000)
• TabuSearch.MinSize ... minimum size of the tabu list
• TabuSearch.MaxSize ... maximum size of the tabu list
• Value.ValueWeight ... weight of a value (i.e., Value.toDouble())
• Value.ConflictWeight ... weight of a conflicting value (see Model.conflictValues(Value)), it is also weighted by the past occurrences when conflict-based statistics is used

Throws:

Exception

Method Detail

init

public void init(Solver solver)

Initialization

Specified by:

init in interface NeighbourSelection

Specified by:

init in interface ValueSelection

selectNeighbour

public Neighbour selectNeighbour(Solution solution)

Neighbor selection

Specified by:

selectNeighbour in interface NeighbourSelection

Parameters:

solution - given solution

Returns:

a neighbour assignment

selectValue

public Value selectValue(Solution solution,
                         Variable variable)

Value selection

Specified by:

selectValue in interface ValueSelection

Parameters:

solution - current solution

variable - selected variable