Linear Programming(solver ?)

R

rick

Hello, I am new to this group and hope you can help me. I have a
problem that I am trying to solve.
I am trying to use solver but not sure if I am setting up the model
correctly.

I have 4 workers Sam, Avery, Ben, and Steve and 4 different duties
(Engine, Trans, Alignment, & Brakes) that the can be performed. Each
person has a different average time(mins) to complete each task. I am
trying to develop the formula to optimize who should do what to get the
lowest amount of time.


Engine Transmission Alignment Brakes
Sam 45 34 23 45
Avery 48 30 36 37
Ben 30 48 40 41
Steve 38 34 30 31


Thoughts on the formula and contraints?
 
G

Gary''s Student

Just use competitive advantage. Assuming that all workers are available,
assign the taks to the most efficient worker for that task.

Ben should get engine work
Avery transmissions
Sam alignments
Steve breaks

If the most suitable worker is busy, then assign the task to the next most
suitable.
 
D

Dana DeLouis

Hi Rick. Solver can do this, but you need helper cells.
Your data is in a 4*4 grid. (Let's name it "Data")
Make another 4*4 area nearby, and name it "Chg" (The Changing cells)
Fill each cell in Chg with 1 for now.
Add a Target cell with the formula
=SUMPRODUCT(Data,Chg)

(We note that Target should now show the total of all the cells in Data).

For Solver, minimize the Target cell, by changing the Chg cells.
Add the constraint that the Chg cells are Binary (Bin). This limits the
cells to either 0 or 1. A "1" means that Solver picked that combination.
However, we need to add Constraints to Chg cells. Each Row, and each Column
in Chg can have only one "1".
Select the Chg table, but expand it by 1 column to the right, and 1 row
down. Hit the Autosum button, and delete the sum formula in the lower right
corner.
You now have Sum formulas for each Row, and each Column.
For the vertical Sum formulas, add two constraints that this area is <1.01,
and >0.99
For example, and the constraints like:
F7:F10 < 1.01
F7:F10 > 0.99

The reason for not using just F7:F10 =1 is that Solver can't really work
with exact integers, so we allow for a little slack. This doesn't affect
any results.
Also, you do not need to do this for each individual cell. Solver applies
the constraint to each cell in Range F7:F10.
Now, add the same constraint for the horizontal sum Formulas.
Under Solver's options, place a check on "Assume linear model." This allows
Solver to work faster on these problems.

I get the same results as Gary's Student.

I like to add Conditional Formatting to my Data area. I like to use a
formula that if the corresponding cell in Chg is >0.5, then add formatting
(Bold, Color, etc).
It's easier for me to see who does what, then looking at the table of 1's &
0's.

Note that Excel's Solver is limited to only 200 changing cells. This limits
an area to about 14*14 (=196). Solver is not very good using this technique
when the problem is large.

You can write macros that can loop to find slightly larger problems, but
it's not easy.
Let's look at 1 possible problem if we "assign the task to the most
efficient worker for that task."
These are hard to spot when the problem is large.
Two people (A & B), and 2 tasks.
A can do each task in {3,5} minutes.
B can do each task in {7,1000} minutes.

A is more efficient at the first task. B gets remaining task.
Total time: 3+1000 = 1003 minutes.

However, if we start by looking at the most inefficient, and give the first
task to B, and the remaining task 2 to A, then total time is 7+5 = 12
minutes.
This is what makes it difficult.
Anyway, hope this helps.
 
R

romelsb

Rick...i believe that u dont need a solver cause you cannot change any
performance rate as shown in the table....this table u have contains
fix-constants. Your problem is a matter of Sum interpolation to get the
minimum time...solver works with cells subject to changes....not pure
selection...
 
J

John Coleman

Dana said:
Hi Rick. Solver can do this, but you need helper cells.
Your data is in a 4*4 grid. (Let's name it "Data")
Make another 4*4 area nearby, and name it "Chg" (The Changing cells)
Fill each cell in Chg with 1 for now.
Add a Target cell with the formula
=SUMPRODUCT(Data,Chg)

(We note that Target should now show the total of all the cells in Data).

For Solver, minimize the Target cell, by changing the Chg cells.
Add the constraint that the Chg cells are Binary (Bin).

Not needed here, and (since this looks like homework for an OR/MS
course) possibly not desired. Assignment problems like this are a
special case of a network flow problem, and it is known that if all
constraints for such a problem are integral then the corresponding LP
has integral solutions, so you don't need to model it as an ILP. But -
you would still need to check assume nonnegative and assume linear in
the options menu.
This limits the
cells to either 0 or 1. A "1" means that Solver picked that combination.
However, we need to add Constraints to Chg cells. Each Row, and each Column
in Chg can have only one "1".
Select the Chg table, but expand it by 1 column to the right, and 1 row
down. Hit the Autosum button, and delete the sum formula in the lower right
corner.
You now have Sum formulas for each Row, and each Column.
For the vertical Sum formulas, add two constraints that this area is <1.01,
and >0.99
For example, and the constraints like:
F7:F10 < 1.01
F7:F10 > 0.99

The reason for not using just F7:F10 =1 is that Solver can't really work
with exact integers, so we allow for a little slack.

If the solver really can't handle equality constraints in a linear
integer programming problem
(which your formulation gives) then its implementation of the
branch-and-bound algorithm is seriously defective. Doesn't the Solver
have slack built in? I thought that was what the precision and
tolerance boxes in the options menu were for. I don't think there is
really any need to detract from the elegance of the model.

This doesn't affect
 
R

romelsb

you are right John....
SET TARGET : MIN
orig data 4x4 : named as Data
another 4x4 : named as CHG ----as the changing cells
another cell : named SUM ----FORMULA IS "=SUM(CHG)"


SAME OPTIONS
CONSTRAINTS
CHG=BIN
SUM=4

....thanks...
 
R

rick

I want to thank all for helping with this problem. I used the solver
and the another 4 x4 array for variables to change to solve.


Engine Trans Align Brakes
Sam 45 34 23 45
Avery 48 30 36 37
Ben 30 48 40 41
Steve 38 34 30 31


Variables
Engine Trans Align Brakes
Total2 Available2
Sam 0 0 1 0 <==(sum)1 1
Avery 0 1 0 0 <==(sum)1 1
Ben 1 0 0 0 <==(sum)1 1
Steve 0 0 0 1 <==(sum)1 1

Total1 1 1 1 1
Available1 1 1 1 1

Constraints
total1 =available1
total2 =available2
Lowest Time= 114 [=sumproduct(1st 4x4 array),(2nd 4x4 array)]
 
R

romelsb

Rick....that looks well....i got a theory that based on such sumproduct
formula....it may not work if one of the mechanic has no skill on any one of
the four category...try if steve do not know how to do "brakes" meaning his
skill = 0 or null....it happens most of the time...then there may be another
type of scenario....
--
"Bright minds are blessed to those who share them.."-rsb.


rick said:
I want to thank all for helping with this problem. I used the solver
and the another 4 x4 array for variables to change to solve.


Engine Trans Align Brakes
Sam 45 34 23 45
Avery 48 30 36 37
Ben 30 48 40 41
Steve 38 34 30 31


Variables
Engine Trans Align Brakes
Total2 Available2
Sam 0 0 1 0 <==(sum)1 1
Avery 0 1 0 0 <==(sum)1 1
Ben 1 0 0 0 <==(sum)1 1
Steve 0 0 0 1 <==(sum)1 1

Total1 1 1 1 1
Available1 1 1 1 1

Constraints
total1 =available1
total2 =available2
Lowest Time= 114 [=sumproduct(1st 4x4 array),(2nd 4x4 array)]
 
D

Dana DeLouis

...if Steve do not know how to do "brakes" meaning his
skill = 0 or null.

Hi. Just some thoughts. In a Minimization problem, Solver would like to
pick 0, as this minimizes the solution.
One common option is to set it to a very high value, say 10000.
When Solver takes a look at Steve & Brakes, the target cell is so high that
this option is not considered.
One technique I use is as follows. Many OR text books use the symbol "M" to
represent a large penalty value.
Therefore, I add a range-name constant "M" set to 10000. In the "Data"
table, I use =M to represent an invalid option, together with a custom
format to display "M"
If one goes too high with the penalty, some problems work better with the
Solver option "Use Automatic Scaling" turned on.
--
HTH :>)
Dana DeLouis
Windows XP & Office 2003


romelsb said:
Rick....that looks well....i got a theory that based on such sumproduct
formula....it may not work if one of the mechanic has no skill on any one
of
the four category...try if steve do not know how to do "brakes" meaning
his
skill = 0 or null....it happens most of the time...then there may be
another
type of scenario....
--
"Bright minds are blessed to those who share them.."-rsb.


rick said:
I want to thank all for helping with this problem. I used the solver
and the another 4 x4 array for variables to change to solve.


Engine Trans Align Brakes
Sam 45 34 23 45
Avery 48 30 36 37
Ben 30 48 40 41
Steve 38 34 30 31


Variables
Engine Trans Align Brakes
Total2 Available2
Sam 0 0 1 0 <==(sum)1 1
Avery 0 1 0 0 <==(sum)1 1
Ben 1 0 0 0 <==(sum)1 1
Steve 0 0 0 1 <==(sum)1 1

Total1 1 1 1 1
Available1 1 1 1 1

Constraints
total1 =available1
total2 =available2
Lowest Time= 114 [=sumproduct(1st 4x4 array),(2nd 4x4 array)]

you are right John....
SET TARGET : MIN
orig data 4x4 : named as Data
another 4x4 : named as CHG ----as the changing cells
another cell : named SUM ----FORMULA IS "=SUM(CHG)"


SAME OPTIONS
CONSTRAINTS
CHG=BIN
SUM=4

...thanks...
--
"Bright minds are blessed to those who share them.."-rsb.


:


Dana DeLouis wrote:
Hi Rick. Solver can do this, but you need helper cells.
Your data is in a 4*4 grid. (Let's name it "Data")
Make another 4*4 area nearby, and name it "Chg" (The Changing
cells)
Fill each cell in Chg with 1 for now.
Add a Target cell with the formula
=SUMPRODUCT(Data,Chg)

(We note that Target should now show the total of all the cells in
Data).

For Solver, minimize the Target cell, by changing the Chg cells.
Add the constraint that the Chg cells are Binary (Bin).

Not needed here, and (since this looks like homework for an OR/MS
course) possibly not desired. Assignment problems like this are a
special case of a network flow problem, and it is known that if all
constraints for such a problem are integral then the corresponding LP
has integral solutions, so you don't need to model it as an ILP.
But -
you would still need to check assume nonnegative and assume linear in
the options menu.

This limits the
cells to either 0 or 1. A "1" means that Solver picked that
combination.
However, we need to add Constraints to Chg cells. Each Row, and
each Column
in Chg can have only one "1".
Select the Chg table, but expand it by 1 column to the right, and 1
row
down. Hit the Autosum button, and delete the sum formula in the
lower right
corner.
You now have Sum formulas for each Row, and each Column.
For the vertical Sum formulas, add two constraints that this area
is <1.01,
and >0.99
For example, and the constraints like:
F7:F10 < 1.01
F7:F10 > 0.99

The reason for not using just F7:F10 =1 is that Solver can't really
work
with exact integers, so we allow for a little slack.

If the solver really can't handle equality constraints in a linear
integer programming problem
(which your formulation gives) then its implementation of the
branch-and-bound algorithm is seriously defective. Doesn't the Solver
have slack built in? I thought that was what the precision and
tolerance boxes in the options menu were for. I don't think there is
really any need to detract from the elegance of the model.

This doesn't affect
any results.
Also, you do not need to do this for each individual cell. Solver
applies
the constraint to each cell in Range F7:F10.
Now, add the same constraint for the horizontal sum Formulas.
Under Solver's options, place a check on "Assume linear model."
This allows
Solver to work faster on these problems.

I get the same results as Gary's Student.

I like to add Conditional Formatting to my Data area. I like to
use a
formula that if the corresponding cell in Chg is >0.5, then add
formatting
(Bold, Color, etc).
It's easier for me to see who does what, then looking at the table
of 1's &
0's.

Note that Excel's Solver is limited to only 200 changing cells.
This limits
an area to about 14*14 (=196). Solver is not very good using this
technique
when the problem is large.

You can write macros that can loop to find slightly larger
problems, but
it's not easy.
Let's look at 1 possible problem if we "assign the task to the most
efficient worker for that task."
These are hard to spot when the problem is large.
Two people (A & B), and 2 tasks.
A can do each task in {3,5} minutes.
B can do each task in {7,1000} minutes.

A is more efficient at the first task. B gets remaining task.
Total time: 3+1000 = 1003 minutes.

However, if we start by looking at the most inefficient, and give
the first
task to B, and the remaining task 2 to A, then total time is 7+5 =
12
minutes.
This is what makes it difficult.
Anyway, hope this helps.
--
Dana DeLouis
Windows XP & Office 2003


Hello, I am new to this group and hope you can help me. I have a
problem that I am trying to solve.
I am trying to use solver but not sure if I am setting up the
model
correctly.

I have 4 workers Sam, Avery, Ben, and Steve and 4 different
duties
(Engine, Trans, Alignment, & Brakes) that the can be performed.
Each
person has a different average time(mins) to complete each task.
I am
trying to develop the formula to optimize who should do what to
get the
lowest amount of time.


Engine Transmission Alignment Brakes
Sam 45 34 23 45
Avery 48 30 36 37
Ben 30 48 40 41
Steve 38 34 30 31


Thoughts on the formula and contraints?
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top