Solver Help

[brownti via OfficeKB.com]

I have a problem that I think, hope, can be solved with solver, although i
havent used solver enough to know how. I get material in 12' lengths and
then cut those into even foot lengths from 3 feet to 12 feet. My quantity of
each length continually changes so i would like to set something up that
would determine how many 12' sticks i would need, to get for example: 5-3'
pieces, 2-4' pieces, 3-5' pieces and 1-10' piece. I think solver might be
able to figure that out for me, but i dont know for sure. Any thoughts or
examples out there? Thanks a lot, i really appreciate it.

 

[Dana]

how many 12' sticks I would need, to get for example:
5- 3' pieces,
2- 4' pieces,
3- 5' pieces, and
1-10' piece.

I think solver might be
able to figure that out for me, but I don't know for sure.
Any thoughts or examples out there? ]

Hi. I'm sure you'll get great responses, so here's just one idea.
Cutting-Stock problems are usually the toughest.
Excel Solver can not usually do these types of problems because of the
complexity, and size of the problem if done "Brute-Force."
One usually runs a secondary program to generate Patterns. The number of
patterns is usually much smaller and more manageable.
For example, Pattern_1 might be to cut your 12' material into two 5-ft
sections with 2' waste.
Another Pattern might be to cut four 3-ft sections with zero waste. Etc.

Do single patterns first. The 10' cut can't be combined with anything else.
Cut your 1-10' section, have 2' scrap, and remove 10' cuts from further
consideration.

You now need to cut {3, 3, 3, 3, 3, 4, 4, 5, 5, 5}

For this problem, I might run it through a Subset Program and look at all
2047 Subsets. (2^11-1 = 2047).
This is a small size, and can be done quickly.
Send the output to Excel's Dictionary object to remove duplicates. now you
are only looking at 143 Patterns.
Next, remove patterns that Total 9 and less, or greater than 12.
You remove patterns that total 9 or less because you can always add another
3' section and still be <= 12. Therefore, these patterns are a waste for
consideration.

Now, you've got only 6 patterns, and this is much easier to work with:

P1) {5, 5},
P2) {3, 3, 4},
P3) {3, 3, 5},
P4) {3, 4, 4},
P5) {3, 4, 5},
P6) {3, 3, 3, 3}

Your total requirement is 38'. We note that 3-12' only gives you 36'.
So, your best case now is to use 4 - 12' Materials.
Now, use Solver to pick how many of each pattern above you need.

You now know you will have multiple solutions when you pick a total of 4
patterns from above.
Here is just one of many techniques to go from here. Usually, you try to
minimize waste. I would try to Maximize waste of one of the cuts.
The larger the waste, the more chance you have of being able to cut a
smaller pattern for profit should the need arise.

I would set a constraint to make one more 5' cut for a total of 4.

I would cut
1 pattern of P6 (4-3')
1 pattern of P4 (1-3', 2-4')
and
2 patterns of P1 (2-5')
..
** However, on the second pattern here, just cut one 5' piece. You now
have 3-5' pieces. Don't cut the other 5'. Leave the material at 7' for use
elsewhere

Again, there are many ways to attack this problem.

 

[brownti via OfficeKB.com]

Well you seem to know what you are talking about, but i dont follow...I think
this might be beyond what i am comfortable attempting...

how many 12' sticks I would need, to get for example:

5- 3' pieces,
2- 4' pieces,
3- 5' pieces, and
1-10' piece.

I think solver might be
able to figure that out for me, but I don't know for sure.
Any thoughts or examples out there? ]

Hi. I'm sure you'll get great responses, so here's just one idea.
Cutting-Stock problems are usually the toughest.
Excel Solver can not usually do these types of problems because of the
complexity, and size of the problem if done "Brute-Force."
One usually runs a secondary program to generate Patterns. The number of
patterns is usually much smaller and more manageable.
For example, Pattern_1 might be to cut your 12' material into two 5-ft
sections with 2' waste.
Another Pattern might be to cut four 3-ft sections with zero waste. Etc.

Do single patterns first. The 10' cut can't be combined with anything else.
Cut your 1-10' section, have 2' scrap, and remove 10' cuts from further
consideration.

You now need to cut {3, 3, 3, 3, 3, 4, 4, 5, 5, 5}

For this problem, I might run it through a Subset Program and look at all
2047 Subsets. (2^11-1 = 2047).
This is a small size, and can be done quickly.
Send the output to Excel's Dictionary object to remove duplicates. now you
are only looking at 143 Patterns.
Next, remove patterns that Total 9 and less, or greater than 12.
You remove patterns that total 9 or less because you can always add another
3' section and still be <= 12. Therefore, these patterns are a waste for
consideration.

Now, you've got only 6 patterns, and this is much easier to work with:

P1) {5, 5},
P2) {3, 3, 4},
P3) {3, 3, 5},
P4) {3, 4, 4},
P5) {3, 4, 5},
P6) {3, 3, 3, 3}

