|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectnet.sf.cpsolver.ifs.solver.Solver<V,T>
public class Solver<V extends Variable<V,T>,T extends Value<V,T>>
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
TerminationCondition
),
SolutionComparator
),
NeighbourSelection
) and
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
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 ) |
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 |
---|
public static int THREAD_PRIORITY
protected static org.apache.log4j.Logger sLogger
protected Solution<V extends Variable<V,T>,T extends Value<V,T>> iCurrentSolution
protected Solution<V extends Variable<V,T>,T extends Value<V,T>> iLastSolution
protected boolean iStop
protected Solver.SolverThread iSolverThread
Constructor Detail |
---|
public Solver(DataProperties properties)
properties
- input configurationMethod Detail |
---|
public void dispose()
public void setTerminalCondition(TerminationCondition<V,T> terminationCondition)
public void setSolutionComparator(SolutionComparator<V,T> solutionComparator)
public void setNeighbourSelection(NeighbourSelection<V,T> neighbourSelection)
public void setPerturbationsCounter(PerturbationsCounter<V,T> perturbationsCounter)
public void addExtension(Extension<V,T> extension)
public TerminationCondition<V,T> getTerminationCondition()
public SolutionComparator<V,T> getSolutionComparator()
public NeighbourSelection<V,T> getNeighbourSelection()
public PerturbationsCounter<V,T> getPerturbationsCounter()
public List<Extension<V,T>> getExtensions()
public void addSolverListener(SolverListener<V,T> listener)
public void removeSolverListener(SolverListener<V,T> listener)
public List<SolverListener<V,T>> getSolverListeners()
public DataProperties getProperties()
protected void autoConfigure()
public void clearBest()
public void setInitalSolution(Solution<V,T> solution)
public void setInitalSolution(Model<V,T> model)
public void start()
public Thread getSolverThread()
public void init()
public void setUpdateProgress(boolean updateProgress)
Progress
)
public Solution<V,T> lastSolution()
public Solution<V,T> currentSolution()
public void initSolver()
public void stopSolver()
public void stopSolver(boolean join)
public boolean isRunning()
protected void onStop()
protected void onStart()
protected void onFinish()
protected void onFailure()
protected void onAssigned(double startTime)
public boolean isStop()
stopSolver()
was called
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |