Solver not working for me

[Bill Renaud]

The web page http://www.solver.com/academic.htm ("Academic Users of
Optimization Start Here") on the Frontline Systems, Inc. web site contains
a link to download the following document:

"Design and Use of the Microsoft Excel Solver" by Daniel Fylstra, Leon
Lasdon, John Watson and Alan Waren in INFORMS INTERFACES 28: 5
September-October 1998 (pp. 29-55).
http://pubsonline.informs.org/main/pdfstore/DesignandUse_article.pdf

See page 17 for their discussion of how integer constraints are handled at
the end after the optimum point has been found.

 

[Dean]

Yes, it's all very interesting, but it's getting a little beyond me. Dana
seems convinced that Solver just won't work with various EXCEL functions
(that you have to be really clever to reformulate things so that solver will
work with it) and, if so, I am surprised that such is not really noted in
the long, seemingly thorough document of your link below (which is 10 years
old, so things should be better, certainly no worse, by now). There is some
mention of certain functions but it is not clear what they are saying. As I
mentioned, even without integer constraints, this EXCEL solver dog 'does not
hunt' (would not solve).

Just to review, this was not a problem that I needed to solve per se. I was
giving a free conference lecture about the wonders of analysis of EXCEL to
analysts (I got loud applause with goal seek, sensitivity via data tables,
etc, etc) and, at the last minute before the presentation, remembered that
for, constrained problems there was solver. So, I prepared a typical
example they might face and was going to show them how to solve it with
solver. Well, it wouldn't work, but I finessed my way thru the presentation
without them knowing - I set the initial point to the value that I already
knew would produce the maximum, had solver run, which told us it had found a
solution, even though, in reality, I knew it didn't even look! So now, I'm
just trying to decide if I should omit solver in my hard copy to be posted
on a website of theirs. I think I need to.

I have vague recollections of, a decade or more ago, talking to Frontline,
perhaps about similar issues, and them telling me they had better versions I
could buy. At this point, it is an issue of academic interest to me, but
nothing urgent. I would appreciate any research you guys want to do.

My conclusion right now is that Solver is pretty useless for anything
reasonably complicated, enough such that Dana's reformulation is not worth
all the effort. Sad to say.

D

 

[Bill Renaud]

I remember studying mathematical optimization techniques for computers way
back in engineering school, so I remember some of the concepts. It is clear
to me that you cannot have step functions or other non-continuous functions
in the model, because that causes the search to get lost.

Basically, at each point, the technique is to take a small step in the
direction of each independent variable, then calculate the "slope" (partial
derivative of F with respect to X) of the function. Then the next point is
calculated by moving all independent variables in the appropriate
direction. If you have any functions in your cells that return the same
result (say 0) when this small step is taken, then the slope appears to be
0, so the technique concludes (wrongly) that it is at the "top of the hill"
(maximization problem) and then stops.

You simply have to take all of the non-continuous functions out of your
model (i.e. ROUND, ROUNDDOWN, ROUNDUP, RAND,
IF(var1<>0,SomeValue,OtherValue), etc.).

I believe that Solver really is a powerful tool and can be used in a lot of
situations, as long as you understand the setup and usage requirements
first.

I guess the other lesson (or rule) is: Always double-check your
presentation demos before class! (You always get questions that can test
your credibility anyway!)

 

[Bill Renaud]

As Dana mentioned, you had one cell with the following formula:
=IF(G12>$I$26,0,IF(G12<$I$26,0,-$I$7)+$I$7*$E$27*-1)

Essentially, this is like a large, flat field with a "pin" pointing upward
somewhere out in the middle of the field. When Solver plugs values in to
this formula, it always gets 0, unless it just happens to land right on top
of the "pin", the probability of which will be essentially "never".
Therefore, Solver stops iterating, because it thinks that it has reached
the top of the "hill".

Simply change that particular cell to:
-$I$7+$I$7*$E$27*-1

 

[Dean]

I understand what you are saying. I'm just perturbed that EXCEL doesn't
seem to do a better job of telling you what functions you can't use, or must
work around.

 

[Dean]

Actually, if you look at the 2nd IF carefully, there are two possible
non-zero results. Regardless, I don't understand your recommended change.
Even if I assumed that g12<i$26 produces zero also, that result you
recommend is only valid for $i$26 = the integer in g26, not just any
integer. In fact, in the next cell down, where this formula is copied, that
result would be valid only when $i$26 = the integer in g27. Ultimately, the
result happens in only one of those 9 cases (where the g column contains the
integers between 1 and 9). I don't see how it is this easy.

If you're curious yellow and actually want to, I can send you my spreadsheet
class example to rework. I don't really need the problem solved, just want
to know if it could be reworked easily enough that I could suggest to
students that solver is worth using for common EXCEL problems (which, in my
mind, have lots of such discontinuities about which one has to work around).

I wonder if any of Frontline's more advanced products somehow do a
conversion for you?

Thanks much, Bill.
Dean

 

[Bill Renaud]

Dean wrote:
<<Actually, if you look at the 2nd IF carefully, there are two possible
non-zero results.>>

