Class PropagationGuidedNeighborhood
- java.lang.Object
-
- org.chocosolver.solver.search.loop.lns.neighbors.PropagationGuidedNeighborhood
-
- All Implemented Interfaces:
INeighbor
- Direct Known Subclasses:
ReversePropagationGuidedNeighborhood
public class PropagationGuidedNeighborhood extends Object implements INeighbor
A Propagation Guided LNSBased on "Propagation Guided Large Neighborhood Search", Perron et al. CP2004.
- Since:
- 08/04/13
- Author:
- Charles Prud'homme
-
-
Field Summary
Fields Modifier and Type Field Description protected int[]allStore the modified variablesprotected int[]bestSolutionLast solution found, wrtvarsprotected List<Integer>candidatesStore the variable elligible for propagationprotected int[]dsizeDomain size of each variable invarsprotected doubleepsilonRestriction parameterprotected intfgmtSizeIntial size of the fragmentprotected BitSetfragmentIndicate which variables are selected in a fragmentprotected intlistSizeNumber of variables modified through propagation to consider while computing the neighborprotected doublelogSumLogarithmic cardinality of domainsprotected ModelmModelReference to the modelprotected intnNumber of variablesprotected RandomrdFor randomnessprotected IntVar[]varsArray of variables to consider in a fragment
-
Constructor Summary
Constructors Constructor Description PropagationGuidedNeighborhood(IntVar[] vars, int fgmtSize, int listSize, long seed)Create a propagation-guided neighbor for LNS
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description voidfixSomeVariables(DecisionPath decisionPath)Freezes some variables in order to have a fast computation.protected voidimpose(int id, DecisionPath decisionPath)Impose a decision to be part of the fragmentvoidinit()Initialize this neighborbooleanisSearchComplete()voidloadFromSolution(Solution solution)Load a solution and record itvoidrecordSolution()Record values of decision variables to freeze some ones during the next LNS runvoidrestrictLess()Use less restriction at the beginning of a LNS run in order to get better solutions Called when no solution was found during a LNS run (trapped into a local optimum)protected intselectVariable()protected voidupdate(DecisionPath decisionPath)Create the fragment
-
-
-
Field Detail
-
n
protected final int n
Number of variables
-
vars
protected final IntVar[] vars
Array of variables to consider in a fragment
-
bestSolution
protected final int[] bestSolution
Last solution found, wrtvars
-
dsize
protected int[] dsize
Domain size of each variable invars
-
rd
protected Random rd
For randomness
-
fgmtSize
protected int fgmtSize
Intial size of the fragment
-
listSize
protected int listSize
Number of variables modified through propagation to consider while computing the neighbor
-
epsilon
protected double epsilon
Restriction parameter
-
logSum
protected double logSum
Logarithmic cardinality of domains
-
all
protected int[] all
Store the modified variables
-
fragment
protected BitSet fragment
Indicate which variables are selected in a fragment
-
mModel
protected Model mModel
Reference to the model
-
-
Constructor Detail
-
PropagationGuidedNeighborhood
public PropagationGuidedNeighborhood(IntVar[] vars, int fgmtSize, int listSize, long seed)
Create a propagation-guided neighbor for LNS- Parameters:
vars- set of variables to considerfgmtSize- initial size of the fragmentlistSize- number of modified variable to store while propagatingseed- for randomness
-
-
Method Detail
-
isSearchComplete
public boolean isSearchComplete()
- Specified by:
isSearchCompletein interfaceINeighbor- Returns:
- true iff the search is in a complete mode (no fixed variable)
-
recordSolution
public void recordSolution()
Description copied from interface:INeighborRecord values of decision variables to freeze some ones during the next LNS run- Specified by:
recordSolutionin interfaceINeighbor
-
loadFromSolution
public void loadFromSolution(Solution solution)
Description copied from interface:INeighborLoad a solution and record it- Specified by:
loadFromSolutionin interfaceINeighbor- Parameters:
solution- a solution to record
-
fixSomeVariables
public void fixSomeVariables(DecisionPath decisionPath)
Description copied from interface:INeighborFreezes some variables in order to have a fast computation. The fixed variables are declared as decisions in the decision path.- Specified by:
fixSomeVariablesin interfaceINeighbor- Parameters:
decisionPath- the decision path in which declaring variable to freeze
-
update
protected void update(DecisionPath decisionPath) throws ContradictionException
Create the fragment- Parameters:
decisionPath- the decision path to feed- Throws:
ContradictionException- if the fragment is trivially infeasible
-
impose
protected void impose(int id, DecisionPath decisionPath) throws ContradictionExceptionImpose a decision to be part of the fragment- Parameters:
id- variable id invarsdecisionPath- the current decision path- Throws:
ContradictionException- if the application of the decision fails
-
selectVariable
protected int selectVariable()
- Returns:
- a variable id in
varsto be part of the fragment
-
restrictLess
public void restrictLess()
Description copied from interface:INeighborUse less restriction at the beginning of a LNS run in order to get better solutions Called when no solution was found during a LNS run (trapped into a local optimum)- Specified by:
restrictLessin interfaceINeighbor
-
-