Wednesday, May 23, 2012

Solver Foundation Enterprise

I would have expected a more formal announcement than just this:

http://social.msdn.microsoft.com/Forums/en-US/solverfoundation/thread/aedcbb42-d3df-4180-bbaf-4db2e66acd9d

Looks to me that the best way forward is to open source the Solver Foundation code. Of course assuming there are no third-party components used directly in the Solver Foundation code base (third party solvers can be easily excluded).

Update: Gurobi has retracted the original statement. It still would be good to have some more visibility on the status of MSF.

Update 2: from http://social.msdn.microsoft.com/Forums/en-US/solverfoundation:

As users have pointed out, Microsoft has not been active on the Solver Foundation forums since Nate left.   We have been quiet while we have gone through restructuring and planning.  Some would say we have been too quiet.  We know we have very loyal and enthusiastic users who want to know the future of Solver Foundation.  So, here is a long overdue statement about our plans for Solver Foundation.

The current 3.1 release of MSF will be the last release as a standalone install.  We are working hard on integrating Microsoft Solver Foundation into a larger analytics framework that will help users build both prescriptive and predictive analytics.  We look forward to releasing this new product for your use as soon as we are able to do so.  This new product will provide a migration path for current Solver Foundation users and partners.  

We would like to continue to keep the current forum open to the community to discuss MSF until the release of the new product. However, Microsoft will be providing limited support of MSF in terms of monitoring the forums and providing bug fixes during this transition time.                                                                                                                               

We have been responding to email and will continue to do so.  If you have feedback on issues/bugs/improvements, we welcome your feedback via msfsupport@microsoft.com.  Please check back on the forum for future announcements with regards to the new analytics product.

Thanks for your support.

The Solver Foundation Team

I am not 100% what this means. Looks like it is going away from a somewhat API centered product largely aimed to programmers who also do want to do some optimization, towards something that has more enterprise umpf (“analytics framework”). I assume this means moving more in the direction of SAS and Fico, i.e. more emphasis on other things such as data base, statistics, data mining than on pure optimization.

Friday, May 18, 2012

Model improvements

Looking at the models used in the paper http://www.ime.usp.br/~egbirgin/publications/rob.pdf I noticed that a few standard “improvements” could be introduced. Here is an example:

image

First equations (13) and (14) have the same RHS. Hence it makes sense to introduce a new variable for this.

Secondly, when we look at the AMPL models provided by the authors, we see:

R1 {j in 1..n}:
    T[j] >=   ( S[j,m] + sum{i in 1..n} ( x[i,j] * p[i,m] ) )
            - sum {i in 1..n} ( x[i,j] * d[i] );

R2 {j in 1..n}:
    E[j] >= - ( S[j,m] + sum{i in 1..n} ( x[i,j] * p[i,m] ) )
            + sum {i in 1..n} ( x[i,j] * d[i] );

I.e. they substituted out C[j,m]. I would probably leave that as it was formulated in the paper.

Now, do these improvements really work? As is sometimes the case: the results on a single instance can be misleading. So here were my experiments:

    old version new version
size rows 335 500
  cols 405 570
  nz 5635 3865
gurobi iterations 1060935 453173
  nodes 31220 5971
  time 60 38
cbc iterations 4589173 4790425
  nodes 36154 49851
  time 395 478

We see that my version has fewer nonzero elements at the expense of more variables and equations. But not with every solver (or with every instance) this pays off. CBC actually becomes slower. Most likely this can be explained with the simple argument that the solver follows a different path. To really assert that a formulation is better one really needs to run a large number of models and see how they behave on average.

Note: the reformulated model (and the computational results) already included the suggestion in the comment from Paul. 

Friday, May 4, 2012

Gurobi version 5.0 is out

New Features and Enhancements

Some of the new additions and enhancements include:

  • New QCP and MIQCP solvers - Allow you to solve quadratically constrained models at more than twice the speed of the leading competitor
  • New MATLAB and R interfaces - Concise and tightly integrated for ease of use
  • Support for Lazy Constraints - Uses a superior implementation that doesn't require you to turn off other key features
  • Enhancements for handling infeasible and unbounded problems - Includes a barrier homogenous algorithm designed to solve infeasible and unbounded problems and a new FeasRelax procedure for finding solutions that minimize constraint violations
  • Enhancements to overall performance - Includes faster presolve times, the ability to warm start the simplex algorithms from solution vectors, enhanced crossover numerical stability, and many more enhancements for speed and robustness

For more info see gurobi.com.

Thursday, May 3, 2012

Binary OR

Is it possible to implement a kind of a boolean addition to binary variables.

For example:

Let X, Y and Z be binary variables.

X and Y ara inputs, Z is a result.

X + Y = Z

Such that

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1

So this would be sometning like a logical .OR. addition?

This can be formulated as a set of inequalities:
image

The variable Z can be relaxed to a continuous variable between 0 and 1 (it will be integer automatically).