Distributing N items into X rectangles with the same size. (Goal: least ammount of space wasted)

Subject:	Distributing N items into X rectangles with the same size. (Goal: least ammount of space wasted)
Date:	Sat, 9 Jan 2010 12:20:58 +0100

Hello,

I have a couple of questions about the problem description below:

1. Is the problem below a "lineair" problem so that it can be solved with a
lineair solver, like "LP Solve" ?

2. What is a good LP model for it ?

3. Is a solver needed or can it be solved with math equations and/or a
custom algorithm ?

4. What would be good/usuable math equations for it ?

5. What would be a good algorithm for it ?

"
Problem description:

N(given) items must be distributed into X(question mark) rectangles.

The rectangles must all be of the same size (constraint).

The rectangles width(question) and height(question) may not exceed
MaxWidth(given) and MaxHeight(given) (constraints).

The number of rectangles (X) must lie between Min(given=1) and Max(given=8)
(constraints).

So the number of rectangles can be 1 to 8.

(Items have a size of 1x1=1)

The mission:

Primary goal:

Find the best width, best height and best number of rectangles so that the
least ammount of space inside the rectangles is wasted.

Secondary bonus goal:

Keep the number of rectangles required as low as possible.
"

Alternative "variable" problem description:

"
N = ItemCount = number of items.

X = RectCount = number of rectangles.

Min = MinRectCount = minimum rectangles to use.
Max = MaxRectCount = maximum rectangles to use.

Width = RectWidth = width of rectangles.
Height = RectHeight = height of rectangles.

MaxWidth = MaxRectWidth = max width of rectangles.
MaxHeight = MaxRectHeight = max height of rectangles.

All variables are/must be at least 1.
"

Thanks for any help/insights !

Bye,
Skybuck.