Optimization Problem. Hard!

1. May 15, 2010

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

2. May 15, 2010

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.

3. May 15, 2010

operationsres

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.

4. May 15, 2010

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 px that we are trying to minimize.

5. May 15, 2010

operationsres

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

6. May 15, 2010

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 px are our decision variables, what equation can we write that ensures that x1 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 p1 conflicts with p2 and p8. What equation can we write that ensures that we won't take both p1 and p2, for example?

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

7. May 15, 2010

operationsres

SIGMApi1 = 1, where pi1 = all the programs that have skill x1 inside of it.
SIGMApi2 = 1,
.
.

I think you're a genius...

THIS IS WORKING IN LINGO!!!! WQOW!

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!!

Last edited: May 15, 2010
8. May 15, 2010

hgfalling

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 p1 and p2 will be more than one, but that's okay. This is easily rectified by changing those constraints to inequalities, however.

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.

9. May 15, 2010

operationsres

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 ?

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

Last edited: May 15, 2010
10. May 15, 2010

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.

11. May 16, 2010

operationsres

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

Thank SOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO much2