What is the Cheapest Program to Train a Senior Manager with Specific Skills?

[operationsres]

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.)

3. attempt at a solution.

Sorry, no deal! Have no idea how to formulate into a program :)

 

[hgfalling]

This seems kind of standard for these types of problems, which have the form:

Maximize/Minimize f(x_1,x_2,...,x_n)
subject to:
constraint
...
constraint

You have something you want to minimize/maximize. What is it?

You have constraints. Here you have two types of constraints. What are they? How can you write them down as equations in the usual constraint form?

Then it's just a typical linear program.

Try and work some of it out for us and then we can help you further.

 

[operationsres]

This seems kind of standard for these types of problems, which have the form:

Maximize/Minimize f(x_1,x_2,...,x_n)
subject to:
constraint
...
constraint

You have something you want to minimize/maximize. What is it?

You have constraints. Here you have two types of constraints. What are they? How can you write them down as equations in the usual constraint form?

Then it's just a typical linear program.

Try and work some of it out for us and then we can help you further.

Thankyou for replying.

If xi are the skills, MAXing or MINing f(x1,x2,x3...) doesn't work. The programs/courses (px) will have to be the decision variables. Beyond that and I'm wholly unsure.

I've been trying for over a week, and have gotten zip. I can't do it.

 

[hgfalling]

Yes, that's right. Programs should be the decision variables.

Each one will be a 0 or 1 integer variable, right? If you take that class, then it's 1, if you don't then it's zero.

Now you can write down an expression in terms of p_x that we are trying to minimize.

 

[operationsres]

Yes, that's right. Programs should be the decision variables.

Each one will be a 0 or 1 integer variable, right? If you take that class, then it's 1, if you don't then it's zero.

Now you can write down an expression in terms of p_x that we are trying to minimize.

Yep I've gotten this far.

Constaints are confounding me, at the moment.

I have:
MINIMIZE,
z = cost1*p1 + cost2*p2 + cost3*p3 + ... + cost15*p15,

s.t.
"..
..
.."

px = 0 or 1 (Binary).

 

[hgfalling]

Yes, all that is right. Now you have two types of constraints.

One type is that you need to make sure that each skill is covered.
Now suppose we consider the first skill. If p_x are our decision variables, what equation can we write that ensures that x₁ will be covered?

If there are ten skills, that's ten constraints.

The other type of constraint is the conflict of various classes with each other.
Consider the first class. It says that p₁ conflicts with p₂ and p₈. What equation can we write that ensures that we won't take both p₁ and p₂, for example?

All these should just be in terms of p_x; there's no need to make explicit reference to the skills at all.

 

[operationsres]

Now suppose we consider the first skill. If p_x are our decision variables, what equation can we write that ensures that x₁ will be covered?

If there are ten skills, that's ten constraints.

SIGMAp_i1 = 1, where p_i1 = all the programs that have skill x1 inside of it.
SIGMAp_i2 = 1,
.
.

I think you're a genius...

THIS IS WORKING IN LINGO! WQOW!

The other type of constraint is the conflict of various classes with each other.
Consider the first class. It says that p₁ conflicts with p₂ and p₈. What equation can we write that ensures that we won't take both p₁ and p₂, for example?.

Wow that's a real brain buster.

p1 = 2y;
p2 = 2(1-y);

BIN(y);

That doesn't work for this problem though.

HMMMMMM



---
THANKYOU SO MUCH FOR YOUR HELP. Seriously!

 

[hgfalling]

SIGMAp_i1 = 1, where p_i1 = all the programs that have skill x1 inside of it.
SIGMAp_i2 = 1,

Almost right. But what if class 1 and class 2 both have skill x1 but are otherwise the most efficient setup because of the other skills they contain and their cost? Then the sum of p₁ and p₂ will be more than one, but that's okay. This is easily rectified by changing those constraints to inequalities, however.

p1 = 2y;
p2 = 2(1-y);

BIN(y);

That doesn't work for this problem though.

HMMMMMM

If we did pick two conflicting classes, what would be true of the sum of the p-values of those classes? Write inequalities that prevent us from picking more than one conflicting class.

 

[operationsres]

Almost right. But what if class 1 and class 2 both have skill x1 but are otherwise the most efficient setup because of the other skills they contain and their cost? Then the sum of p₁ and p₂ will be more than one, but that's okay. This is easily rectified by changing those constraints to inequalities, howeve

You are amazing. I'll deal with the other part of your post after this bit.

"MIN=785.71*p1+2300*p2+900*p3+1325*p4+1200*p5+1150*p6+1450*p7+1166.67*p8+800*p9+1100*p10+985.71*p11+1933.33*p12+828.57*p13+2233.33*p14+2200*p15;

p1+p4+p5+p9>=1;
p1+p4+p5++p7+p9+p10>=1;
p1+p8+p10+p13>=1;
p1+p4+p5+p8+p13>=1;
p1+p9+p12>=1;
.
.
."

Then the middle of the output is like this:

"
10 2.000000 0.000000
11 1.000000 0.000000
12 1.000000 0.000000
13 1.000000 0.000000
14 0.000000 0.000000
15 0.000000 0.000000
16 1.000000 0.000000
17 1.000000 0.000000
18 1.000000 0.000000"

How are some of the constraints 0? I put >=1 ?

If we did pick two conflicting classes, what would be true of the sum of the p-values of those classes? Write inequalities that prevent us from picking more than one conflicting class.

It's presented like this.
...... Programs that Interfere
Program 1... 3 5 8
Program 2... 3 7 10


p1 + p3<=1;
p1 + p5<=1;
p1 + p8<=1;

right?

^^ Infeasible. What the ef :(

Those constraints are correct... wowowowowowow

ROARRRRRRRR

 

[hgfalling]

Hard for me to evaluate why that might be happening, what your software is doing, etc. It seems you are on the right track now, though, as far as formulating the linear program.

 

[operationsres]

Hard for me to evaluate why that might be happening, what your software is doing, etc. It seems you are on the right track now, though, as far as formulating the linear program.

It turns out that I had made mistakes in typing the correct constraints.
I fixed them up, AND IT WORKED, PERFECTLY.

Thank SOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO much²