[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: [Help-glpk] Identical variables
From: |
Meketon, Marc |
Subject: |
RE: [Help-glpk] Identical variables |
Date: |
Wed, 17 Dec 2008 10:54:24 -0500 |
There's one case when you do not want the preprocessor to process out
symmetry constraints.
Interior point algorithms for sparse matrices work well unless the
matrix had "dense" columns, in which case the computations dramatically
increase. A common way to get rid of dense columns is to split them up.
So if the column corresponding to variable x[i] is dense, new variables
called z[1], z[2], z[3], ... ,z[K] are created where, say, 5 non-zeros
from column x[i] are used for the column associated with z[1], and 5
more are associated with z[2] and so on (so 5*K = the number of
non-zeros in the original column x[i]), then we remove column x[i] but
add the constraints z[1] = z[2], z[2]=z[3], ... z[K-1]=z[K]. This helps
retain the quickness of interior point calculations, and having the
preprocessor put them together back into the equivalent of x[i] would
be counter-productive.
-----Original Message-----
From: address@hidden
[mailto:address@hidden On
Behalf Of Oscar Gustafsson
Sent: Wednesday, December 17, 2008 9:10 AM
To: address@hidden
Subject: [Help-glpk] Identical variables
Dear all,
I just formulated an FIR filter design problem where I want to utilize
symmetry of filter taps (for linear-phase FIR filters the filter taps
are
summetrix or anti-symmetric and this is a pre-requisite for the problem
to
be formulated as LP). This is usually not a problem since it is pretty
straightforward to formulate it using just one set of variables.
However, the current filter structure is ratehr non-trivial leading to
that I use both instances of the symmetric variables and then put a
symmetry constraint (basically s.t. c{in in C}: h[i] = h[N-i];)
However, it doesn't seem like the pre-processing removes the additional
variables, which I sort of expected/hoped for. My question is really if
the solver does something smart when such equality constaints are
present
or if it would be worthwhile to merge the variables, either using a
better
model or by pre-processing. I assume that there in general can be
round-off issues when performing this type of variable merging, but
maybe
that is tractable.
I could probably give it a go and write the required pre-processing
function given that there are no objections or something I have missed.
Regards
Oscar
_______________________________________________
Help-glpk mailing list
address@hidden
http://lists.gnu.org/mailman/listinfo/help-glpk
----------------------------------------------------------------------------
This e-mail and any attachments may be confidential or legally privileged. If
you received this message in error or are not the intended recipient, you
should destroy the e-mail message and any attachments or copies, and you are
prohibited from retaining, distributing, disclosing or using any information
contained herein. Please inform us of the erroneous delivery by return e-mail.
Thank you for your cooperation.
----------------------------------------------------------------------------