net.sf.cpsolver.ifs.solver

## Class Solver<V extends Variable<V,T>,T extends Value<V,T>>

- java.lang.Object
- - net.sf.cpsolver.ifs.solver.Solver<V,T>

- Direct Known Subclasses:
    TimetableSolver

      public class Solver<V extends Variable<V,T>,T extends Value<V,T>>
      extends Object

  IFS Solver.
  The iterative forward search (IFS) algorithm is based on ideas of local search methods. However, in contrast to classical local search techniques, it operates over feasible, though not necessarily complete solutions. In such a solution, some variables can be left unassigned. Still all hard constraints on assigned variables must be satisfied. Similarly to backtracking based algorithms, this means that there are no violations of hard constraints.
  This search works in iterations. During each step, an unassigned or assigned variable is initially selected. Typically an unassigned variable is chosen like in backtracking-based search. An assigned variable may be selected when all variables are assigned but the solution is not good enough (for example, when there are still many violations of soft constraints). Once a variable is selected, a value from its domain is chosen for assignment. Even if the best value is selected (whatever ???best??? means), its assignment to the selected variable may cause some hard conflicts with already assigned variables. Such conflicting variables are removed from the solution and become unassigned. Finally, the selected value is assigned to the selected variable.
  Algorithm schema:
  `procedure net.sf.cpsolver.ifs(initial) // initial solution is the parameter
  iteration = 0; // iteration counter
  current = initial; // current (partial) feasible solution
  best = initial; // best solution
  while canContinue(current, iteration) do
  iteration = iteration + 1;
  variable = selectVariable(current);
  value = selectValue(current, variable);
  UNASSIGN(current, CONFLICTING_VARIABLES(current, variable, value));
  ASSIGN(current, variable, value);
  if better(current, best) then best = current;
  end while
  return best;
  end procedure
  `
  The algorithm attempts to move from one (partial) feasible solution to another via repetitive assignment of a selected value to a selected variable. During this search, the feasibility of all hard constraints in each iteration step is enforced by unassigning the conflicting variables. The search is terminated when the requested solution is found or when there is a timeout, expressed e.g., as a maximal number of iterations or available time being reached. The best solution found is then returned.
  The above algorithm schema is parameterized by several functions, namely:
  - the termination condition (function canContinue, see `TerminationCondition`),
  - the solution comparator (function better, see `SolutionComparator` ),
  - the neighbour selection (function selectNeighbour, see `NeighbourSelection`) and
  Usage:
  `DataProperties cfg = ToolBox.loadProperties(inputCfg); //input configuration
  Solver solver = new Solver(cfg);
  solver.setInitalSolution(model); //sets initial solution
  solver.start(); //server is executed in a thread
  try { //wait untill the server finishes
  solver.getSolverThread().join();
  } catch (InterruptedException e) {}
  Solution solution = solver.lastSolution(); //last solution
  solution.restoreBest(); //restore best solution ever found
  `
  Solver's parameters:

  Parameter | Type | Comment
  --- | --- | ---
  General.SaveBestUnassigned | `Integer` | During the search, solution is saved when it is the best ever found solution and if the number of assigned variables is less or equal this parameter (if set to -1, the solution is always saved)
  General.Seed | `Long` | If set, random number generator is initialized with this seed
  General.SaveConfiguration | `Boolean` | If true, given configuration is stored into the output folder (during initialization of the solver, ${General.Output}/${General.ProblemName}.properties)
  Solver.AutoConfigure | `Boolean` | If true, IFS Solver is configured according to the following parameters
  Termination.Class | `String` | Fully qualified class name of the termination condition (see `TerminationCondition`, e.g. `GeneralTerminationCondition`)
  Comparator.Class | `String` | Fully qualified class name of the solution comparator (see `SolutionComparator`, e.g. `GeneralSolutionComparator`)
  Neighbour.Class | `String` | Fully qualified class name of the neighbour selection criterion (see `NeighbourSelection`, e.g. `StandardNeighbourSelection`)
  PerturbationCounter.Class | `String` | Fully qualified class name of the perturbation counter in case of solving minimal perturbation problem (see `PerturbationsCounter`, e.g. `DefaultPerturbationsCounter`)
  Extensions.Classes | `String` | Semi-colon separated list of fully qualified class names of IFS extensions (see `Extension`, e.g. `ConflictStatistics` or `MacPropagation`)

  Version:
    IFS 1.2 (Iterative Forward Search)
    Copyright (C) 2006 - 2010 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 .
  See Also:
    `SolverListener`, `Model`, `Solution`, `TerminationCondition`, `SolutionComparator`, `PerturbationsCounter`, `VariableSelection`, `ValueSelection`, `Extension`

