choco.palm.benders.search
Class MasterGlobalSearchSolver

java.lang.Object
  choco.AbstractEntity
      choco.AbstractSolver
          choco.search.AbstractGlobalSearchSolver
              choco.search.Solve
                  choco.palm.cbj.search.JumpGlobalSearchSolver
                      choco.palm.benders.search.MasterGlobalSearchSolver

All Implemented Interfaces:

Entity

Direct Known Subclasses:

ApproximateMaster, MasterOptimizer

public class MasterGlobalSearchSolver
extends JumpGlobalSearchSolver

Default implementation of Benders search (used for P_{0}) basis for {P'_{0},P_{y}, and P_{xy}

Field Summary

protected Explanation[]	bendersCut store bendersCuts extracted on each subproblem
protected NogoodConstraint	cuts The nogood constraint gathering all benders cuts
protected MasterSlavesRelation	decomposition Objective function formulated as a specific relation
protected Explanation	fail
protected boolean	feasible feasability of the whole problem
protected static java.util.logging.Logger	logger
protected SubSearchSolver	master A search solver corresponding to the master
protected int	masterWorld
protected int	nbCutLearned number of cuts extracted at the current iteration
protected int	nbFeasibleProblems number of feasible sub-problems found at the current iteration
protected java.util.ArrayList	partialSol Store the solutions found on sub-problems.
protected boolean	stop
protected AbstractIntBranching[]	subgoals the goal corresponding to the variables of each subproblems
protected SubSearchSolver	subproblems A search solver used for the subproblems

Fields inherited from class choco.palm.cbj.search.JumpGlobalSearchSolver

currentFail

Fields inherited from class choco.search.AbstractGlobalSearchSolver

baseWorld, currentTraceIndex, DOWN_BRANCH, encounteredLimit, INIT_SEARCH, limits, loggingMaxDepth, mainGoal, nbSolutions, nextMove, OPEN_NODE, stopAtFirstSol, traceStack, UP_BRANCH

Fields inherited from class choco.AbstractSolver

maxNbSolutionStored, solutions

Fields inherited from class choco.AbstractEntity

hook, problem

Constructor Summary

MasterGlobalSearchSolver(AbstractProblem pb, int nbsub)

MasterGlobalSearchSolver(AbstractProblem pb, int nbsub, MasterSlavesRelation relation)

Method Summary

void	addCuts(java.util.ArrayList currentCuts)
void	cleanPartialSolutions()
SubSearchSolver	getMaster()
int	getNbCuts() getter on the number of cuts stored (without inclusion)
int	getOptimumValue() return -1 as it is a satisfaction problem
SubSearchSolver	getSubproblems()
void	incrementalRun() main entry point: searching for one solution Note: the initial propagation must be done before pushing any world level.
void	logCuts(java.util.ArrayList li)
void	logSolution()
void	manageCuts() compute the global cut using the MasterSlavesRelation and add the cut the nogood constraint managing BendersCut
void	nextMasterMove() Describes the way the master search solver has to be set to look for the next solution.
java.lang.Boolean	nextSolution() Browses the search tree until the next solution or until all the tree has been checked.
void	restorePartialSolutions()
void	setCutsConstraint(NogoodConstraint cuts) set the way BendersCut are managed
void	setMainGoal(AbstractIntBranching branch) set the branching of the master solver
void	setSubGoal(int i, AbstractIntBranching branch) set the branching of subproblem number i
void	solutionFound()
void	solveSubProblems() Main iteration over the subproblems
void	storeCuts(Explanation expl, int i)
void	storePartialSolution(int subpb)
void	updateLimit() set the limit objects to both master and slaves.

Methods inherited from class choco.search.AbstractGlobalSearchSolver

endTreeNode, endTreeSearch, getEncounteredLimit, isEncounteredLimit, newTreeNode, newTreeSearch, popTrace, popTraceUntil, postDynamicCut, printRuntimeStatistics, pushTrace, recordSolution, run, setLoggingMaxDepth, topTrace

Methods inherited from class choco.AbstractSolver

existsSolution, makeSolutionFromCurrentState, restoreBestSolution, showSolution, storeSolution

Methods inherited from class choco.AbstractEntity

getProblem, pretty

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

logger

protected static java.util.logging.Logger logger

cuts

protected NogoodConstraint cuts

The nogood constraint gathering all benders cuts

master

protected SubSearchSolver master

A search solver corresponding to the master

subproblems

protected SubSearchSolver subproblems

A search solver used for the subproblems

subgoals

protected AbstractIntBranching[] subgoals

the goal corresponding to the variables of each subproblems

bendersCut

protected Explanation[] bendersCut

store bendersCuts extracted on each subproblem

nbCutLearned

protected int nbCutLearned

number of cuts extracted at the current iteration

nbFeasibleProblems

protected int nbFeasibleProblems

number of feasible sub-problems found at the current iteration

partialSol

protected java.util.ArrayList partialSol

Store the solutions found on sub-problems. As only one global search solver is used, solutions of sub-problems need to be stored

feasible

protected boolean feasible

feasability of the whole problem

decomposition

protected MasterSlavesRelation decomposition

Objective function formulated as a specific relation

fail

protected Explanation fail

masterWorld

protected int masterWorld

stop

protected boolean stop

Constructor Detail

MasterGlobalSearchSolver

public MasterGlobalSearchSolver(AbstractProblem pb,
                                int nbsub,
                                MasterSlavesRelation relation)

MasterGlobalSearchSolver

public MasterGlobalSearchSolver(AbstractProblem pb,
                                int nbsub)

Method Detail

updateLimit

public void updateLimit()

set the limit objects to both master and slaves. They share the same limits.

getNbCuts

public int getNbCuts()

getter on the number of cuts stored (without inclusion)

Returns:

the number of cuts learned

getSubproblems

public SubSearchSolver getSubproblems()

Returns:

the global search solver associated to the subproblems

getMaster

public SubSearchSolver getMaster()

Returns:

the global search solver associated to the master

setMainGoal

public void setMainGoal(AbstractIntBranching branch)

set the branching of the master solver

setSubGoal

public void setSubGoal(int i,
                       AbstractIntBranching branch)

set the branching of subproblem number i

setCutsConstraint

public void setCutsConstraint(NogoodConstraint cuts)

set the way BendersCut are managed

getOptimumValue

public int getOptimumValue()

return -1 as it is a satisfaction problem

incrementalRun

public void incrementalRun()

Description copied from class: AbstractGlobalSearchSolver

main entry point: searching for one solution Note: the initial propagation must be done before pushing any world level. It is therefore kept before restoring a solution

Overrides:

incrementalRun in class AbstractGlobalSearchSolver

nextSolution

public java.lang.Boolean nextSolution()

Description copied from class: JumpGlobalSearchSolver

Browses the search tree until the next solution or until all the tree has been checked.

Overrides:

nextSolution in class JumpGlobalSearchSolver

Returns:

Boolean.TRUE if a solution has been found, Boolean.FALSE if no solution has been found and null if the search has been interrupted by a limit

solveSubProblems

public void solveSubProblems()

Main iteration over the subproblems

nextMasterMove

public void nextMasterMove()

Describes the way the master search solver has to be set to look for the next solution.

storeCuts

public void storeCuts(Explanation expl,
                      int i)

manageCuts

public void manageCuts()

compute the global cut using the MasterSlavesRelation and add the cut the nogood constraint managing BendersCut

addCuts

public void addCuts(java.util.ArrayList currentCuts)

solutionFound

public void solutionFound()

cleanPartialSolutions

public void cleanPartialSolutions()

storePartialSolution

public void storePartialSolution(int subpb)

restorePartialSolutions

public void restorePartialSolutions()

logSolution

public void logSolution()

logCuts

public void logCuts(java.util.ArrayList li)