Dana: A different bug in Solver?

[joeu2004]

Solver is just quiting early because it got confused when the
starting values in B3:B4 are equal.

At least B3:B4 are within their constraints in this case.

But consider this following situation, which I have distilled from a
more complex formulation.

In A1:
=510-(IF(A2+510<123700,(A2+510-61300)*25%+8440,(A2+510-123700)*28%
+24040)
-IF(A2<123700,(A2-61300)*25%+8440,(A2-123700)*28%+24040))

In B1, put 371. Now use Solver to maximize $A$2, changing $A$2 with
the constraint $A$1>=$B$1.

When A2 is blank or less than 123700 (so far as I can tell), Solver
finds the right answer: about 123573.33 in A2 and 371 in A1. All
Options are the default. I am using Office Excel 2003.

But when A2 is initially 123700, 123750 or 123900 (to name a few),
Solver leaves those numbers in A2, with about 367.20 in A1 --
__less_than__ B1, which violates the constraint.

In other words, it is not a correct solution.

But if A2 is initially 123800, Solver works fine, even though A1 is
still initially about 367.20. That is, it finds the correct
solution: about 123573.33 in A2 and 371 in A1.

Can this really be dismissed as simple "confusion"? How is this not a
defect?

 

[Bernard Liengme]

The developers of Solver (Frontline Systems ) clearly state in many places
that the simple Solver in Excel (and QuattroPro) cannot handle discontinuous
expression such as those with IF, Vlookup, etc. Visit www.solver.com.

I also think the max of (x-y)^2 with x and y from 1 to 0 is a rather
contrived problem. The max of z^2 when z can only be 0 to 1 is clearly 1.

 

[joeu2004]

The developers of Solver (Frontline Systems ) clearly state in many places
that the simple Solver in Excel (and QuattroPro) cannot handle discontinuous
expression such as those with IF, Vlookup, etc. Visit www.solver.com.

Thanks for the pointer. But can you provide some URLs for the "many
places" where that limitation is mentioned?

What I do find at www.solver.com are many statements to the effect
that such "nonsmooth nonlinear" characteristics of a model make the
problem "hard", with solutions that might be only "locally optimal" or
not optimal at all. Here is one quote (emphasis added) from
http://www.solver.com/tutorial6.htm :

"Nonsmooth optimization problems -- where the relationships may
include functions like IF, CHOOSE, LOOKUP and the like -- __can_be__
solved up to scores, and occasionally up to hundreds of variables and
constraints, given enough memory and time. You can only have
confidence that the solutions obtained are "good" (i.e. better than
many alternative solutions) -- they are not guaranteed to be globally
or even locally optimal."

Note that it says that Frontline's Solver __can__ solve such problems,
at least sometimes, in contrast to your blanket "cannot" assertion.

On the other hand, it is true that Frontier does also make the
following statement (on the same web page; emphasis added):

"A model that consists of mostly linear relationships but a few
nonlinear relationships generally must be solved with more 'expensive'
nonlinear optimization methods. The same is true of models with
mostly linear or smooth nonlinear relationships, but a few nonsmooth
relationships. Hence, a single IF or CHOOSE function that depends on
the variables __can__ turn a simple linear model into an extremely
difficult or even unsolvable nonsmooth model."

Note that it says that it __can__ (might) be unsolvable, but not
necessarily so. Moreover, I hasten to point out that I used the
default Solver options, which deselect the Assume Linear Model
option. I ass-u-me that means that Solver uses the "more expensive
nonlinear optimization method", which is needed to solve such
"nonsmooth" models, if they can be solved at all, according to the
Frontline web page.

That said, I do agree that you have offered a __potential__
explanation of the behavior. Without detailed knowledge of
Frontline's algorithms, it is hard to say. I find it surprising that
Solver works fine when the target cell is empty, but it finds "no
solution" (i.e. a solution that violates the constraint) when the
target cell has certain values.

