How to check Mixed Integer Linear Program has no solution

[pegah Ali]

Hello Everybody,

Is there anyway to check is a linear program which has been implemented by MixedIntegerLinearprogram 

has a solution or not. and also can I verify why it doesn't have any solution, it might be because of any reasons :

"the model is infeasible", "the model is unbounded" and so on.

For instance I have a function which makes an LP based on the given variable, I wish to verify is the LP has any solution.

def find_solution(variable):

      lp = my MixedIntegerLinearProgram

      lp.solve()

      output = lp has solution or not 

      return output

 

Thank you for your help and hints

Regards

[john_perry_usm]

Hello

Is there anyway to check is a linear program which has been implemented by MixedIntegerLinearprogram 

has a solution or not.

Try creating & solving your program. If it has no solution, Sage will throw an exception. The exception will contain a message with some information, though offhand I don't know whether it covers all the information you want. I think that depends to a large extent on the backend; for instance, glpk will sometimes segfault when there is no solution, and sometimes go into an infinite loop. I find that I have a doctstring documenting that glpk's developers consider this "essentially innate" to their design, so it may be impossible for Sage to give more information than it does. I'm open to correction..

john perry

[Dima Pasechnik]

On 2014-12-15, pegah Ali <pegah.a...@gmail.com> wrote:
> ------=_Part_3151_822295702.1418661065675
> Content-Type: multipart/alternative;
> boundary="----=_Part_3152_1266595069.1418661065675"
>
> ------=_Part_3152_1266595069.1418661065675
> Content-Type: text/plain; charset=UTF-8

if your LP has all variables continuous, then basically you
want to produce a Farkas certificate of infeasibilty.
Most LP solvers (but not GLPK) can do this.
In the LP language, you need to compute the dual of it, and
check that it has unbounded optimum.

I have some Sage code for this that I wanted at some point
to include into Sage, but never got around to.
I can dig it up.

Dima