choco.palm
Class BendersProblem

java.lang.Object
  choco.AbstractModel
      choco.AbstractProblem
          choco.palm.JumpProblem
              choco.palm.BendersProblem

All Implemented Interfaces:

BoolModeler, IntModeler, ExplainedProblem

public class BendersProblem
extends JumpProblem

Choco problem extension involving explanations and a Benders decomposition algorithm based on the use of explanations. The decomposition is made among the variables and the choco model need only to be enrich by indicating for each variable the problem to which it belongs. Warning : subproblems must be independent once the master is instantiated. If it is not the case, it has to be precised with the use of setApproximatedStructure().

Field Summary

protected boolean	approximatedStructure Boolean indicating whether the subproblems are completely independant once master variables instantiated.
protected java.util.ArrayList	masterVariables List of the Master variables.
protected int	nbSubProblems The number of sub problems considered at each iteration
protected java.util.ArrayList	subvariables for each subproblems, a table of variables corresponding to the subproblem n°i is stored in subvariables.get(i)

Fields inherited from class choco.palm.JumpProblem

contradictionExplanation, displayRelease, erasedCst, indexOfLastInitializedStaticConstraint, logger, maxRelaxLevel

Fields inherited from class choco.AbstractProblem

environment, feasible, precision, propagationEngine, reduction, solved, solver

Fields inherited from class choco.AbstractModel

constraints, doMaximize, FALSE, floatVars, intVars, nbConstraint, objective, setVars, TRUE

Constructor Summary

BendersProblem()
build a problem that will use the decomposition algorithm

Method Summary

void	addMasterVariables(IntDomainVar v) Add a variable to the master set.
void	addSubVariables(int i, IntDomainVar v) Add a variable to a given sub-problem.
IntDomainVar[]	getMasterVariables()
java.util.ArrayList	getMasterVariablesList()
int	getNbCutsLearned()
int	getNbSubProblems()
IntDomainVar[]	getSubvariables(int i)
java.util.ArrayList	getSubvariablesList(int i)
boolean	isApproximatedStructure()
Explanation	makeExplanation() factory to build explanation within the Benders Framework
Explanation	makeExplanation(int level) factory to build an explanation at a given level within the Benders Framework
void	maximize(IntDomainVar obj) minimize an objective function only including variables of the master.
void	maximize(IntDomainVar mobj, IntDomainVar[] objs, MasterSlavesRelation relation) maximize an objective function over both the master and sub-problems.
void	minimize(IntDomainVar obj) minimize an objective function only including variables of the master.
void	minimize(IntDomainVar mobj, IntDomainVar[] objs, MasterSlavesRelation relation) minimize an objective function over both the master and sub-problems.
protected java.lang.Boolean	optimize(boolean maximize, IntDomainVar mobj, IntDomainVar[] objs, MasterSlavesRelation relation)
protected java.lang.Boolean	optimize(boolean maximize, IntDomainVar obj, MasterSlavesRelation relation)
void	setApproximatedStructure() precise that the structures used as subproblems is not ideal but has week relationships WARNING : it can only be used in case of satisfaction problem.

Methods inherited from class choco.palm.JumpProblem

boolChanneling, createAC2001BinConstraint, createAC3BinConstraint, createAC4BinConstraint, createAllDifferent, createBinConjunction, createBinDisjunction, createBoolChanneling, createBoundAllDiff, createCardinality, createCspLargeConstraint, createCumulative, createDisjoint, createEqualXC, createEqualXYC, createEquation, createEquiv, createGlobalCardinality, createGreaterOrEqualXC, createGreaterOrEqualXYC, createGuard, createIntLinComb, createIntVar, createIntVar, createInverseChanneling, createLargeConjunction, createLargeDisjunction, createLessOrEqualXC, createLex, createMemberX, createMemberXY, createNotEqualXC, createNotEqualXYC, createNotMemberX, createNotMemberXY, createOccurrence, createRealCos, createRealIntegerPower, createRealIntervalConstant, createRealMinus, createRealMult, createRealPlus, createRealSin, createRealVal, createSetCard, createSetIntersection, createSetVar, createSubscript, createSubscript, createTimesXYZ, explainedFail, getConstraintNb, getContradictionExplanation, getVars, inverseChanneling, makeConstraintPlugin, post, postCut, ReleaseJumpDisplay, setContradictionExplanation, solve, worldPop

Methods inherited from class choco.AbstractProblem

constraintsToString, eraseConstraint, getEnvironment, getIntConstraint, getIntConstraintIterator, getIntVarIndex, getNbIntConstraints, getPrecision, getProblem, getPropagationEngine, getReduction, getSolver, getWorldIndex, isConsistent, isFeasible, maximize, minimize, nextSolution, optimize, pretty, printRuntimeSatistics, propagate, setPrecision, setReduction, solutionToString, solve, solveAll, varsToString, worldPopUntil, worldPush

Methods inherited from class choco.AbstractModel

