Re: [Help-glpk] Option to set to generate all solutions

[Meketon, Marc]

Since we're sharing stories of using multiple solutions...

 

One of the products of my group helps railways plan to route hazardous materials.  We use a specialized K-shortest path algorithm to generate a number of alternatives, which are then evaluated by another system out of our control; this evaluation is way beyond what can be modeled as a simple linear cost function.

 

The problem with using K-shortest paths is that in complex networks, many of the solutions are just minor variations that are very uninteresting.  In the US, consider the problem of going from the East cost to the West Coast.  If I take I-80 I go from New York to Chicago to Omaha to Salt Lake City to San Francisco.  If I take I-40, it's a southern route through Raleigh North Carolina, Memphis Tennessee, and onto Los Angeles.

 

But a K-shortest path algorithm generally returns minor variations, such as two I-40 routes, but one uses a bypass that goes around Knoxville and adds 5 miles to the total mileage and is dfferent by around 15 miles from the normal I-40 route.

 

In this case, getting all the solutions is worse than useless - it's distracting.  A lot of work is needed to weed out the minor variations from the really important differences.

 

I suspect this is similar to many other situations in which someone says "I want all the solutions."

 

-Marc

---

From: help-glpk-bounces+address@hidden [mailto:help-glpk-bounces+address@hidden On Behalf Of Suleyman Demirel
Sent: Tuesday, April 12, 2011 1:52 PM
Cc: address@hidden
Subject: Re: [Help-glpk] Option to set to generate all solutions

To address Andrew's earlier comment, "Nevertheless, imagine that you have obtained all the feasible or optimal
solutions. In which way would you use them?", I want to cite an anecdote.

My department is trying to match the skill sets and strengths of students (around 90 of them) with projects (around 30 of them). They solve a typical assignment problem to create 30 teams of size 2-4. In a typical assignment problem, you have costs of assigning a person to a project and you minimize the total cost. In reality, this is restrictive. First, how do you decide these cost coefficients? Second, what if you do not know your exact objective function? (For example, when you see a solution, you feel like there is something wrong that you do not like about it, but it is hard to express why you don't like it in linear equations). The department usually plays with these cost coefficients and obtains several solutions and make judgement calls to see which one is the best. (This is roughly the story, I am skipping many details.)

It would be interesting to generate all solutions. If that is expensive, generating a lot of reasonable solutions would be great.

This is an example of a case where you want to see all (or many) feasible solutions. I suspect that it should be the case when a problem involves the human factor.

2011/4/12 Michael Hennebry <address@hidden>

On Mon, 11 Apr 2011, Klas Markström wrote:

I think that Jeff had approximately the right idea.
In the callback to check possible integer feasible solutions
test whether it is actaully fesible.
If so, add it to your list, add a constraint and declare it infeasible.
If not, proceeed as usual.
At the end, GLPK will return infeasible and
I think that the list will contain at least
the extreme points of the convex hull.

--
Michael   address@hidden
"Pessimist: The glass is half empty.
Optimist:   The glass is half full.
Engineer:   The glass is twice as big as it needs to be."
_______________________________________________
Help-glpk mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/help-glpk

--

_________________________________________

Sent via my good, old desktop.

_________________________________________
Suleyman Demirel - Office: (734) 647-3167

PhD Candidate in Operations Management
Stephen M. Ross School of Business
University of Michigan, Ann Arbor
Web: http://www.umich.edu/~sdemirel
_________________________________________

---

This e-mail and any attachments may be confidential or legally privileged. If you received this message in error or are not the intended recipient, you should destroy the e-mail message and any attachments or copies,
 and you are prohibited from retaining, distributing, disclosing or using any information contained herein. Please inform us of the erroneous delivery by return e-mail. Thank you for your cooperation.