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

[Suleyman Demirel]

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
_________________________________________