Mathias Brandewinder on .NET, F#, VSTO and Excel development, and quantitative analysis / machine learning.
20. September 2009 07:10

I was recently inspired by an article in OR/MS mag to write 2 posts on using Excel data tables to resolve optimization problems. As it turns out, these puzzles are not only published in the magazine: they also have their online home at Puzzlor.com. So if you like optimization and math problems in general, and like puzzles, check it out!

3. September 2009 17:50

In my last post, I illustrated how to quickly to pick the best value from a selection to get the optimal result, by using Excel Data Tables. This time, we will see how to pick the best possible pair of values.

We are trying to figure out which 2 bridges we should build, in order to minimize the overall travel time for the inhabitants of the island.

I worked out the math for one bridge last time. We will start we a similar setup, but adjust our spreadsheet so that for each islander, we compute the travelling distance for 2 bridges, and select the shortest route.

The ranges B1 and B2 are named Bridge1 and Bridge2. Column I now contains the formula computing the shortest route for each islander. For row 5 for instance, the formula is

=MIN(D5+E5-H5,F5+G5-H5)

Cell I10 is the total of the vertical distances travelled by each individual.

We can select from 4 bridge locations: 2, 4, 7 and 12. What we need is to find out which 2 numbers give us the lowest total travel. Let’s build our data table, this time using 2 bridge positions.

More...

28. August 2009 17:54

In the current issue of OR/MS Today, I came across this nice optimization puzzle, “Bridges to Somewhere”. There are these two islands. Five people A, B, C, D and F live on the first island, and need to commute to work to the second island. Individual A lives in the spot marked A, and needs to go to spot A on the second island – and so on for the 4 others. People can travel only vertically and horizontally (no diagonals), and will always take the shortest path available.

There is currently no bridge between the islands, but a budget for 2 bridges has been approved (the island just received a stimulus package). There are 4 bridge proposals to chose from (One, Two, Three and Four on the map). Which 2 bridges should be built to minimize the travel distance of the population?

Before trying to figure out which 2 bridges are best, I thought it would be interesting to investigate a simpler problem: if you could build one bridge anywhere, where should you build it?

There are a number of ways you could resolve this using Excel; I will illustrate how to find the best solution, using Excel Data Tables.More...