Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## ifs.solver
Class Solver

    java.lang.Object
      ifs.solver.Solver

    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 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 variable selection (function selectVariable, see `VariableSelection`) and
- the value selection (function selectValue, see `ValueSelection`).

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`)
Value.Class | `String` | Fully qualified class name of the value selection criterion (see `ValueSelection`, e.g. `GeneralValueSelection`)
Variable.Class | `String` | Fully qualified class name of the variable selection criterion (see `VariableSelection`, e.g. `GeneralVariableSelection`)
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:
  1.0
Author:
  Tomáš Müller
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 boolean` | `iDone` solver status: done
`protected Solution` | `iLastSolution` last solution (after IFS Solver finishes)
`protected boolean` | `iRunning` solver status: running
`protected Solver.SolverThread` | `iSolverThread` solver thread
`protected boolean` | `iStop` solver status: stopped
`protected static Logger` | `sLogger` log

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)
`Vector` | `getExtensions()` Returns list of all used extensions
`PerturbationsCounter` | `getPerturbationsCounter()` Returns perturbation counter (minimal perturbation problem)
`DataProperties` | `getProperties()` Returns configuration
`SolutionComparator` | `getSolutionComparator()` Returns solution comparator
`Thread` | `getSolverThread()` Returns solver's thread
`TerminationCondition` | `getTerminationCondition()` Returns termination condition
`ValueSelection` | `getValueSelection()` Returns values selection criterion
`VariableSelection` | `getVariableSelection()` Returns variable selection criterion
`void` | `init()` Initialization
`boolean` | `isDone()` Solver status: solver is done
`boolean` | `isRunning()` Solver status: solver is running
`boolean` | `isStopped()` Solver status: solver is stopped
`Solution` | `lastSolution()` Last solution (when solver finishes)
`void` | `removeSolverListener(SolverListener listener)` Removes a solver listener
`void` | `setInitalSolution(Model model)` Sets initial solution
`void` | `setInitalSolution(Solution solution)` Sets initial solution
`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` | `setValueSelection(ValueSelection valueSelection)` Sets value selection criterion
`void` | `setVariableSelection(VariableSelection variableSelection)` Sets variable selection criterion
`void` | `start()` Starts solver
`void` | `stopSolver()` Stops the running solver

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Field Detail

### sLogger

    protected static Logger sLogger

  log

### iCurrentSolution

    protected Solution iCurrentSolution

  current solution

### iLastSolution

    protected Solution iLastSolution

  last solution (after IFS Solver finishes)

### iDone

    protected boolean iDone

  solver status: done

### iRunning

    protected boolean iRunning

  solver status: running

### iStop

    protected boolean iStop

  solver status: stopped

### iSolverThread

    protected Solver.SolverThread iSolverThread

  solver thread

Constructor Detail

### Solver

    public Solver(DataProperties properties)

  Constructor.

  Parameters:
    `properties` - input configuration

Method Detail

### setTerminalCondition

    public void setTerminalCondition(TerminationCondition terminationCondition)

  Sets termination condition

### setSolutionComparator

    public void setSolutionComparator(SolutionComparator solutionComparator)

  Sets solution comparator

### setValueSelection

    public void setValueSelection(ValueSelection valueSelection)

  Sets value selection criterion

### setVariableSelection

    public void setVariableSelection(VariableSelection variableSelection)

  Sets variable 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

### getValueSelection

    public ValueSelection getValueSelection()

  Returns values selection criterion

### getVariableSelection

    public VariableSelection getVariableSelection()

  Returns variable 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

### 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

### lastSolution

    public Solution lastSolution()

  Last solution (when solver finishes)

### currentSolution

    public Solution currentSolution()

  Current solution (during the search)

### isDone

    public boolean isDone()

  Solver status: solver is done

### isRunning

    public boolean isRunning()

  Solver status: solver is running

### stopSolver

    public void stopSolver()

  Stops the running solver

### isStopped

    public boolean isStopped()

  Solver status: solver is stopped

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright © 2005 Tomáš Müller