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

[Michael Hennebry]

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

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