Option optcr

Some of the MIP models in http://www.amazon.com/gp/product/0471150436 (these models are written in GAMS) seem to be missing OPTION OPTCR=0, so some non-optimal solutions are presented. By default GAMS uses a 10% relative gap criterion.

E.g.:

But I see:

Next month teaching a GAMS course in Germany. I’ll be sure to mention this (and how to spot this in the listing file).

GAMS is quite unique in having a default with nonzero gap optimality criteria. Other systems typically like to solve to optimality unless instructed otherwise.

PS. See comment for another system with a nonzero gap tolerance.

Cplex 12.5 vs 12.4 Out of memory handling

With Cplex 12.4:

Besides Cplex crashing here, we also see poor error recovery and exception handling by the calling problem. It is good to see that with Cplex 12.5 we see much better behavior:

This is with 32 bit software. We could use a 64-bit version instead to allow larger memories, but instead I opted for reformulating the model and making it smaller so I don’t leave this work to the presolver.

Better element names

Sometimes I see GAMS code like:

SETS
  K index of periods of time  /1*4/
  J index of generators /1*3/

In general I don’t like plain numbers as set elements. I prefer something like:

SETS
  K index of periods of time  /t1*t4/
  J index of generators /gen1*gen3/

This often improves the readability of the output. This is especially the case in the GDX viewer where we can swap rows and columns. Here is a some sample output:

Numerical	Id+Numerical
SETS   K index of periods of time  /1*4/   J index of generators /1*3/	SETS   K index of periods of time  /t1*t4/   J index of generators /gen1*gen3/
----    110 VARIABLE p.L  output power of generator j at period k               2           3           4   1     150.000     350.000     260.000 2                 100.000 3                  50.000     140.000	----    110 VARIABLE p.L  output power of generator j at period k                 t2          t3          t4   gen1     150.000     350.000     260.000 gen2                 100.000 gen3                  50.000     140.000

For this small example this is not terribly convincing, but for larger, high-dimensional data it surely helps in understanding output quickly.

Lazy Constraints and GAMS

> Can I use lazy constraints in my GAMS model?

Sorry, the answer is “no”. Lazy constraints are supported by the Cplex and Gurobi solvers. Other modeling systems (AMPL, AIMMS) support lazy constraints, but GAMS does not. There have been some attempts to implement this in GAMS but they were not useable in practice (using scalar models as intermediary). This was more for testing I think. 

Here is a discussion on lazy constraints: http://orinanobworld.blogspot.com/2012/08/user-cuts-versus-lazy-constraints.html

Long SQL queries

Over the holidays I ran a small script against SQL Server. Basically spatial queries. I ran the script in pieces to make sure I did not have to rerun the whole thing if something went wrong. That was a good idea: some of the queries took 6 or 7 hours or more. With memories getting larger, may be tasks like this are better done in-core than using a database. 

No error message

I have posted regularly about poor error messages from software. In general I find that the importance of formulating meaningful  error messages is underestimated by developers, leading to some level of frustration by users. Of course, issuing no error message at all is even easier for a developer (and even more difficult for users to deal with).

S O L V E      S U M M A R Y      MODEL   LANDfeas            OBJECTIVE  totallow      TYPE    LP                  DIRECTION  MINIMIZE      SOLVER  MOSEK               FROM LINE  165233 **** SOLVER STATUS     4 Terminated By Solver      **** MODEL STATUS      14 No Solution Returned     **** OBJECTIVE VALUE                0.0000 RESOURCE USAGE, LIMIT         20.311    900000.000 ITERATION COUNT, LIMIT         0        900000     Copyright (C)   MOSEK ApS, Fruebjergvej 3, Box 16                     DK-2100 Copenhagen, Denmark                     http://www.mosek.com GAMS/MOSEK Extended license detected No solution returned

I received a listing file with this fragment. I have no idea how I can help the user as I have no idea what went wrong. Now I need to get the model and data files and see if I can reproduce the problem. We see some strange trade-offs at work here: the developers saved some time by not providing code to print a readable message, and as a result (multiple) users have to spent extra time and effort in supporting and maintaining an application.

MySQL and union

For a GAMS model I need to read data from a MySQL database. Some of the data can be easily imported into a GAMS gdx file using an SQL UNION construct:

