Howdy,

I am working a homework problem involving non-linear programming for
an operations research class. The problem is in three parts. The
objective is to minimize the total distance traveled between a
facility and thirty different towns each year by optimally locating
the facility amongst the towns. There are a fixed number of trips
between each facility and each town each year. The second and third
parts of the problem require locating two and three facilities. I
believe I’ve got the first part correct. Excel’s solver give a
consistent and reasonable answer. Of course, two and three facilities
seems to produce local minima. I’ve downloaded and I’m trying to use
Frontline systems Premium solver add-in. Other than randomly sorting
through different starting points, how do I configure the premium
solver to identify the global maximum for each case? Thanks for any
advice or help.

-g

Is this just the traveling-salesman problem in another guise, Gary? Last I
heard, no one has come up with a theoretical solution, beyond the brute-force
method of trying all possible combinations, which in a population of 30 towns
is impractical. If you could locate your facility in a geometrically random
location -- without regard to the road layout, I mean -- it might be
different. But I speak in ignorance of this area of mathematics.

--- "Gary" wrote:
I am working a homework problem involving non-linear programming for
an operations research class. The problem is in three parts. The
objective is to minimize the total distance traveled between a
facility and thirty different towns each year by optimally locating
the facility amongst the towns. There are a fixed number of trips
between each facility and each town each year. The second and third
parts of the problem require locating two and three facilities. I
believe Ive got the first part correct. Excels solver give a
consistent and reasonable answer. Of course, two and three facilities
seems to produce local minima. Ive downloaded and Im trying to use
Frontline systems Premium solver add-in. Other than randomly sorting
through different starting points, how do I configure the premium
solver to identify the global maximum for each case? Thanks for any
advice or help.

Its not quite a traveling salesman problem. Each town makes x number
of trips to a single facility. The facilities are to be located so as
to minimize the total distance traveled from all towns to each towns
respective facility. So, the distance between each town and its
facility is weighted. The real problem is avoiding solver settling on
a locally optimal solution. I need to find a way to get solver to
brute force it in a way and find the globally optimal solution.

On Sep 11, 10:54 pm, Bob Bridges
wrote:
Is this just the traveling-salesman problem in another guise, Gary? Last I
heard, no one has come up with a theoretical solution, beyond thebrute-force
method of trying all possible combinations, which in a population of 30 towns
is impractical. If you could locate your facility in a geometrically random
location -- without regard to the road layout, I mean -- it might be
different. But I speak in ignorance of this area of mathematics.

--- "Gary" wrote:
I am working a homework problem involving non-linear programming for
an operations research class. The problem is in three parts. The
objective is to minimize the total distance traveled between a
facility and thirty different towns each year by optimally locating
the facility amongst the towns. There are a fixed number of trips
between each facility and each town each year. The second and third
parts of the problem require locating two and three facilities. I
believe I’ve got the first part correct.Excel’ssolvergive a
consistent and reasonable answer. Of course, two and three facilities
seems to produce local minima. I’ve downloaded and I’m trying to use
Frontline systems Premiumsolveradd-in. Other than randomly sorting
through different starting points, how do I configure the premium
solverto identify the global maximum for each case? Thanks for any
advice or help.

Sometimes, on problems such as these, you can search for a possible solution.
Then, run solver again with the added constraint that the Target is smaller by some amount from it's current value.
Loop until Solver returns that it did not find a solution.
In general...

Sub Demo()

SolverReset
Call YourSolverSetup 'Make separate routine
Do
Results = SolverSolve(True)
If Results = 3 Then Exit Do 'An error..Assume last solution is best

'// We assume we found a solution
'// Let's try to make it better.
'// Solve again, but try to make Target smaller.

'// Assume Result was 0,1,2 (Found a solution)
SolverReset
Call YourSolverSetup 'Make separate routine
'// Subtract 1 from Target, or whatever you think is best...
'Add constraint that Target <= Current Target -1
Loop

End Sub

Again, not the best, but it can sometimes help. :~

As a side note...

I've never gotten around to figuring it out with Excel, but there are cluster algorithms that can group your data in about 0 seconds.
A common distance function used is "Euclidean Distance" (ie direct distance), so you would want to adjust your towns coordinates into some sort of x-y system.
Once clustered, we can run solver to make sure no constraints are violated, and try once again to improve this solution.
Again, I've not figured out how it is done so quickly.

If we cluster your towns into 3 groups, we can quickly count the number of possible solution combinations with Stirling numbers of the second kind.

ie ? StirlingS2(30, 3)
34,314,651,811,530

Some towns may be so far away that it may be better to build 1 facility for that 1 town. Again, the objective is to minimize total distance traveled
Good luck.
- -
HTH :)
Dana DeLouis



"Gary" wrote in message ...
Its not quite a traveling salesman problem. Each town makes x number
of trips to a single facility. The facilities are to be located so as
to minimize the total distance traveled from all towns to each towns
respective facility. So, the distance between each town and its
facility is weighted. The real problem is avoiding solver settling on
a locally optimal solution. I need to find a way to get solver to
brute force it in a way and find the globally optimal solution.

On Sep 11, 10:54 pm, Bob Bridges
wrote:

Is this just the traveling-salesman problem in another guise, Gary? Last I
heard, no one has come up with a theoretical solution, beyond thebrute-force
method of trying all possible combinations, which in a population of 30 towns
is impractical. If you could locate your facility in a geometrically random
location -- without regard to the road layout, I mean -- it might be
different. But I speak in ignorance of this area of mathematics.

--- "Gary" wrote:

I am working a homework problem involving non-linear programming for
an operations research class. The problem is in three parts. The
objective is to minimize the total distance traveled between a
facility and thirty different towns each year by optimally locating
the facility amongst the towns. There are a fixed number of trips
between each facility and each town each year. The second and third
parts of the problem require locating two and three facilities. I
believe I’ve got the first part correct.Excel’ssolvergive a
consistent and reasonable answer. Of course, two and three facilities
seems to produce local minima. I’ve downloaded and I’m trying to use
Frontline systems Premiumsolveradd-in. Other than randomly sorting
through different starting points, how do I configure the premium
solverto identify the global maximum for each case? Thanks for any
advice or help.