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.

CC: @dimpase @videlec @jdemeyer

Component: numerical

Author: Matthias Koeppe

Branch/Commit: 9f35b65

Reviewer: Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/20351

[dimpase]

comment:2

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]

comment:5

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 ;)

[mkoeppe]

Branch: u/mkoeppe/sage_libs_ppl_mip_problem_and_pplbackend__add_support_for_integer_variables

[sagetrac-git]

Commit: 9f35b65

[sagetrac-git]

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

9f35b65

Wrap MIP_Problem.add_to_integer_space_dimensions

[mkoeppe]

Author: Matthias Koeppe

[dimpase]

comment:10

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

[dimpase]

comment:11

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]

comment:12

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]

comment:13

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]

comment:14

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]

comment:15

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

[dimpase]

Reviewer: Dima Pasechnik

[vbraun]

Changed branch from u/mkoeppe/sage_libs_ppl_mip_problem_and_pplbackend__add_support_for_integer_variables to 9f35b65