- - ### Nested Class Summary

    Nested Classes
    Modifier and Type | Class and Description
    --- | ---
    `protected class` | `Solver.SolverThread` Solver thread

  - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected Solution<V,T>` | `iCurrentSolution` current solution
    `protected Solution<V,T>` | `iLastSolution` last solution (after IFS Solver finishes)
    `protected Solver.SolverThread` | `iSolverThread` solver thread
    `protected boolean` | `iStop` solver is stopped
    `protected static Logger` | `sLogger` log
    `static int` | `THREAD_PRIORITY`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `Solver(DataProperties properties)` Constructor.

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `void` | `addExtension(Extension<V,T> extension)` Add an IFS extension
    `void` | `addSolverListener(SolverListener<V,T> listener)` Adds a solver listener
    `protected void` | `autoConfigure()` Automatic configuratin of the solver -- when Solver.AutoConfigure is true
    `void` | `clearBest()` Clears best solution
    `Solution<V,T>` | `currentSolution()` Current solution (during the search)
    `void` | `dispose()` Dispose solver
    `List<Extension<V,T>>` | `getExtensions()` Returns list of all used extensions
    `NeighbourSelection<V,T>` | `getNeighbourSelection()` Returns neighbour selection criterion
    `PerturbationsCounter<V,T>` | `getPerturbationsCounter()` Returns perturbation counter (minimal perturbation problem)
    `DataProperties` | `getProperties()` Returns configuration
    `SolutionComparator<V,T>` | `getSolutionComparator()` Returns solution comparator
    `List<SolverListener<V,T>>` | `getSolverListeners()` Registered solver listeners
    `Thread` | `getSolverThread()` Returns solver's thread
    `TerminationCondition<V,T>` | `getTerminationCondition()` Returns termination condition
    `void` | `init()` Initialization
    `void` | `initSolver()`
    `boolean` | `isRunning()` True, if the solver is running
    `boolean` | `isStop()` Return true if `stopSolver()` was called
    `Solution<V,T>` | `lastSolution()` Last solution (when solver finishes)
    `protected void` | `onAssigned(double startTime)` Called in each iteration, after a neighbour is assigned
    `protected void` | `onFailure()` Called when the solver fails
    `protected void` | `onFinish()` Called when the solver is finished
    `protected void` | `onStart()` Called when the solver is started
    `protected void` | `onStop()` Called when the solver is stopped
    `void` | `removeSolverListener(SolverListener<V,T> listener)` Removes a solver listener
    `void` | `setInitalSolution(Model<V,T> model)` Sets initial solution
    `void` | `setInitalSolution(Solution<V,T> solution)` Sets initial solution
    `void` | `setNeighbourSelection(NeighbourSelection<V,T> neighbourSelection)` Sets neighbour selection criterion
    `void` | `setPerturbationsCounter(PerturbationsCounter<V,T> perturbationsCounter)` Sets perturbation counter (minimal perturbation problem)
    `void` | `setSolutionComparator(SolutionComparator<V,T> solutionComparator)` Sets solution comparator
    `void` | `setTerminalCondition(TerminationCondition<V,T> terminationCondition)` Sets termination condition
    `void` | `setUpdateProgress(boolean updateProgress)` True, when solver should update progress (see `Progress`)
    `void` | `start()` Starts solver
    `void` | `stopSolver()` Stop running solver
    `void` | `stopSolver(boolean join)` Stop running solver

    - ### Methods inherited from class java.lang.Object

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

- - ### Field Detail

    - #### THREAD_PRIORITY

          public static int THREAD_PRIORITY

    - #### sLogger

          protected static Logger sLogger

      log

    - #### iCurrentSolution

          protected Solution<V extends Variable<V,T>,T extends Value<V,T>> iCurrentSolution

      current solution

    - #### iLastSolution

          protected Solution<V extends Variable<V,T>,T extends Value<V,T>> iLastSolution

      last solution (after IFS Solver finishes)

    - #### iStop

          protected boolean iStop

      solver is stopped

    - #### iSolverThread

          protected Solver.SolverThread iSolverThread

      solver thread

  - ### Constructor Detail

    - #### Solver

          public Solver(DataProperties properties)

      Constructor.
      Parameters:
        `properties` - input configuration

  - ### Method Detail

    - #### dispose

          public void dispose()

      Dispose solver

    - #### setTerminalCondition

          public void setTerminalCondition(TerminationCondition<V,T> terminationCondition)

      Sets termination condition

    - #### setSolutionComparator

          public void setSolutionComparator(SolutionComparator<V,T> solutionComparator)

      Sets solution comparator

    - #### setNeighbourSelection

          public void setNeighbourSelection(NeighbourSelection<V,T> neighbourSelection)

      Sets neighbour selection criterion

    - #### setPerturbationsCounter

          public void setPerturbationsCounter(PerturbationsCounter<V,T> perturbationsCounter)

      Sets perturbation counter (minimal perturbation problem)

    - #### addExtension

          public void addExtension(Extension<V,T> extension)

      Add an IFS extension

    - #### getTerminationCondition

          public TerminationCondition<V,T> getTerminationCondition()

      Returns termination condition

    - #### getSolutionComparator

          public SolutionComparator<V,T> getSolutionComparator()

      Returns solution comparator

    - #### getNeighbourSelection

          public NeighbourSelection<V,T> getNeighbourSelection()

      Returns neighbour selection criterion

    - #### getPerturbationsCounter

          public PerturbationsCounter<V,T> getPerturbationsCounter()

      Returns perturbation counter (minimal perturbation problem)

    - #### getExtensions

          public List<Extension<V,T>> getExtensions()

      Returns list of all used extensions

    - #### addSolverListener

          public void addSolverListener(SolverListener<V,T> listener)

      Adds a solver listener

    - #### removeSolverListener

          public void removeSolverListener(SolverListener<V,T> listener)

      Removes a solver listener

    - #### getSolverListeners

          public List<SolverListener<V,T>> getSolverListeners()

      Registered solver listeners

    - #### getProperties

          public DataProperties getProperties()

      Returns configuration

    - #### autoConfigure

          protected void autoConfigure()

      Automatic configuratin of the solver -- when Solver.AutoConfigure is true

    - #### clearBest

          public void clearBest()

      Clears best solution

    - #### setInitalSolution

          public void setInitalSolution(Solution<V,T> solution)

      Sets initial solution

    - #### setInitalSolution

          public void setInitalSolution(Model<V,T> model)

      Sets initial solution

    - #### start

          public void start()

      Starts solver

    - #### getSolverThread

          public Thread getSolverThread()

      Returns solver's thread

    - #### init

          public void init()

      Initialization

    - #### setUpdateProgress

          public void setUpdateProgress(boolean updateProgress)

      True, when solver should update progress (see `Progress`)

    - #### lastSolution

          public Solution<V,T> lastSolution()

      Last solution (when solver finishes)

    - #### currentSolution

          public Solution<V,T> currentSolution()

      Current solution (during the search)

    - #### initSolver

          public void initSolver()

    - #### stopSolver

          public void stopSolver()

      Stop running solver

    - #### stopSolver

          public void stopSolver(boolean join)

      Stop running solver

    - #### isRunning

          public boolean isRunning()

      True, if the solver is running

    - #### onStop

          protected void onStop()

      Called when the solver is stopped

    - #### onStart

          protected void onStart()

      Called when the solver is started

    - #### onFinish

          protected void onFinish()

      Called when the solver is finished

    - #### onFailure

          protected void onFailure()

      Called when the solver fails

    - #### onAssigned

          protected void onAssigned(double startTime)

      Called in each iteration, after a neighbour is assigned

    - #### isStop

          public boolean isStop()

      Return true if `stopSolver()` was called