Package org.jacop.constraints.cumulative

Class Cumulative

java.lang.Object

org.jacop.constraints.DecomposedConstraint<Constraint>

org.jacop.constraints.Constraint

org.jacop.constraints.cumulative.CumulativeBasic

org.jacop.constraints.cumulative.Cumulative

Direct Known Subclasses:

CumulativeUnary

public class Cumulative
extends CumulativeBasic

Cumulative implements the scheduling constraint using

edge-finding (edgeFind) algorithms based on

Petr Vilim, "Edge Finding Filtering Algorithm for Discrete Cumulative Resources in O(kn log n)", Principles and Practice of Constraint Programming - CP 2009 Volume 5732 of the series Lecture Notes in Computer Science pp 802-816.

and

Joseph Scott, "Filtering Algorithms for Discrete Cumulative Resources", MSc thesis, Uppsala University, Department of Information Technology, 2010, no IT 10 048,

edge-finding algorithm with quadratic complexity (edgeFindQuad) is based on

Roger Kameugne, Laure Pauline Fotso, Joseph Scott, and Youcheu Ngo-Kateu, "A quadratic edge-finding filtering algorithm for cumulative resource constraints", Constraints, 2014, July, vol. 19, no. 3, pp. 243--269.

Version:

4.8

See Also:

http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-132172

Field Summary

Fields

Modifier and Type	Field	Description
private boolean	doEdgeFind
private boolean	doQuadraticEdgeFind
private java.util.Set<java.lang.Integer>	preComputedCapacities
private int[]	preComputedCapMap
protected java.util.Comparator<TaskView>	taskDecLctComparator
protected java.util.Comparator<TaskView>	taskIncEstComparator
(package private) TaskView[]	taskReversed

Fields inherited from class org.jacop.constraints.cumulative.CumulativeBasic

cumulativeForConstants, limit, possibleZeroTasks, taskNormal

Fields inherited from class org.jacop.constraints.Constraint

atomicExecution, consistencyPruningEvents, constraintScope, earlyTerminationOK, increaseWeight, numberId, scope, trace

Fields inherited from class org.jacop.constraints.DecomposedConstraint

queueIndex

Constructor Summary

Constructors

Constructor	Description
Cumulative(java.util.List<? extends IntVar> starts, java.util.List<? extends IntVar> durations, java.util.List<? extends IntVar> resources, IntVar limit)	It creates a cumulative constraint.
Cumulative(IntVar[] starts, IntVar[] durations, IntVar[] resources, IntVar limit)	It creates a cumulative constraint.

Method Summary

Modifier and Type	Method	Description
private void	adjustBounds(Store store, ThetaLambdaTree tree, TaskView[] t, int[] prec, long cap)
void	consistency(Store store)	It is a (most probably incomplete) consistency function which removes the values from variables domains.
private int[]	detectOrder(ThetaLambdaTree tree, TaskView[] t, int[] lctInvOrder, long C)
private long	divRoundUp(long a, long b)
void	doQuadraticEdgeFind(boolean doQEF)
private void	edgeFind(Store store)
private void	edgeFind(Store store, TaskView[] tn)
private void	edgeFindQuad(Store store)
private void	edgeFindQuad(Store store, TaskView[] tn)
(package private) TaskView[]	filterZeroTasks(TaskView[] ts)
int	getDefaultConsistencyPruningEvent()
java.lang.String	toString()	It produces a string representation of a constraint state.

Methods inherited from class org.jacop.constraints.cumulative.CumulativeBasic

profileProp

Methods inherited from class org.jacop.constraints.Constraint

afc, arguments, cleanAfterFailure, decompose, getConsistencyPruningEvent, getGuideConstraint, getGuideValue, getGuideVariable, grounded, grounded, id, impose, impose, imposeDecomposition, increaseWeight, intArrayToString, numberArgs, queueVariable, removeConstraint, requiresMonotonicity, setConsistencyPruningEvent, setConstraintScope, setScope, setScope, setScope, setScope, setScope, setWatchedVariableGrounded, supplyGuideFeedback, updateAFC, watchedVariableGrounded

Methods inherited from class org.jacop.constraints.DecomposedConstraint

auxiliaryVariables, checkInput, checkInput, checkInputForDuplication, checkInputForDuplicationSkipSingletons, checkInputForNullness, checkInputForNullness, checkInputForNullness, derivative, getDubletonsSkipSingletons, imposeDecomposition

Methods inherited from class java.lang.Object

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

Field Detail

taskReversed

TaskView[] taskReversed

doEdgeFind

private boolean doEdgeFind

doQuadraticEdgeFind

private boolean doQuadraticEdgeFind

preComputedCapacities

private java.util.Set<java.lang.Integer> preComputedCapacities

preComputedCapMap

private int[] preComputedCapMap

taskIncEstComparator

protected java.util.Comparator<TaskView> taskIncEstComparator

taskDecLctComparator

protected java.util.Comparator<TaskView> taskDecLctComparator

Constructor Detail

Cumulative

public Cumulative(IntVar[] starts,
                  IntVar[] durations,
                  IntVar[] resources,
                  IntVar limit)

It creates a cumulative constraint.

Parameters:

starts - variables denoting starts of the tasks.

durations - variables denoting durations of the tasks.

resources - variables denoting resource usage of the tasks.

limit - the overall limit of resources which has to be used.

Cumulative

public Cumulative(java.util.List<? extends IntVar> starts,
                  java.util.List<? extends IntVar> durations,
                  java.util.List<? extends IntVar> resources,
                  IntVar limit)

It creates a cumulative constraint.

Parameters:

starts - variables denoting starts of the tasks.

durations - variables denoting durations of the tasks.

resources - variables denoting resource usage of the tasks.

limit - the overall limit of resources which has to be used.

Method Detail

doQuadraticEdgeFind

public void doQuadraticEdgeFind(boolean doQEF)

consistency

public void consistency(Store store)

Description copied from class: Constraint

It is a (most probably incomplete) consistency function which removes the values from variables domains. Only values which do not have any support in a solution space are removed.

Overrides:

consistency in class CumulativeBasic

Parameters:

store - constraint store within which the constraint consistency is being checked.

edgeFind

private void edgeFind(Store store)

edgeFind

private void edgeFind(Store store,
                      TaskView[] tn)

detectOrder

private int[] detectOrder(ThetaLambdaTree tree,
                          TaskView[] t,
                          int[] lctInvOrder,
                          long C)

adjustBounds

private void adjustBounds(Store store,
                          ThetaLambdaTree tree,
                          TaskView[] t,
                          int[] prec,
                          long cap)

edgeFindQuad

private void edgeFindQuad(Store store)

edgeFindQuad

private void edgeFindQuad(Store store,
                          TaskView[] tn)

filterZeroTasks

TaskView[] filterZeroTasks(TaskView[] ts)

getDefaultConsistencyPruningEvent

public int getDefaultConsistencyPruningEvent()

Overrides:

getDefaultConsistencyPruningEvent in class CumulativeBasic

toString

public java.lang.String toString()

Description copied from class: Constraint

It produces a string representation of a constraint state.

Overrides:

toString in class CumulativeBasic

divRoundUp

private long divRoundUp(long a,
                        long b)