Class Solver
- java.lang.Object
-
- org.chocosolver.solver.Solver
-
- All Implemented Interfaces:
Serializable,ISelf<Solver>,ISolver,IResolutionHelper,ILearnFactory,ISearchMonitorFactory,IMoveFactory,IMeasures,IOutputFactory
public class Solver extends Object implements ISolver, IMeasures, IOutputFactory
This class is inspired from : Inspired from "Unifying search algorithms for CSP" N. Jussien and O. Lhomme, Technical report 02-3-INFO, EMNIt declares a search loop made of three components:
- Propagate: it aims at propagating information throughout the constraint network when a decision is made,
- Learn: it aims at ensuring that the search mechanism will avoid (as much as possible) to get back to states that have been explored and proved to be solution-less,
- Move: aims at, unlike other ones, not pruning the search space but rather exploring it.
Created by cprudhom on 01/09/15. Project: choco.
- Since:
- 01/09/15.
- Author:
- Charles Prud'homme
- See Also:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static classSolver.ActionDefine the possible actions of SearchLoop-
Nested classes/interfaces inherited from interface org.chocosolver.solver.trace.IOutputFactory
IOutputFactory.DefaultDecisionMessage, IOutputFactory.DefaultSolutionMessage
-
-
Field Summary
Fields Modifier and Type Field Description protected Solver.ActionactionThe next action to execute in the search loopprotected List<Criterion>criteriaList of stopping criteria.protected DecisionPathdpathThe current decisionprotected PropagationEngineengineThe propagation engine to useprotected ContradictionExceptionexceptionInternal unique contradiction exception, used on propagation failuresprotected IExplanationEngineexplainerAn explanation engineprotected ESatfeasibleProblem feasbility: - UNDEFINED if unknown, - TRUE if satisfiable, - FALSE if unsatisfiableprotected LearnLThe learning component of this search loopprotected MoveMThe moving component of this search loopprotected MeasuresRecordermMeasuresThe measure recorder to keep up to dateprotected ModelmModelThe declaring modelprotected IObjectiveManagerobjectivemanagerThe objective manager declareprotected PropagatePThe propagate component of this search loopprotected SearchMonitorListsearchMonitorsList of search monitors attached to this search loopprotected booleanstopSet to true to stop the search loop
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description voidaddStopCriterion(Criterion... criterion)Adds a stop criterion, which, when met, stops the search loop.protected voidextend()Search loop extend phaselonggetBackTrackCount()NumbergetBestSolutionValue()IBoundsManagergetBoundsManager()ContradictionExceptiongetContradictionException()longgetCurrentDepth()longgetDecisionCount()DecisionPathgetDecisionPath()PropagationEnginegetEngine()IEnvironmentgetEnvironment()PrintStreamgetErr()IExplanationEnginegetExplainer()Return the explanation engine plugged intothis.longgetFailCount()intgetJumpTo()LearngetLearner()longgetMaxDepth()MeasuresRecordergetMeasures()Returns a reference to the measures recorder.ModelgetModel()StringgetModelName()MovegetMove()longgetNodeCount()<V extends Variable>
IObjectiveManager<V>getObjectiveManager()PrintStreamgetOut()PropagategetPropagate()floatgetReadingTimeCount()longgetReadingTimeCountInNanoSeconds()longgetRestartCount()<V extends Variable>
AbstractStrategy<V>getSearch()SearchMonitorListgetSearchMonitors()SearchStategetSearchState()intgetSearchWorldIndex()longgetSolutionCount()floatgetTimeCount()longgetTimeCountInNanoSeconds()longgetTimestamp()voidhardReset()Resetting a solver to its creation state.booleanhasEndedUnexpectedly()booleanhasObjective()protected booleaninitialize()Preparation of the search: - start time recording, - store root world - push a back up world, - run the initial propagation, - initialize the Move and the search strategybooleanisDefaultSearchUsed()Indicates if the default search strategy is usedESatisFeasible()Returns information on the feasibility of the current problem defined by the solver.booleanisObjectiveOptimal()ESatisSatisfied()Return the current state of the CSP.booleanisSearchCompleted()Indicates if the search strategy is completed with one over all variablesbooleanisStopCriterionMet()voidmakeCompleteStrategy(boolean isComplete)Completes (or not) the declared search strategy with one over all variablesvoidplugMonitor(ISearchMonitor sm)Put a search monitor to react on search events (solutions, decisions, fails, ...).voidpropagate()Propagates constraints and related events through the constraint network until a fix point is find, or a contradiction is detected.protected voidpropagate(boolean left)Search loop propagation phase.Solverref()voidremoveAllStopCriteria()Empties the list of stop criteria declared.voidremoveStopCriterion(Criterion... criterion)Removes one or many stop criterion from the one to declare to the search loop.protected voidrepair()Search loop repair phasevoidreset()Resetting a solver to the state just before running the last resolution instruction.voidrestart()Sets the following action in the search to be a restart instruction.booleansearchLoop()Executes the search loopvoidsetEngine(PropagationEngine propagationEngine)Attaches a propagation enginethis.voidsetErr(PrintStream printStream)Set the current error stream (default is System.err)voidsetExplainer(IExplanationEngine explainer)Overrides the explanation engine.voidsetJumpTo(int jto)Sets how many worlds to rollback when backtrackingvoidsetLearner(Learn l)Replaces the current learn withlvoidsetMove(Move... m)Replaces the current move withmvoidsetObjectiveManager(IObjectiveManager om)Declares an objective manager to use.voidsetOut(PrintStream printStream)Set the current output stream (default is System.out)voidsetPropagate(Propagate p)Overrides the Propagate objectvoidsetSearch(AbstractStrategy... strategies)Override the default search strategies to use inthis.booleansolve()Executes the resolver as it is configured.voidthrowsException(ICause c, Variable v, String s)voidunplugAllSearchMonitors()Empties the list of search monitors.voidunplugMonitor(ISearchMonitor sm)Removes a search monitors from the ones to plug when the search will start.-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Methods inherited from interface org.chocosolver.solver.search.loop.learn.ILearnFactory
setCBJLearning, setDBTLearning, setNoLearning
-
Methods inherited from interface org.chocosolver.solver.search.measure.IMeasures
toArray, toCSV, toDimacsString, toMultiLineString, toOneLineString
-
Methods inherited from interface org.chocosolver.solver.search.loop.move.IMoveFactory
setDDS, setDFS, setGeometricalRestart, setHBFS, setLDS, setLNS, setLNS, setLubyRestart, setRestartOnSolutions, setRestarts
-
Methods inherited from interface org.chocosolver.solver.trace.IOutputFactory
constraintNetworkToGephi, outputSearchTreeToCPProfiler, outputSearchTreeToGephi, outputSearchTreeToGraphviz, printCSVStatistics, printFeatures, printShortFeatures, printShortStatistics, printStatistics, printVersion, showContradiction, showDashboard, showDashboard, showDecisions, showDecisions, showShortStatistics, showShortStatisticsOnShutdown, showSolutions, showSolutions, showStatistics, showStatisticsDuringResolution
-
Methods inherited from interface org.chocosolver.solver.search.IResolutionHelper
eachSolutionWithMeasure, findAllOptimalSolutions, findAllSolutions, findLexOptimalSolution, findOptimalSolution, findParetoFront, findSolution, streamOptimalSolutions, streamSolutions
-
Methods inherited from interface org.chocosolver.solver.search.loop.monitors.ISearchMonitorFactory
limitBacktrack, limitFail, limitNode, limitSearch, limitSolution, limitTime, limitTime, setNoGoodRecordingFromRestarts, setNoGoodRecordingFromSolutions
-
-
-
-
Field Detail
-
P
protected Propagate P
The propagate component of this search loop
-
L
protected Learn L
The learning component of this search loop
-
M
protected Move M
The moving component of this search loop
-
mModel
protected Model mModel
The declaring model
-
objectivemanager
protected IObjectiveManager objectivemanager
The objective manager declare
-
action
protected Solver.Action action
The next action to execute in the search loop
-
mMeasures
protected MeasuresRecorder mMeasures
The measure recorder to keep up to date
-
dpath
protected DecisionPath dpath
The current decision
-
criteria
protected List<Criterion> criteria
List of stopping criteria. When at least one is satisfied, the search loop ends.
-
explainer
protected IExplanationEngine explainer
An explanation engine
-
searchMonitors
protected SearchMonitorList searchMonitors
List of search monitors attached to this search loop
-
engine
protected PropagationEngine engine
The propagation engine to use
-
exception
protected final ContradictionException exception
Internal unique contradiction exception, used on propagation failures
-
feasible
protected ESat feasible
Problem feasbility: - UNDEFINED if unknown, - TRUE if satisfiable, - FALSE if unsatisfiable
-
stop
protected boolean stop
Set to true to stop the search loop
-
-
Constructor Detail
-
Solver
protected Solver(Model aModel)
Create a resolver based for the model aModel.- Parameters:
aModel- the target model
-
-
Method Detail
-
throwsException
public void throwsException(ICause c, Variable v, String s) throws ContradictionException
- Throws:
ContradictionException
-
getContradictionException
public ContradictionException getContradictionException()
-
solve
public boolean solve()
Executes the resolver as it is configured. Default configuration: - SATISFACTION : Computes a feasible solution. Use while(solve()) to enumerate all solutions. - OPTIMISATION : Computes a feasible solution, wrt to the objective defined. Use while(solve()) to find the optimal solution. Indeed, each new solution improves the objective. If no new solution is found (and no stop criterion encountered), the last one is guaranteed to be the optimal one.- Returns:
- if at least one new solution has been found.
-
searchLoop
public boolean searchLoop()
Executes the search loop- Returns:
- true if ends on a solution, false otherwise
-
initialize
protected boolean initialize()
Preparation of the search: - start time recording, - store root world - push a back up world, - run the initial propagation, - initialize the Move and the search strategy
-
propagate
protected void propagate(boolean left)
Search loop propagation phase. This needs to be distinguished frompropagate()- Parameters:
left- true if we are branching on the left false otherwise
-
extend
protected void extend()
Search loop extend phase
-
repair
protected void repair()
Search loop repair phase
-
reset
public void reset()
Resetting a solver to the state just before running the last resolution instruction. That is,
Propagate,Learn,MoveandSearchare kept as declared.ISearchMonitorare also kept plugged to the search loop.For hard reset, see
In details, calling this method will:hardReset().- backtrack to
rootWorldIndex - set
searchWorldIndexto 0 - set
actiontoinitialize() - reset
mMeasures - flush
engine - synchronize
dpathto erase out-dated decisions, presumably all of them - reset bounds of
objectivemanager(callingIBoundsManager.resetBestBounds() - remove all stop criteria
removeAllStopCriteria() - set
feasibletoESat.UNDEFINED
- See Also:
hardReset()
- backtrack to
-
hardReset
public void hardReset()
Resetting a solver to its creation state.
For soft reset, see
reset().In details, calling this method will, first call
reset()and then:- replace
MbyMoveBinaryDFS - replace
PbyPropagateBasic - call
ILearnFactory.setNoLearning() - clear
searchMonitors, that forget any declared one - call
Model.removeMinisat() - call
Model.removeNogoodStore()
- See Also:
reset()
- replace
-
propagate
public void propagate() throws ContradictionExceptionPropagates constraints and related events through the constraint network until a fix point is find, or a contradiction is detected.- Throws:
ContradictionException- inconsistency is detected, the problem has no solution with the current set of domains and constraints.
-
restart
public void restart()
Sets the following action in the search to be a restart instruction. Note that the restart may not be immediate
-
getModel
public Model getModel()
- Returns:
- the model of this resolver
-
getLearner
public Learn getLearner()
- Returns:
- the current learn.
-
getMove
public Move getMove()
- Returns:
- the current move.
-
getPropagate
public Propagate getPropagate()
- Returns:
- the current propagate.
-
getEnvironment
public IEnvironment getEnvironment()
- Returns:
- the backtracking environment used for this solver
-
getDecisionPath
public DecisionPath getDecisionPath()
- Returns:
- the current decision path
-
getSearch
public <V extends Variable> AbstractStrategy<V> getSearch()
- Type Parameters:
V- kind of variables the search strategy deals with- Returns:
- the current search strategy in use
-
getObjectiveManager
public <V extends Variable> IObjectiveManager<V> getObjectiveManager()
- Type Parameters:
V- type of the objective variable- Returns:
- the currently used objective manager
-
isDefaultSearchUsed
public boolean isDefaultSearchUsed()
Indicates if the default search strategy is used- Returns:
- false if a specific search strategy is used
-
isSearchCompleted
public boolean isSearchCompleted()
Indicates if the search strategy is completed with one over all variables- Returns:
- false if no strategy over all variables complete the declared one
-
hasEndedUnexpectedly
public boolean hasEndedUnexpectedly()
- Returns:
- true if the search loops ends unexpectedly (externally killed, for instance).
-
isStopCriterionMet
public boolean isStopCriterionMet()
- Returns:
- true if the search loops encountered at least one of the stop criteria declared.
-
getSearchWorldIndex
public int getSearchWorldIndex()
- Returns:
- the index of the world where the search starts, after initialization.
-
getMeasures
public MeasuresRecorder getMeasures()
Returns a reference to the measures recorder. This enables to get, for instance, the number of solutions found, time count, etc.- Returns:
- this model's measure recorder
-
getExplainer
public IExplanationEngine getExplainer()
Return the explanation engine plugged intothis.- Returns:
- this model's explanation engine
-
getEngine
public PropagationEngine getEngine()
- Returns:
- the propagation engine used in
this.
-
isFeasible
public ESat isFeasible()
Returns information on the feasibility of the current problem defined by the solver.Possible back values are:
-ESat.TRUE: a solution has been found,
-ESat.FALSE: the CSP has been proven to have no solution,
-ESat.UNDEFINED: no solution has been found so far (within given limits) without proving the unfeasibility, though.- Returns:
- an
ESat.
-
isSatisfied
public ESat isSatisfied()
Return the current state of the CSP.Given the current domains, it can return a value among:
-ESat.TRUE: all constraints of the CSP are satisfied for sure,
-ESat.FALSE: at least one constraint of the CSP is not satisfied.
-ESat.UNDEFINED: neither satisfiability nor unsatisfiability could be proven so far.Presumably, not all variables are instantiated.
- Returns:
- ESat.TRUE if all constraints of the problem are satisfied, ESat.FLASE if at least one constraint is not satisfied, ESat.UNDEFINED neither satisfiability nor unsatisfiability could be proven so far.
-
getJumpTo
public int getJumpTo()
- Returns:
- how many worlds should be rolled back when backtracking (usually 1)
-
setLearner
public void setLearner(Learn l)
Replaces the current learn withl- Parameters:
l- the new learn to apply
-
setMove
public void setMove(Move... m)
Replaces the current move withm- Parameters:
m- the new move to apply
-
setPropagate
public void setPropagate(Propagate p)
Overrides the Propagate object- Parameters:
p- the new Propagate to use
-
setObjectiveManager
public void setObjectiveManager(IObjectiveManager om)
Declares an objective manager to use.- Parameters:
om- the objective manager to use instead of the declared one (if any).
-
setSearch
public void setSearch(AbstractStrategy... strategies)
Override the default search strategies to use inthis. In case many strategies are given, they will be called in sequence: The first strategy in parameter is first called to compute a decision, if possible. If it cannot provide a new decision, the second strategy is called ... and so on, until the last strategy.- Parameters:
strategies- the search strategies to use.
-
setExplainer
public void setExplainer(IExplanationEngine explainer)
Overrides the explanation engine.- Parameters:
explainer- the explanation to use
-
setEngine
public void setEngine(PropagationEngine propagationEngine)
Attaches a propagation enginethis. It overrides the previously defined one, only if no propagation was done yet. Indeed, some incremental propagators may have set up their internal structure, which cannot be set up twice safely. If propagation was done callingsolve(), callingreset()enables to set the propagation engine anew. If propagation was done "manually" (callingpropagate(), then nothing can be done.- Parameters:
propagationEngine- a propagation strategy- Throws:
SolverException- is already initialized.
-
makeCompleteStrategy
public void makeCompleteStrategy(boolean isComplete)
Completes (or not) the declared search strategy with one over all variables- Parameters:
isComplete- set to true to complete the current search strategy
-
addStopCriterion
public void addStopCriterion(Criterion... criterion)
Adds a stop criterion, which, when met, stops the search loop. There can be multiple stop criteria, a logical OR is then applied. The stop criteria are declared to the search loop just before launching the search, the previously defined ones are erased. There is no check if there are any duplicates.
Examples:
With a built-in counter, stop after 20 seconds:SMF.limitTime(solver, "20s");With lambda, stop when 10 nodes are visited:() -> solver.getNodeCount() >= 10- Parameters:
criterion- one or many stop criterion to add.- See Also:
removeStopCriterion(Criterion...),removeAllStopCriteria()
-
removeStopCriterion
public void removeStopCriterion(Criterion... criterion)
Removes one or many stop criterion from the one to declare to the search loop.- Parameters:
criterion- criterion to remove
-
removeAllStopCriteria
public void removeAllStopCriteria()
Empties the list of stop criteria declared. This is not automatically called onreset().
-
getSearchMonitors
public SearchMonitorList getSearchMonitors()
- Returns:
- the list of search monitors plugged in this resolver
-
plugMonitor
public void plugMonitor(ISearchMonitor sm)
Put a search monitor to react on search events (solutions, decisions, fails, ...). Any search monitor is actually plugged just before the search starts. There is no check if there are any duplicates. A search monitor added during while the resolution has started will not be taken into account.- Parameters:
sm- a search monitor to be plugged in the solver
-
unplugMonitor
public void unplugMonitor(ISearchMonitor sm)
Removes a search monitors from the ones to plug when the search will start.- Parameters:
sm- a search monitor to be unplugged in the solver
-
unplugAllSearchMonitors
public void unplugAllSearchMonitors()
Empties the list of search monitors.
-
setJumpTo
public void setJumpTo(int jto)
Sets how many worlds to rollback when backtracking- Parameters:
jto- how many worlds to rollback when backtracking
-
getModelName
public String getModelName()
- Specified by:
getModelNamein interfaceIMeasures- Returns:
- name of the model/solver observed
-
getTimestamp
public long getTimestamp()
- Specified by:
getTimestampin interfaceIMeasures- Returns:
- the current world unique id
-
getTimeCount
public float getTimeCount()
- Specified by:
getTimeCountin interfaceIMeasures- Returns:
- the time count (in seconds), including initial propagation time count
-
getTimeCountInNanoSeconds
public long getTimeCountInNanoSeconds()
- Specified by:
getTimeCountInNanoSecondsin interfaceIMeasures- Returns:
- the time count (in nano seconds), including initial propagation time count
-
getReadingTimeCountInNanoSeconds
public long getReadingTimeCountInNanoSeconds()
- Specified by:
getReadingTimeCountInNanoSecondsin interfaceIMeasures- Returns:
- the reading time count (in nano seconds).
-
getReadingTimeCount
public float getReadingTimeCount()
- Specified by:
getReadingTimeCountin interfaceIMeasures- Returns:
- the reading time count (in sec)
-
getNodeCount
public long getNodeCount()
- Specified by:
getNodeCountin interfaceIMeasures- Returns:
- the node count
-
getBackTrackCount
public long getBackTrackCount()
- Specified by:
getBackTrackCountin interfaceIMeasures- Returns:
- the backtrack count
-
getFailCount
public long getFailCount()
- Specified by:
getFailCountin interfaceIMeasures- Returns:
- the fail count
-
getRestartCount
public long getRestartCount()
- Specified by:
getRestartCountin interfaceIMeasures- Returns:
- the restart count
-
getSolutionCount
public long getSolutionCount()
- Specified by:
getSolutionCountin interfaceIMeasures- Returns:
- the solution count of the measure
-
getDecisionCount
public long getDecisionCount()
- Specified by:
getDecisionCountin interfaceIMeasures- Returns:
- the decision count
-
getMaxDepth
public long getMaxDepth()
- Specified by:
getMaxDepthin interfaceIMeasures- Returns:
- the maximum depth of the search tree
-
getCurrentDepth
public long getCurrentDepth()
- Specified by:
getCurrentDepthin interfaceIMeasures- Returns:
- the current depth in the search tree
-
hasObjective
public boolean hasObjective()
- Specified by:
hasObjectivein interfaceIMeasures- Returns:
- true iff the problem has an objective variable (i.e. optimization problem)
-
isObjectiveOptimal
public boolean isObjectiveOptimal()
- Specified by:
isObjectiveOptimalin interfaceIMeasures- Returns:
- true iff the optimum has been found and proved
-
getBestSolutionValue
public Number getBestSolutionValue()
- Specified by:
getBestSolutionValuein interfaceIMeasures- Returns:
- the objective value of the best solution found (can be Integer or Double)
-
getSearchState
public SearchState getSearchState()
- Specified by:
getSearchStatein interfaceIMeasures- Returns:
- the search state
-
getBoundsManager
public IBoundsManager getBoundsManager()
- Specified by:
getBoundsManagerin interfaceIMeasures- Returns:
- the currently used objective manager
-
setOut
public void setOut(PrintStream printStream)
Description copied from interface:IOutputFactorySet the current output stream (default is System.out)- Specified by:
setOutin interfaceIOutputFactory- Parameters:
printStream- a print stream
-
getOut
public PrintStream getOut()
- Specified by:
getOutin interfaceIOutputFactory- Returns:
- the current output stream (default is System.out)
-
setErr
public void setErr(PrintStream printStream)
Description copied from interface:IOutputFactorySet the current error stream (default is System.err)- Specified by:
setErrin interfaceIOutputFactory- Parameters:
printStream- a print stream
-
getErr
public PrintStream getErr()
- Specified by:
getErrin interfaceIOutputFactory- Returns:
- the current error stream (default is System.err)
-
-