Saturday, June 13, 2009

Generated models

When programs generate models in MathProg/AMPL they tend to have a different structure. In this case a scalar model was generated with some very long lines. The user reports some very large memory usage:

Model has been successfully generated
glp_simplex: original LP has 93 rows, 5256 columns, 84143 non-zeros
glp_simplex: presolved LP has 82 rows, 5256 columns, 77163 non-zeros
Scaling...
A: min|aij| =  1.000e+00  max|aij| =  1.600e+02  ratio =  1.600e+02
GM: min|aij| =  4.952e-01  max|aij| =  2.019e+00  ratio =  4.077e+00
EQ: min|aij| =  2.471e-01  max|aij| =  1.000e+00  ratio =  4.048e+00
Crashing...
Size of triangular part = 82
      0: obj =   0.000000000e+00  infeas =  5.657e+00 (0)
*    50: obj =   1.410800000e+00  infeas =  0.000e+00 (0)
*    80: obj =  -7.209526707e-32  infeas =  2.776e-17 (0)
OPTIMAL SOLUTION FOUND
Time used:   0.1 secs
Memory used: 2008.7 Mb (2106232859 bytes)

(With some versions it may even stop with a stack overflow). Indeed this is due to the modeling language part and not the solver per se. When we run:

$ glpsol --math big.mod --wcpxlp big.lp
$ glpsol --cpxlp big.lp

the second invocation will just use a fraction of the memory. Clearly glpk has troubles with very long scalar expressions.

Actually AMPL is not doing much better:

big.mod, line 7005 (offset 158374):
        HES03 is not defined

Looks like we hit a max line length limit, and a variable name is truncated leading to this error. A better message would be “line is too long”. Even better is not to have artificial limits on input lines.

I remember reports about similar issues with early versions of the GCC compiler: it had problems with machine generated C code where expressions were spanning several pages. This was very different from how a normal programmer would write code.

7 comments:

  1. Dear Erwin,
    First of all, congratulations for your blog. It's very very useful and interesting. I am a professor at an university from Brazil (Fortaleza, CearĂ¡). I am using lp_solve (IDE and API) in my classes. However, I want to use an another most powerfull alternative. I know there is a lot of kind of solvers (free, not free, etc).
    I would like to know what is the best open source alternative (lp_solve, coin_or, glpk, etc). Have you got any opinion about that?
    I can't find any reliable benchmark.
    Thanks,
    Jorge Bergson.

    ReplyDelete
  2. Lp_solve does not always seem to be able solve more complicated MIPS. GLPK has some cuts and has some more chance. CBC and SCIP are even more advanced and should in general often perform better. In practice you may want think about using a LP/MIP solver in conjunction with a modeling language. GLPK comes with its own AMPL clone. I am not 100% sure about availability of an open source modeling system for CBC or SCIP.

    ReplyDelete
  3. Erwin, thank you for your considerations. You are right when talk about solver-modeling language (it's really better working with a modeling language). I have a important question for you :-).If you have to choose an open source solver, which these (cbc,scip, another?) you will choose?

    COIN-OR is a very good iniciative, but I think that it's need more attention from your members.

    My english isn't very good. Please, forgive me for any errors :-)

    Thanks,
    Jorge Bergson.

    ReplyDelete
  4. I would probably not decide on a solver in advance: I would develop a model and then see which solver is most suitable. Of course I don't teach math programming classes, so my situation is different. For a class the open source gusek+glpk may be a nice combination to implement medium sized models. Otherwise I would look into student versions of AMPL and GAMS.

    ReplyDelete
  5. Take a look at drools-solver (apache license) too: it lays no restrictions on the model, except that it has to be java classes.
    Those classes can extend whatever they want and be annotated with JPA, ... annotations as much as they like.
    Your model does need 1 class that implements the Solution interface (which has 2 methods: 1 to clone the solution and 1 to let the solver know of all your other class(es) instances).

    http://www.jboss.org/drools/documentation.html
    http://blog.athico.com/search/label/solver

    https://hudson.jboss.org/hudson/job/drools/lastSuccessfulBuild/artifact/trunk/target/docs/drools-solver/html_single/index.html

    ReplyDelete
  6. Hi Ervin,
    I want to know, how it's possible to connect Data to a Oracle 10g databae using the gusek interface in gmpl. Mybe you know where i can get some informations or you know how to do and make a little example. google is not very helpful.
    with kind regards
    Thomas

    ReplyDelete
  7. Yes that should be possible via ODBC. My help would need to be covered by some consultancy contract.

    ReplyDelete