Perhaps the "right" answer for my example is: Solver is taking the
value in the target cell as a "guess" and progressing from there. If
that is not the user's intention (it was not mine; I did not select
the Guess option), perhaps it is best to leave the target cell empty.
(But presumably, offering a guess somehow might, in fact, improve
Solver's result sometimes.)

My greater concern is that Solver does not offer any indication of the
"quality" of its result. In this case, I think it should have warned
the user that the result is "no solution" at all, since it violates
the constraint.

Bottom line: bugs or not, I think the user should be very cautious
about relying on results from Solver. It behooves the user to study
the result carefully to be sure that it is a solution at all. Even if
it is, the user should not assume that it is optimal, even locally.
(Sigh!)

 

[Harlan Grove]

. . . I find it surprising that
Solver works fine when the target cell is empty, but it finds "no
solution" (i.e. a solution that violates the constraint) when the
target cell has certain values.

....

Target cell is empty? Dunno 'bout you, but when I run Solver with an
enpty target cell, it immediately displays an error dialog with the
message, 'Set Target Cell contents must be a formula.' Not so for you?

 

[Dana DeLouis]

Can this really be dismissed as simple "confusion"? How is this not a

defect?

Hi. I understand that you want to Maximize "A1" by Changing A2, with
the constraint that A1 hopefully > B1 (ie 371)

I copied your equation (named equ) to A1 and placed different values in
B1 and got your same results.
I wasn't sure on your Target Cell Equation, so I threw it at another
program...
equ // PiecewiseExpand

If I am not mistaken, your complex equation can be re-written as:
382.5 if A2 < 123190
367.2 if A2 >= 123700
and
0.03*(135940-A2) in between.

What this seems to indicate is that the output is fixed, except between
123190 thru 123700 where it is linear.

I'm curious of your linear part...

If I copy your the linear equation with the two constraints...

v={0.03*(135940.-A2),A2>=123190,A2<123700};

Find Max and Min within this range...

Maximize[v,A2]

{382.5,{A2->123190.}}

Minimize[v,A2]

{367.2,{A2->123700.}}

The Max and MIn points are at the two ends.
What this says is that your output is fixed at both ends, with a simple
linear change in between.

If I copy your equation down, and have different values in Column B,
this appears to confirm the above.

This explains Solver's behavior. You have a large range where the value
is fixed. When Solver detects the output is not changing with
changing inputs, it usually gives up quickly.

I believe the Maximum is 382.5 when A2 <= 123190

Hope this helps. :>)
Dana DeLouis

 

[joeu2004]

I understand that you want to Maximize "A1" by Changing A2, with
the constraint that A1 hopefully > B1 (ie 371)
No....

I wasn't sure on your Target Cell Equation

I wrote: "Now use Solver to maximize $A$2, changing $A$2 with the
constraint $A$1>=$B$1". In Solver, the only thing that can be
"maximized" is the Target Cell. Ergo, $A$2 is the Target Cell. (It
is also the By Changing Cell.)

If I am not mistaken, your complex equation can be re-written as:
382.5 if A2 < 123190
367.2 if A2 >= 123700
and
0.03*(135940-A2) in between.

