Solver Problem

[Sam]

Hopefully, I have posted this in the right place . . . .
I have a 2 page spreadheet.
Page 1 contains data (customers, depots and locations) and a summary of the
results
Page 2 contains all the messy calculations (essentially calc cost of
delivering to a number customers, each customer can be delivered to from a
number of depots, pick a the chepaest depot for each customer, all up the
total cost for all customers)

I want to pick locations for the depots so that the total cost is smallest.

So I tell it to use only one depot and ask solver to change the coordinates
to minimise total cost.. Works fine.
(Works fine in this case means produces the same answer from different
starting points and small changes to locations increase costs)
2 depots, 3 depots seem to works fine.

4 depots struggles and although it produces a 'optimal' answer, it is easy
to improve the solution by changing locations (X,Y Coordinates) manually

I then add one new depot (to give 5 depots) with some suggested coordinates
and start solver off again. This time it tells me it has found a solution
but it has changed nothing. It is easy to change the coordinates of the new
depot and get an improved solution (value of target cell in solver) so why
does solver not do this and why does it think it has found an answer?

And most importantly, what can I do to improve Solver's performance. I have
tried fiddling with the options and sonmetinmes it makes a difference and
sometimes not.

Thanks for any help

 

[Myrna Larson]

I believe this "travelling salesman" problem is the subject of a whole field in computer
science, i.e. this isn't a trivial problem.

Solver is the "lite" version of this software. You may need to purchase the "professional"
version. It comes from FrontLine. The pro version is $750, and there's another that's $1295
[sic]. You'll find more information at www.solver.com

 

[Dana DeLouis]

I would be curious to know if your model uses any of the following
"non-smooth" functions...

Abs, Min, Max, Int, Round, Ceiling, Floor



You may want to adjust the options for Convergence (smaller number closer to
zero), and also try turning on AutoScaling (depending on your distances
involved).

Just curious. Are you using any constraints that keep the distances between
any two depot a certain distance apart?

Excel's Solver often gives up easily when the model gets too complicated, so
this is not unusual behavior. Sometimes, looking for ways to simplify the
model is an option. For example, are you using Spherical Geometry to
calculate the great circle distance between customers and depot locations?
Maybe using a less sophisticated x & y coordinate system might be better at
this point.


--
Dana DeLouis
Using Windows XP & Office XP
= = = = = = = = = = = = = = = = =

Thanks for the thoughts:-

1) If I set "assume linear" I get Conditions for Assume Linear Model are not
satisfied (which doesn't surprise me as there are all sorts of square roots
and other stuff in the calculation bit!)

2) This is not a TSP (shortest distance through a network) problem and
should be easier to solve althought the solution might not be a global
optimum. I think its known in the trade as "depot location".

3) I thought the basic solver approach was:
a) change each cell that is allowed to be changed and see if the solution
gets better (very simplistic description I know)
b) change one or more of these cells to get a new solution
c) repeat from a) until no improvement possible

4) I therefore struggle to see how solver can give up when a simple change
in one of these cells makes the solution better. I fully accept that it
might find a local optimum (as opposed to a global one) but to stop and say
'all constraints and optimality conditions satisfied' when a simple change
to one of the 'cells to change' makes an improvement leaves me baffled. Is
it just that this problem (only 10 variables to change) is just to hard for
the 'lite' version? If so, perhaps solver ought to expire gently with a
message - "too hard, I give up"

5) I'm just a poor academic setting up some stuff for the students. If I
asked for $750, I'd get laughed out of court!!! Nice thought though.

--
Sam
He uses statistics as a drunken man uses lampposts - for support rather than
illumination
(remove CAP to reply)

