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: | 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, 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 follow-up: ↓ 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 0-based, 1-based? 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 optimisation-only thing?
comment:12 Changed 6 years ago by
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 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 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 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...)