distribute
distribute |
Purpose
A distribute constraint also known as GCC (Global Cardinality Constraint) over a set of variables is defined by three arrays called values, lowerBound, and upperBound. The constraint is satisfied if, and only if, the number of variables of the given set, which are assigned to values[i], is greater than or equal to lowerBound[i], and less than or equal to upperBound[i] for all i, and if no variable of the given set is assigned to a value which does not belong to values. The constraint is equivalent, from a modelization point of view, to posting two instances of
occurrence constraints for each value. But this is absolutely not equivalent from a propagation point of view: distribute acquires a far better propagation, using the Regin algorithm.
Synopsis
function distribute(vars:array of cpvar, values:set of integer, bound:array(integer) of integer) : cpctr
function distribute(vars:array of cpvar, values:set of integer, lowerBound:array(integer) of integer, upperBound:array(integer) of integer) : cpctr
function distribute(vars:set of cpvar,vals:set of integer, lowerBound:array(integer) of integer, upperBound:array(integer) of integer) : cpctr
function distribute(vars:cpvarlist, vals:set of integer, lowerBound:array(integer) of integer, upperBound:array(integer) of integer) : cpctr
Arguments
|
vars
|
Array/set/list of variables
|
|
values
|
Set of values represented by their names
|
|
lowerBound
|
Array of lower bounds on occurrences
|
|
upperBound
|
Array of upper bounds on occurrences
|
|
bound
|
Array of occurrence values
|
Return value
A distribute constraint
Example
A simple planning problem for personnel in a theater. Suppose that a movie theatre director has to decide in which location each of his employees should be posted. There are eight employees: Andrew, David, Jane, Jason, Leslie, Michael, Marilyn and Oliver. There are four locations: the ticket office, the first entrance, the second entrance and the coat check. These locations require three, two, two, and one person respectively. This constraint will be modeled by one distribute constraint:
model "Distribute example"
uses "kalis"
declarations
PERS = {"David","Andrew","Leslie","Jason","Oliver","Michael",
"Jane","Marilyn"} ! Set of personnel
LOC = 1..4 ! Set of locations
REQ: array(LOC) of integer ! No. of pers. req. per loc.
place: array(PERS) of cpvar ! Workplace for each peson
end-declarations
! Initialize data
REQ:: [3, 2, 2, 1]
! Each variable has a lower bound of 1 (Ticket office) and
! an upper bound of 4 (Cloakroom)
forall(p in PERS) do
setname(place(p), "workplace("+p+")")
1 <= place(p); place(p) <= 4
end-do
! Creation of a resource constraint of for every location
forall(d in LOC) occurrence(d, place) = REQ(d)
! Elegant way to declare theses constraints,
! moreover achieving stronger prunning (using global
! cardinality constraint)
distribute(place, LOC, REQ)
! Solve the problem
if not(cp_find_next_sol) then
writeln("Problem is infeasible")
exit(1)
end-if
! Solution printout
writeln(place)
end-model
Related topics