Solver

[Alec Erskine]

I am delighted to see that Microsoft have made an important development in
Excel 2007 with their optimiser. You have effectively introduced a
combinatorial optimiser in Excel 2007 which was not available in Excel 2003.
This allows us to solve the “Knapsack problem†in Excel. The Knapsack
problem, sometimes called the Capital Investment problem is as follows.
Suppose we have a list of schemes, each with defined cost and defined
benefit, and we have a budget ceiling. Which schemes should we do to
maximise the total benefit, while keeping the total cost under budget? The
Excel version appears to use the fairly robust method of a standard linear
simplex optimiser combined with a branch-and-bound searcher. Can you
confirm?

An example involving 70 schemes with randomised C and B is easy to create.
There seems to be a small starting position effect in that you seem to have
to run the optimiser twice from 0’s to get it to work properly, it only gets
the “right†answer – or what I hope is the right answer on the second attempt.

I would have assumed that this optimser is independent of starting position
and am quite worried that it claims to have optimised when it has not. This
is a bug, really. Any thoughts as to why it is finishing at the wrong answer?

I cannot find any email addresses on your site to send this to and am being
warned not to send contact information. So I guess that's it then.

----------------
This post is a suggestion for Microsoft, and Microsoft responds to the
suggestions with the most votes. To vote for this suggestion, click the "I
Agree" button in the message pane. If you do not see the button, follow this
link to open the suggestion in the Microsoft Web-based Newsreader and then
click "I Agree" in the message pane.

http://www.microsoft.com/office/com...4-2fe17d84f7fe&dg=microsoft.public.excel.misc

 

[Mike Middleton]

Alec Erskine -

It is my understanding that the only change to standard Solver from Excel
2003 to Excel 2007 is to accommodate the increase in rows and columns.

According to the Help item "Excel specifications and limits, Worksheet and
workbook specifications," the number of "Adjustable cells in Solver" is 200
in both Excel 2003 and Excel 2007. Each of those adjustable cells can be a
binary variable used in a knapsack problem.

- Mike Middleton
http://www.MikeMiddleton.com

 

[Dana DeLouis]

There seems to be a small starting position effect

Hi. Excel's Solver finds "Local" Min/Max, and does not have enough
logic to find "Global" min/max.
Try starting with all 1's, and see if you get a different solution.

The classic example would be to find the Min of x*Sin(x) on the range
0-15. If you start near 0, you will get one answer - zero. This would
not be as good as the solution near 5, or the better solution near 11.
= = = = =
Dana DeLouis

 

[Dana DeLouis]

This allows us to solve the “Knapsack problem†in Excel.

and am quite worried that it claims to have optimized when it has not.

Hi. Just to mention ...
Excel's Solver does have a logic problem in that if the 'finite
difference' in its derivative calculation indicates a problem, Solver
will immediately finish, usually without any warnings. Solver will quit
on the first hint of a problem.
For example, if your model uses discontinuous functions like IF(),
MAX(), MIN(), etc, then this "usually" causes a problem. The results
are most often not reliable. The model must be re-written in linear form.
= = = = = = = = =
Dana DeLouis