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

[Robbie Morrison]

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]