org.cpsolver.ifs.solver

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

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

- Type Parameters:
    `V` - Variable
    `T` - Value
  Direct Known Subclasses:
    ParallelSolver, 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 org.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:

  Related Solver 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.3 (Iterative Forward Search)
    Copyright (C) 2006 - 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
  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 Progress` | `iProgress`
    `protected int` | `iSaveBestUnassigned`
    `protected List<SolverListener<V,T>>` | `iSolverListeners`
    `protected Solver.SolverThread` | `iSolverThread` solver thread
    `protected boolean` | `iStop` solver is stopped
    `protected static org.apache.logging.log4j.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
    `boolean` | `hasSingleSolution()` Returns true if the solver works only with one solution (regardless the number of threads it is using)
    `void` | `init()` Initialization
    `void` | `initSolver()`
    `boolean` | `isRunning()` True, if the solver is running
    `boolean` | `isStop()` Return true if `stopSolver()` was called
    `protected boolean` | `isUpdateProgress()` True, when solver should update progress (see `Progress`)
    `Solution<V,T>` | `lastSolution()` Last solution (when solver finishes)
    `protected void` | `onAssigned(double startTime, Solution<V,T> solution)` 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 org.apache.logging.log4j.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

    - #### iSolverListeners

          protected List<SolverListener<V extends Variable<V,T>,T extends Value<V,T>>> iSolverListeners

    - #### iSaveBestUnassigned

          protected int iSaveBestUnassigned

    - #### iProgress

          protected Progress iProgress

  - ### 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
      Parameters:
        `terminationCondition` - termination condition

    - #### setSolutionComparator

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

      Sets solution comparator
      Parameters:
        `solutionComparator` - solution comparator

    - #### setNeighbourSelection

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

      Sets neighbour selection criterion
      Parameters:
        `neighbourSelection` - neighbour selection criterion

    - #### setPerturbationsCounter

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

      Sets perturbation counter (minimal perturbation problem)
      Parameters:
        `perturbationsCounter` - perturbation counter

    - #### addExtension

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

      Add an IFS extension
      Parameters:
        `extension` - an extension

    - #### getTerminationCondition

          public TerminationCondition<V,T> getTerminationCondition()

      Returns termination condition
      Returns:
        termination condition

    - #### getSolutionComparator

          public SolutionComparator<V,T> getSolutionComparator()

      Returns solution comparator
      Returns:
        solution comparator

    - #### getNeighbourSelection

          public NeighbourSelection<V,T> getNeighbourSelection()

      Returns neighbour selection criterion
      Returns:
        neighbour selection criterion

    - #### getPerturbationsCounter

          public PerturbationsCounter<V,T> getPerturbationsCounter()

      Returns perturbation counter (minimal perturbation problem)
      Returns:
        perturbation counter

    - #### getExtensions

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

      Returns list of all used extensions
      Returns:
        list of all registered extensions

    - #### addSolverListener

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

      Adds a solver listener
      Parameters:
        `listener` - solver listener

    - #### removeSolverListener

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

      Removes a solver listener
      Parameters:
        `listener` - solver listener

    - #### getSolverListeners

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

      Registered solver listeners
      Returns:
        list of all registered solver listeners

    - #### getProperties

          public DataProperties getProperties()

      Returns configuration
      Returns:
        solver 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
      Parameters:
        `solution` - initial solution

    - #### setInitalSolution

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

      Sets initial solution
      Parameters:
        `model` - problem model

    - #### start

          public void start()

      Starts solver

    - #### getSolverThread

          public Thread getSolverThread()

      Returns solver's thread
      Returns:
        solver's thread

    - #### init

          public void init()

      Initialization

    - #### isUpdateProgress

          protected boolean isUpdateProgress()

      True, when solver should update progress (see `Progress`)
      Returns:
        true if the solver should update process

    - #### setUpdateProgress

          public void setUpdateProgress(boolean updateProgress)

      True, when solver should update progress (see `Progress`)
      Parameters:
        `updateProgress` - true if the solver should update process (default is true)

    - #### lastSolution

          public Solution<V,T> lastSolution()

      Last solution (when solver finishes)
      Returns:
        last solution

    - #### currentSolution

          public Solution<V,T> currentSolution()

      Current solution (during the search)
      Returns:
        current solution

    - #### initSolver

          public void initSolver()

    - #### stopSolver

          public void stopSolver()

      Stop running solver

    - #### stopSolver

          public void stopSolver(boolean join)

      Stop running solver
      Parameters:
        `join` - wait for the solver thread to finish

    - #### isRunning

          public boolean isRunning()

      True, if the solver is running
      Returns:
        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,
                                    Solution<V,T> solution)

      Called in each iteration, after a neighbour is assigned
      Parameters:
        `startTime` - solver start time in seconds
        `solution` - current solution

    - #### hasSingleSolution

          public boolean hasSingleSolution()

      Returns true if the solver works only with one solution (regardless the number of threads it is using)
      Returns:
        true

    - #### isStop

          public boolean isStop()

      Return true if `stopSolver()` was called
      Returns:
        true if the solver is to be stopped