[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] C API: Setting up a least-absolute-deviation
From: |
glpk xypron |
Subject: |
Re: [Help-glpk] C API: Setting up a least-absolute-deviation |
Date: |
Wed, 05 Sep 2012 17:03:25 +0200 |
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