sage.libs.ppl.MIP_Problem: Add support for integer variables

[mkoeppe]

PPL's solver is a rational *MIP* solver. Its support for integer variables should be exposed in Sage.

Reference: ​http://bugseng.com/products/ppl/documentation/user/ppl-user-1.2-html/classParma__Polyhedra__Library_1_1MIP__Problem.html

For sage.libs.ppl.MIP_Problem, I think one just needs to add a wrapper for this method:

void Parma_Polyhedra_Library::MIP_Problem::add_to_integer_space_dimensions(const Variables_Set &i_vars)	

and then a wrapper class for ​`Variables_Set`.

On another ticket (#20354), PPLBackend will be updated accordingly.

[dimpase]

Good catch! I wish I knew this when I still had the student, who wrote the Cython bindings for the ppl LP, around. (He is now at Facebook...)

[mkoeppe]

Replying to dimpase:

Good catch! I wish I knew this when I still had the student, who wrote the Cython bindings for the ppl LP, around. (He is now at Facebook...)

I'll write it if you review my other tickets ;)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9f35b65

Wrap MIP_Problem.add_to_integer_space_dimensions

[dimpase]

Are indices of variables 0-based, 1-based? Could this info be added to docs?

[dimpase]

Can one use this to generate integer hull of a polytope defined by inequalities (perhaps after adjusting the corresponding Polyhedron code)? Or is this optimisation-only thing?

[mkoeppe]

Are indices of variables 0-based, 1-based? Could this info be added to docs?

This is already documented in the class docstring of Variable. (It's 0-based.)

Can one use this to generate integer hull of a polytope defined by inequalities (perhaps after adjusting the corresponding Polyhedron code)? Or is this optimisation-only thing?

No, PPL does not have code for computing integer hulls. The closest that there is in the polyhedron code is the following interesting function:

void Parma_Polyhedra_Library::Polyhedron::drop_some_non_integer_points(Complexity_Class complexity = ANY_COMPLEXITY)	
Possibly tightens *this by dropping some points with non-integer coordinates.

I would be quite interested in having code in Sage that computes a polyhedron given only by a linear optimization oracle [for example, implemented by a MIP solver], see for example ​http://arxiv.org/pdf/1412.3987.pdf. But this has nothing to do with this ticket.

[dimpase]

IMHO in add_to_integer_space_dimensions one should have sig_on() inside try: block, not outside. And sig_off() should be immediately after the call to the backend.

see catch_interrupts()

[mkoeppe]

The code in add_to_integer_space_dimensions matches the last example in the documentation that you cited. I'm assuming it's correct. Besides, it was copy-paste from elsewhere in ppl.pyx.

Alternatively, you can use try/finally which will also catch exceptions raised by subroutines inside the try:

def try_finally_example():
    sig_on()
    try:
        # (some long computation, potentially raising exceptions)
    finally:
        sig_off()
    return something

[dimpase]

OK, good. Although I am a bit concerned about few def statements that could be cdef or cpdef, for efficiency reasons.