[PPL-devel] [GIT] ppl/ppl(master): Added a workaround to a space efficiency bug affecting MIP_Problem.
Enea Zaffanella
zaffanella at cs.unipr.it
Sun Dec 19 12:17:43 CET 2010
Module: ppl/ppl
Branch: master
Commit: 96604c0b36129ddc2ab6079a11c3babfb4dc69cd
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=96604c0b36129ddc2ab6079a11c3babfb4dc69cd
Author: Enea Zaffanella <zaffanella at cs.unipr.it>
Date: Sun Dec 19 12:05:02 2010 +0100
Added a workaround to a space efficiency bug affecting MIP_Problem.
The baseline patch has been contributed by Marco Poletti.
MIP_Problem now stores the input constraints as a sequence of Constraint*.
In this sequence, we distinguish between owned constraints (whose resources
are under control of the current MIP_Problem object) and inherited constraints
(whose resources are shared with, and owned by, another MIP_Problem object).
When starting a branch-and-bound computation looking for an integral
feasible/optimal solution, we now inherit (rather than copy) the input
constraints.
The workaround greatly improves space/time efficiency on (mixed) integral
problems, also providing a (simple and reasonable) partial solution to
https://www.cs.unipr.it/mantis/view.php?id=62
The solution is still partial: a complete solution requires the implementation
of a backtracking mechanism for incrementally added constraints.
---
src/MIP_Problem.cc | 78 +++++++++++++++++-----
src/MIP_Problem.defs.hh | 90 ++++++++++++++++++++++++--
src/MIP_Problem.inlines.hh | 147 ++++++++++++++++++++++++++++++++++++++++--
src/MIP_Problem.templates.hh | 6 +-
4 files changed, 288 insertions(+), 33 deletions(-)
Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=96604c0b36129ddc2ab6079a11c3babfb4dc69cd
More information about the PPL-devel
mailing list