Elimination of redundant inequalities
Mathieu Dutour
I have a list of 3774 linear inequalities:
sum_{1<= k<=21} a_{ik} xk >=0
1<=i<=3774
many of them are redundant. I am interested in the geometry
of the cone defined by these inequalities and in particular to
the extreme rays of that cone.
I use cdd to find those extreme rays:
http://www.ifor.math.ethz.ch/~fukuda/cdd_home/cdd.html
and it works quite well usually. Unfortunately this is not the
case here and I am quite sure that elimination of redundancy will
improve things a lot.
To test if j-th inequality is redundant I consider the linear
programming problem:
sum_{1<= k<=21} a_{ik} xk >=0
1<=i<=3774, i not equal j
minimize
sum_{1<= k<=21} a_{jk} xk
if infimum is 0 this mean that j-th inequality is redundant, if it
is -infty this mean it is not redundant.
cdd manage to solve one minimization problem of that type in 5
minutes on a K6-200 (and there thousands of minimization to
consider).
This is insufficient, I need something faster and of free use to
do this. Do you have any idea of a suitable program to do this?
Mathieu
Lutz Tautenhahn
"Mathieu Dutour" <dut...@nef.ens.fr> schrieb im Newsbeitrag
news:9ipiba$1fku$1...@nef.ens.fr...
Hi,
I would do some precomputing, first transform the problem into
n_i * x >= 0 with normal vectors n_i = a_i/|a_i|,
where a_i and x are the vectors of a_{ik} and xk,
respectively. If |a_i|=0 then throw this inequality away.
Calculate vector m=sum(n_i)/|sum(n_i)| and the scalar product
d_i = m * n_i for every i. The inequalities with d_i close to 1 are
likely to be redundant. Sort the inequalities, so that
d_{rank[1]}= d_min and d_{rank[3774]} = d_max
Then use your approach with a reduced problem size
(N instead of 3774 inequalities)
n_{rank[i]} x >=0
1<=i<=N
minimize
n_{rank[j]} x (for a j >N)
This will find many of the redundant inequalities. Finally you must
apply your method on the remaining inequalities, but this will be
hopefully much less than 3774. I think a good choice for N is about
100 (a few times the dimension of your problem, which is 21).
When you choose a smaller value than 100 for the precomputing,
then precomputing is faster, but you will probably find less redundant
inequalities, so your final computing will take more time. You could also
do the precomputing several times with increasing N (N= 50, 100, 200)
and recalculated m and d_i and rank[i] values.
Regards, Lutz Tautenhahn
Mathieu Dutour
Lutz Tautenhahn <lutz.ta...@wirtschaft.tu-chemnitz.de> wrote:
>Hi,
>I would do some precomputing, first transform the problem into
>n_i * x >= 0 with normal vectors n_i = a_i/|a_i|,
>where a_i and x are the vectors of a_{ik} and xk,
>respectively. If |a_i|=0 then throw this inequality away.
>Calculate vector m=sum(n_i)/|sum(n_i)| and the scalar product
I don't understand what is m
>d_i = m * n_i for every i. The inequalities with d_i close to 1 are
>likely to be redundant. Sort the inequalities, so that
>d_{rank[1]}= d_min and d_{rank[3774]} = d_max
>Then use your approach with a reduced problem size
>(N instead of 3774 inequalities)
>
>n_{rank[i]} x >=0
>1<=i<=N
>minimize
>n_{rank[j]} x (for a j >N)
>
>This will find many of the redundant inequalities. Finally you must
>apply your method on the remaining inequalities, but this will be
>hopefully much less than 3774. I think a good choice for N is about
>100 (a few times the dimension of your problem, which is 21).
>When you choose a smaller value than 100 for the precomputing,
>then precomputing is faster, but you will probably find less redundant
>inequalities, so your final computing will take more time. You could also
>do the precomputing several times with increasing N (N= 50, 100, 200)
>and recalculated m and d_i and rank[i] values.
>Regards, Lutz Tautenhahn
>
Thank you very much the idea of taking only a finite subset of the
inequalities where the leader are expected to live is a good one
Time cost change from 5min to 7 seconds which is quite a progress.
Nevertheless I apply another heuristic since I don't understand the
definition of vector m.
But I need to explain a little what I am doing:
I have 3773 inequalities (math stuff: "hypermetric" inequalities with
very few zeros, the bad case).
I add one inequality to this one and many inequalities become
redundant. Associated to this inequality (facet )is some 20 extreme
rays. for each of this 3773 extreme rays, I count their incidence
with the 20 extreme rays.
These incidence number serve me as an heuristic for their importance.
Now that my problem is mainly solved (only hard work now) I have a more
general question:
Do you know some reference on the web or in the litterature for the
Heuristics in Linear programming and redundant elimination?
Thank you very much Lutz!
Mathieu
Lutz Tautenhahn
m is a normalized vector which direction is the average direction of the
n_i vectors. In 3 instead of 21 dimensions and with 3 instead
of 3774 vectors, for example
n_1=(1,0,0), n_2=(0,1,0) and n_3=(0,0,1)
you would get
m=(1,1,1)/|(1,1,1)|=(1,1,1)/sqrt(3)=(sqrt(1/3),sqrt(1/3),sqrt(1/3))
Your problem is equivalent to finding a convex hull in higher
dimensions.
(I wouldn't use this approach, as it will not simplify things, its just only
worth to think about it). Assume you have found a normalized vector m, with
n_i * m > 0 for all i.
If there doesn't exist such a vector, then your system would only have the
trivial solution x=0.But even if there exist such a vector m, it can be hard
to find one. How hard this is, depends on your data.
When you have found m, you could calculate the projection of the n_i vectors
on the hyperplane which has the normal vector m:
p_i = n_i - m * (m * n_i)
and find the convex hull of the p_i, which correspond to the not redundant
inequalities. But finding the convex hull is also a hard job.
Btw, if you already know the extreme rays r_j of the system with 3773
inequalities and want to add another inequality to the system you could
easily check if this is a redundant inequality: if there exists a r_j with
r_j * n_3774 < 0
then the new inequality is not redundant, otherwise it is redundant.
> Now that my problem is mainly solved (only hard work now) I have a more
> general question:
> Do you know some reference on the web or in the litterature for the
> Heuristics in Linear programming and redundant elimination?
We use to recommend http://plato.la.asu.edu/guide.html
and also http://www.ifor.math.ethz.ch/~fukuda/polyfaq/polyfaq.html
(as you surely already know) is a good reference for your problem.
Note that your problem is easier then the general problem of eliminating
redundant inequalities, because all of your inequalities are ...>=0.
Regards, Lutz.