Perhaps. I see no point in parsing the details. The example was
distilled from a much more complex model that cannot be reduced so
simply. I chose to retain some of the complexity of the structure of
the formula. I saw no harm in doing so since anyone can cut-and-paste
what I wrote easily. I believe the actual formula is unrelated to the
question (Solver's behavior) -- other than the fact that elements of
the formula seem to make the problem more difficult for Solver, as
Bernard noted. So it is good that I retained that complexity, if only
to facilitate duplication of my observations.

This explains Solver's behavior. You have a large range where the value
is fixed. When Solver detects the output is not changing with
changing inputs, it usually gives up quickly.

Perhaps. That makes sense. But I would still expect Solver to tell
me that it gave up before finding a solution that satisfies the
constraint(s).

And even with your conjecture, I do not see why putting 123800 into A2
allows Solver to find a correct (and optimal) solution, whereas that
is not so with 123750 and 123900. But arguably, that depends on the
internal algorithms that Solver uses. Who knows!?

Nonetheless, I do not see why putting __any__ value into A2 would
affect the behavior of Solver.

I think there is an aspect of using Solver that no one has yet
mentioned, namely (guessing): if a value is put into the Target Cell,
Solver uses that as an initial guess. Is that right?

 

[joeu2004]

Target cell is empty? Dunno 'bout you, but when I run Solver with an
enpty target cell, it immediately displays an error dialog

Did you try the example that I provided?

 

[Dana DeLouis]

...$A$2 is the Target Cell. (It is also the By Changing Cell.)

Hi. This should give you an error.
Target Cell is a formula you are trying to Maximize, Changing cells are
empty cells that Solver Changes to Maximize Target Formula. These should be
two different cells.

the correct solution: 123573.33 in A2 and 371 in A1.

This can't be correct because your constraint is that A1 >= B1 (ie 371)
A1 "can" be larger.

I may be wrong, but it appears you are trying to set Target Cell A1 "to a
value" of 371 by changing A2.

This would make sense based on your "solution."

I see no point in parsing the details...

Because I can visualize the solution you provided better with..

Solve[0.03*(135940 - A2) = 371]

A2 -> 123573.33

Instead of:

=510-(IF(A2+510<123700,(A2+510-61300)*25%+8440,(A2+510-123700)*28%
+24040) - IF(A2<123700,(A2-61300)*25%+8440,(A2-123700)*28%+24040))

It also explains your observed behavior...

But when A2 is initially 123700, 123750 or 123900 (to name a few),
Solver leaves those numbers in A2, with about 367.20 in A1

It also showed that you have a very narrow range in which your output will
change with changing input. I personally can not see that from your
equation.
I'm surprised Solver was able to solve this at all with such a narrow range.
It got lucky with a few of its guesses.

 

[Bernard Liengme]

I would be happy to send you a file with a "no target cell" Solver model
There is also an example at
http://people.stfx.ca/bliengme/ExcelTips/Solver.mht
best wishes

 

[joeu2004]

...$A$2 is the Target Cell. (It is also the By Changing Cell.)

This should give you an error.
[....] These should be two different cells.

Fine. Either way, it appears that Solver has a defect or design flaw,
namely: (1) it fails to flag "misusage" when the Target and By
Changing cells are the same; and/or (2) it fails to notify the user
when the result is not a solution (i.e. it violates one or more
constraints).

This can't be correct because your constraint is that A1 >= B1 (ie 371)
A1 "can" be larger.

I don't know why you think that is not a solution. If A2 is less than
123573, I believe A1>=B1 remains true. If A2 is more than 123573, I

I may be wrong, but it appears you are trying to set Target Cell A1 "to a
value" of 371 by changing A2.

Well, I am trying to find the largest A2 that makes A1 __as_close_
to__ 371 (but no less) as possible. But yes, the ideal solution would
set A1 to 371 (i.e. same as B1), if that is possible. You might be
correct that that is always possible in this example. But I am not
sure it is always possible in the real-world problem from which the
example was distilled.

I see no point in parsing the details...

Because I can visualize the solution you provided better with..
Solve[0.03*(135940 - A2) = 371]
A2 -> 123573.33
Instead of:
[... my complex formulation ...]

As I have said repeatedly, the example is a __distillation__
(simplification) of a much more complex model, which I deemed too
complex to post here and an imposition to ask experts to duplicate and
experiment with. I retained the complexity so as not to change the
problem that I encountered with Solver.

My primary interest was in pointing out alleged Solver misbehavior,
not in trying to solve my problem differently.

But since you express some interest in the real problem (model) and
you believe that I have constructed the Solver solution incorrectly, I
would be happy if you offered some ideas to improve or correct the
model, as a way of educating me on the use of Solver. Normally, I
would start a new thread. But I seem to have your attention here ;-).

