5.41. bin_packing

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ.

Constraint

πš‹πš’πš—_πš™πšŠπšŒπš”πš’πš—πš(π™²π™°π™Ώπ™°π™²π™Έπšƒπšˆ,π™Έπšƒπ™΄π™Όπš‚)

Arguments
π™²π™°π™Ώπ™°π™²π™Έπšƒπšˆπš’πš—πš
π™Έπšƒπ™΄π™Όπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš‹πš’πš—-πšπšŸπšŠπš›,πš πšŽπš’πšπš‘πš-πš’πš—πš)
Restrictions
π™²π™°π™Ώπ™°π™²π™Έπšƒπšˆβ‰₯0
πš›πšŽπššπšžπš’πš›πšŽπš(π™Έπšƒπ™΄π™Όπš‚,[πš‹πš’πš—,πš πšŽπš’πšπš‘πš])
π™Έπšƒπ™΄π™Όπš‚.πš πšŽπš’πšπš‘πšβ‰₯0
π™Έπšƒπ™΄π™Όπš‚.πš πšŽπš’πšπš‘πšβ‰€π™²π™°π™Ώπ™°π™²π™Έπšƒπšˆ
Purpose

Given several items of the collection π™Έπšƒπ™΄π™Όπš‚ (each of them having a specific weight), and different bins of a fixed capacity, assign each item to a bin so that the total weight of the items in each bin does not exceed π™²π™°π™Ώπ™°π™²π™Έπšƒπšˆ.

Example
5,πš‹πš’πš—-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 both less than or equal to the maximum π™²π™°π™Ώπ™°π™²π™Έπšƒπšˆ 5. FigureΒ 5.41.1 shows the solution associated with the example.

Figure 5.41.1. Bin-packing solution
ctrs/bin_packing1
Typical
π™²π™°π™Ώπ™°π™²π™Έπšƒπšˆ>πš–πšŠπš‘πšŸπšŠπš•(π™Έπšƒπ™΄π™Όπš‚.πš πšŽπš’πšπš‘πš)
π™²π™°π™Ώπ™°π™²π™Έπšƒπšˆβ‰€πšœπšžπš–(π™Έπšƒπ™΄π™Όπš‚.πš πšŽπš’πšπš‘πš)
|π™Έπšƒπ™΄π™Όπš‚|>1
πš›πšŠπš—πšπšŽ(π™Έπšƒπ™΄π™Όπš‚.πš‹πš’πš—)>1
πš›πšŠπš—πšπšŽ(π™Έπšƒπ™΄π™Όπš‚.πš πšŽπš’πšπš‘πš)>1
π™Έπšƒπ™΄π™Όπš‚.πš πšŽπš’πšπš‘πš>0
Symmetries
  • π™²π™°π™Ώπ™°π™²π™Έπšƒπšˆ can be increased.

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

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

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

Remark

Note the difference with the classical bin-packing problem [MartelloToth90] where one wants to find solutions that minimise the number of bins. In our case each item may be assigned only to specific bins (i.e.,Β the different values of the bin variable) and the goal is to find a feasible solution. This constraint can be seen as a special case of the πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ constraintΒ [AggounBeldiceanu93], where all task durations are equal to 1.

InΒ [Shaw04] the π™²π™°π™Ώπ™°π™²π™Έπšƒπšˆ parameter of the πš‹πš’πš—_πš™πšŠπšŒπš”πš’πš—πš constraint is replaced by a collection of domain variables representing the load of each bin (i.e.,Β the sum of the weights of the items assigned to a bin). This allows representing problems where a minimum level has to be reached in each bin.

CoffmanΒ and al. give inΒ [CoffmanGareyJohnson84] the worst case bounds of different list algorithms for the bin packing problem (i.e.,Β given a positive integer π™²π™°π™Ώπ™°π™²π™Έπšƒπšˆ and a list L of integer sizes πš πšŽπš’πšπš‘πš 1 ,πš πšŽπš’πšπš‘πš 2 ,...,πš πšŽπš’πšπš‘πš n (0β‰€πš πšŽπš’πšπš‘πš i β‰€π™²π™°π™Ώπ™°π™²π™Έπšƒπšˆ), what is the smallest integer m such that there is a partition L=L 1 βˆͺL 2 βˆͺ...βˆͺL m satisfying βˆ‘ πš πšŽπš’πšπš‘πš i ∈L j πš πšŽπš’πšπš‘πš i β‰€π™²π™°π™Ώπ™°π™²π™Έπšƒπšˆ for all j∈[1,m]?).

