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

[Jared Miller]

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