I want to find the largest amount of taxable income at which it is
advantageous to invest x dollars in taxable bonds instead of tax-free
bonds.

The solution is straight-forward if we assume that the marginal tax
rate (combined state and federal) is the same with and without the
taxable interest. That requires only simple algebra; I do not need
Solver for that.

However, I believe the solution is non-trivial when: (a) we cross one
or more tax brackets, depending on the amount of interest (which
depends on the amount invested -- "x"); and/or (b) we cross state and
federal tax brackets at different "times" -- that is, the size of the
state and federal tax brackets differ significantly. (In particular,
compare the California and federal tax rate schedules.)

So I constructed the following model. I hope I can explain this well
enough without actually providing the spreadsheet. If my explanation
is insufficient for discussion and you are interested in working with
the spreadsheet, contact me by email.

A1: amount invested (input data)
A2: interest earned on taxable bond (=A1*APY1)
B2: interest earned on non-taxable bond (=A1*APY2)
A3: after-tax taxable interest earned
B3: after-tax non-taxable interest earned (=B2)
A4: taxable income before adding taxable interest earned

The formula for after-tax taxable interest (A3) is complicated. It is
taxable interest (A2) minus the difference between: (a) total tax
after adding taxable interest (A2) to other taxable income (A4); and
(b) total tax on other taxable income alone (A4). Total tax can be
computed in a variety of ways. I chose to enter 2006 federal and
state marginal tax rate schedules for MFJ, then construct appropriate
expressions to perform the evaluation.

I believe the optimatization problem becomes: find the largest
taxable income (A4) at which adding taxable interest (A2) results in a
larger or equal after-tax earned interest (A3>=B3). I believe the
solution space is continous.

Since I am trying to find the largest taxable income (A4), it seems to
me that A4 is the Target Cell for Solver. But A4 is not a formula; it
is one number that is input to the formula in A3.

If I were do solve this by brute force as a "what if" model, I would
repeatedly change A4 in a methodical manner (binary search) until I
found the largest A4 that satisfied the constraint A3>=B3 (and
preferrably A3=B3). For that reason, I ass-u-me-d that A4 is also the
By Changing cell for Solver.

Of course, A3>=B3 was entered as a Constraint. And all cell
references entered into Solver were absolute (e.g. $A$4), not the
relative references that I wrote here for convenience.

If that set-up is incorrect for Solver, I would appreciate it if you
would explain what I should do instead to construct a tractable
problem for Solver.

When I put a number (say 10000) into A1 (investment) for the first
time, A4 was blank, and Solver found an appropriate solution.

When I subsequently put a different number (say 100000) into A1, A4
was no longer blank. As I recall, Solver did not find an appropriate
solution -- that is, one that obeys the constraint (A3>=B3). It was
only after I deleted the contents of A4 again that Solver found an
appropriate solution.

Note: I am writing that historical description from memory. The
order might have been reversed, and I might used different numbers for
A1 when I encountered the problem.

 

[Harlan Grove]

Did you try the example that I provided?

I could have sworn I did, but I must have screwed something up.

 

[Harlan Grove]

Well, I am trying to find the largest A2 that makes A1 __as_close_
to__ 371 (but no less) as possible. But yes, the ideal solution would
set A1 to 371 (i.e. same as B1), if that is possible. You might be
correct that that is always possible in this example. But I am not
sure it is always possible in the real-world problem from which the
example was distilled.

....

Actually in the problem posed, the A1 formula could be simplified to

=IF(A2<123190,382.5,IF(A2<123700,4078.2-0.03*A2,367.2))

which is constant on A2<123190 and A2>=123700, and strictly decreasing
on 123190<=A2<123700. Since 382.5 and 367.2 bracket 371, this boils
down to finding A1=371=4078.2-.03*A2 -> A2 = (4078.2-371)/.03 =
123573.3333. The A1 formula varies only on a small interval of the A2
value. All of which Dana already pointed out.

