A Simple Approach to the Assortment Problem

Götz Uebe - Universität der Bundesweher Hamburg

As illustrated by the algorithms of Chen et al. and Li et al., the assortment problem, i.e. how to place n rectangles of given size into a minimum rectangle hull, is a problem of extreme computational requirements, rarely to be solved globally. By elementary reasoning for minimum size, bounds can be established. By use of an auxiliary linear objective, the circumference, by this surrogate objective function, one can obtain the same minimum hull. This is surprising since the quadratic IP can be solved by a less difficult linear integer program. Numerical evidence is given.

Scheduled for Session 3.6 Numerical Methods