Sven Verdoolaege [Thu, 21 Jan 2010 09:54:51 +0000 (10:54 +0100)]
isl_tab_basic_map_partial_lexopt: properly handle empty input map
In particular, when no empty set is requested (i.e., empty == NULL),
then we shouldn't try to add the context to the empty set.
Sven Verdoolaege [Wed, 20 Jan 2010 16:50:28 +0000 (17:50 +0100)]
isl_basic_map_set_to_empty: remove sample (if any)
Sven Verdoolaege [Sun, 17 Jan 2010 19:50:31 +0000 (20:50 +0100)]
add isl_set_fast_is_empty
Sven Verdoolaege [Wed, 13 Jan 2010 08:59:16 +0000 (09:59 +0100)]
properly remove piplib submodule
309036c (add copyright statements) accidentally removed the piplib submodule.
Removing the piplib submodule was not a bad idea since we don't really need it
anymore, but it should be done properly.
Sven Verdoolaege [Sun, 29 Nov 2009 17:24:39 +0000 (18:24 +0100)]
isl_basic_map_update_from_tab: re-gauss resulting bmap
Many functions assume that their inputs have been gaussed.
Sven Verdoolaege [Fri, 1 Jan 2010 17:02:30 +0000 (18:02 +0100)]
ax_submodule.m4: don't let --with-module conflict with --with-module-prefix=
Sven Verdoolaege [Sat, 12 Dec 2009 22:43:31 +0000 (23:43 +0100)]
add isl_set_follows_at
Sven Verdoolaege [Thu, 24 Dec 2009 18:02:26 +0000 (19:02 +0100)]
isl_basic_set_compare_at: compute result in terms of maximal (integral) difference
Computing the maximal instead of the minimal difference will allow
us to reuse much of the code in isl_basic_set_follows_at later.
Since we only need the sign of the optimum, we don't really need
the exact value.
Sven Verdoolaege [Thu, 24 Dec 2009 16:59:59 +0000 (17:59 +0100)]
isl_tab_pip.c: add cuts for all non-integer coordinates in lexmin context
The lexmin context applies basically the same algorithm that is
used in the main tableau to the context tableau.
In particular, each cut that is added is immediately used to move
to a lexico-greater point.
It was reported by François Galea, who was working on the implementation
of parametric integer programming in PPL, that first adding cuts
for all non-integer coordinates results in a significant speed
improvement on at least one example.
This patch implements the same idea and results in a similar improvement
on the same example.
Sven Verdoolaege [Sat, 19 Dec 2009 10:20:34 +0000 (11:20 +0100)]
isl_basic_map_gist: don't drop equalities from context
The context isn't cowed, so this dropping of equalities would
be visible to the caller. Instead, drop the equalities after
duplicating the context.
Sven Verdoolaege [Fri, 18 Dec 2009 22:41:29 +0000 (23:41 +0100)]
isl_convex_hull.c: initial_facet_constraint: drop all redundant bounds on face
While constructing an initial facet, we may end up with an intermediate
face that makes some of the as yet unconsidered bounds redundant.
Remove all of them, instead of only those that happen to vanish.
Sven Verdoolaege [Fri, 18 Dec 2009 20:26:31 +0000 (21:26 +0100)]
isl_convex_hull.c: is_independent_bound: normalize bounds
Sven Verdoolaege [Fri, 18 Dec 2009 19:53:46 +0000 (20:53 +0100)]
isl_convex_hull.c: extend: check hull argument
Sven Verdoolaege [Fri, 18 Dec 2009 19:52:33 +0000 (20:52 +0100)]
isl_mat_right_inverse: be more verbose on error condition
Sven Verdoolaege [Fri, 18 Dec 2009 17:26:58 +0000 (18:26 +0100)]
isl_constraint_dup: make sure line refers to equation in constraint's bmap
Sven Verdoolaege [Wed, 16 Dec 2009 19:25:40 +0000 (19:25 +0000)]
add copyright statements
Sven Verdoolaege [Wed, 16 Dec 2009 14:17:19 +0000 (14:17 +0000)]
remove functions for converting between isl and PolyLib
These functions could be seen as being derived work from PolyLib
and would therefore infect the whole library with the GPLv2 license.
They will be moved into a separate isl-polylib library.
Sven Verdoolaege [Wed, 16 Dec 2009 12:53:03 +0000 (12:53 +0000)]
isl_tab_solve_lp: invert optimal value back when computing maximum
A maximum is computed by computing the minimum of the opposite objective
function. The maximal value is then the opposite of the computed value.
Sven Verdoolaege [Sun, 6 Dec 2009 10:54:41 +0000 (11:54 +0100)]
isl_map_intersect: add special case for adding a single constraint
Sven Verdoolaege [Sat, 5 Dec 2009 17:50:12 +0000 (18:50 +0100)]
isl_map_is_subset: break off as soon as difference is known to be non-empty
Sven Verdoolaege [Mon, 7 Dec 2009 16:09:59 +0000 (17:09 +0100)]
compute set difference using a backtracking algorithm
In particular, treat all basic maps in the minuend separately
and only subtract parts of the subtrahend that actually overlap
with the minuend. Moreover, only use non-redundant constraints
when performing this subtraction.
Using only non-redundant constraints in overlapping parts
avoids the minuend being split in several parts unnecessarily.
Treating each basic map separately should help speed up
isl_map_is_subset in a subsequent commit.
Sven Verdoolaege [Tue, 1 Dec 2009 11:42:46 +0000 (12:42 +0100)]
isl_map_subtract.c: extract from isl_map.c
Sven Verdoolaege [Mon, 7 Dec 2009 16:00:15 +0000 (17:00 +0100)]
isl_tab: keep track of isl_basic_map instead of isl_basic_set
Sven Verdoolaege [Sat, 28 Nov 2009 20:47:29 +0000 (21:47 +0100)]
privately export isl_basic_map_contains
Sven Verdoolaege [Sat, 28 Nov 2009 20:44:28 +0000 (21:44 +0100)]
add isl_basic_map_add_ineq and isl_basic_map_add_eq
Sven Verdoolaege [Sat, 28 Nov 2009 19:16:03 +0000 (20:16 +0100)]
isl_tab_detect_redundant: return status instead of isl_tab *
Sven Verdoolaege [Sat, 28 Nov 2009 18:47:58 +0000 (19:47 +0100)]
isl_tab: add isl_tab_freeze_constraint
Sven Verdoolaege [Sat, 28 Nov 2009 15:09:56 +0000 (16:09 +0100)]
isl_tab_add_ineq and isl_tab_mark_empty: return status instead of isl_tab *
isl_tabs are not reference counted, so it's easier to deal with a status
than to have to keep track of whether the isl_tab may have been destroyed.
Sven Verdoolaege [Sun, 29 Nov 2009 18:34:13 +0000 (19:34 +0100)]
add missing AUTHORS file
Sven Verdoolaege [Sun, 29 Nov 2009 17:24:39 +0000 (18:24 +0100)]
isl_basic_set_swap_vars: re-gauss resulting bset
Many functions assume that their inputs have been gaussed.
Sven Verdoolaege [Mon, 16 Nov 2009 14:58:31 +0000 (15:58 +0100)]
add isl_basic_map_first_constraint
Sven Verdoolaege [Sun, 15 Nov 2009 19:28:40 +0000 (20:28 +0100)]
export isl_basic_map_lexmax
Sven Verdoolaege [Sun, 15 Nov 2009 17:22:07 +0000 (18:22 +0100)]
add isl_basic_set_lexmax
Sven Verdoolaege [Sun, 15 Nov 2009 16:31:52 +0000 (17:31 +0100)]
isl_map_drop_basic_map: consistently keep basic map argument
Sven Verdoolaege [Sun, 1 Nov 2009 14:41:28 +0000 (15:41 +0100)]
isl_tab: row is only (obviously) redundant if it does not depend on variables
Variables are not assumed to be nonnegative, but are only marked as being
nonnegative based on the constraints. This nonnegativity can therefore
not be used to mark rows as being redundant as that could lead to
circular reasoning.
Sven Verdoolaege [Sun, 1 Nov 2009 14:34:03 +0000 (15:34 +0100)]
isl_basic_map_simplify: make sure to rerun Gauss when equality has been added
remove_duplicate_constraints failed to set the progress flag when
it replaces a pair of inequalities by an equality, resulting in
the result of isl_basic_map_simplify possibly not having the equalities
in the expected form.
Sven Verdoolaege [Sun, 1 Nov 2009 13:49:46 +0000 (14:49 +0100)]
isl_tab_basic_map_partial_lexopt: use context constraints when detecting equalities
The constraints of the context of the actual map may conspire to form
equalities and we generally want to detect as many equalities as possible.
Therefore, detect equalities in the intersection of the two
and add these equalities to the map.
Note that the equalities are now no longer detected in the map
itself, so we may have to detect equalities again later if
we are ever interested in the equalities of the map itself.
Sven Verdoolaege [Sun, 1 Nov 2009 13:36:32 +0000 (14:36 +0100)]
isl_tab_pip.c: ignore dead columns when checking integrality
The dead columns are zero, which means that it does not matter
that they may have a fractional coefficient.
Moreover, dead columns can't be used to pivot, so it is actually
wrong to take them into account.
Sven Verdoolaege [Wed, 21 Oct 2009 21:49:13 +0000 (23:49 +0200)]
isl_pip: optionally perform some check on the results
Sven Verdoolaege [Wed, 21 Oct 2009 21:39:23 +0000 (23:39 +0200)]
put options in a separate isl_options structure
Sven Verdoolaege [Wed, 21 Oct 2009 21:22:39 +0000 (23:22 +0200)]
add rudimentary argument parsing facility
Sven Verdoolaege [Wed, 21 Oct 2009 19:04:26 +0000 (21:04 +0200)]
isl_tab_compute_reduced_basis: handle empty tables
Sven Verdoolaege [Wed, 21 Oct 2009 12:41:31 +0000 (14:41 +0200)]
isl_basic_set_solve_ilp: handle obviously empty sets
Sven Verdoolaege [Wed, 21 Oct 2009 12:31:22 +0000 (14:31 +0200)]
isl_basic_set_solve_ilp: fix handling of sets with equalities
First, the input set should be protected from being modified,
and second, the test for whether a solution is requested was wrong.
Sven Verdoolaege [Wed, 21 Oct 2009 12:05:13 +0000 (14:05 +0200)]
add isl_set_remove
Sven Verdoolaege [Wed, 21 Oct 2009 12:04:29 +0000 (14:04 +0200)]
add isl_set_fix
Sven Verdoolaege [Wed, 21 Oct 2009 12:01:53 +0000 (14:01 +0200)]
add isl_basic_set_fix
Sven Verdoolaege [Tue, 20 Oct 2009 10:34:24 +0000 (12:34 +0200)]
extract isl_basic_set_scan from polytope_scan.c
Sven Verdoolaege [Wed, 21 Oct 2009 16:13:19 +0000 (18:13 +0200)]
isl_basic_map_simplify: avoid removal of div definitions in eliminate_divs_eq
Sven Verdoolaege [Sun, 18 Oct 2009 16:24:26 +0000 (18:24 +0200)]
isl_map.c: declare variable at start of code block
Sven Verdoolaege [Sun, 18 Oct 2009 16:00:05 +0000 (18:00 +0200)]
isl_basic_set_project_out: handle rational sets
For rational sets, projection boils down to (Fourier-Motzkin)
elimination, so just call isl_basic_set_remove.
Sven Verdoolaege [Sun, 18 Oct 2009 15:52:51 +0000 (17:52 +0200)]
add isl_basic_set_remove
Sven Verdoolaege [Fri, 16 Oct 2009 12:46:28 +0000 (14:46 +0200)]
isl_tab_pip: keep cache of partial solutions
This cache allows us to combine two partial solutions into a single
partial solution if they have the same mapping. The domain of the
single partial solution is that before it was split to arrive at
the two domains of the two partial solutions.
In particular, this happens if it turns out there is no solution
in either part of the context.
It also happens when the initial set has existentially quantified
variables. In this case, we only insist that these variables
have an integer value, but we don't care about the actual value.
The solutions in the two parts of the context may therefore still
agree on the remaining variables.
Sven Verdoolaege [Fri, 16 Oct 2009 12:40:34 +0000 (14:40 +0200)]
isl_tab_pip: don't free isl_sol on error condition
Instead, set a flag. isl_sol is not reference counted, so it's better
not to destroy it along the way.
Sven Verdoolaege [Fri, 16 Oct 2009 12:30:24 +0000 (14:30 +0200)]
isl_tab: support generic undo records
Sven Verdoolaege [Fri, 16 Oct 2009 12:24:49 +0000 (14:24 +0200)]
add isl_mat_is_equal
Sven Verdoolaege [Fri, 16 Oct 2009 12:10:59 +0000 (14:10 +0200)]
isl_tab_pip.c: remove some code duplication between isl_map_add and isl_for_add
Sven Verdoolaege [Mon, 12 Oct 2009 12:12:55 +0000 (14:12 +0200)]
isl_map_is_subset: add special case for singleton maps
Sven Verdoolaege [Mon, 12 Oct 2009 08:26:07 +0000 (10:26 +0200)]
isl_map_compute_divs: skip computation if divs are known already
Sven Verdoolaege [Sat, 10 Oct 2009 13:09:10 +0000 (15:09 +0200)]
isl_map_is_subset: exploit another easy special case
Sven Verdoolaege [Sat, 10 Oct 2009 13:07:02 +0000 (15:07 +0200)]
add isl_map_fast_is_universe
Sven Verdoolaege [Sat, 10 Oct 2009 12:13:25 +0000 (14:13 +0200)]
add isl_set_size
Sven Verdoolaege [Sat, 10 Oct 2009 11:19:09 +0000 (13:19 +0200)]
mark some functions as requiring use of return value
Sven Verdoolaege [Sat, 10 Oct 2009 11:14:19 +0000 (13:14 +0200)]
isl_tab: improved error handling
Sven Verdoolaege [Thu, 8 Oct 2009 07:29:33 +0000 (09:29 +0200)]
isl_tab_pip.c: incrementally build recession cone of gbr context
When checking the feasibility of a constraint in the gbr context,
we compute a sample. The first step of this computation builds
a recession cone since we need to know which directions are unbounded.
By incrementally building up the recession cone, we can avoid
the complete recomputation. This is especially useful when
the context is/becomes bounded, since we can then avoid the
recession cone computation altogether.
Sven Verdoolaege [Mon, 12 Oct 2009 20:25:22 +0000 (22:25 +0200)]
isl_tab_pip.c: propagate some equalities from gbr context to main tableau
If a new equality in the context can be used to eliminate
a parameter in the main tableau, we perform the elimination
as this allows us to more easily determine the signs of rows
and it may avoid the introduction of some redundant integer
divisions.
Sven Verdoolaege [Mon, 5 Oct 2009 10:22:56 +0000 (12:22 +0200)]
isl_tab_pip.c: detect equalities in gbr context on each parametric cut
A new div that was introduced to express a parametric cut may,
within the current context, be an affine combination of other divs.
If so, we want to find these equalities as soon as possible
as this may allow us to more easily determine feasibility of
a constraint.
Sven Verdoolaege [Thu, 8 Oct 2009 12:14:10 +0000 (14:14 +0200)]
add isl_tab_detect_equalities
Sven Verdoolaege [Sun, 4 Oct 2009 14:38:28 +0000 (16:38 +0200)]
add isl_tab_set_initial_basis_with_cone
Sven Verdoolaege [Fri, 18 Sep 2009 07:02:40 +0000 (09:02 +0200)]
isl_tab_pip: use generalized basis reduction based context by default
Sven Verdoolaege [Thu, 8 Oct 2009 12:10:30 +0000 (14:10 +0200)]
isl_tab_pip: add generalized basis reduction based context handling
Sven Verdoolaege [Thu, 8 Oct 2009 11:49:57 +0000 (13:49 +0200)]
isl_tab_pip.c: extract out context handling
Sven Verdoolaege [Thu, 17 Sep 2009 13:40:46 +0000 (15:40 +0200)]
isl_tab_pip.c: add_div: use more reliable way to test whether div is nonneg
Before, we used the fact that if all parameters are non-negative,
then the big parameter is not used.
However, it is perfectly valid to have negative parameters and
still not use any big parameter.
Sven Verdoolaege [Fri, 25 Sep 2009 17:17:20 +0000 (19:17 +0200)]
isl_tab_basic_map_partial_lexopt: remove samples that are no longer useful
When we test an inequality in row_sign, it is useful to store any
samples found, so we can use them to speed up the computation
of future row signs.
However, when we return from a branch, then all the samples found
since we entered the branch all satisfy the constraints on that
branch and so they will not satisfy the constraints on any other
branch. We therefore save the current number of samples when
we enter a branch and then discard all subsequently added samples
when we return from the branch.
Sven Verdoolaege [Mon, 5 Oct 2009 09:41:37 +0000 (11:41 +0200)]
isl_tab.c: extract out samples handling from isl_tab_pip.c
Sven Verdoolaege [Fri, 9 Oct 2009 15:16:24 +0000 (17:16 +0200)]
isl_affine_hull.c: uset_affine_hull_bounded: use tableaus to perform computation
Sven Verdoolaege [Tue, 29 Sep 2009 10:25:57 +0000 (12:25 +0200)]
isl_basic_map_detect_equalities: keep track of sample
Sven Verdoolaege [Tue, 29 Sep 2009 07:22:13 +0000 (09:22 +0200)]
isl_basic_map_detect_equalities: only compute recession cone once
Before, the recession cone was computed both during the computation
of the initial sample and then later again to project out this
recession cone.
Sven Verdoolaege [Sun, 4 Oct 2009 07:46:23 +0000 (09:46 +0200)]
isl_tab_sample: handle unbounded directions in initial basis
Sven Verdoolaege [Sun, 4 Oct 2009 07:33:06 +0000 (09:33 +0200)]
isl_tab_compute_reduced_basis: handle unbounded directions in initial basis
Sven Verdoolaege [Mon, 28 Sep 2009 19:20:19 +0000 (21:20 +0200)]
exploit equalities in isl_tab_sample
Sven Verdoolaege [Tue, 29 Sep 2009 08:25:40 +0000 (10:25 +0200)]
isl_tab: keep (in)equalities of bset (if any) in sync
Sven Verdoolaege [Tue, 6 Oct 2009 08:58:17 +0000 (10:58 +0200)]
isl_tab_sample: be more verbose about unbounded directions
Sven Verdoolaege [Sun, 27 Sep 2009 20:00:02 +0000 (22:00 +0200)]
separate out isl_tab_sample from sample_bounded
Sven Verdoolaege [Sat, 26 Sep 2009 14:42:31 +0000 (16:42 +0200)]
sample_bounded: reimplement to work directly on a tableau
In other words, adapt the implementation of isl_basic_set_samples
in polytope_scan.c
This avoids the reconstruction of tableaus and allows for a refactoring
that takes a tableau as input.
Sven Verdoolaege [Sat, 26 Sep 2009 13:49:55 +0000 (15:49 +0200)]
isl_tab_compute_reduced_basis: work with affine basis instead of linear basis
Sven Verdoolaege [Sat, 26 Sep 2009 13:31:12 +0000 (15:31 +0200)]
isl_tab_compute_reduced_basis: allow incremental computation
Sven Verdoolaege [Sat, 26 Sep 2009 13:05:07 +0000 (15:05 +0200)]
isl_polytope_scan: use isl_tab_from_basic_set
Sven Verdoolaege [Sat, 26 Sep 2009 11:20:40 +0000 (13:20 +0200)]
separate out isl_tab_reduced_basis from isl_basic_set_reduced_basis
This allows us to compute a reduced basis on a set given in tableau form.
Sven Verdoolaege [Fri, 25 Sep 2009 10:57:10 +0000 (12:57 +0200)]
basis_reduction_tab.c: use isl_tab_product to construct product tableau
Before, we would manually construct a tableau for the Cartesian
product of a set with itself. Now, we first create a tableau
for the set and then construct the product tableau.
This should be more efficient and allows us to refactor
the code to pass in a tableau instead of a set.
Sven Verdoolaege [Thu, 8 Oct 2009 20:53:30 +0000 (22:53 +0200)]
add isl_tab_product
Sven Verdoolaege [Wed, 7 Oct 2009 18:28:30 +0000 (20:28 +0200)]
isl_basic_set_reduced_basis: fix value in directions with only one integer value
If two or more directions have a width that is smaller than one,
i.e., such that the only one integer value can be attained,
then the standard algorithm would still try to order these
directions. However, if the first directions only admit one
value, then it doesn't matter in which order they are put.
We therefore keep track of such directions explicitly and
also set the value in the tableau to the fixed value, rather
than keeping the rational interval with only one integer value.
Sven Verdoolaege [Fri, 9 Oct 2009 08:40:23 +0000 (10:40 +0200)]
isl_basic_set_reduced_basis: fix up documentation
Sven Verdoolaege [Fri, 25 Sep 2009 10:46:06 +0000 (12:46 +0200)]
basis_reduction_tab.c: keep track of con_offset instead of n_ineq
This is a minor cosmetic change.
Sven Verdoolaege [Thu, 8 Oct 2009 12:43:07 +0000 (14:43 +0200)]
add isl_tab_add_eq
Sven Verdoolaege [Wed, 7 Oct 2009 18:19:03 +0000 (20:19 +0200)]
isl_tab_add_valid_eq: add special treatment for manifestly zero rows
Sven Verdoolaege [Thu, 17 Sep 2009 10:09:46 +0000 (12:09 +0200)]
isl_tab_extend_cons: check tab argument
Sven Verdoolaege [Tue, 29 Sep 2009 12:13:29 +0000 (14:13 +0200)]
rename isl_tab_detect_equalities to isl_tab_detect_implicit_equalities
Sven Verdoolaege [Sun, 27 Sep 2009 19:38:20 +0000 (21:38 +0200)]
isl_tab_from_recession_cone: take basic set instead of basic map as argument
Sven Verdoolaege [Sun, 27 Sep 2009 16:55:27 +0000 (18:55 +0200)]
isl_ilp.c: separate out solve_ilp_search