# Formulating a linear optimization task for a given problem

New firefighter stations shall be build in a municipality that will take care of 6 locations altogether. There are 6 possible places for the stations. The following list describes the sphere of action (locations) of the potential firefighter stations:

Place    |    A        B       C       D        E        F
------------------------------------------------------------------
Location |  1,2,5    2,3,4    1,4    2,3,6    1,4,6     4,5


The municipality is interested in building as few as possible stations in order to keep the building costs as low as possible. Formulate a linear optimization task which modellises the described problem.

I call A,B,C,D,E,F as $x_1,x_2,x_3,x_4,x_5,x_6$.

This is my objective function: $x_1+x_2+x_3+x_4+x_5+x_6 \rightarrow \text{ min }$

and these are my constraints:

$x_1+x_3+x_5 \leq 6$

$x_1+x_2+x_4 \leq 6$

$x_2+x_4 \leq 6$

$x_2+x_3+x_5+x_6 \leq 6$

$x_1+x_6 \leq 6$

$x_4+x_5 \leq 6$

Big thanks to @Marcello Sammarra for the comment!

Is my solution correct now?

• google "Set Covering Problem" – Marcello Sammarra May 27 '17 at 11:39
• @MarcelloSammarra Thank you very much for this info :) I have read about it and tried to solve this task again. I think it's (almost) correct, though I'm not sure if this $\leq 6$ is fine and the objective, if this is correct. Maybe you can tell me if it is? – tenepolis May 27 '17 at 16:05
• Assuming that your six decision variables are binary (0=station not used, 1=station used), the objective function is correct. The constraints, however, should have "greater 0" as right-hand-side. Example: To cover location 1, either A, C or E have to be used. Therefore: x1+x3+x5 > 0 – Axel Kemper May 27 '17 at 17:06
• @AxelKemper Shall I better write that assumption in my homework? And can I write "$\geq 1$" instead of "$> 0$" ? Thank you for help too :) – tenepolis May 27 '17 at 17:18
• It is helpful to write down assumptions.Your reasoning is easier to follow. "≥1" is equivalent to ">0" for binary decision variables. – Axel Kemper May 27 '17 at 17:53