Thursday, September 22, 2011

Most popular programming languages

http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html. I never know how to interpret these things exactly. May be the trends are more important than the absolute positions.

Some of my impressions:

Tuesday, September 20, 2011

Time schedules

Here is a good example how a web based rostering system can look like: http://www.timeforge.com. The videos at http://www.timeforge.com/manual/video-manual/ are an easy way to see how this all works.

They are in fact using MIPs in some of their algorithms!

Monday, September 19, 2011

Cplex MIP and time limits

Looks like Cplex tries to do something smart just before it hits a time limit: see the logs in http://www.ibm.com/developerworks/forums/thread.jspa?messageID=14684289&tstart=0#14684289. In there you see that the gap is reduced just before the time limit kicks in, almost independent of the value of the time limit itself.

image

Above: run with 100 seconds time limit and below: 1000 seconds time limit.

 

image

You would almost think it would be beneficial for Cplex to have this end-of-time behavior every now and then.

Note: these runs are on one thread (thus hopefully deterministic – may be apart from the exact iteration number where the time limit kicks in). The statement “The answer to this is an implementational detail: when you use time limits, the solving process becomes non-deterministic close to the end of the time limit.” does not completely satisfy me. I would like to have a better understanding about what is happening here.

GPU computing on Amazon cloud

May be this can help bringing parallel computation on GPUs to business applications:

Dear Amazon Web Services Customer,

We are excited to announce that starting today you can run Microsoft Windows Server 2008 R2 and Microsoft Windows SQL Server Standard 2008 R2 on Cluster Compute and Cluster GPU instances for Amazon EC2. Cluster Compute Instances provide customers with high CPU capability within a high bandwidth, low latency network for IO intensive computing. Cluster GPU instances allow customers to additionally take advantage of NVidia Tesla GPUs for general purpose GPU (GPGPU) computing using the CUDA or OpenCL programming models. A number of customers with database workloads and applications in areas such as media processing, rendering, and computational finance, have expressed interest in running Microsoft Windows Server on the most powerful Amazon EC2 instances. Starting today, customers can run applications on Microsoft Windows Server across all Amazon EC2 instance types.
Cluster Compute and Cluster GPU instances are currently available in the US-East (N. Virginia) region. For more information, please visit http://aws.amazon.com/ec2 andhttp://aws.amazon.com/windows.

Sincerely,
The Amazon EC2 Team

Tuesday, September 13, 2011

Big-M and Scaling

I was working on a client MIP model that showed strange behavior: with Cplex and Mosek optimal values were found while Gurobi and Xpress reported the model to be infeasible. There were a few Big-M values in the model, in equations like:

Capture5

Some of the big M values were very large e.g. 99999999. The actual value of this M should be equal to the upper bound of x. Unfortunately x can assume very large values, something like $100,000,000. This meant we could only reduce the big M values by a small amount. With some trial and error we found some big M values that worked. Of course this was just a band-aid solution.

In the end we chose to scale the model by changing units for x. Instead of $ we now use millions of $. As a result the new big M values can just be M=100. As the model was rather complex we needed to spend half a day on this exercise. After this work, the model solved with all solvers without a problem.

Tuesday, September 6, 2011

Open source MIP solvers

Hi Erwin,
I have a 2 questions, could you please point me into a good direction?


1. Which open source optimization solver do you recommend? (One that can withstand a large and complex problem)
I've been researching online and I've come across with lpsolve, coin-or lp (CLP), and GLPK.


2. I've been having a really tough time to get GLPK to work. I'm new to this field of open source software but I've found out that I need an interface from where I should call the GLPK library. My question is, which application (or interface) should I use?

Thanks in advance!

CBC (https://projects.coin-or.org/Cbc) seems to be the fastest open source MIP solver (see http://plato.asu.edu/ftp/milpc.html). The academic code SCIP is also quite good but is not open source (it requires a license for any non-academic application). Of course the commercial codes are often (much) faster.

The GLPK API is simpler to use than CBC however.

In general I would say the low level solver API are often not a good idea to use for larger, more complex models. For those a modeling language is often more appropriate. 

You may want to consider making your application solver independent. Then you can pick the solver most suited for the occasion. Again this is most easily done using a modeling framework.

Implementing Parsers

During my transatlantic flight I was reading

Although it was a good read I expected a little bit more info about implementing funky languages and some advice about that. Actually this book is largely about parsing (parsing using the ANTRL parser generator to be more precise) and largely about traditional programming languages.

I usually write simple recursive-descent parsers directly (i.e. without the aid of a parser generator) as typically I only parse very simple things. in addition I feel a little more sure-footed this way as I have a little bit more control to handle an occasional dirty thing. So this is a little bit outside my direct interest. However, I learned a bit about memoizing parsers, a term I was not yet familiar with.