Feasibility of linear program

[Dillon Mayhew]

Hi all,

I thought I would start by asking the matroid group this non-matroidal sage question, just in case I am missing something obvious.

I set up a linear program:

lp=MixedIntegerLinearProgram(maximization=True)

Now I want to test whether lp has a feasible solution. Can I do this without throwing an error? If there is no feasible solution, then

lp.solve()

produces an error:

Traceback (click to the left of this block for traceback)
...
sage.numerical.mip.MIPSolverException: 'GLPK : Solution is undefined'

I would like a command along the lines of lp.is_feasible(), but I can find no trace of such a thing. lp.polyhedron() will return an empty polyhedron if the lp is not feasible, but this is far too slow. I can get the error message from lp.solve() in a fraction of second, but it takes minutes/hours for lp.polyhedron() to tell me that the polyhedron is empty.

Does anyone know how to do this? Surely I am not the first person who wants to run multiple linear programs in a row without knowing in advance that they are feasible and without wanting to stop if they are not.

Thanks,

Dillon

[Dima Pasechnik]

On Thursday, 29 October 2015 17:03:26 UTC-7, Dillon wrote:

Hi all,

I thought I would start by asking the matroid group this non-matroidal sage question, just in case I am missing something obvious.

I set up a linear program:

lp=MixedIntegerLinearProgram(maximization=True)

Now I want to test whether lp has a feasible solution. Can I do this without throwing an error? If there is no feasible solution, then

lp.solve()

produces an error:

Traceback (click to the left of this block for traceback)

sure, but there is Python's try: except: construction that makes it easy to deal with. 

And it is quite quick, too.

HTH,

Dima

[Dillon Mayhew]

Yep, that's the work-around I needed, thanks.

Dillon

--

---
You received this message because you are subscribed to the Google Groups "sage-matroid" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-matroid...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Rob Beezer]

And I will add that this is the "pythonic" way. It is better to ask for
forgiveness than to ask permission.

You will see places in the Sage code where an input n to a method is suppose
to be an integer, and the command n = ZZ(n) is wrapped in a try/except block
that provides an error message peculiar to the routine at hand, or just goes on
its way with a proper Sage integer stored in n.

Rob

On 10/29/2015 05:48 PM, Dillon Mayhew wrote:
> Yep, that's the work-around I needed, thanks.
>
> Dillon
>
> On Fri, Oct 30, 2015 at 1:34 PM, Dima Pasechnik <dim...@gmail.com
> <mailto:dim...@gmail.com>> wrote:
>
>
>
> On Thursday, 29 October 2015 17:03:26 UTC-7, Dillon wrote:
>
>
> Hi all,
>
> I thought I would start by asking the matroid group this non-matroidal
> sage question, just in case I am missing something obvious.
>
> I set up a linear program:
>
> lp=MixedIntegerLinearProgram(maximization=True)
>
> Now I want to test whether lp has a feasible solution. Can I do this
> without throwing an error? If there is no feasible solution, then
>
> lp.solve()
>
> produces an error:
>
> Traceback (click to the left of this block for traceback)
>
>
> sure, but there is Python's try: except: construction that makes it easy to
> deal with.
> And it is quite quick, too.
>
> HTH,
> Dima
>
>
> ...
> sage.numerical.mip.MIPSolverException: 'GLPK : Solution is undefined'
>
>

> I would like a command along the lines of lp.is_feasible(), but I can find no trace of such a thing.lp.polyhedron() will return an empty polyhedron if the lp is not feasible, but this is far too slow. I can get the error message from lp.solve() in a fraction of second, but it takes minutes/hours for lp.polyhedron() to tell me that the polyhedron is empty.

>
>
> Does anyone know how to do this? Surely I am not the first person who wants to run multiple linear programs in a row without knowing in advance that they are feasible and without wanting to stop if they are not.
>
>
> Thanks,
>
>
> Dillon
>
> --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "sage-matroid" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-matroid...@googlegroups.com

> <mailto:sage-matroid...@googlegroups.com>.

> For more options, visit https://groups.google.com/d/optout.
>
>

> --
>
> ---
> You received this message because you are subscribed to the Google Groups
> "sage-matroid" group.
> To unsubscribe from this group and stop receiving emails from it, send an email
> to sage-matroid...@googlegroups.com

> <mailto:sage-matroid...@googlegroups.com>.