Titre : A new algorithm for the Orthogonal Packing Problem
Exposant : Petru Valicov
Rsum : Let $V$ be a set of rectangular items
and $C$ a rectangular container. The two-dimensional
Orthogonal Packing Problem (OPP-2) consists in
deciding whether the set $V$ can be packed in $C$
without overlapping and without rotating the items. If
the set $V$ can be packed in $C$, then $V$ is called a
feasible set. This problem is NP-complete and can be
seen as a sub-problem of the well known
two-dimensional Orthogonal Knapsack Problem.
Fekete and Schepers introduced a powerful
characterization of feasible packings, based on
interval graphs. Using this characterization they
designed an efficient algorithm to solve OPP by
enumerating the interval graphs with a certain number
of constraints. In this work, we present a new
algorithm for solving OPP-2 based on a more compact
representation of interval graphs. One of the main
advantages is having a reduced number of
"symmetrical" solutions. This is a joint work with C.
Joncour and A. Pcher.