pack

Syntax

constraint pack(intExprArray load, intExprArray where, intArray size, intExpr used = null)

Parameters

• load: An array of integer expressions, each element representing the load (total size of the objects inside) the corresponding container.
• where: An array of integer expressions, each element representing in which container the corresponding object is placed.
• size: An array of integers, each element representing the size of the corresponding object.
• used: (optional) An integer expression indicating the number of used containers. That is, the number of containers with at least one object inside.

Description

The pack constraint is used to represent sub-problems where the requirement is to assign objects to containers such that the capacities or minimum fill levels of the containers are respected. Let's assume we have n objects and m containers. The sizes of the array arguments of pack must correspond to these constants. That is, load must be of size m, whereas where and size must be of size n. Given assignments to the where expressions, the pack constraint will calculate the values of the load and used expressions.

All counting is done from 0, and so the interpretation of 5 being assigned to where[3] is that object 3 (the 4th object) is placed into container 5 (the 6th container). This will be reflected by the inclusion of the size of object 3 (size[3]) being included in the calculation of the value of load[5].

Naturally, all the arguments (with the exception of size) can be constrained by additional constraints. The most common form is to limit the capacity of a container. For example, to limit container 2 to a capacity of 15, one would write load[2] <= 15. Minimum fill level requirements can also be specified this way: for example load[2] >= 12. Other more esoteric constraints are possible, for example to say that only an even number of containers can be used: (used % 2) == 0. If used is omitted from the signature, then it will not be possible to specifically constrain the number of containers used.

Example

A decomposition of the pack constraint with n=3 and m=2 could be written as follows. Please note that this form will result in less inference being made by CP Optimizer during search than using pack:

// Must use at least one container and can't use more than exists
used >= 1;
used <= 2;

// Loads are non-negative and limited to total object size
load[0] >= 0;
load[0] <= sum(size);
load[1] >= 0;
load[1] <= sum(size);

// Objects must be placed in one of the containers
where[0] >= 0;
where[0] <= 1;
where[1] >= 0;
where[1] <= 1;
where[2] >= 0;
where[2] <= 1;

// Load maintenance
load[0] == scalProd(size, [where[0] == 0, where[1] == 0, where[2] == 0]);
load[1] == scalProd(size, [where[0] == 1, where[1] == 1, where[2] == 1]);

// Used
used == (count(where, 0) != 0) + (count(where, 1) != 0);

Requirements

• The where and size arrays must be the same size.
• Elements of the size array must be non-negative, but may be zero. Placing a zero-sized object in a container still counts as using the container. That is, a container can be considered used even if its load is zero.
• The sum of the elements of the size array must be no larger than intmax.