As Myrna pointed out, the Traveling Salesman Problem (TSP) is not
amenable to easy solutions. However, a 5 node problem should be easy
for Solver to address. You might want to ensure you are setting up the
problem so that it is 'linear' [In Solver, click Options... and then
check the 'Assume Linear Model' box. Then, when you click Solve..., if
Solver complains that the problem is not linear you'll know.]

In any case, from what I remember, TSP can be constructed as a linear
optimization problem. Once that is done, even the 'lite' version of
Solver should be able to solve the TSP. Check the tutorials at
frontline.com (or search google or yahoo) and you might find a 'ready
made' solution.

--
Regards,

Tushar Mehta, MS MVP -- Excel
www.tushar-mehta.com
Excel, PowerPoint, and VBA add-ins, tutorials
Custom MS Office productivity solutions

Hopefully, I have posted this in the right place . . . .
I have a 2 page spreadheet.
Page 1 contains data (customers, depots and locations) and a summary

of

the

from

a

the

new

rather

than

 

[Sam]

Dana,
Thanks for your interest.

1) Abs.Max,Min,Int,Round,Ceiling.Floor are not used. In fact there are no
discontinuous functions in use at all. However there are some table lookups
to find the closest depot to a customer and obviously this adds some
discontinuity
2) Autoscaling is on as some numbers get quite large.
3) Spherical geometry has been done earlier and the coordinates (which were
lat
and long) converted into rectangular coordinates
4) there are no constraints of any sort.
5) convergence seems fine to me. If I set it smaller, solver does more
iterations but the objective function hardly changes (as one would expect
'cos its fiddling around with the small print at this stage)

That is what is so depressing - the scope for improvement is quite large.
For example:
If I give it 5 depots at
211.25 195.13
174.97 121.47
277.09 115.40
104.52 424.46
290.77 124.34
total cost=33563571

and tell it to optimise (Convergence at this stage is set at 0.000000001) it
gives me
208.18 187.33
175.33 119.81
216.73 119.11
162.58 473.55
286.25 115.32
total cost=30755848

which is great and looks really good until you find (by accident and
suspicion) that if I change
216.73 to 218 total cost reduces by 3229
218.96 to 230 total cost reduced by 26,566
218.96 to 245 total cost reduces by 138,971
which seems quite a significant change to me.

If I set the coordinate at 245 and ask it to solve, it tells me all
constraints and optimality conditions satisfied.
Those of us that have read this far know better!!!!

If I change the 119.11 to 123 the total cost reduces by 151,754
In fact by fiddling round further (just changing each coordinate in turn to
find its lowest cost point) I can reduce the costs by another 172,931
207.00 191.00
175.33 121.00
244.00 118.00
162.58 473.55
289.00 123.00
total cost = 30292192

At least Solver also thinks this is optimal!!!

So any suggestions to avoid this tedious process would be welcome (as would
knowing exactly what are these 'optimality conditions' that are satisfied)

Cheers

--


Sam
He uses statistics as a drunken man uses lampposts - for support rather than
illumination
(remove CAP to reply)

I would be curious to know if your model uses any of the following
"non-smooth" functions...

Abs, Min, Max, Int, Round, Ceiling, Floor



You may want to adjust the options for Convergence (smaller number closer to
zero), and also try turning on AutoScaling (depending on your distances
involved).

Just curious. Are you using any constraints that keep the distances between
any two depot a certain distance apart?

Excel's Solver often gives up easily when the model gets too complicated, so
this is not unusual behavior. Sometimes, looking for ways to simplify the
model is an option. For example, are you using Spherical Geometry to
calculate the great circle distance between customers and depot locations?
Maybe using a less sophisticated x & y coordinate system might be better at
this point.


--
Dana DeLouis
Using Windows XP & Office XP
= = = = = = = = = = = = = = = = =

Thanks for the thoughts:-

1) If I set "assume linear" I get Conditions for Assume Linear Model are not
satisfied (which doesn't surprise me as there are all sorts of square roots
and other stuff in the calculation bit!)

2) This is not a TSP (shortest distance through a network) problem and
should be easier to solve althought the solution might not be a global
optimum. I think its known in the trade as "depot location".

3) I thought the basic solver approach was:
a) change each cell that is allowed to be changed and see if the solution
gets better (very simplistic description I know)
b) change one or more of these cells to get a new solution
c) repeat from a) until no improvement possible

4) I therefore struggle to see how solver can give up when a simple change
in one of these cells makes the solution better. I fully accept that it
might find a local optimum (as opposed to a global one) but to stop and say
'all constraints and optimality conditions satisfied' when a simple change
to one of the 'cells to change' makes an improvement leaves me baffled. Is
it just that this problem (only 10 variables to change) is just to hard for
the 'lite' version? If so, perhaps solver ought to expire gently with a
message - "too hard, I give up"

5) I'm just a poor academic setting up some stuff for the students. If I
asked for $750, I'd get laughed out of court!!! Nice thought though.

--
Sam
He uses statistics as a drunken man uses lampposts - for support rather than
illumination
(remove CAP to reply)

