Scheduling & packing constraints

Constraints that place tasks in time or shapes in space without overlapping a limited resource.

Tasks are described by parallel arrays: start, duration and where relevant resource, all indexed alike, so task i occupies the half-open interval from start[i] to start[i] + duration[i].

Rectangle packing is int_no_overlap rather than diffn: the name says what the constraint enforces, and its arguments pair position with extent per dimension (x, dx, y, dy) rather than listing all positions and then all extents.

Beyond two dimensions there is nothing to pair, so int_no_overlap_nd takes a dimensions count and flattens position and size row-major, since a list cannot carry a shape. int_no_overlap_shape — geost in MiniZinc and the literature — generalises again: an object’s extent is a shape, a union of rectangles, and kind picks one per object.

14 constraints

int_bin_packing

int_bin_packing(list of var int: bin, list of int: weight, list of int: capacity, int: offset)

also declarable as int_bin_packing_reif and int_bin_packing_imp

Items are assigned to bins, each bin having its own capacity.

$$\left( \forall i : \mathit{offset} \leq \mathit{bin}_i \leq \mathit{offset} + \lvert \mathit{capacity} \rvert - 1 \right) \;\wedge\; \forall b : \sum_{i \,:\, \mathit{bin}_i = b} \mathit{weight}_i \;\leq\; \mathit{capacity}_{b - \mathit{offset} + 1}$$

bin and weight must have equal length, and weights must be non-negative. A single shared capacity is this constraint with a constant array.

int_bin_packing_load

int_bin_packing_load(list of var int: bin, list of int: weight, list of var int: load, int: offset)

Each bin’s load variable holds the total weight assigned to that bin.

$$\left( \forall i : \mathit{offset} \leq \mathit{bin}_i \leq \mathit{offset} + \lvert \mathit{load} \rvert - 1 \right) \;\wedge\; \forall b : \mathit{load}_{b - \mathit{offset} + 1} = \sum_{i \,:\, \mathit{bin}_i = b} \mathit{weight}_i$$

load is numbered from offset, the lowest bin number. Makes the loads available to the rest of the model, so they can be bounded or optimised.

int_cumulative

int_cumulative(list of var int: start, list of var int: duration, list of var int: resource, var int: capacity)

also declarable as int_cumulative_reif and int_cumulative_imp

At no point in time do the running tasks consume more than the available capacity.

$$\forall t : \sum_{i \,:\, \mathit{start}_i \leq t < \mathit{start}_i + \mathit{duration}_i} \mathit{resource}_i \;\leq\; \mathit{capacity}$$

start, duration and resource must have equal length. Durations and resource requirements must be non-negative.

int_cumulatives

int_cumulatives(list of var int: start, list of var int: duration, list of var int: resource, list of var int: machine, list of var int: capacity, int: capacity_offset, bool: is_upper_bound)

also declarable as int_cumulatives_reif and int_cumulatives_imp

As int_cumulative, but each task runs on one of several machines, each with its own capacity.

$$\forall m, t : \left( \exists i : \mathit{machine}_i = m \wedge \mathit{start}_i \leq t < \mathit{start}_i + \mathit{duration}_i \right) \rightarrow \sum_{i \,:\, \mathit{machine}_i = m \,\wedge\, \mathit{start}_i \leq t < \mathit{start}_i + \mathit{duration}_i} \mathit{resource}_i \;\leq\; \mathit{capacity}_{m - \mathit{capacity\_offset} + 1}$$

capacity is numbered from capacity_offset, the lowest machine number. With is_upper_bound false the capacities are lower bounds instead, and the inequality reverses. The bound binds only at times when some task occupies the machine, which is what makes the lower bound usable.

int_disjunctive

int_disjunctive(list of var int: start, list of var int: duration)

also declarable as int_disjunctive_reif and int_disjunctive_imp

No two tasks overlap in time.

$$\forall i < j : \mathit{start}_i + \mathit{duration}_i \leq \mathit{start}_j \;\vee\; \mathit{start}_j + \mathit{duration}_j \leq \mathit{start}_i$$

Zero-duration tasks may coincide with anything. Use int_disjunctive_strict to forbid that.

int_disjunctive_strict

int_disjunctive_strict(list of var int: start, list of var int: duration)

also declarable as int_disjunctive_strict_reif and int_disjunctive_strict_imp

No two tasks overlap, and a zero-duration task may not fall inside another task.

$$\forall i < j : \mathit{start}_i + \mathit{duration}_i \leq \mathit{start}_j \;\vee\; \mathit{start}_j + \mathit{duration}_j \leq \mathit{start}_i$$

Differs from int_disjunctive only for zero-duration tasks, which here must still be separated.

int_knapsack

int_knapsack(list of int: weight, list of int: profit, list of var int: xs, var int: total_weight, var int: total_profit)

Items are selected in given quantities, with their total weight and total profit reported.

$$\left( \forall i : \mathit{xs}_i \geq 0 \right) \;\wedge\; 0 \leq \mathit{total\_weight} = \sum_{i} \mathit{weight}_i \cdot \mathit{xs}_i \;\wedge\; 0 \leq \mathit{total\_profit} = \sum_{i} \mathit{profit}_i \cdot \mathit{xs}_i$$

xs holds the quantity chosen of each item. Bound total_weight to impose the knapsack’s capacity.

int_no_overlap

int_no_overlap(list of var int: x, list of var int: dx, list of var int: y, list of var int: dy)

