Foundation of Operative Research - Esercizio

The linear optimum solution is the sum of all object's weights (475), which is

about 2.96 containers.

The integer problem can only hope at most to match 3 containers solution of the

fractional problem.

To modelise the problem, I use a decision matrix A_o_c, which takes value 1 if

object o in container c is present, 0 otherwise.

Also, to impose every object to be present in only one container, we impose for

all objects sum(container c) a_o_c = 1.

By applying the linear relaxation method, we have that every element of the

decision matrix takes a value in the closed interval [0,1], and to impose the

presence we require that the sum for every object across the containers is equal

to 1, which will intuitively spread an object across the containers.

The objective function is to minimize the number of containers used. I manage

this by imposing a big penalty every time it uses one, thus encouraging 0, free

containers:

minimize sum(all c) (M * sum(all o) a[o,c])

The matrix is multiplied by the weigths column, and the system looks like this:

C1: 40*x1_1 + 25*x1_2 + 70*x1_3 + 70*x1_4 + 90*x1_5 + 80*x1_6 + 100*x_17 <= 160

C2: 40*x1_1 + 25*x1_2 + 70*x1_3 + 70*x1_4 + 90*x1_5 + 80*x1_6 + 100*x_17 <= 160

C2: 40*x1_1 + 25*x1_2 + 70*x1_3 + 70*x1_4 + 90*x1_5 + 80*x1_6 + 100*x_17 <= 160

To cut some complexity out of the problem, I observe that object 4 and 5 fit

perfectly into a container, and I fix them in the first container. An "ideal"

solution would be for all the objects to fit perfectly, case in which the

optimal solution would be equal to the fractional one.

C1 = {4,5} => rest 0

The first row of the system will then look something like: C1: .... <= 0 which

becomes useless.

Additionally, object 7 cannot fit together with either object 6 or 3, thus we

reduce the problem complexity further by placing object 7 in C2, and either

object 6 or 3 in another one. I choose object 6 to place in container 3.

C2 = {7, } => rest 60

C3 = {6, } => rest 80

After the first set of reductions, the restrictions are:

C2: 40*x1_2 + 25*x2_2 + 70*x3_2 <= 60

C3: 40*x1_3 + 25*x2_3 + 70*x3_3 <= 80;

The AMPL solver finds in the linear relaxed problem a solution with o1 in C3, o2

in C3, and o3 divided between C2 (0.85) and C3 (0.15) roughly.

We firstly place the integer solutions found:

C2 = {7, } => rest 60

C3 = {6, 1, 2} => rest 15

It is clear by now that 3 containers are not sufficient for the integer problem.

Fixing the 3rd object in either one of the present containers would violate

their maximum capacity, thus, as a final solution - which is far from being

unique - we have: