Solver not working for me

[Dean]

I'm having positing problems to boot, so I don't even know if this will make
it to the newsgroup, but I hope so. If it does, I'll see it. Though I
seldom use solver, I recall it to be powerful. I wanted to show some other
users how nice it is, but it is not working for me. I concocted an example
with only nine integer choices for an input, values of 1 thru 9. I asked it
to maximize an output cell. Using a data table, I can quickly see that the
output cell's curve is concave down and definitely has a clear maximum in
about the middle. Bu, for some reason, Solver will not budge from whatever
starting integer value I give it. It says it has found a solution but the
solution is always whatever value it had when I started the solver.



I am simply saying maximize the output cell subject to constraints that the
input cell (that I am changing) being an integer, being greater than or
equal to 1, and being less than or equal to 9. I have checked and rechecked
and there just doesn't seem to be any reason this is not working. It can
find the minimum (which is at one of the two endpoints) just fine. I notice
that it takes about 20 seconds (and you see some fleeting calcs at the
bottom left) to find that minimum, whereas it thinks it finds the maximum in
about 10 seconds, and you don't see much of the fleeting calculation.



Can anyone explain how this could happen? I don't think I'm doing something
stupid, I tried an example with a much simpler output cell, output cell
equals input cell plus 2, and it found that constrained maximum just fine,
so the solver seems to be working. I can't fathom what the problem can be.
I've used it before and it solved much harder problems.



Thanks!

Dean

 

[Bill Renaud]

I am not familiar with Solver, since I haven't used it, but I can guess
that maybe the problem is with your forcing the input to be (or round off
to) an integer. A lot of mathematical techniques attempt to take a small
step in one direction, then effectively compute deltaY/deltaX. In this
case, you end up with 0/0, which is indeterminate.

I am guessing that maybe you should try removing the integer requirement
from the input variable, let Solver find the maximum, then round the input
value off to the nearest integer, or evaluate the result at both integral
values on both sides of the result, then choose the best value.

Solver may not be designed to work with problems where the input variable
is a quantized variable in this fashion. What does the documentation say?

 

[Dean]

No - one of the canned constraints is that it be an integer, so it's
definitely allowed. Nevertheless, I took it out and it didn't help. I took
out all the constraints and that didn't help either. It's really bizarre
to me. Solver actually says it has found a solution, but the solution is
always the same as whatever value you start it off with. I was thinking
that I had too high numbers for some of the options, such as convergence,
etc, but I set them all really low, as EXCEL help suggested to do, and it
did not help.

D

 

[Bill Renaud]

Does the vendor have a tech support group or peer-to-peer self-help message
board (like this one)? You might have to repost this question (with a
little more detail about the function you are using) to that forum.

 

[Bill Renaud]

Are you using the Excel Solver add-in, or the one from Frontline Systems?
If using the Excel Solver, then post your worksheet setup (cell values and
formulas) or post to the worksheet functions newsgroup.

 

[Bill Renaud]

I set up a sample problem similar to your description, and it seems to work
fine (I use Excel 2000).

B1: value
B2: =-1*((B1-5)^2)+10

This is a parabola, with the maximum at 5 and cupped downward, like you
mentioned.

Solver Parameters:
---------------------
Set Target Cell: $B$2
By Changing Cells: $B$1
Subject to the Constraints:
$B$1 <= 10
$B$1 = integer
$B$1 >= 0

Options: (I left everything at the defaults)
--------------------------------------------
Max Time: 100 seconds
Iterations: 100
Precision: 0.000001
Tolerance: 5%
Convergence: 0.0001

All checkboxes OFF (Assume Linear Model, Assume Non-Negative, Use Automatic
Scaling, Show Iteration Results).

Estimates: Tangent
Derivatives: Forward
Search: Newton

I could start with cell $B$1 at 0 or 10, and it would converge to
4.9999999824217 in about 1 second.

 

[Dana DeLouis]

Could you give us the function of your Target Cell?
Feel free to send me your workbook, and I'llbe glad to take a look at it.

 

[Dean]

It's an NPV function, which is a polynomial. I'll e-mail it to you.

Thanks much!
Dean

 

[Dean]

I am using the EXCEL solver. Now that you mention Frontline, it rings a
distant bell in my memory, such as them sending me stuff about some of their
more advanced stuff. I am hoping that the EXCEL version is capable of
understanding its own NPV function but am, now, starting to wonder if it
can't handle that one; and that frontline told me that 10 years ago!

Thanks! Dana has offered to help but if he can't, I'll post where you say -
I assume you mean that this is another Microsoft newsgroup.

D

 

[Bill Renaud]

(Excel Solver add-in that won't converge.)

Dean wrote:
<<It's an NPV function, which is a polynomial.>>

Is the setup too complex to post here in the newsgroup, for the benefit of
other viewers?

 

[Dean]

Yes, it would take too long for folks to recreate, plus I doubt it would
provide any insight to the problem. If there is somewhere I could post the
spreadsheet, I'd be happy to do so. It is a small one, albeit with some
hairy equations.

Thanks for asking, Bill
Dean

 

[Dana DeLouis]

Hi. Got your sheet. I can see what the problem is.
Although your Target Cell does not use any "Discontinuous functions," the
Target Cell is dependent on many cells that do use these functions.
The Target Cell is dependent on many uses of the IF function. This is the
problem !!

But, for some reason, Solver will not budge from whatever starting integer
value I give it.

I'll try to give a quick explanation as to the problem.
In a nutshell, Solver can easily get confused, and when it does, will often
give up immediately without a warning. This is a known issue.

Lets look at one of your dependant cells.
=IF(G12>$I$26,0,IF(G12<$I$26,0,-$I$7)+$I$7*$E$27*-1)

(G12 and I26 represent Integer Years)

Even if G12 were "suppose" to equal I26, and tolerances in Excel might show
these as unequal. Hence, a problem.
Suppose we do start off with an integer guess like you mention.
Only 1 of these cells would show a value and in theory would work as
planned.
However, on the very next guess, the value of your changing cell would most
likely "NOT" be a true integer. (Even though the constraint is integer).
Excel does not start out with most of the integer constraints set at true
integers. Later on, it will try to get them "closer" to integer values.
So, on the next guess, "ALL" of the equations like that above come into
play. This is enough to confuse Solver, and will quit immediately.
That is one reason the use of IF functions will not work in Solver.

Your equation above might be written like this:
IF G12 = "Integer Changing Cell, then ...

This would almost NEVER be true.

The whole model would have to be re-written.
It appears to me that one solution might be the following.
Select 9 Cells as your changing cells. Make the constraint "Binary" (ie 0
or 1)

Also, in another cell, Sum these 9 Cells.
Add a constraint that the sum of these 9 cells =1.
(Actually, I might use >=0.9 and <= 1.1 since we want to avoid problems of
equality.

Now, Solver will put a 1 in only 1 of the 9 Cells. It is up to you to use
that 1 value and calculate a value.
The cell that ends up with a 1 represents the number of years.
Anyway, hope this helps a little.

 

[Dean]

Oh, I missed this. Yes, I also tried the default settings. Believe me,
I've used solver before in the past with no such problems, for generally
hairier workbooks than this.

Dean

 

[Dean]

Interesting that, despite what you refer to as giving up, Solver always says
it has found a solution. I guess that's part of the known issue. The EXCEL
imprecision is something that I recall from long ago and, to this day, I
will often write if statements that say, if (abs(A-B) <0.00000001, ...)
which confuses readers but covers tiny roundoff. That said, slowly over the
years, I do this less often since I don't notice the problem being there.
Perhaps it was only there, even back then, when using things like solver.

It will take me a little while to understand your workaround but, in the
meantime, I first tried replacing all the integer cell references "X" with
round(X,0) but that did not help. I then replaced all if statement
arguments with:

abs(x-y)<-0.1, abs (x-y) > 0.1, or abs(x-y)< 0.0001, Since x-y will always
be infinitesimally close to an integer, this should work. But it didn't.
Assuming I didn't miss one (and my plot of the data, table results seems to
confirm the 9 values are unchanged - also if I try 3.99999, rather than 4,
manually it produces the same answer), shouldn't this have also worked as a
workaround? Or, perhaps, I am missing the point.

Thanks so much for your analysis.

Dean

 

[Bill Renaud]

After experimenting some more with the hypothetical problem that I posted
earlier, it appears that Solver ignores any Integer constraints on a
variable, then simply rounds the answer off to the nearest integer after
the convergence has finished.

For example, if I set my parabola to peak at 4.49, then Solver returns 4 as
the answer. If I set the peak at 4.51, then Solver returns 5 as the answer.

 

[Dean]

If true, that seems very misleading. It would seem to me that the closest
integer could be much further off from the maximum than some other integer
that may not be as close to where the best solution is, depending upon the
nature of the curve.

Or am I missing something?

Dean

 

[Dana DeLouis]

Hi. Just some thoughts.

if (abs(A-B) <0.00000001

In General, ABS is another function that can not be used with Solver.
A variable (say B) will most likely never get that close to return a True
value ( ie < 0.00000001. )
Look under Solver's options for (precision and Tolerance)

Suppose Solver's variable varies between 4.9 and 5.1

=ABS(5-5.1)
=ABS(5-4.9)

Both of these solutions return the same answer.
In addition, the slope reverses direction.
This is enough to confuse Solver, and give up without warning.

round(X,0)

Note however, that

=ROUND(3.6,0)
=ROUND(4.3,0)

Both of these return the same answer. This is enough to confuse Solver, and
give up.
Therefore, Round is another function that can not be used with Solver.

It now becomes an art to rewrite your model with functions that Solver can
use.

Here's an small example. Suppose you need to pick 1 of 2 variables (v1 and
v2).
The beginners method would be to use an IF statement.
However, lets use a changing cell whose constraint is "Binary" (0 or 1)

The function might be

=v1*B + v2*(1-B)

If Solver picks B=1, then the function returns V1 (other goes to zero)
If Solver picks 0, then the function returns V2 .

Solver "CAN" keep track of jumps using this technique.

Hope you see the pattern.

Anyway, hope this helps.

 

[Bill Renaud]

Dean wrote:
<<It would seem to me that the closest integer could be much further off
from the maximum than some other integer that may not be as close to where
the best solution is, depending upon the nature of the curve.>>

You're point is quite valid.

My "parabola" example was probably overly simplistic. Upon further thought,
it might be that Solver finds the maximum, then checks each of the
variables that are constrained to be an integer, then checks each
combination to see which combination produces the maximum.

Extending my previous "parabola" example to 2 independent variables,
suppose that you have a "hill" made by 2 variables: X and Y. The result is
given by Z. Then suppose Solver finds the optimum answer at X=4.5 and
Y=4.5, with Z=10 in this case. The iteration table might look like the
following:

Iteration X Y Z
--------- --- --- ----
1-4 - - -
5 4.5 4.5 10.0
6 4.0 4.0 8.2
7 5.0 4.0 8.1
8 4.0 5.0 8.3
9 5.0 5.0 7.9

I would hope that Solver would then "walk around" the optimum point (X=4.5,
Y=4.5) to get the best answer, which would be X=4.0 and Y=5.0 (Z=8.3).
Hopefully, the problem remains fairly-well behaved around this area, but
then the Sensitivity report should probably be checked to verify this.

I haven't spent the time trying to develop some functions that would create
a "known hill" like this, so that I could verify this behavior. Hopefully,
somebody else will have some input on this.

 

[Bill Renaud]

The Sensitivity report is not generated for problems with variables
constrained to an integer.

 

[Bill Renaud]

See "How to Find Resources on Microsoft Excel Solver" at
http://support.microsoft.com/kb/146606

Also, see "Solver Uses Generalized Reduced Gradient Algorithm" at:
http://support.microsoft.com/kb/82890/EN-US/