RE: [Help-glpk] Identical variables

[Meketon, Marc]

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.
----------------------------------------------------------------------------