Bin packing constraints

Functions
void	Gecode::binpacking (Home home, const IntVarArgs &l, const IntVarArgs &b, const IntArgs &s, IntPropLevel ipl=IPL_DEF)
	Post propagator for bin packing.

Detailed Description

Function Documentation

binpacking()

void Gecode::binpacking	(	Home	home,
		const IntVarArgs &	l,
		const IntVarArgs &	b,
		const IntArgs &	s,
		IntPropLevel	ipl = IPL_DEF )

Post propagator for bin packing.

The variables in l are the loads for each bin, whereas the variables in b define for each item into which bin it is packed. The integer values s define the size of the items.

It is propagated that for each \(j\) with \(0\leq j<|l|\) the constraint \(l_j=\sum_{0\leq i<|b|\wedge b_i=j}s_i\) holds and that for each \(i\) with \(0\leq i<|b|\) the constraint \(0\leq b_i<|l|\) holds.

Basic and knapsack propagation are based on: Paul Shaw. A Constraint for Bin Packing. CP 2004. The lower-bound phase uses dual-feasible functions described in: Tardivo et al. CP for Bin Packing with Multi-Core and GPUs. CP 2024. The propagation level ipl controls the amount of filtering:

• IPL_BASIC performs basic load and item filtering only.
• IPL_ADVANCED performs basic filtering, knapsack filtering using NoSum, and a small DFF portfolio (CCM1 and MT). It is the default (IPL_DEF).
• IPL_FULL performs all of the above and the complete DFF portfolio.

Throws the following exceptions:

• Of type Int::ArgumentSizeMismatch if b and s are not of the same size.
• Of type Int::ArgumentSame if l and b share unassigned variables.
• Of type Int::OutOfLimits if s contains a negative number.