Re: [Help-glpk] Certificates of infeasibility or unboundness

[Nathann Cohen]

Hello !!

> Can't you use something like (in C/C++, not Python):
>
>  glp_prob* lp;
>  ...
>  const int status = glp_get_status(lp);
>
>  std::string buf;
>  switch ( status )
>    {
>      case GLP_INFEAS: buf = "soln infeasible but not proven bad"; break;
>      case GLP_NOFEAS: buf = "problem proven infeasible";          break;
>    }
>  ...
>  return buf;    // or whatever it is you need

Oh. Well, Sage already tells when the problem is infeasible thanks to
GLPK's signals, but I would like something stronger like a proof that
the LP is indeed infeasible if it is the case, something like a Farkas
certificate :

http://en.wikipedia.org/wiki/Farkas'_lemma
http://www.win.tue.nl/~rudi/farkas_handout.pdf

That's what I thought glp_get_unbnd_ray was all about ^^;

It seems CPLEX already has something of the kind

http://orinanobworld.blogspot.com/2010/07/finding-extreme-rays-in-cplex.html

but I would really like to have it through GLPK too, as CPLEX is not
part of Sage, unlike GLPK :-/

> Could you tell this list something about using GLPK
> from Sage (just curious)?

Of course !!  Well, Sage is a bit like Maple, it is a general math
software, and I am studying Graph Theory myself. LP and Mixed Integer
LP are just a wonderful way to solve optimization problems on graphs,
and for something like one year I've been working on an interface
between several LP solvers and Sage to improve Sage's graph library.
We can use GLPK, COIN Branch-and-Cut and CPLEX from Sage at the moment
(SCIP is on the way), though GLPK is our default solver for license
reasons.

Here is a tutorial on how to use LP (and so GLPK, unless you install
other packages) from Sage :

http://www.sagemath.org/doc/thematic_tutorials/linear_programming.html

This being said, LP is heavily used in the Graph library. *Heavily*.
We use it to solve all kinds of optimization problems (graph coloring,
dominating sets, hamiltonian cycles, steiner trees, minimum feedback
arc set.... really a LOT of things). So there's a large chance that if
you are doing anything with the Graph library, you are using GLPK at
some point !

Now, I would be quite glad to improve the LP interface for itself, and
not as a tool for Graph theory.... Having certificates of
unboundedness/infeasibility is on this path, so any information you
could have on how this would be possible is just pure gold to me :-)

Thanks,

Nathann Cohen
http://www-sop.inria.fr/members/Nathann.Cohen/

P.S. : Oh, I forgot something that may interest you : the interface
between Sage and GLPK is at C level. Sage is Python, and uses Cython
(Python + C), so it is possible for us to directly deal with C. GLPK's
called directly through its library.