SELECT id,xxx FROM tableA
UNION
SELECT `obj’,xxx FROM tableB

Now the interesting part is that ids are INTs. So basically the first column looks like

1	xxx
2	xxx
3	xxx
obj	xxx

On my MySQL installation, the first column gets a correct type of VARCHAR(11) as the integer type was INT(10) – the extra char is for the sign I think (although we have only positive ids). However when the client was testing this, it went terribly wrong. Turned out that their MySQL version created a type of VARBINARY(11), a BLOB like type. This created havoc downstream. Luckily I was using $LOADDC in GAMS to read the GDX file produced by SQL2GMS, so we caught a domain error.

No doubt this was bad SQL produced by me. I tried something similar with SQL Server, and SQL Server complains directly about not being able to put a string into integer type. The fix: using a cast as in:

SELECT cast(id as char(10)),xxx FROM tableA
UNION
SELECT `obj’,xxx FROM tableB

A little bit troublesome that different versions of MySQL behave differently on this.

Fun with SQL Server and Quotes

I am trying to help with some SQL and we were really having fun today! A complicated dynamic SQL statement involving cursors was failing with the illuminating error: syntax error near ‘a’. When working with SQL Server it is not easy to parameterize for table names, hence the dynamic SQL instead of normal static SQL. Well, the problem turned out to be a quote in a name in the database. This was causing the generated SQL statement to be incorrect.

The best would be to fix all SQL queries, but that was not feasible right now. Instead we tried to replace all quotes by two quotes. (This was a staging table anyway, so no problem in polluting this table: it is not used by others). Sometimes you have to be pragmatic and take a short cut. The static SQL to do: replace a single quote by two single quotes looks already funky but the dynamic SQL version is really horrific:

Low cost parallel computing

There are a few interesting projects going on:

• Raspberry Pi + Lego based “supercomputer”: http://www.southampton.ac.uk/~sjc/raspberrypi/. It is estimated you need 1.4 million Raspis (and a lot of Lego) to build a machine that appears in the TOP500 of supercomputers (http://hackaday.com/2012/09/12/64-rasberry-pis-turned-into-a-supercomputer/).
• Adepteva (http://www.adapteva.com/) is working on a $99 board including some 16 parallel RISC coprocessor cores. “A cluster of 100 16-core Parallellas would cost $10,000 and provide 10 teraflops” (http://arstechnica.com/information-technology/2012/09/99-raspberry-pi-sized-supercomputer-touted-in-kickstarter-project/).

History of LP/MIP

http://www.gurobi.com/pdf/a-brief-history-of-optimization.pdf. I am always fascinated by these stories… Every time when looking back I am impressed by the size and complexity of models we can solve these days on our laptops compared to what we could solve on mainframes and supercomputers a few decades ago (and with much more convenience).

PS. You also may want to look at the whole issue at: http://www.zib.de/groetschel/publications/OptimizationStories.pdf. More interesting historic details about optimization.

GAMS question

A question was posed at https://groups.google.com/forum/?fromgroups=#!topic/gamsworld/0qYEcVd9x8I:

set    j  /n1*n5/,        k  /n5/; variable pi(j); scalar ab; ab=sum (k, sum(j$(ord(j)=ord(k)), pi.L(j) )  );

The user want to pick the 5-th element. This implementation clearly does not work. Some valid answers were given:

Ab= sum(j$sameas(j,“n5“), pi.L(j) )  ; or ab=sum (k, sum(j$sameas(j,k), pi.L(j) )  );

However I would say this is not really good modeling practice. The best approach IMHO would be:

set   j     /n1*n5/,       k(j)  /n5/; variable pi(j); scalar ab; ab=sum(k, pi.L(k));

There are two advantages of this approach:

• The set k is now domain checked against j; no elements outside j can be specified here without alarm bells going off. Domain checking is very important when developing large, complex models.
• We can substantially simplify the assignment to ab and increase readability. The expression conveys immediately what it is supposed to do.

Setting up proper subsets will help you down the road.

Parallel LP

> Can I run LP solver in parallel on multiple cores? What about all running on GPUs?

All major LP solvers include a barrier/interior point code that can run on multiple cores. This includes Cplex, Gurobi and Mosek. Do not expect perfect scaling but some speed-up is possible. Sparse simplex algorithms are not ideally suited for parallelization. Some recent results were shown by John Forrest. See: ISMP 2012 talk.

About GPUs:

(From the same talk).

There are some other algorithms that can be implemented on GPUs. Many meta-heuristics have been ported to these devices. Here are some links:

• http://www.fit.vutbr.cz/research/view_pub.php?file=%2Fpub%2F9184%2F60240442.pdf&id=9184
• http://link.springer.com/chapter/10.1007%2F978-3-642-04843-2_4?LI=true
• http://www.gputechconf.com/content/GTC/posters/2010/A04-Parallel-Ant-Colony-Optimization-with-CUDA.pdf
• http://sikaman.dyndns.org:8888/honours/karim-tantawy-winter-2011.pdf
• and many more