org.cpsolver.exam.heuristics

## Class ExamTabuSearch

- java.lang.Object
- - org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext<Exam,ExamPlacement,ExamTabuSearch.TabuList>
  - - org.cpsolver.exam.heuristics.ExamTabuSearch

- All Implemented Interfaces:
    CanHoldContext, HasAssignmentContext<Exam,ExamPlacement,ExamTabuSearch.TabuList>, NeighbourSelection<Exam,ExamPlacement>, ValueSelection<Exam,ExamPlacement>

      public class ExamTabuSearch
      extends NeighbourSelectionWithContext<Exam,ExamPlacement,ExamTabuSearch.TabuList>
      implements ValueSelection<Exam,ExamPlacement>

  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.3 (Examination Timetabling)
    Copyright (C) 2008 - 2014 Tomáš Müller
    muller@unitime.org
    http://muller.unitime.org
    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 3 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 see http://www.gnu.org/licenses/.
  Author:
    Tomáš Müller

- - ### Nested Class Summary

    Nested Classes
    Modifier and Type | Class and Description
    --- | ---
    `static class` | `ExamTabuSearch.TabuList` Tabu-list

  - ### Field Summary

    - ### Fields inherited from class org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext

      `iContextOverride`

    - ### Fields inherited from interface org.cpsolver.ifs.assignment.context.CanHoldContext

      `sMaxSize`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `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(Assignment)`) Value.ConflictWeight ... weight of a conflicting value (see `Model.conflictValues(Assignment, Value)`), it is also weighted by the past occurrences when conflict-based statistics is used

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `ExamTabuSearch.TabuList` | `createAssignmentContext(Assignment<Exam,ExamPlacement> assignment)` Create a new assignment context for the given assignment.
    `void` | `init(Solver<Exam,ExamPlacement> solver)` Initialization
    `Neighbour<Exam,ExamPlacement>` | `selectNeighbour(Solution<Exam,ExamPlacement> solution)` Neighbor selection
    `ExamPlacement` | `selectValue(Solution<Exam,ExamPlacement> solution, Exam exam)` Value selection

    - ### Methods inherited from class org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext

      `getAssignmentContextReference, getContext, getContext, hasContextOverride, isSingleContextSolver, setAssignmentContextReference`

    - ### 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(Assignment)`)
      - Value.ConflictWeight ... weight of a conflicting value (see `Model.conflictValues(Assignment, Value)`), it is also weighted by the past occurrences when conflict-based statistics is used
      Parameters:
        `properties` - solver configuration
      Throws:
        `Exception` - thrown when the initialization fails

  - ### Method Detail

    - #### init

          public void init(Solver<Exam,ExamPlacement> solver)

      Initialization
      Specified by:
        `init` in interface `NeighbourSelection<Exam,ExamPlacement>`
      Specified by:
        `init` in interface `ValueSelection<Exam,ExamPlacement>`
      Overrides:
        `init` in class `NeighbourSelectionWithContext<Exam,ExamPlacement,ExamTabuSearch.TabuList>`
      Parameters:
        `solver` - current solver

    - #### selectNeighbour

          public Neighbour<Exam,ExamPlacement> selectNeighbour(Solution<Exam,ExamPlacement> solution)

      Neighbor selection
      Specified by:
        `selectNeighbour` in interface `NeighbourSelection<Exam,ExamPlacement>`
      Parameters:
        `solution` - given solution
      Returns:
        a neighbour assignment

    - #### selectValue

          public ExamPlacement selectValue(Solution<Exam,ExamPlacement> solution,
                                           Exam exam)

      Value selection
      Specified by:
        `selectValue` in interface `ValueSelection<Exam,ExamPlacement>`
      Parameters:
        `solution` - current solution
        `exam` - selected variable
      Returns:
        selected value (of the given variable)

    - #### createAssignmentContext

          public ExamTabuSearch.TabuList createAssignmentContext(Assignment<Exam,ExamPlacement> assignment)

      Description copied from interface: `HasAssignmentContext`
      Create a new assignment context for the given assignment. If there are already some variables assigned in the value, the method should make sure that the context is appropriately initialized.
      Specified by:
        `createAssignmentContext` in interface `HasAssignmentContext<Exam,ExamPlacement,ExamTabuSearch.TabuList>`
      Parameters:
        `assignment` - an assignment for which there needs to be an assignment context
      Returns:
        a new instance of the assignment context, filled according to the given assignment