Opened 3 years ago

Closed 3 years ago

#20351 closed enhancement (fixed)

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

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-7.2
Component: numerical Keywords: lp
Cc: dimpase, vdelecroix, jdemeyer Merged in:
Authors: Matthias Koeppe Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: 9f35b65 (Commits) Commit: 9f35b65ae443d565bcf53319fc57751baf640fc8
Dependencies: Stopgaps:

Description (last modified by 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.

Change History (16)

comment:1 Changed 3 years ago by mkoeppe

  • Cc dimpase vdelecroix jdemeyer added

comment:2 follow-up: Changed 3 years ago by 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...)

comment:3 Changed 3 years ago by mkoeppe

  • Description modified (diff)

comment:4 Changed 3 years ago by mkoeppe

  • Description modified (diff)

comment:5 in reply to: ↑ 2 Changed 3 years ago by 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 ;)

comment:6 Changed 3 years ago by mkoeppe

  • Branch set to u/mkoeppe/sage_libs_ppl_mip_problem_and_pplbackend__add_support_for_integer_variables

comment:7 Changed 3 years ago by git

  • Commit set to 9f35b65ae443d565bcf53319fc57751baf640fc8

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

9f35b65Wrap MIP_Problem.add_to_integer_space_dimensions

comment:8 Changed 3 years ago by mkoeppe

  • Authors set to Matthias Koeppe
  • Description modified (diff)
  • Status changed from new to needs_review
  • Summary changed from sage.libs.ppl.MIP_Problem and PPLBackend: Add support for integer variables to sage.libs.ppl.MIP_Problem: Add support for integer variables

comment:9 Changed 3 years ago by mkoeppe

  • Description modified (diff)

comment:10 Changed 3 years ago by dimpase

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

comment:11 Changed 3 years ago by 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?

comment:12 Changed 3 years ago by 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.

comment:13 Changed 3 years ago by 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()

comment:14 Changed 3 years ago by 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

comment:15 Changed 3 years ago by dimpase

  • Reviewers set to Dima Pasechnik
  • Status changed from needs_review to positive_review

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

comment:16 Changed 3 years ago by vbraun

  • Branch changed from u/mkoeppe/sage_libs_ppl_mip_problem_and_pplbackend__add_support_for_integer_variables to 9f35b65ae443d565bcf53319fc57751baf640fc8
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.