## 5.54. bin_packing_capa

Origin
Constraint

$\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi }\left(\mathrm{\pi ±\pi Έ\pi ½\pi },\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }\right)$

Arguments
 $\mathrm{\pi ±\pi Έ\pi ½\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi }-\mathrm{\pi \pi \pi },\mathrm{\pi \pi \pi \pi }-\mathrm{\pi \pi \pi }\right)$ $\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }$
Restrictions
 $|\mathrm{\pi ±\pi Έ\pi ½\pi }|>0$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi ±\pi Έ\pi ½\pi },\left[\mathrm{\pi \pi },\mathrm{\pi \pi \pi \pi }\right]\right)$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi ±\pi Έ\pi ½\pi },\mathrm{\pi \pi }\right)$ $\mathrm{\pi ±\pi Έ\pi ½\pi }.\mathrm{\pi \pi }\beta ₯1$ $\mathrm{\pi ±\pi Έ\pi ½\pi }.\mathrm{\pi \pi }\beta €|\mathrm{\pi ±\pi Έ\pi ½\pi }|$ $\mathrm{\pi ±\pi Έ\pi ½\pi }.\mathrm{\pi \pi \pi \pi }\beta ₯0$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ $\mathrm{\pi \pi }_\mathrm{\pi \pi \pi \pi }$$\left(\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi },\mathrm{\pi \pi \pi },\mathrm{\pi ±\pi Έ\pi ½\pi },\mathrm{\pi \pi }\right)$
Purpose

Given several items of the collection $\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }$ (each of them having a specific weight), and different bins described the the items of collection $\mathrm{\pi ±\pi Έ\pi ½\pi }$ (each of them having a specific capacity $\mathrm{\pi \pi \pi \pi }$), assign each item to a bin so that the total weight of the items in each bin does not exceed the capacity of the bin.

Example

The $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ constraint holds since the sum of the height of items that are assigned to bins 1 and 3 is respectively equal to 3 and 5. The previous quantities are respectively less than or equal to the maximum capacities 4 and 5 of bins 1 and 3. FigureΒ 5.54.1 shows the solution associated with the example.

Typical
 $|\mathrm{\pi ±\pi Έ\pi ½\pi }|>1$ $\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi ±\pi Έ\pi ½\pi }.\mathrm{\pi \pi \pi \pi }\right)>1$ $\mathrm{\pi ±\pi Έ\pi ½\pi }.\mathrm{\pi \pi \pi \pi }>$$\mathrm{\pi \pi \pi ‘\pi \pi \pi }$ $\mathrm{\pi ±\pi Έ\pi ½\pi }.\mathrm{\pi \pi \pi \pi }\beta €$$\mathrm{\pi \pi \pi }$ $|\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }|>1$ $\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }.\mathrm{\pi \pi \pi }\right)>1$ $\mathrm{\pi \pi \pi \pi \pi }$
Symmetries
• Items of $\mathrm{\pi ±\pi Έ\pi ½\pi }$ are permutable.

• Items of $\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }$ are permutable.

• $\mathrm{\pi ±\pi Έ\pi ½\pi }.\mathrm{\pi \pi \pi \pi }$ can be increased.

• can be decreased to any value $\beta ₯0$.

• All occurrences of two distinct values in $\mathrm{\pi ±\pi Έ\pi ½\pi }.\mathrm{\pi \pi }$ or $\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }.\mathrm{\pi \pi \pi }$ can be swapped; all occurrences of a value in $\mathrm{\pi ±\pi Έ\pi ½\pi }.\mathrm{\pi \pi }$ or $\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }.\mathrm{\pi \pi \pi }$ can be renamed to any unused value.

Arg. properties

Contractible wrt. $\mathrm{\pi Έ\pi \pi ΄\pi Ό\pi }$.

Remark

In MiniZinc (http://www.minizinc.org/) there is also a constraint called $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ which, for each bin has a domain variable that is equal to the sum of the weights assigned to the corresponding bin.

Systems
generalisation: $\mathrm{\pi \pi \pi \pi \pi ‘\pi \pi }_\mathrm{\pi \pi \pi }$Β (negative contribution also allowed).
specialisation: $\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$Β (non-fixed capacity replaced by fixed overall capacity).