Re: [Help-glpk] Applying a threshold to the solution using GMPL?

[Reginald Beardsley]

 Marc's suggestion fits very nicely with what I'm trying to do at the moment.

I sometimes get terms which constitute much less than 1% of the total result.  
Those are what I want to drop.  Doing so requires recalculating the other terms 
to minimize the error. 

I may want to do something fancier eventually, but right now I'm still trying 
to develop an appropriate mathematical model for the physics.

That said, there's another problem for which what is suggested here looks very 
attractive.  I've attempted to solve that problem several times over the course 
of 20+ years without ever finding a satisfactory solution.  It involves finding 
the derivative of a series irregularly sampled in x with truncation errors in 
both x & y.  When the data are finely sampled in x the truncation to 3-4 digits 
in y leads to wild swings in the derivative.  To date the only solution has 
been smoothing based on ersatz heuristics.  Good enough, but not aesthetically 
satisfying.

--------------------------------------------
On Mon, 11/11/13, Michael Hennebry <address@hidden> wrote:

 Subject: RE: [Help-glpk] Applying a threshold to the solution using GMPL?
 To: "Meketon, Marc" <address@hidden>
 Cc: "Reginald Beardsley" <address@hidden>, "glpk" <address@hidden>
 Date: Monday, November 11, 2013, 11:53 AM
 
 On Sun, 10 Nov 2013, Meketon, Marc
 wrote:
 
 > Instead of Awk, there is another way of doing this
 which I often find is easier because all the calculations
 stay within GMPL:
 
 I expect that your GMP will work as advertised,
 but that what OP wants is a bit more compilcated than that.
 
 What I expect OP wants is to have as many X's as possible
 forced to zero without damaging the L1 norm too much.
 
 I'm not clear whether that is best expressed as a bound
 on the L1 norm or providing a penalty for nonzero X's.
 
 More than two iterations might be useful.
 
 The first iteration is, of course,
 to find an optimal solution for the problem without
 considering sparsity.
 
 If, from simple arthmetic, one can find X's that can be
 forced
 to zero without changing other X's, one should do so.
 OP's original approach seemed to be intended select each X
 independently,
 so that even if all met the threshold and the damage was
 completely additive, the total damage would not be too much.
 (*)
 After re-solving, that approach could be used
 again until it failed to zero any more X's.
 
 Subsequent iterations wouuld involve separately forcing
 each nonzero X to zero and assessing the damage.
 After that, one could force X's to zero in ascending
 order of damage until the L1 threshold had been reached.
 
 
 (*) If one can sort, Add in the X's in ascending
 order of damage until the sum is too big.
 If one prefers GMPL, I think that one can do something like
 this:
 TDA=total damage allowed
 S1={ (i,j) : damage[i,j]<=TDA }   
    # probably too big
 S2={ (i,j) : damage[i,j]*|S1|<=TDA }  # probably too
 small
 TDA2=SUM{ (i,j) in S2 }(damage[i,j])  # not best
 formula
 S3={ (i,j) : damage[i,j]<=TDA-TDA2 } - S2  #
 probably too big
 S4={ (i,j) : damage[i,j]*|S3|<=TDA-TDA2 }  #
 probably too small
 Zero X[i,j] : (i,j) in S2+S4
 
 One can sort with GMPL, but I suspect that it is at least
 quadratic:
 http://en.wikibooks.org/wiki/GLPK/GMPL_Workarounds
 
 -- address@hidden
 "On Monday, I'm gonna have to tell my kindergarten class,
 whom I teach not to run with scissors,
 that my fiance ran me through with a broadsword." 
 --  Lily