# Math Help - Optimization Problem. Hard!

1. ## Optimization Problem. Hard!

This problem is killing me!

Goal: You want to train your Senior Manager. He needs skills:
x1, x2, x3, x4, x5, x6, x7, x8, x9, x10.

You are to choose from the following programs/courses that fulfills all the senior manager's skill needs at the cheapest cost.
p1 has x1, x3, x4 at $500 p2 has x3, x5, x9, x10 at$1000
p3 has x2 at \$ 600
.
.
.
.
p15 has ......

p1 conflicts with p2, p8.
p2 conflicts with p1, p4, p10.
.
.
. (.. This part can probably be inputted into our program later on, if we try and formulate the whole thing at once our brains will probably asplode.)

I feel like dying when trying to formulate this.

2. I assume your looking for a mathematical solution, rather thanjust gong through the options one a a time and finding the cheapest (that may be quicker)

You want to minimise the total cost of training subject to a long list of constraints. Define the following variables:

$q_i~~~~~ i=(1,...,n)$ flags to indicate if each training was purchased
$p_i$ the cost of each training
$Z_{ij}$ indicates if training i gives you skill j

You want to minimise the total cost, subject to having all skills learned.
$min \sum{q_{i}p_i}$

subject to: Learning every skill
$\sum{q_iZ_{i1}} \ge 1~~~~~$ (skill 1 must be learned at least once)
$\sum{q_iZ_{i2}} \ge 1~~~~~$ (skill 2 must be learned at least once)
$\sum{q_iZ_{i3}} \ge 1~~~~~$ (skill 3 must be learned at least once)
...etc

Subjec to: Constraints for program conflicts:
$q_1+q_2 \le 1~~~~~$ (training 1 and 2 cant BOTH be taken)
$q_1+q_8 \le 1~~~~~$ (training 1 and 8 cant BOTH be taken)
$q_2+q_4 \le 1~~~~~$ (training 2 and 4 cant BOTH be taken)
$q_2+q_{10} \le 2~~~~~$ (training 2 and 10 cant BOTH be taken)

Subject to: More attendance constraints:
$q_1 \le 1~~~~~$ (you can take training 1 at most 1 time)
$q_2 \le 1~~~~~$ (you can take training 2 at most 1 time)
$q_3 \le 1~~~~~$ (you can take training 2 at most 1 time)
...etc

$q_1 \ge 0$
$q_2 \ge 0$
..etc

in principle, you can drop the "more attendance constraints" and get the same answer, because atttending the same program twice wont add any more skills but will increase the cost, so cant be the optimal solution

Hope that helps, dont ask me to solve it!!

3. Ah... this is actually a trick question.. Senior Managers cannot be trained!

4. This seems like a good candidate for a backtracking algorithm. I think you can approach it in a pretty straightforward manner using recursion and returning whenever a condition is not met, or whenever your current total cost exceeds the current minimum you've obtained. You'll probably want to use an array/list or multiple arrays/lists to keep track of things as an argument in your recursive function, and be sure to make deep copies as opposed to shallow copies. I would offer to help with the program itself but I have a busy week and wouldn't be able to help you until the weekend. Good luck.

Note: If you write some code, I can take a look, but I won't have time to actually produce code for you this week.

Edit: I used a backtracking approach on this thread, not sure if it would be a useful example for you.