Saturday, December 24, 2011

INFORMS 2011 presentation on correlated random variables

In the INFORMS Fall Annual Conference 2011 at Charlotte, NC, which concluded in November, I did a small presentation on correlated random variables. One of the very important aspect of creating a Monte Carlo simulation model is to consider correlations between the random variables. In this presentation, I talk about why considering correlations is important, how to consider correlations between random variables, and how to generate random numbers from correlated random variables (mostly, using the Crystal Ball implementation as a standard). 

Here is a link to the presentation. As always, please comment if you have additional questions.

Thursday, December 8, 2011

New blog on developing Operations Research and mathematical software

A quick note: I have started writing another blog on developing Operations Research and mathematical software. Our development platform is .NET, but the posts in this blog are not necessarily .NET related. They are just notes focused on developing OR software or math software. 

Some of the recent posts:
... and a few more. Some of the posts also contain entrepreneurial thoughts related to developing these type of software. If you enjoy developing math software, I think you will enjoy the posts. Please join me at http://orsoftware.blogspot.com/

Comparing doubles - an old old problem

The problem of comparing two doubles occurs in so many situation, I am sure that in some dev circles, it probably has got the name “the double trouble”. I am referring to the problem where you have to compare two doubles for equality, and based on the result (i.e., based on if they are equal or not), the code either kills a demon or self-destroys itself (put your own example here). In iterative algorithms, these situations are quite common. Searching through my code-base, I seem to have used these checks in the following situations:
  • Matrix and Vector operations
    • In a routine for reducing a symmetric matrix to tridiagonal matrix (believe me, there is a reason why I couldn’t use one of the numerous BLAS packages)
    • Comparing real matrices for equality overload operator
  • Comparing coefficients of two polynomials for solving ARIMA equations in time-series forecasting
  • Calculating approximate correlation coefficients for groups of variables
  • Coding Quasi-Newton methods (specially for solving box-constrained problems)
So, I was quite pleased to see this topic covered in a recent post by Peter Vogel in the Visual Studio magazine. Comparing my code with Peter’s code got me thinking a bit, and hence this post.

Absolute and Relative Comparison
For starters, I have been using absolute comparison with constant epsilon value (1E-15), and it has been working pretty well. The code is simple, and looks like below:

public static bool AreEqual(double a, double b, double EPS)
{
     if ((a < 0 && b > 0) || (a > 0 && b < 0))
         return false;
     else
         return (Math.Abs(a - b) < EPS);
}

Peter, however, mentions: “Any fixed epsilon would likely be too small when comparing large numbers, or too large when comparing small numbers.” That is indeed true, and I generally get by with passing separate epsilon value for other situations. The relative version of the method, from Peter’s post, looks like this:

public static bool AlmostEqual(double a, double b)
{
     if (a == b)
         return true;
     else
         return Math.Abs(a - b) < Math.Abs(a) / 281474976710656.0;
}

For an explanation about the constant, see the original post. As is obvious, this won’t work well with numbers close to zero. There are other schemes, where one calculates (a-b)/a, or (a-b)/b, or (a-b)/max(a,b) and compares with an epsilon.

Using Double.Epsilon
Note, however, that using Double.Epsilon available in .NET as the epsilon value is not a good idea in these comparisons. Double.Epsilon is only useful if one is subtracting values between 0 and 1 as it's the "smallest positive Double value greater than zero". Since double values aren't evenly spaced and their distance increases with their magnitude, one won't ever get something around Double.Epsilon if one is subtracting two arbitrary values.

Other Methods
Recently, I came across another interesting post which shows how to compare two floats (and by extension, doubles) using integers. If you are interested, definitely check this out. Another suggestion that has been floated in these discussions, is to use arbitrary precision arithmetic (APA), but in most applications, doing everything in APA would be really slow. An example of the use of APA is Microsoft Windows Calculator (the calc.exe program).

End Word
One sentiment that repeatedly seems to appear in posts related to this topic is that “the chosen method would really depend on what one would consider equal”. It is definitely application specific, and with enough spread in test cases, a wrong choice of method would show up in wrong result (or, so we hope !!).

References
Following are two really good references I have found on this topic:
[1] Jon Skeet’s coverage for floats and doubles and decimals
[2] Bruce Dawson’s coverage

Update (March 5th, 2017): Updated dead link.

Thursday, December 1, 2011

Recent developments in OR solutions

Recently the following two new OR solutions have come to my attention. Good to see enrichments in the OR solution space.
  • OpenSolver: This is an add-in to Microsoft Excel for solving LP and MIP. It is not a new solver per se, rather it provides an interface similar to the familiar Microsoft Excel Solver (provided by Frontline Systems, the limited version is included with Microsoft Excel for free) for solving LPs and MIPs, using the COIN-OR's CLP (COIN LP) solver through CBC (COIN Branch and Cut). I came to know about this project from a presentation at INFORMS Annual Meeting 2010. At this year's INFORMS Annual Meeting (2011), they were judged winner of the COIN-OR Cup award. Here is the blurb:
Pietro Belotti, the Chair of the Award Committee, delivered the announcement, and this year's award went to Andrew Mason from the University of Auckland and Iain Dunning, currently at MIT Center for Operations Research, for OpenSolver, a linear and integer optimization solver for Microsoft Excel. OpenSolver harnesses the power of the COIN-OR CBC optimization engine and is compatible with Excel 2003, 2007, and 2010. Neither Andrew nor Iain could attend this year's meeting, so the award---a cup full of coins---was accepted by Ted Ralphs on their behalf. In his speech delivered on Andrew's behalf, Ted highlighted the rapid traction OpenSolver gained in the O.R. community, going from 0 downloads 18 months ago to roughly 30 downloads per day currently. He also mentioned the release of the beta version of OpenSolver Studio, which allows users to use Excel maneuver models built using the Python-based PuLP modeling language, which provides a more elegant solution for modeling complex optimization problems.
         I hope to check out the interface sometime.