also declarable as int_no_overlap_reif and int_no_overlap_imp

No two rectangles overlap.

$$\forall i < j : x_i + \mathit{dx}_i \leq x_j \;\vee\; x_j + \mathit{dx}_j \leq x_i \;\vee\; y_i + \mathit{dy}_i \leq y_j \;\vee\; y_j + \mathit{dy}_j \leq y_i$$

All four arrays must have equal length. Position and extent are paired per dimension, so the arguments read x, dx, y, dy rather than all positions then all extents. Rectangles that merely touch do not overlap.

int_no_overlap_nd

int_no_overlap_nd(int: dimensions, list of var int: position, list of var int: size)

also declarable as int_no_overlap_nd_reif and int_no_overlap_nd_imp

No two boxes overlap, in any number of dimensions.

$$\forall i < j : \exists k \leq d : p_{i,k} + s_{i,k} \leq p_{j,k} \;\vee\; p_{j,k} + s_{j,k} \leq p_{i,k} \quad \text{where } d = \mathit{dimensions},\; p_{i,k} = \mathit{position}_{(i-1)d+k},\; s_{i,k} = \mathit{size}_{(i-1)d+k}$$

position and size are flattened row-major, dimensions entries per box. int_no_overlap stays beside it for two dimensions, where a caller already has an array per coordinate.

int_no_overlap_nd_nonstrict

int_no_overlap_nd_nonstrict(int: dimensions, list of var int: position, list of var int: size)

also declarable as int_no_overlap_nd_nonstrict_reif and int_no_overlap_nd_nonstrict_imp

No two boxes of non-zero volume overlap; a box with zero extent in any dimension is ignored.

$$\forall i < j : \exists k \leq d : s_{i,k} = 0 \;\vee\; s_{j,k} = 0 \;\vee\; p_{i,k} + s_{i,k} \leq p_{j,k} \;\vee\; p_{j,k} + s_{j,k} \leq p_{i,k} \quad \text{where } d = \mathit{dimensions},\; p_{i,k} = \mathit{position}_{(i-1)d+k},\; s_{i,k} = \mathit{size}_{(i-1)d+k}$$

int_no_overlap_nonstrict

int_no_overlap_nonstrict(list of var int: x, list of var int: dx, list of var int: y, list of var int: dy)

also declarable as int_no_overlap_nonstrict_reif and int_no_overlap_nonstrict_imp

No two rectangles of non-zero area overlap; rectangles with zero width or height are ignored.

$$\forall i < j : \mathit{dx}_i \cdot \mathit{dy}_i = 0 \;\vee\; \mathit{dx}_j \cdot \mathit{dy}_j = 0 \;\vee\; x_i + \mathit{dx}_i \leq x_j \;\vee\; x_j + \mathit{dx}_j \leq x_i \;\vee\; y_i + \mathit{dy}_i \leq y_j \;\vee\; y_j + \mathit{dy}_j \leq y_i$$

int_no_overlap_shape

int_no_overlap_shape(int: dimensions, list of int: rect_size, list of int: rect_origin, list of set of int: shape, list of var int: position, list of var int: kind)

also declarable as int_no_overlap_shape_reif and int_no_overlap_shape_imp

Objects of the given shapes are placed so that none overlap.

$$\forall i < j : R_i \cap R_j = \emptyset \quad \text{where } d = \mathit{dimensions},\; R_i = \bigcup_{r \in \mathit{shape}_{\mathit{kind}_i}} \prod_{k=1}^{d} \left[\, p_{i,k},\; p_{i,k} + \mathit{rect\_size}_{(r-1)d+k} \,\right),\; p_{i,k} = \mathit{position}_{(i-1)d+k} + \mathit{rect\_origin}_{(r-1)d+k}$$

dimensions is the number of dimensions, and every array indexed by rectangle or object is flattened row-major with that many entries per row. Each shape is a set of rectangles given by rect_size and rect_origin; kind selects one per object and position places its origin.

int_no_overlap_shape_bounded

int_no_overlap_shape_bounded(int: dimensions, list of int: rect_size, list of int: rect_origin, list of set of int: shape, list of var int: position, list of var int: kind, list of var int: lower_bound, list of var int: upper_bound)

also declarable as int_no_overlap_shape_bounded_reif and int_no_overlap_shape_bounded_imp

As int_no_overlap_shape, and additionally every object lies within a given bounding box.

$$\forall i, k : \mathit{lower\_bound}_k \leq p_{i,k} \;\wedge\; p_{i,k} \leq \mathit{upper\_bound}_k \quad \text{where } p_{i,k} = \mathit{position}_{(i-1)\mathit{dimensions}+k}$$

int_no_overlap_shape_tightest_bound

int_no_overlap_shape_tightest_bound(int: dimensions, list of int: rect_size, list of int: rect_origin, list of set of int: shape, list of var int: position, list of var int: kind, list of var int: lower_bound, list of var int: upper_bound)

also declarable as int_no_overlap_shape_tightest_bound_reif and int_no_overlap_shape_tightest_bound_imp

As int_no_overlap_shape_bounded, with the bounding box constrained to fit the objects exactly.

$$\forall k : \mathit{lower\_bound}_k = \min_{i} p_{i,k} \;\wedge\; \mathit{upper\_bound}_k = \max_{i} p_{i,k} \quad \text{where } p_{i,k} = \mathit{position}_{(i-1)\mathit{dimensions}+k}$$