As Myrna pointed out, the Traveling Salesman Problem (TSP) is not
amenable to easy solutions. However, a 5 node problem should be easy
for Solver to address. You might want to ensure you are setting up the
problem so that it is 'linear' [In Solver, click Options... and then
check the 'Assume Linear Model' box. Then, when you click Solve..., if
Solver complains that the problem is not linear you'll know.]

In any case, from what I remember, TSP can be constructed as a linear
optimization problem. Once that is done, even the 'lite' version of
Solver should be able to solve the TSP. Check the tutorials at
frontline.com (or search google or yahoo) and you might find a 'ready
made' solution.

--
Regards,

Tushar Mehta, MS MVP -- Excel
www.tushar-mehta.com
Excel, PowerPoint, and VBA add-ins, tutorials
Custom MS Office productivity solutions

Hopefully, I have posted this in the right place . . . .
I have a 2 page spreadheet.
Page 1 contains data (customers, depots and locations) and a summary

of

the
results
Page 2 contains all the messy calculations (essentially calc cost of
delivering to a number customers, each customer can be delivered to

from

a
number of depots, pick a the chepaest depot for each customer, all

up
the

total cost for all customers)

I want to pick locations for the depots so that the total cost is smallest.

So I tell it to use only one depot and ask solver to change the coordinates
to minimise total cost.. Works fine.
(Works fine in this case means produces the same answer from different
starting points and small changes to locations increase costs)
2 depots, 3 depots seem to works fine.

4 depots struggles and although it produces a 'optimal' answer, it

is
easy

to improve the solution by changing locations (X,Y Coordinates) manually

I then add one new depot (to give 5 depots) with some suggested coordinates
and start solver off again. This time it tells me it has found a solution
but it has changed nothing. It is easy to change the coordinates of

the

new
depot and get an improved solution (value of target cell in solver)

so
why

does solver not do this and why does it think it has found an answer?

And most importantly, what can I do to improve Solver's performance.

I
have

tried fiddling with the options and sonmetinmes it makes a

difference
and

sometimes not.

Thanks for any help

rather

than
illumination
(remove CAP to reply)

 

[Dana DeLouis]

However there are some table lookups

to find the closest depot to a customer and obviously this adds some
discontinuity

Hi Sam. My guess is that Excel's Solver does not know how to procede when a
value jumps based on a LookUp function. Therefore, it may be working around
an area to one side of a Table jump.

From Frontline, here is a short copy of some some discussion on this...

<short copy>
Here is a short list of common discontinuous functions in Excel:

IF CHOOSE LOOKUP, HLOOKUP, VLOOKUP COUNT

Where the graph of a continuous function is an unbroken line or curve, the
graph of a discontinuous function contains one or more "breaks." The most
common example is the IF function. For example:

IF(A1>10,B1,2*B1)

is discontinuous around A1=10 because its value "jumps" from whatever value
B1 has to twice that value. A nonlinear solver relies on (partial)
derivative values to guide it towards a feasible and optimal solution; since
it is unable to compute the derivatives of a function at points where that
function is discontinuous, it has trouble determining how to proceed. In
practice, the nonlinear GRG Solver used in Excel can sometimes deal with
discontinuities which are "incidental" to the problem, but as a general
statement, the nonlinear Solver cannot be expected to find optimal solutions
to such problems.

<end of copy>

When one uses Lookup tabels, this usually confuses Solver. Suppose you had
a table with a lookup tabel value of 10.
Solver thinks it is close to a solution at 9.8. It tries 9.9 and notices
that the Target value hardly changes by the amount of convergence. It then
tries 9.9 and 9.99. Target cell is still hardly changing, so Solver thinks
it found a solution. Well, it tries 1 more time with 10, and the Target
cell changes by 1000 miles. Solver says "Hey! What happened!?"

--
Dana DeLouis
Using Windows XP & Office XP
= = = = = = = = = = = = = = = = =

Dana,
Thanks for your interest.

1) Abs.Max,Min,Int,Round,Ceiling.Floor are not used. In fact there are no
discontinuous functions in use at all. However there are some table lookups
to find the closest depot to a customer and obviously this adds some
discontinuity

<snip>

 

[Sam]

Dana,
Thanks for this. Interesting stuff espectially the look up table piece . .
.. .
I understand all of that and if it was a simple flip from A to B or back
again I could understand it 'cos this is effectively an integer program
requiring B&B techniques to solve.

But my problem is not like that (well not as extreme). As you change a
coordinate, the objective value changes gradually (not linear I grant but
pretty well behaved)
216 30779268.76
220 30768967.01
225 30759505.27
230 30750739.67
235 30722497.76
240 30677721.97
245 30638367.23
250 30653792.15
255 30669816.61

and it remains a mystery to know why it stopped and considered 216 to be
optimal

No matter if that is what it does, that is what it does.

Do you happen to know what the 'Optimality Conditions' are?

 

[Tushar Mehta]

But my problem is not like that (well not as extreme). As you change a
coordinate, the objective value changes gradually (not linear I grant but
pretty well behaved)
216 30779268.76
220 30768967.01
225 30759505.27

The fractional change from 216 to 220 is 0.00033. For smaller 'step's
near 216, the change might be even smaller. You might want to check
the Convergence value in Tools | Solver... | Options.

Also, when you run Solver, you might want to turn on 'Show Iteration
Results' to learn what is happening as Solver moves away from 216.

Finally, you might want to experiment with 'Use Automatic Scaling' as
well as the options at the bottom of the Solver Options dialog box.

--
Regards,

Tushar Mehta, MS MVP -- Excel
www.tushar-mehta.com
Excel, PowerPoint, and VBA add-ins, tutorials
Custom MS Office productivity solutions