allDifferent, allDifferent, and, and, and, and, around, atleast, atmost, card, cos, countNonNullCoeffs, cst, cst, cumulative, eq, eq, eq, eq, eq, eq, eqCard, eqCard, feasPairAC, feasPairAC, feasPairAC, feasPairAC, feasTuple, geq, geq, geq, geq, geq, geq, geqCard, geqCard, getIntVar, getIntVarIndex, getNbIntVars, getNbRealVars, getNbSetVars, getRealVar, getSetVar, globalCardinality, globalCardinality, gt, gt, gt, ifOnlyIf, ifThen, implies, infeasPairAC, infeasPairAC, infeasPairAC, infeasPairAC, infeasTuple, leq, leq, leq, leq, leq, leq, leqCard, leqCard, lex, lexeq, lt, lt, lt, makeBoundIntVar, makeBoundIntVar, makeBoundIntVarArray, makeBoundIntVarArray, makeConjunction, makeConstantIntVar, makeConstantIntVar, makeDisjunction, makeEnumIntVar, makeEnumIntVar, makeEnumIntVarArray, makeEnumIntVarArray, makeEquation, makeIntLinComb, makeOccurrence, makePairAC, makePairAC, makeRealVar, makeRealVar, makeRealVar, makeSetVar, makeTupleFC, member, member, member, member, minus, minus, minus, minus, mult, mult, neq, neq, neq, not, notMember, notMember, notMember, notMember, nth, nth, occurenceMax, occurenceMin, occurrence, or, or, or, or, plus, plus, plus, plus, plus, power, relationPairAC, relationPairAC, relationTuple, scalar, scalar, setDisjoint, setInter, setMaximizationObjective, setMinimizationObjective, sin, sum, times

Methods inherited from class java.lang.Object

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

Field Detail

nbSubProblems

protected int nbSubProblems

The number of sub problems considered at each iteration

masterVariables

protected java.util.ArrayList masterVariables

List of the Master variables.

subvariables

protected java.util.ArrayList subvariables

for each subproblems, a table of variables corresponding to the subproblem n°i is stored in subvariables.get(i)

approximatedStructure

protected boolean approximatedStructure

Boolean indicating whether the subproblems are completely independant once master variables instantiated.

Constructor Detail

BendersProblem

public BendersProblem()

build a problem that will use the decomposition algorithm

Method Detail

addMasterVariables

public void addMasterVariables(IntDomainVar v)

Add a variable to the master set.

Parameters:

v - the variable to be added to the master

addSubVariables

public void addSubVariables(int i,
                            IntDomainVar v)

Add a variable to a given sub-problem.

Parameters:

i - the number of considered sub-problem

v - the variable to be added

makeExplanation

public Explanation makeExplanation()

factory to build explanation within the Benders Framework

Specified by:

makeExplanation in interface ExplainedProblem

Overrides:

makeExplanation in class JumpProblem

Returns:

makeExplanation

public Explanation makeExplanation(int level)

factory to build an explanation at a given level within the Benders Framework

Overrides:

makeExplanation in class JumpProblem

Returns:

isApproximatedStructure

public boolean isApproximatedStructure()

setApproximatedStructure

public void setApproximatedStructure()

precise that the structures used as subproblems is not ideal but has week relationships WARNING : it can only be used in case of satisfaction problem.

getNbSubProblems

public int getNbSubProblems()

Returns:

the number of subproblems considered by the algorithm

getNbCutsLearned

public int getNbCutsLearned()

Returns:

the number of cuts learned during the search

getMasterVariables

public IntDomainVar[] getMasterVariables()

Returns:

the array of master variables

getMasterVariablesList

public java.util.ArrayList getMasterVariablesList()

Returns:

the list of master variables

getSubvariablesList

public java.util.ArrayList getSubvariablesList(int i)

Returns:

the list of variable of the subproblem number i

getSubvariables

public IntDomainVar[] getSubvariables(int i)

Returns:

the array of variable of the subproblem number i

minimize

public void minimize(IntDomainVar mobj,
                     IntDomainVar[] objs,
                     MasterSlavesRelation relation)

minimize an objective function over both the master and sub-problems.

Parameters:

mobj - objective variable of the master

objs - objectives variables of each subproblem

relation - a relation representing the objective function

minimize

public void minimize(IntDomainVar obj)

minimize an objective function only including variables of the master.

Parameters:

obj - objective variable of the master

maximize

public void maximize(IntDomainVar mobj,
                     IntDomainVar[] objs,
                     MasterSlavesRelation relation)

maximize an objective function over both the master and sub-problems.

Parameters:

mobj - objective variable of the master

objs - objectives variables of each subproblem

relation - a relation representing the objective function

maximize

public void maximize(IntDomainVar obj)

minimize an objective function only including variables of the master.

Parameters:

obj - objective variable of the master

optimize

protected java.lang.Boolean optimize(boolean maximize,
                                     IntDomainVar obj,
                                     MasterSlavesRelation relation)

optimize

protected java.lang.Boolean optimize(boolean maximize,
                                     IntDomainVar mobj,
                                     IntDomainVar[] objs,
                                     MasterSlavesRelation relation)