Initializing help system before first use

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
occurrence all_different

Parent Topic Constraints

© 2001-2024 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.