Your total requirement is 38'. We note that 3-12' only gives you 36'.
So, your best case now is to use 4 - 12' Materials.
Now, use Solver to pick how many of each pattern above you need.

You now know you will have multiple solutions when you pick a total of 4
patterns from above.
Here is just one of many techniques to go from here. Usually, you try to
minimize waste. I would try to Maximize waste of one of the cuts.
The larger the waste, the more chance you have of being able to cut a
smaller pattern for profit should the need arise.

I would set a constraint to make one more 5' cut for a total of 4.

I would cut
1 pattern of P6 (4-3')
1 pattern of P4 (1-3', 2-4')
and
2 patterns of P1 (2-5')
.
** However, on the second pattern here, just cut one 5' piece. You now
have 3-5' pieces. Don't cut the other 5'. Leave the material at 7' for use
elsewhere

Again, there are many ways to attack this problem.

I have a problem that I think, hope, can be solved with solver, although i
havent used solver enough to know how. I get material in 12' lengths and

[quoted text clipped - 5 lines]

able to figure that out for me, but i dont know for sure. Any thoughts or
examples out there? Thanks a lot, i really appreciate it.

 

[joeu2004]

I would cut
1 pattern of P6 (4-3')
1 pattern of P4 (1-3', 2-4')
and
2 patterns of P1 (2-5')

Nice work. But I believe your solution results in 5 feet of
"scrap" (by that, I mean 1- and 2-foot pieces, which are unusable)
plus the extra 7-foot length that you mention. That includes the
unavoidable 2 feet of scrap from the 10-foot length.

I found another solution by trial-and-error. Coincidentally, it is
the same solution that Solver finds, using the design and set-up that
I describe in my response to "brownti". That is:

1 of the 5+3+3 pattern
2 of the 5+4+3 pattern
1 of the 9+3 pattern

That results in only 3 feet of "scrap" plus an extra 9-foot length.

After finding that solution, then asking Solver to minimize scrap,
Solver finds:

3 of the 5+4+3 pattern
1 of the 6+3+3 pattern

Although that results in only 2 feet of scrap (the minimum), it is a
dubious optimal solution. it results in extra 4- and 6-foot lengths,
instead of the one 7- or 9-foot length in yours and my solutions. It
also requires 9 cuts, compared to the 8 cuts required for all of the
above solutions, including yours.

(All of these solutions require 5 of the 12-foot raw material.)

Oh well.... Fun problem!

 

[joeu2004]

[repost due to apparent Google Groups error]

Well you seem to know what you are talking about, but i dont follow...
I think this might be beyond what i am comfortable attempting...

Dana's approach is similar to mine. So you might be uncomfortable
with my response as well. But I am able to set it up in a form that
allows for Solver to be used.

The problem with using Solver is: there are really 3 results to
minimize. They are: (1) number of raw material in 12-foot lengths;
(2) amount of scrap (see my definition below); and (3) number of
cuts. Solver can only minimize one result at a time. Presumably we
would choose #1 (number of 12-foot raw material); but that might not
minimize #2 (amount of scrap). (But see the Endnotes.)

I define "scrap" to be a length of 1 or 2 feet. Longer pieces are not
really scrap because they might be used for other projects that
require material in the same lengths, namely 3-12 feet.

I might note that with the set-up described below, it might be just as
easy (or easier!) to find the optimal solution manually by trial-and-
error.

My set-up is quite complicated to describe. It would be easier to
send you the Excel file. Feel free to send me email for that.
Needless to say, there is nothing sacrosant about my choice of cells
to use. You might prefer a very different layout. That said, here
goes....

Let B1:B10 represent the required number of 12-, 11-,..., 3-foot
lengths. These are cells in which you enter your requirements.

The following cells will contain the number of each indicated pattern
(with the amount of scrap in parentheses). These are the Solver
variables ("by changing cells"), which we want to vary to find an
optimal solution. Usually, it is prudent to blank these cells each
time before using Solver.

E1: 9+3
G1: 8+4
G2: 8+3 (1)
I1: 7+5
I2: 7+4 (1)
I3: 7+3 (2)
K1: 6+5 (1)
K2: 6+4 (2)
K3: 6+3+3
M1: 5+5 (2)
M2: 5+4+3
M3: 5+3+3 (1)
O1: 4+4+3 (1)
O2: 4+3+3 (2)
Q1: 3+3+3+3

As you might imagine, the gaps between columns are used for
descriptive labels.

The following cells compute the sum of the number of each cut length
produced by the solution. The summation cells are used to specify the
Solver constraints.

#9: E4: =sum(E1:E3)
#8: G4: =sum(G1:G3)
#7: I4: =sum(I1:I3)
#6: K4: =sum(K1:K3)

7+5: E7: =I1
6+5: E8: =K1
5+5: E9: =M1
5+4+3: E10: =M2
5+3+3: E11: =M3
#5: E16: =sum(E7:E15,E9)

8+4: G7: =G1
7+4: G8: =I2
6+4: G9: =K2
5+4+3: G10: =M2
4+4+3: G11: =O1
4+3+3: G12: =O2
#4: G16: =sum(G7:G15,G11)

9+3: I7: =E1
8+3: I8: =G2
7+3: I9: =I3
6+3+3: I10: =K3
5+4+3: I11: =M2
5+3+3: I12: =M3
4+4+3: I13: =O1
4+3+3: I14: =O2
3+3+3+3: I15: =Q1
#3: I16: =sum(I7:I15,I10,I12,I14,3*I15)

B14 computes the total number of 12-foot raw material. That is the
"target cell" for Solver. B15 computes the amount of scrap. B16
computes the number of cuts. The formulas are:

B14: =SUM(B1:B3,E1,G1:G2,I1:I3,K1:K3,M1:M3,O1:O2,Q1)
B15: =B2+G2+I2+K1+M3+O1+ 2*(B3+I3+K2+M1+O2)
B16: =SUM(B2:B3,E1,G1:G2,I1:I3,K1:K2,M1) + 2*SUM(K3,M2:M3,O1:O2) +
3*Q1

Whew! Now for the Solver set-up....

Target Cell:
$B$14, Min

By Changing Cells:
$E$1, $G$1:$G$2, $I$1:$I$3, $K$1:$K$3, $M$1:$M$3, $O$1:$O$2, $Q$1

Constraints:
$E$1 = integer
$E$16 >= $B$8
$E$4 >= $B$4
$G$16 >= $B$9
$G$1:$G$2 = integer
$G$4 >= $B$5
$I$16 >= $B$10
$I$1:$I$3 = integer
$I$4 >= $B$6
$K$1:$K$3 = integer
$K$4 >= $B$7
$M$1:$M$3 = integer
$O$1:$O$2 = integer
$Q$1 = integer

HTH.


Endnotes:

1. After using Solver with B14 as the Target Cell, change the Target
Cell to B15 and click on Solve again, __without__ blanking the
variable cells in E1:Q3. This might improve the solution with the
additional goal of minimizing the amount of scrap.

2. Note that the constraints are ">=" instead of "=". If you used
"=", Solver usually might not find a solution with integer values in
the variables. Solver will silently use non-integers.

3. There may be multiple optimal solutions. Solver merely finds one.
There may be subjective reasons for you to choose one of the other
optimal solutions -- or even a non-optimal solution. I think it is
best to think of the Solver result as a starting point, not
necessarily a final answer.

4. I am a Solver neophyte. Experts might weigh in with improvements
or a completely different and better approach.

 

[Dana DeLouis]

1 of the 5+3+3 pattern

2 of the 5+4+3 pattern
1 of the 9+3 pattern

Hi. Excellent catch! I think you're right. This is a "better" choice.
I didn't use as many patterns as you. I had only 6.
For mine, I think I could have done better by changing the logic.
Ideally, as in your solution, would have been to think of using the 4th
piece of material to cut the "smallest" piece (3'), and have the rest (9')
available for something else.
If no solution, run the solution again to cut a 4' section from the 4th
piece, etc.
So, run Solver with the constraint to only make 4-3' pieces instead of 5-3'
pieces.
If you get a solution with 3 sections of material, Great! Just remember to
use a 4th piece to cut the remaining 3' piece.

I selected my range, and ran a small program. I haven't look at the code in
awhile, especially since Excel 2007. However, I think this is ok for now...
For the OP, go to the worksheet, and start Solver. Then close it.
Paste the following code in a regular module.
In the vba editor, select Tools - References - Solver.
Then, run code. This "should" set the problem up for you. ???

Sub MakeSheet_1()
'// Currently, Range Names first...
ActiveSheet.Names.Add "Bin", [B2:B7]
ActiveSheet.Names.Add "Actual", [D9:F9]
ActiveSheet.Names.Add "Required", [D10:F10]
ActiveSheet.Names.Add "Target", [F11]

[A2:A7] = [{"P1";"P2";"P3";"P4";"P5";"P6"}]
[D1:F1] = [{"C3","C4","C5"}]
[D2:F7] = [{0,0,2;2,1,0;2,0,1;1,2,0;1,1,1;4,0,0}]
[D10:F10] = [{4,2,3}]

[D9].Formula = "=SUMPRODUCT(Bin,D27)"
[E9].Formula = "=SUMPRODUCT(Bin,E2:E7)"
[F9].Formula = "=SUMPRODUCT(Bin,F2:F7)"
[F11].FormulaArray = "=SUM(Actual,-Required)"

'// Borders not Recorded at this time...
With [Bin].Interior
.Color = 65535
End With

With [Target].Interior
.Color = 49407
End With

With [Bin]
.HorizontalAlignment = xlCenter
.NumberFormat = "#,##0"
End With

With [D2:F10]
.HorizontalAlignment = xlCenter
End With

'// Comments
With [F9]
.ClearComments
.AddComment "Row of Actual Production"
End With

With [F10]
.ClearComments
.AddComment "Row of Required Production"
End With

'// Solver Section...
Const Minimize As Long = 2
Const GreaterThan = 3
Const AsBinary As Long = 4
Const ByChanging As String = vbNullString

SolverReset

SolverOptions _
Precision:=0.000001, _
AssumeLinear:=True, _
AssumeNonNeg:=True

Solverok [Target], Minimize, ByChanging, [Bin]
SolverAdd [Actual], GreaterThan, [Required]
SolverAdd [Bin], AsBinary
SolverSolve True

End Sub


So, Thanks again for this Catch.
I learned something from this example! :>)

= = = = =
As a little side note...

1 of the 5+3+3 pattern
2 of the 5+4+3 pattern
1 of the 9+3 pattern
That results in only 3 feet of "scrap" plus an extra 9-foot length.

The total scrap should be 10', and you mention 12' from above.
I show you have the correct 10' scrap as:
1+ 2*0 +9 = 10.

Anyway..Thanks again. :>)

 

[joeu2004]

Errata....

B16 computes the number of cuts. The formulas are:
[....]
B16: =SUM(B2:B3,E1,G1:G2,I1:I3,K1:K2,M1) + 2*SUM(K3,M2:M3,O1:O2) +
3*Q1

I believe the formula for the number of cuts should be:

=B2+B3+E1+G1+I1 + 2*SUM(G2,I2:I3,K1:K3,M1:M2) + 3*SUM(M3,O1:O2,Q1)

I was counting the number of "+" in my labels. I overlooked the scrap
cut. I would not have made this mistake if I had included the scrap
length in my labels (e.g. 4+3+3+1 instead of 4+3+3).

Improvement....

7+5: E7: =I1
6+5: E8: =K1
5+5: E9: =M1
5+4+3: E10: =M2
5+3+3: E11: =M3
#5: E16: =sum(E7:E15,E9)
[ ....etc.... ]

I did not need to enumerate the patterns again. I could have referred
to the variable cells directly in the SUM() expression; e.g.
=sum(I1,K1,M1:M3). The above design just reflects my style; it makes
it easy to double-check.

 

[brownti via OfficeKB.com]

I'm not sure how to send a private message to you, but if you would email me
a sample worksheet i would appreciate it. Thanks.

[repost due to apparent Google Groups error]

Well you seem to know what you are talking about, but i dont follow...
I think this might be beyond what i am comfortable attempting...

Dana's approach is similar to mine. So you might be uncomfortable
with my response as well. But I am able to set it up in a form that
allows for Solver to be used.

The problem with using Solver is: there are really 3 results to
minimize. They are: (1) number of raw material in 12-foot lengths;
(2) amount of scrap (see my definition below); and (3) number of
cuts. Solver can only minimize one result at a time. Presumably we
would choose #1 (number of 12-foot raw material); but that might not
minimize #2 (amount of scrap). (But see the Endnotes.)

I define "scrap" to be a length of 1 or 2 feet. Longer pieces are not
really scrap because they might be used for other projects that
require material in the same lengths, namely 3-12 feet.

I might note that with the set-up described below, it might be just as
easy (or easier!) to find the optimal solution manually by trial-and-
error.

My set-up is quite complicated to describe. It would be easier to
send you the Excel file. Feel free to send me email for that.
Needless to say, there is nothing sacrosant about my choice of cells
to use. You might prefer a very different layout. That said, here
goes....

Let B1:B10 represent the required number of 12-, 11-,..., 3-foot
lengths. These are cells in which you enter your requirements.

The following cells will contain the number of each indicated pattern
(with the amount of scrap in parentheses). These are the Solver
variables ("by changing cells"), which we want to vary to find an
optimal solution. Usually, it is prudent to blank these cells each
time before using Solver.

E1: 9+3
G1: 8+4
G2: 8+3 (1)
I1: 7+5
I2: 7+4 (1)
I3: 7+3 (2)
K1: 6+5 (1)
K2: 6+4 (2)
K3: 6+3+3
M1: 5+5 (2)
M2: 5+4+3
M3: 5+3+3 (1)
O1: 4+4+3 (1)
O2: 4+3+3 (2)
Q1: 3+3+3+3

As you might imagine, the gaps between columns are used for
descriptive labels.

The following cells compute the sum of the number of each cut length
produced by the solution. The summation cells are used to specify the
Solver constraints.

#9: E4: =sum(E1:E3)
#8: G4: =sum(G1:G3)
#7: I4: =sum(I1:I3)
#6: K4: =sum(K1:K3)

7+5: E7: =I1
6+5: E8: =K1
5+5: E9: =M1
5+4+3: E10: =M2
5+3+3: E11: =M3
#5: E16: =sum(E7:E15,E9)

8+4: G7: =G1
7+4: G8: =I2
6+4: G9: =K2
5+4+3: G10: =M2
4+4+3: G11: =O1
4+3+3: G12: =O2
#4: G16: =sum(G7:G15,G11)

9+3: I7: =E1
8+3: I8: =G2
7+3: I9: =I3
6+3+3: I10: =K3
5+4+3: I11: =M2
5+3+3: I12: =M3
4+4+3: I13: =O1
4+3+3: I14: =O2
3+3+3+3: I15: =Q1
#3: I16: =sum(I7:I15,I10,I12,I14,3*I15)

B14 computes the total number of 12-foot raw material. That is the
"target cell" for Solver. B15 computes the amount of scrap. B16
computes the number of cuts. The formulas are:

B14: =SUM(B1:B3,E1,G1:G2,I1:I3,K1:K3,M1:M3,O1:O2,Q1)
B15: =B2+G2+I2+K1+M3+O1+ 2*(B3+I3+K2+M1+O2)
B16: =SUM(B2:B3,E1,G1:G2,I1:I3,K1:K2,M1) + 2*SUM(K3,M2:M3,O1:O2) +
3*Q1

Whew! Now for the Solver set-up....

Target Cell:
$B$14, Min

By Changing Cells:
$E$1, $G$1:$G$2, $I$1:$I$3, $K$1:$K$3, $M$1:$M$3, $O$1:$O$2, $Q$1

Constraints:
$E$1 = integer
$E$16 >= $B$8
$E$4 >= $B$4
$G$16 >= $B$9
$G$1:$G$2 = integer
$G$4 >= $B$5
$I$16 >= $B$10
$I$1:$I$3 = integer
$I$4 >= $B$6
$K$1:$K$3 = integer
$K$4 >= $B$7
$M$1:$M$3 = integer
$O$1:$O$2 = integer
$Q$1 = integer

HTH.

Endnotes:

1. After using Solver with B14 as the Target Cell, change the Target
Cell to B15 and click on Solve again, __without__ blanking the
variable cells in E1:Q3. This might improve the solution with the
additional goal of minimizing the amount of scrap.

2. Note that the constraints are ">=" instead of "=". If you used
"=", Solver usually might not find a solution with integer values in
the variables. Solver will silently use non-integers.

3. There may be multiple optimal solutions. Solver merely finds one.
There may be subjective reasons for you to choose one of the other
optimal solutions -- or even a non-optimal solution. I think it is
best to think of the Solver result as a starting point, not
necessarily a final answer.

4. I am a Solver neophyte. Experts might weigh in with improvements
or a completely different and better approach.

 

[joeu2004]

I'm not sure how to send a private message to you, but if you would
email me a sample worksheet i would appreciate it. Thanks.

I tried to send email to brownti "@" officekb.com, but apparently that
is not your email address. My email address is joeu2004 "@"
hotmail.com.

 

[brownti via OfficeKB.com]

Joe tried sending you an email but it must not have gone through. If you
could send me a worksheet at brownti "@" uwstout.edu that would be great.
thanks.