Opened 6 years ago
Closed 6 years ago
#20351 closed enhancement (fixed)
sage.libs.ppl.MIP_Problem: Add support for integer variables
Reported by:  mkoeppe  Owned by:  

Priority:  major  Milestone:  sage7.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, GitHub, GitLab)  Commit:  9f35b65ae443d565bcf53319fc57751baf640fc8 
Dependencies:  Stopgaps: 
Description (last modified by )
PPL's solver is a rational *MIP* solver. Its support for integer variables should be exposed in Sage.
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 6 years ago by
 Cc dimpase vdelecroix jdemeyer added
comment:2 followup: ↓ 5 Changed 6 years ago by
comment:3 Changed 6 years ago by
 Description modified (diff)
comment:4 Changed 6 years ago by
 Description modified (diff)
comment:5 in reply to: ↑ 2 Changed 6 years ago by
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 6 years ago by
 Branch set to u/mkoeppe/sage_libs_ppl_mip_problem_and_pplbackend__add_support_for_integer_variables
comment:7 Changed 6 years ago by
 Commit set to 9f35b65ae443d565bcf53319fc57751baf640fc8
Branch pushed to git repo; I updated commit sha1. New commits:
9f35b65  Wrap MIP_Problem.add_to_integer_space_dimensions

comment:8 Changed 6 years ago by
 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 6 years ago by
 Description modified (diff)
comment:10 Changed 6 years ago by
Are indices of variables 0based, 1based? Could this info be added to docs?
comment:11 Changed 6 years ago by
Can one use this to generate integer hull of a polytope defined by inequalities (perhaps after adjusting the corresponding Polyhedron code)? Or is this optimisationonly thing?
comment:12 Changed 6 years ago by
Are indices of variables 0based, 1based? Could this info be added to docs?
This is already documented in the class docstring of Variable
. (It's 0based.)
Can one use this to generate integer hull of a polytope defined by inequalities (perhaps after adjusting the corresponding Polyhedron code)? Or is this optimisationonly 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 noninteger 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 6 years ago by
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.
comment:14 Changed 6 years ago by
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 copypaste 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 6 years ago by
 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 6 years ago by
 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
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...)