You are correct. I didn't look at the formula carefully enough! This still
causes a discontinuity, though, since the value of the cell will always be
zero anytime G12 is greater than $I$26. Apparently, Solver isn't
sophisticated enough to work around discontinuities (or work when the
formula changes slope near a limit). I guess a user would have to do a grid
search first, to get an idea of where the maximum or minimum would be, then
narrow down the limits to a smaller area around this.

Yes, I would like to have your workbook, if you can also include a brief
explanation of what the practical application is.

I think your point is quite valid about Solver not being very useful, if a
user has to make a large number of changes to a model to remove all of the
discontinuities first.

 

[Dana DeLouis]

...Target cell.. integers between 1 and 9.

Hi. Your Adjustable cell is "Years of Refinance" and is an integer between
1-9.
Based on a simple look at the model, I think it is best to re-write your
model.
This is a fairly common technique in other Solvers as well.
This is not complete, but have your years listed 1-9.
Then have adjacent "Binary" adjustable cells next to the years.
Add the constraint that the sum of the Binary cells =1.

NOW, your "Years of Refinance" becomes the Formula =Sumproduct(Year,Bin)
(Only 1 number, 1-9 will show up here)
Do you see how this works now?

You have a "Backstop Payback" column that uses an IF function. As we know,
"IF" don't work with Solver. However, if is now easy to fix. The formula
now becomes =Bin*CumBackstop.
It is this technique that we are able to eliminate IF formulas.
Solver won't get confused now because it is keeping track on Integer &
Binary changing cells.

You are also using a few MAX Formulas in other columns, so they are major
problems as well.

It really becomes an Art at this point to adjust your model.

When dealing with complex financial models, and especially
Least-square-fitting, one must be aware that Solver locks on "Local"
mim/max, and will not find Global optimization.

Let's look at a simple example.
ie: Maximize Sin(x)/x.

If we start start with x=12, and run Solver, we will get 1 solution.
However, it is the "local" solution, and not the best solution.
If we start with 5 or 6, and run Solver, we will get another solution.

However, if we start with 0, then the function has an Error (Div/0!), and
Solver will not even start. However, 0 is the correct solution!! Both
Excel, and Solver are not aware of this. Not that there is anything wrong
with Solver, you just have to know some of its limitations.
In fact, if Solver is searching around 0, and selects 0, Solver will abort
with an Error, despite that fact that 0 is the correct solution.
We would want to go to Solver's options and make Solver work a little
harder.

Again, more of an art than a science at this point.

 

[Dean]

Bill,

I would be happy to send the file and an explanation. However, I want to be
clear that it was a concocted example so that students could see how solver
might be used. It is not a problem I need the solution to and, now that I
realize how hard I would have to work to recast the equations, I really
don't have any interest in pursuing it any further. It sounds like Dana has
suggested a not too hard way to go, so there is no need to put yourself out
over this.

Bottom line, I will send it to you if you want it for your own intellectual
curiosity, but the practical application is totally concocted and I don't
need/want the answer. Actually, with only nine possible solutions, I can
use data table to test all nine!

Let me know what YOU want.

Thanks much!
Dean

 

[Dean]

Very informative, Dana. Thanks much!

Dean

Hi. Your Adjustable cell is "Years of Refinance" and is an integer
between 1-9.
Based on a simple look at the model, I think it is best to re-write your
model.
This is a fairly common technique in other Solvers as well.
This is not complete, but have your years listed 1-9.
Then have adjacent "Binary" adjustable cells next to the years.
Add the constraint that the sum of the Binary cells =1.

NOW, your "Years of Refinance" becomes the Formula =Sumproduct(Year,Bin)
(Only 1 number, 1-9 will show up here)
Do you see how this works now?

You have a "Backstop Payback" column that uses an IF function. As we
know, "IF" don't work with Solver. However, if is now easy to fix. The
formula now becomes =Bin*CumBackstop.
It is this technique that we are able to eliminate IF formulas.
Solver won't get confused now because it is keeping track on Integer &
Binary changing cells.

You are also using a few MAX Formulas in other columns, so they are major
problems as well.

It really becomes an Art at this point to adjust your model.

When dealing with complex financial models, and especially
Least-square-fitting, one must be aware that Solver locks on "Local"
mim/max, and will not find Global optimization.

Let's look at a simple example.
ie: Maximize Sin(x)/x.

If we start start with x=12, and run Solver, we will get 1 solution.
However, it is the "local" solution, and not the best solution.
If we start with 5 or 6, and run Solver, we will get another solution.

However, if we start with 0, then the function has an Error (Div/0!), and
Solver will not even start. However, 0 is the correct solution!! Both
Excel, and Solver are not aware of this. Not that there is anything wrong
with Solver, you just have to know some of its limitations.
In fact, if Solver is searching around 0, and selects 0, Solver will abort
with an Error, despite that fact that 0 is the correct solution.
We would want to go to Solver's options and make Solver work a little
harder.

Again, more of an art than a science at this point.

 

[Bill Renaud]

I would be curious to see the model and try Dana's changes. Can you save it
in Excel 2000 format before sending?

 

[Dean]

Ok, I have sent it to you. Feel free to share it with anyone you wish.