net.sf.cpsolver.ifs.solver
Class Solver<V extends Variable<V,T>,T extends Value<V,T>>

java.lang.Object
  extended by 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:


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:
Usage:
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 Tomas Muller
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
protected  class Solver.SolverThread
          Solver thread
 
Field Summary
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 org.apache.log4j.Logger sLogger
          log
static int THREAD_PRIORITY
           
 
Constructor Summary
Solver(DataProperties properties)
          Constructor.
 
Method Summary
 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 org.apache.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

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



Copyright © 2014 UniTime LLC. All Rights Reserved.