net.sf.cpsolver.ifs.solver
Class Solver

java.lang.Object
  net.sf.cpsolver.ifs.solver.Solver

Direct Known Subclasses:

TimetableSolver

public class Solver
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.1 (Iterative Forward Search)
Copyright (C) 2006 Tomáš Müller
muller@unitime.org
Lazenska 391, 76314 Zlin, Czech Republic

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 2.1 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, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

See Also:

SolverListener, Model, Solution, TerminationCondition, SolutionComparator, PerturbationsCounter, VariableSelection, ValueSelection, Extension

Nested Class Summary

protected class

Solver.SolverThread Solver thread

Field Summary

protected Solution	iCurrentSolution current solution
protected Solution	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

Solver(DataProperties properties)
Constructor.

Method Summary

void	addExtension(Extension extension) Add an IFS extension
void	addSolverListener(SolverListener listener) Adds a solver listener
protected void	autoConfigure() Automatic configuratin of the solver -- when Solver.AutoConfigure is true
void	clearBest() Clears best solution
Solution	currentSolution() Current solution (during the search)
void	dispose() Dispose solver
Vector	getExtensions() Returns list of all used extensions
NeighbourSelection	getNeighbourSelection() Returns neighbour selection criterion
PerturbationsCounter	getPerturbationsCounter() Returns perturbation counter (minimal perturbation problem)
DataProperties	getProperties() Returns configuration
SolutionComparator	getSolutionComparator() Returns solution comparator
Vector	getSolverListeners() Registered solver listeners
Thread	getSolverThread() Returns solver's thread
TerminationCondition	getTerminationCondition() Returns termination condition
void	init() Initialization
void	initSolver()
boolean	isRunning() True, if the solver is running
Solution	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 listener) Removes a solver listener
void	setInitalSolution(Model model) Sets initial solution
void	setInitalSolution(Solution solution) Sets initial solution
void	setNeighbourSelection(NeighbourSelection neighbourSelection) Sets neighbour selection criterion
void	setPerturbationsCounter(PerturbationsCounter perturbationsCounter) Sets perturbation counter (minimal perturbation problem)
void	setSolutionComparator(SolutionComparator solutionComparator) Sets solution comparator
void	setTerminalCondition(TerminationCondition 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

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 iCurrentSolution

current solution

iLastSolution

protected Solution 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 terminationCondition)

Sets termination condition

setSolutionComparator

public void setSolutionComparator(SolutionComparator solutionComparator)

Sets solution comparator

setNeighbourSelection

public void setNeighbourSelection(NeighbourSelection neighbourSelection)

Sets neighbour selection criterion

setPerturbationsCounter

public void setPerturbationsCounter(PerturbationsCounter perturbationsCounter)

Sets perturbation counter (minimal perturbation problem)

addExtension

public void addExtension(Extension extension)

Add an IFS extension

getTerminationCondition

public TerminationCondition getTerminationCondition()

Returns termination condition

getSolutionComparator

public SolutionComparator getSolutionComparator()

Returns solution comparator

getNeighbourSelection

public NeighbourSelection getNeighbourSelection()

Returns neighbour selection criterion

getPerturbationsCounter

public PerturbationsCounter getPerturbationsCounter()

Returns perturbation counter (minimal perturbation problem)

getExtensions

public Vector getExtensions()

Returns list of all used extensions

addSolverListener

public void addSolverListener(SolverListener listener)

Adds a solver listener

removeSolverListener

public void removeSolverListener(SolverListener listener)

Removes a solver listener

getSolverListeners

public Vector 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 solution)

Sets initial solution

setInitalSolution

public void setInitalSolution(Model 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 lastSolution()

Last solution (when solver finishes)

currentSolution

public Solution currentSolution()

Current solution (during the search)

initSolver

public void initSolver()

stopSolver

public void stopSolver()

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