Re: [Help-glpk] C API: Setting up a least-absolute-deviation

[glpk xypron]

Hello Jared,

you will have to keep the u[i] variables as columns in your problem.
And the objective will only have nonzereo coefficients w[i] for these
columns.

Have a look at http://www.xypron.de/projects/linopt/examples.html
to see how accessing the GLPK API can be eased by a wrapper.

Best regards

Xypron

-------- Original-Nachricht --------
> Datum: Tue, 4 Sep 2012 17:39:54 -0700
> Von: Jared Miller <address@hidden>
> An: GLPK help <address@hidden>
> Betreff: Re: [Help-glpk] C API: Setting up a least-absolute-deviation

> Robbie,
> 
> Thanks for the reply. To clarify, I'm not asking for help with the basics
> of the C API (it looks pretty straightforward if your problem is in the
> right form); rather I'm asking how to translate my high-level formulation
> (which includes the dummy u[i]'s) into the low-level formulation (with only
> auxiliary and structural variables, objective only in terms of the structural,
> and all the bounds constant).
> 
> I'll try loading/translating my MathProg file into a "glp_prob" struct and
> examining the internal translation. Eventually I need to work on
> abstracting a way of getting problems of this type into the GLPK low-level 
> form.
> 
> On Sep 1, 2012, at 11:25 AM, Robbie Morrison wrote:
> 
> > 
> > Hello Jared
> > 
> > ------------------------------------------------------------
> > To:           address@hidden
> > Subject:      [Help-glpk] C API: Setting up a least-absolute-deviation
> > Message-ID:  <address@hidden>
> > From:         Jared Miller <address@hidden>
> > Date:         Fri, 31 Aug 2012 15:52:11 -0700
> > ------------------------------------------------------------
> > 
> >> I have an absolute value objective function, minimizing
> >> the sum of abs( s[i] - x[i] ) for two vectors s and x,
> >> with the constraints given by Ax = b where A is a large
> >> but very sparse matrix.
> >> 
> >> So I'm using a dummy vector "u" in a MathProg model:
> >> 
> >>  minimize least_abs_dev: sum {i in I} (u[i]);
> >>  s.t. constr1{i in I} : b[i] = sum{j in I} (A[i,j] * x[j]);
> >>  s.t. constr2{i in I} : u[i] >= (s[i] - x[i]);
> >>  s.t. constr3{i in I} : u[i] >= -(s[i] - x[i]);
> >> 
> >> I also eventually want to incorporate weights into the
> >> objective:
> >> 
> >>  minimize least_abs_dev: sum {i in I} (u[i] * w[i]);
> >> 
> >> I've got this type of model working using MathProg
> >> and glpsol, but now I'm trying to figure out how to
> >> translate it to the strict form required by the C
> >> API.  Has anyone done this?  What's the best way to
> >> go about it?  I'm going to need high performance on
> >> some large problems.
> >> 
> >> I am fairly new to optimization and GLPK.  Any help
> >> would be much appreciated.
> >> 
> >> - JM
> > 
> > I'm not exactly sure what your question is, but here
> > are some observations base on my experiences.  I'm
> > going to assume C++ too.
> > 
> > First, there are some GLPK wikibook pages:
> > 
> >  http://en.wikibooks.org/wiki/GLPK/Using_the_GLPK_callable_library
> >  http://en.wikibooks.org/wiki/GLPK >> sections 14.1 thru 14.6
> > 
> > Second, you will probably need to understand how the
> > GLPK MathProg translator translates your high-level
> > model into a low-level problem -- unless you have some
> > other insights based on the theoretical formulation of
> > your problem.  One way of doing this is to formulate
> > simple instances of your model and examine the problem
> > in say CPLEX LP format.
> > 
> >  http://en.wikibooks.org/wiki/GLPK/Interoperability#CPLEX.C2.A0LP_format
> > 
> > I ended up writing a C++ class that interrogated the
> > GLPK problem object and produces an HTML table to view
> > in a web browser.  Detailed routine work which
> > invariably took several loops to get right.
> > 
> > Third, some kind of abstraction between your model
> > formulation and the raw GLPK calls could be useful.
> > One relatively simple example can be found here:
> > 
> >  http://en.wikibooks.org/wiki/GLPK/IAJAAR.H_project
> > 
> > I wrote a large class to provide a semi-intelligent
> > interface with GLPK.  This class tracked rows and
> > columns as they were added and performed integrity
> > checks too.  Then I had another abstraction above this
> > related to my domain modeling needs.  A background in
> > computer science can help here.
> > 
> > In any event, I am guessing that you will need to know
> > exactly how your structural matrix and your objective
> > vector are being build, one API call at a time.
> > 
> > REFERENCES
> > 
> > One reference.  Not sure exactly how useful it is.
> > I could dig out some more if you can give me a better
> > idea of where exactly you are headed.
> > 
> > @incollection{
> >   Author = {Hultberg, Tim H.},
> >   Title = {Formulation of linear optimization problems in C++ [includes
> > MIP]},
> >   BookTitle = {Programming languages and systems in computational
> > economics and finance},
> >   Editor = {Nielsen, Soren S.},
> >   Publisher = {Kluwer Academic Publishers},
> >   Address = {Boston, MA, USA},
> >   Pages = {199-229},
> >   Note = {Chapter 6},
> >   Year = {2002} }
> > 
> > HTH, Robbie
> > ---
> > Robbie Morrison
> > PhD student -- policy-oriented energy system simulation
> > Technical University of Berlin (TU-Berlin), Germany
> > University email (redirected) : address@hidden
> > Webmail (preferred)           : address@hidden
> > [from Webmail client]
> > 
> > 
> 
> 
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/help-glpk