Solver (Constraint Solver API Documentation -- CPSolver v1.4 build 75)

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

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.

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

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

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

THREAD_PRIORITY

sLogger

iCurrentSolution

iLastSolution

iStop

iSolverThread

iSolverListeners

iSaveBestUnassigned

iProgress

Constructor Detail

Solver

Method Detail

dispose

setTerminalCondition

setSolutionComparator

setNeighbourSelection

setPerturbationsCounter

addExtension

getTerminationCondition

getSolutionComparator

getNeighbourSelection

getPerturbationsCounter

getExtensions

addSolverListener

removeSolverListener

getSolverListeners

getProperties

autoConfigure

clearBest

setInitalSolution

setInitalSolution

start

getSolverThread

init

isUpdateProgress

setUpdateProgress

lastSolution

currentSolution

initSolver

stopSolver

stopSolver

isRunning

onStop

onStart

onFinish

onFailure

onAssigned

hasSingleSolution

isStop