Monday, September 28, 2009

VSTO+Solver Foundation

Microsoft Solver Foundations provides a simple plug-in too to develop optimization applications with Excel as front-end. For more complex models it may be needed to use the API’s. Basically there are two alternatives: develop a .NET DLL and call this from VBA (an example is demonstrated here) or create a VSTO application. VSTO is a framework to develop .NET based tools for use in an Office environment. Actually the Excel plug-in is an example of an application level VSTO tool. Here I describe a document level VSTO application.

A delayed column generation algorithm for the cutting stock problem is a good example of a modeling tool that can not be coded in OML. Here is a simple example in GAMS. It is not very difficult to code this in the solver API of MSF.

The Excel demo application has two sheets. One with the input and the progress log and one with the results.




The algorithm is using the duals of the master problem to form the sub-problems. Access to duals is only available in the solver level API (for the current version of MSF). This means a very low-level way to describe the model. In this case the models are simple and well-structured so the pain is limited. For more complex models this approach may become burdensome.

In order to get duals we needed to create the following options:

colgen3

The reason for setting the presolve level to zero is a bug in the solver. This is fixed in the next version of MSF.

Note that the algorithm used is different from the example My Documents\Microsoft Solver Foundation\Samples\Solvers\MixedIntegerProgramming\CuttingStock from the Solver Foundation distribution. That algorithm will generate all patterns in advance. In our algorithm we generate new patterns as we go.

VSTO applications are quite fun to develop. Excel integrates nicely in Visual Studio and debugging is easy.



A few issues I encountered:

  • Sometimes there is still an Excel.exe process after terminating Visual Studio. Kill it using the process manager.
  • C# does not really do COM very nicely. That means lots of type casts and no proper handling of optional parameters (need to use a lot of “missing” for them in calls). I believe this is much better in the next version of C#/Visual Studio.
  • Reading the documentation on deployment and security gave me a headache. This is not for the faint-hearted.

7 comments:

  1. Nice post! Yeah, the Office interop stuff is way better in C# 4.0. More info here: http://msdn.microsoft.com/en-us/library/dd264733(VS.100).aspx

    ReplyDelete
  2. Well done got some nice information, keep going...

    ReplyDelete
  3. Excellent!

    Could you please email a copy of the project'source code to smartinzhang@gmail.com?


    Thanks in advance.

    Martin

    ReplyDelete
  4. Nice work... Could you please send to source code to ersen.sen@gmail.com? Thanks.

    ReplyDelete
  5. I read your article VSTO+Solver Foundation and read about Delayed Cutting Stock Problem from a pdf like: amsterdamoptimization.com/models/msf/oml.pdf

    Although I copied the code line by line it does not work. I used VS 2010, Excel 2010 and Microsoft Solver Foundation 3.

    ReplyDelete
  6. Not worth to spend hours. It does not work.
    SolveSubProblem() method generates negative values. So that sub problem is not able to find a new pattern.

    ReplyDelete
  7. The sub problems are small knapsack problems, Should be easy to debug. Make sure your duals have the correct sign.

    Negative values indicate you did not form the sub problem correctly.

    ReplyDelete