5.54. bin_packing_capa

DESCRIPTIONLINKS
Origin

Derived from πš‹πš’πš—_πš™πšŠπšŒπš”πš’πš—πš.

Constraint

πš‹πš’πš—_πš™πšŠπšŒπš”πš’πš—πš_πšŒπšŠπš™πšŠ(π™±π™Έπ™½πš‚,π™Έπšƒπ™΄π™Όπš‚)

Arguments
π™±π™Έπ™½πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πš-πš’πš—πš,πšŒπšŠπš™πšŠ-πš’πš—πš)
π™Έπšƒπ™΄π™Όπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš‹πš’πš—-πšπšŸπšŠπš›,πš πšŽπš’πšπš‘πš-πš’πš—πš)
Restrictions
|π™±π™Έπ™½πš‚|>0
πš›πšŽπššπšžπš’πš›πšŽπš(π™±π™Έπ™½πš‚,[πš’πš,πšŒπšŠπš™πšŠ])
πšπš’πšœπšπš’πš—πšŒπš(π™±π™Έπ™½πš‚,πš’πš)
π™±π™Έπ™½πš‚.πš’πšβ‰₯1
π™±π™Έπ™½πš‚.πš’πšβ‰€|π™±π™Έπ™½πš‚|
π™±π™Έπ™½πš‚.πšŒπšŠπš™πšŠβ‰₯0
πš›πšŽπššπšžπš’πš›πšŽπš(π™Έπšƒπ™΄π™Όπš‚,[πš‹πš’πš—,πš πšŽπš’πšπš‘πš])
πš’πš—_πšŠπšπšπš›(π™Έπšƒπ™΄π™Όπš‚,πš‹πš’πš—,π™±π™Έπ™½πš‚,πš’πš)
π™Έπšƒπ™΄π™Όπš‚.πš πšŽπš’πšπš‘πšβ‰₯0
Purpose

Given several items of the collection π™Έπšƒπ™΄π™Όπš‚ (each of them having a specific weight), and different bins described the the items of collection π™±π™Έπ™½πš‚ (each of them having a specific capacity πšŒπšŠπš™πšŠ), 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
πš’πš-1πšŒπšŠπš™πšŠ-4,πš’πš-2πšŒπšŠπš™πšŠ-3,πš’πš-3πšŒπšŠπš™πšŠ-5,πš’πš-4πšŒπšŠπš™πšŠ-3,πš’πš-5πšŒπšŠπš™πšŠ-3,πš‹πš’πš—-3πš πšŽπš’πšπš‘πš-4,πš‹πš’πš—-1πš πšŽπš’πšπš‘πš-3,πš‹πš’πš—-3πš πšŽπš’πšπš‘πš-1

The πš‹πš’πš—_πš™πšŠπšŒπš”πš’πš—πš_πšŒπšŠπš™πšŠ 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.

Figure 5.54.1. Bin-packing solution to the Example slot
ctrs/bin_packing_capa-1-tikz
Typical
|π™±π™Έπ™½πš‚|>1
πš›πšŠπš—πšπšŽ(π™±π™Έπ™½πš‚.πšŒπšŠπš™πšŠ)>1
π™±π™Έπ™½πš‚.πšŒπšŠπš™πšŠ>πš–πšŠπš‘πšŸπšŠπš•(π™Έπšƒπ™΄π™Όπš‚.πš πšŽπš’πšπš‘πš)
π™±π™Έπ™½πš‚.πšŒπšŠπš™πšŠβ‰€πšœπšžπš–(π™Έπšƒπ™΄π™Όπš‚.πš πšŽπš’πšπš‘πš)
|π™Έπšƒπ™΄π™Όπš‚|>1
πš›πšŠπš—πšπšŽ(π™Έπšƒπ™΄π™Όπš‚.πš‹πš’πš—)>1
πš›πšŠπš—πšπšŽ(π™Έπšƒπ™΄π™Όπš‚.πš πšŽπš’πšπš‘πš)>1
π™Έπšƒπ™΄π™Όπš‚.πš πšŽπš’πšπš‘πš>0
Symmetries
  • Items of π™±π™Έπ™½πš‚ are permutable.

  • Items of π™Έπšƒπ™΄π™Όπš‚ are permutable.

  • π™±π™Έπ™½πš‚.πšŒπšŠπš™πšŠ can be increased.

  • π™Έπšƒπ™΄π™Όπš‚.πš πšŽπš’πšπš‘πš can be decreased to any value β‰₯0.

  • All occurrences of two distinct values in π™±π™Έπ™½πš‚.πš’πš or π™Έπšƒπ™΄π™Όπš‚.πš‹πš’πš— can be swapped; all occurrences of a value in π™±π™Έπ™½πš‚.πš’πš or π™Έπšƒπ™΄π™Όπš‚.πš‹πš’πš— can be renamed to any unused value.

Arg. properties

Contractible wrt. π™Έπšƒπ™΄π™Όπš‚.

Remark

In MiniZinc (http://www.minizinc.org/) there is also a constraint called πš‹πš’πš—_πš™πšŠπšŒπš”πš’πš—πš_πš•πš˜πšŠπš which, for each bin has a domain variable that is equal to the sum of the weights assigned to the corresponding bin.

Systems

pack in Choco, binpacking in Gecode, bin_packing_capa in MiniZinc.

See also

generalisation: πš’πš—πšπšŽπš‘πšŽπš_πšœπšžπš–Β (negative contribution also allowed).

specialisation: πš‹πš’πš—_πš™πšŠπšŒπš”πš’πš—πšΒ (non-fixed capacity replaced by fixed overall capacity).

Keywords

application area: assignment.

constraint type: predefined constraint, resource constraint.

modelling: assignment dimension, assignment to the same set of values.

modelling exercises: assignment to the same set of values.