[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
summetrix or anti-symmetric and this is a pre-requisite for the problem
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
or if it would be worthwhile to merge the variables, either using a
model or by pre-processing. I assume that there in general can be 
round-off issues when performing this type of variable merging, but
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.



Help-glpk mailing list
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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]