Algorithm

Initial filtering algorithms are described inΒ [MullerHannemannStilleWeihe03a], [MullerHannemannStilleWeihe03b], [MullerHannemannStilleWeihe03c], [MullerHannemannStilleWeihe03d], [Shaw04]. More recently, linear continuous relaxations based on the graph associated with the dynamic programming approach for knapsack by TrickΒ [Trick03], and on the more compact model introduced by CarvalhoΒ [Carvalho99], [Carvalho02] are presented inΒ [CambazardSullivan10].

Systems

pack in Choco.

See also

generalisation: πš‹πš’πš—_πš™πšŠπšŒπš”πš’πš—πš_πšŒπšŠπš™πšŠΒ (fixed overall capacity replaced by non-fixed capacity), πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽΒ (task of πšπšžπš›πšŠπšπš’πš˜πš— 1 replaced by task of given πšπšžπš›πšŠπšπš’πš˜πš—), πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ_𝚝𝚠𝚘_𝚍 (πšπšŠπšœπš” of πšπšžπš›πšŠπšπš’πš˜πš— 1 replaced by πšœπššπšžπšŠπš›πšŽ of size 1 with a πš‘πšŽπš’πšπš‘πš), πš’πš—πšπšŽπš‘πšŽπš_πšœπšžπš–Β (negative contribution also allowed, fixed capacity replaced by a set of variables).

used in graph description: πšœπšžπš–_πšŒπšπš›.

Keywords

application area: assignment.

characteristic of a constraint: automaton, automaton with array of counters.

constraint type: resource constraint.

final graph structure: acyclic, bipartite, no loop.

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

modelling exercises: assignment to the same set of values.

Arc input(s)

π™Έπšƒπ™΄π™Όπš‚ π™Έπšƒπ™΄π™Όπš‚

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πšπšŽπš–πšœ1,πš’πšπšŽπš–πšœ2)

Arc arity
Arc constraint(s)
πš’πšπšŽπš–πšœ1.πš‹πš’πš—=πš’πšπšŽπš–πšœ2.πš‹πš’πš—
Graph class
β€’ π™°π™²πšˆπ™²π™»π™Έπ™²
β€’ π™±π™Έπ™Ώπ™°πšπšƒπ™Έπšƒπ™΄
β€’ 𝙽𝙾_𝙻𝙾𝙾𝙿

Sets
π–²π–΄π–’π–’β†¦πšœπš˜πšžπš›πšŒπšŽ,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ-πšŒπš˜πš•πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›),πš’πšπšŽπš–(πšŸπšŠπš›-π™Έπšƒπ™΄π™Όπš‚.πš πšŽπš’πšπš‘πš)]

Constraint(s) on sets
πšœπšžπš–_πšŒπšπš›(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ,≀,π™²π™°π™Ώπ™°π™²π™Έπšƒπšˆ)
Graph model

We enforce the πšœπšžπš–_πšŒπšπš› constraint on the weight of the items that are assigned to the same bin.

PartsΒ (A) andΒ (B) of FigureΒ 5.41.2 respectively show the initial and final graph associated with the Example slot. Each connected component of the final graph corresponds to the items that are all assigned to the same bin.

Figure 5.41.2. Initial and final graph of the πš‹πš’πš—_πš™πšŠπšŒπš”πš’πš—πš constraint
ctrs/bin_packingActrs/bin_packingB
(a) (b)
Automaton

FigureΒ 5.41.3 depicts the automaton associated with the πš‹πš’πš—_πš™πšŠπšŒπš”πš’πš—πš constraint. To each item of the collection π™Έπšƒπ™΄π™Όπš‚ corresponds a signature variable πš‚ i that is equal to 1.

Figure 5.41.3. Automaton of the πš‹πš’πš—_πš™πšŠπšŒπš”πš’πš—πš constraint
ctrs/bin_packing2