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: [email protected] [mailto:[email protected]] On Behalf Of Oscar Gustafsson Sent: Wednesday, December 17, 2008 9:10 AM To: [email protected] 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 [email protected] 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. ---------------------------------------------------------------------------- _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