Maybe Solver should abort with an error message when the target cell
doesn't contain a formula. In that sense, I'll go along with Solver
not behaving in the proper way.

However, I see this as good proof that a little algebra goes a long
way.

As I have said repeatedly, the example is a __distillation__
(simplification) of a much more complex model, which I deemed too
complex to post here and an imposition to ask experts to duplicate and
experiment with. I retained the complexity so as not to change the
problem that I encountered with Solver.

All newsgroup postings are impositions. What a fatuous excuse!

The A1(A2) formula you provided was a ramp function, which means the
inverse, A2(A1) is also a ramp function, so it attains it's maximum
value at either end of the ramp. If the constraint on A1 fell between
the interval bounds on which the ramp function varied, and that A1
value threw off a lower value of A2(A1), then that constraint point
would produce the constrained maximum value.

Graphing A2(A1) or A1(A2) would have shown the neighborhood of the
constrained maximum, thus providing additional constraints on A1.

My primary interest was in pointing out alleged Solver misbehavior,
not in trying to solve my problem differently.

....

Fair enough. Solver is inappropriate for this sort of function.

I want to find the largest amount of taxable income at which it is
advantageous to invest x dollars in taxable bonds instead of tax-free
bonds. ....
. . . I believe the solution space is continous.

....

It is continuous, but optimization algorithms usually require more
than just continuity. If you're aware of points at which a function
isn't differentiable, you should run solver between such adjacent
points.

As long as you're dealing with nontaxable interest that isn't an AMT
preference, all that matters is maximizing after-tax total income. You
do realize that this is further complicated by interest on US
Treasuries being tax-exempt in most states but subject to federal
income tax? So as I see it, you need three buckets: state and
municipal bond interest (tax-exempt at federal and state level), US
Treasury bond interest (taxable at federal level, tax-exempt at state
level), and all other interest income (taxable at federal and state
levels). Note that if you ignore state tax peculiarities in re US
Treasuries, the optimal interest income mix would include no US
Treasuries for ALL income levels.

If you throw in a state tax rate schedule that's significantly
different than the federal schedule, you may still have continuity,
but you won't have anything near differentiability, and I doubt the
free, stripped-down version of Solver that's bundled with Excel would
be able to handle it.

Use an x-y graph.

Or use some general reasoning.

If non-interest income already puts the individual into the top
marginal rate, maximum after-tax interest income would come from tax-
exempt interest if the yield exceeded the after-tax yield at the top
marginal rate, but from taxable interest if the after-tax yield
exceeded the tax-exempt yield. If the latter obtained, then there's no
maximum non-interest income at which it didn't make sense to max out
on taxable interest income.

If non-interest income puts the individual into the bottom marginal
tax rate, the same applies. If the after-tax yield on taxable interest
at the bottom marginal rate exceeds the tax-exempt yield, invest in
taxables up to the point at which total taxable income would kick into
the next higher bracket. Treat that portion of taxable income as non-
interest income, and continue the analysis above. If after-tax yield
on taxables at the bottom marginal rate is less than the tax-exempt
yield, invest entirely in tax-exempts.

If your yields are also variables, there may be no solution. If the
yields are taken as constants, you could solve this directly.

 

[Harlan Grove]

If non-interest income already puts the individual into the top
marginal rate, maximum after-tax interest income would come from tax-
exempt interest if the yield exceeded the after-tax yield at the top
marginal rate, but from taxable interest if the after-tax yield
exceeded the tax-exempt yield. If the latter obtained, then there's no
maximum non-interest income at which it didn't make sense to max out
on taxable interest income.

....

Actually that means that the mix between taxable and tax-exempt
interest income in the top marginal tax bracket is DISCONTINUOUS with
respect to the tax-exempt and after-tax taxable yields. Depending on
what they are, the indivudual should have all interest income from one
or the other, but never a mixture of the two.