Linear programming problem : minimise number of truck used

Question

I need to modelize with a Linear Integer Program the following problem :

We need to carry n different products from a factory to a warehouse. Each product has its own weight (the element i has a weight wi<W). We are using trucks with a maximum weight capacity of W, the objective is to minimize the number of truck used.

I tried different way but I always have trouble to modelize the number of truck in the objective function.

I used a variable Yij which equals 1 if the truck i carries the item j, 0 otherwise and managed to write the different constraints. But I can't find how to count the number of trucks used with that variable.

If anyone has any suggestion it would be very helpful.

Thanks

Answer 1

Assuming that Yij is a rectangular matrix of size (m=items, n=trucks) full of binary-variables like:

truck    0    1   2
item 0   x00  x   x
item 1   x10  x   x
item 2   x20  x   x
item 3   x30  x   x

you can create additional binary variables t_used_0 (shown for truck_0 only) like:

sum(Yij_column_0) <= m * t_used_0

    <-> x00 + x10 + x20 + x30 <= 4 * t_used_0

sum(Yij_column_0) >= t_used_0

    <-> x00 + x10 + x20 + x30 >= t_used_0

You then have n auxiliary binary-variables t_used_i which you can sum up in your objective.

(There is lots of degree of freedom in those linearizations (e.g. equivalence vs. implication only) which somewhat explains why user abc asked for more information. In general, you exploit everything possible.)