[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Andrew Makhorin
Subject: Re: [Help-glpk] Option to set to generate all solutions
Date: Sun, 17 Apr 2011 20:49:04 +0400

> 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.

Thank you for the story.

> 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.

I think that the main problem which the modeler encounters in many 
practical cases is that it is often impossible to formalize some 
requirements to the solution, which is called "optimal". Imagine, for 
example, that given a cantus firmus one needs to find (compose) a "best" 
counterpoint to it. Though in this case it is easy to describe the 
solution space with binary variables, and even there exists some formal 
theory, nor constraints neither objective can be formalized to the end.
So the only way is to find a set of solutions and try to choose a "best"
one by listening to them :) Formalization is the problem, not a human

Mentioning a Turing machine I didn't mean modeling it literally. I only
meant that that was said by Manfred Padberg: "The functioning of the
whole world can--with a sufficient degree of approximation--be modeled
as a huge mixed-integer linear program." If we can formalize something,
we can describe it algorithmically, and therefore we can model it as
mip. Here is another example. If a class of matrices is described with
binary variables (as in Klas' example), and there is some requirement,
say, that all eigenvalues must have postive real parts, this requirement
can be formalized and therefore can be described as mip constraints.
This doesn't mean, of course, that one needs to model computing
eigenvalues with a Turing machine or similar device, just because the
class of matrices is parametrized by binary variables, i.e. we don't
need to consider a general case which assumes arbitrary matrices.
Obviously, positiveness of real parts of eignevalues or some other
property of any matrix from the class is a binary function of binary
variables, and the problem is only how to find that function and
describe it efficiently. This is my opinion.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]