# Mixed Integer Linear Programming: Construction Rods

I have an interesting problem involving linear programming. The problem is the following, I have 4 different kinds of rods (rod sized found in the local market):

• 9m rod
• 11m rod
• 12m rod
• 15m rod

Slabs on construction have steel rods and I want to minimize the quantity of rods used horizontally and vertically. I have a total length (Ltotal) and I want to know what is the minimum amount of rods I need to use for a slab,that still fits at least inside it or possibly longer. The remaining rod length that exceeds the slab is going to be cut. So I suppose the objective function will be:

$$\min x_{1} + x_{2} + x_{3} + x_{4}$$

$$s.t. \ 9x_{1} + 11x_{2} + 12x_{3} + 15x_{4}\ \ (\lt,\le or =)? \ \ \ L_{total}$$ $$x_{1} \ge 0$$ $$x_{2} \ge 0$$ $$x_{3} \ge 0$$ $$x_{4} \ge 0$$ where

$x_{1}$: total amount of 9m rods used
$x_{2}$: total amount of 11m rods used
$x_{3}$: total amount of 12m rods used
$x_{4}$: total amount of 15m rods used

I assume all this 4 variables should be integers(MILP)

The constraint expresses the amount of rods multiplied by its length should be less than or equal to the total length. I want some advice as I am not very familiar to optimization methods. I put this same example in PuLP but it throwed 0 for all values.

I need help to solve this problem.

Thanks

• You swapped an inequality. If the total length should be less than some specified total length, the trivial solution is to set all lengths equal to zero, as you have obtained numerically. – Johan Löfberg Feb 25 '15 at 9:42
• Hi @JohanLöfberg , should I set it as an equality instead? How would you set it? – Diego Gallegos Feb 25 '15 at 13:46
• Does it make sense to you to specify that the length of the rod should be less than some value? Just think in terms of common sense. If you tell your welder to build the cheapest possible rod, and it has to be at most 10 meters, any smart welder would give you a rod of length 0 and happily take your money. Hence you should specify that the rod should be... – Johan Löfberg Feb 25 '15 at 13:54
• @JohanLöfberg, oh I see but the total length is not the length of the rod but the length of the entire slab(Ltotal). I have to find a configuration of the given rods(rods in the market) that fit in the slab. – Diego Gallegos Feb 25 '15 at 14:06
• Then you are obviously missing some constraint, as the trivially optimal solution is $x=0$ (or actually $x = -\infty$ as you do not have any non-negativity constraint on $x$). A rod of length 0 clearly fits in your slab. – Johan Löfberg Feb 25 '15 at 14:13

$$\min x_{1} + x_{2} + x_{3} + x_{4}$$
$$s.t. \ 9x_{1} + 11x_{2} + 12x_{3} + 15x_{4}\ \geq L_{total}$$ $$x_{1} \ge 0$$ $$x_{2} \ge 0$$ $$x_{3} \ge 0$$ $$x_{4} \ge 0$$