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

[Reginald Beardsley]

I've already tested adding a binary weight parameter for the 2nd stage job.  
Works great!  

I've roughed out the script that will generate the necessary specification in 
the data file, but have not implemented and tested.  But it's pretty simple to 
write an awk script that writes a script that is then executed.  Something I've 
done many times.  The reason for doing it this way is it avoids having to 
specify all the weights.  By default awk initializes everything to zero, so all 
I have to do is specify the few non-zero elements and then print out the array 
in  GMPL form.  With potentially 10-30,000 elements and only a handful of 
non-zero elements, this is a big win.

Were it  not for your suggestion I'd have wandered off and done something much 
harder.

I've got a book on the way describing the mathematics of compressive sensing.  
So I'm likely  to be pushing a good bit farther with this.  There's a huge 
range of applications in science and engineering.

A few years ago if asked about doing some of this I'd have given the inquirer a 
severe look and said, "You realize that won't work, don't you."  Foreman Acton 
describes a number of problems he asserts should not be solved with a computer. 
 But the world has changed. Now you can do it easily. No one has quite figured 
out what all the new rules are, but L1 has some amazing properties when solving 
inverse problems.  We just couldn't afford the compute until a few years ago.  
The only down side is lots of different jargon for describing the same thing 
because so many disciplines are using the techniques.

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

 Subject: Re: [Help-glpk] Applying a threshold to the solution using GMPL?
 To: "Reginald Beardsley" <address@hidden>
 Cc: "glpk" <address@hidden>
 Date: Sunday, November 10, 2013, 11:54 AM
 
 On Sat, 9 Nov 2013, Reginald
 Beardsley wrote:
 
 > I've been  hoping it can be done with binary
 variables in GMPL as I'm still trying to refine the problem
 statement.  I'd like to be confident it's a good choice
 before coding it. I'd also like to improve my grasp of
 expressing problems in GMPL.  I started out using CPLEX
 format and switching to GMPL has been a huge improvement
 when trying to explore various problem formulations.
 
 I'd recommend against.
 You end up with constraints like
 x <= U(x)*b
 where U(x) is an upper bound on x.
 
 > With a two step solution if i set the weights to 0 or 1
 I can probably get what I want by light editing of the data
 file using awk to add the weighting array.  Not perhaps
 as elegant as solving in a single step, but it would allow
 using a pure LP solution and avoid the performance hit that
 a MIP formulation implies.  Until I read your
 suggestion I'd been thinking along the lines of writing a
 whole new data file which was pretty painful to
 contemplate.
 
 In the second stage, binaries might be more useful.
 You already have a feasible solution and you
 can substitute smaller numbers for the U(x)'s.
 
 If you do not mind writing code:
 
 more=false
 do {
     for each x[j]:
         if x[j] != 0:
             if changing x[j]
 to 0 would not increase L1 too much:
                
 change x[j] to 0
                
 more=true
 } while(more)
 
 This would not necessarily be optimal.
 The only x's changing are those changed to zero.
 You could run the LP again with the new constraints and
 repeat the process.
 Of course, using the API,
 each change x[j] to 0 could be followed by a
 reoptimization.
 
 -- 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