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

Contents

Index

Glossary

Search Results

distribute