Lengning Liu's Blog

Using Solver Foundation and plug-in solvers in IronPython

Lengning

Sparse input data and data binding

Solver Foundation supports flexible data binding so that the algebraic model can be separated from the data source. In Solver Foundation, both parameters and decisions can be bound to data source.  It makes writing and maintaining models really easy.

 To bind a parameter to a data source, we usually need to specify the data source, the value field, and indexes. For example, the following parameter WarehouseCap is bound to the table that has two columns.

The table looks as follows.

Column warehouse is the index column/field, and column capacity is the value column/field.

In C#, the binding can be set via the following line.

  _model.WarehouseCap.SetBinding(warehouseCaps, "Capacity", "Warehouse");

assuming warehouseCaps is an IEnumerable that contains the data.

The sparse data case is where the table contains multiple index columns and not all the combinations of the index values exist in the table. For example, there could be a table that records the cost of shipping goods from warehouses to stores. However, it is usually not the case that every warehouse can ship goods and every store. For example,

Such table represents input data that are sparse. By default, the missing rows all have the value column being zero.

Currently in Solver Foundation v2.0, we cannot bind to such sparse data directly. However, we observe that the values appearing in an index column of the sparse table form a subset of the values allowed for that index column. Furthermore, Solver Foundation allows parameters to appear as the indexes to other parameters or decisions. We can use the following approach to bind to this sparse table.

Let us introduce a helper column called costid into the table.

Now we create two extra parameters called CostWarehouse and CostStore, which will be bound to the warehouse column and store column respectively. The needed parameter Cost will be bound to the cost column as we expected. All three parameters now use costid as the index.

Here are the actual definitions for the three parameters.

Assume we have a decision called Ship defined as follows.

Ship[w, s] being 1 if and only if we want to ship goods from warehouse w to store s.

Now suppose we want to construct as constraint that says “the total cost of shipping is between 100 and 400. The constraint can be written as follows.

Notice that we iterate through all rows in the cost table and use parameter CostWarehouse[id] and CostStore[id] as indexes on decision Ship.

To ensure that we do not ship any goods from incompatible warehouse and store pairs, we add the following constraint using the fact that default values are zero:

We leave it to the reader to figure out how this constraint works. Notice that, in the last constraint, the complicated right-hand side of the inequality actually is reduced to a constant value. So the model is still a MILP model.

Here is the complete model.

Here is a sample run.

The actual workbook is attached too.

Lengning

Deploy OML model from Excel to Visual Studio

Deploy-to-C# is a new feature we shipped in Solver Foundation v2.0 Excel Add-in. The idea is to simplify the process of deploying an OML model written in the Add-in into a Visual Studio project that builds the same model using Solver Foundation Services APIs. With this new feature, users who are comfortable in writing and debugging their models in Excel/OML environment now can produce an equivalent C# model by a click of a button. Once the C# model is generated, users can further embed the model code into their applications. It is also possible now to solve the model using multiple directives or use plug-in solvers.

In this post, we will show how to use the Deploy functionality to convert an OML model into a Visual Studio project. To repeat the following steps yourself, please make sure you have Microsoft Office 2007, Visual Studio 2008, and Solver Foundation v2.0 installed. Furthermore, to try out the plug-in solver you have, please update the solver registration section in the config file accordingly.

In Solver Foundation v2.0 release, we include a sample on the supply chain planning. It can be found under <your documents folder>\Microsoft Solver Foundation\Samples\Excel\LP. Let us start with this sample.

Once we load this Excel file, we can see the data are stored in the spreadsheet and the OML model is presented in our new modeling pane.

We can solve the model in Excel by clicking the Solve button. Here is the result.

As we can see from the log, Solver Foundation simplex solver is used with the default setting to solve this model.

Now let us start deploying the model into C#. We notice the new Deploy button in the Ribbon.

Let us click on it. The following window pops up, where we can specify the C# file name for the model to be deployed. Let's call it SupplyChainPlanning.cs.

Now we have two files created under the target folder: SupplyChainPlanning.cs and SupplyChainPlanning.xml. The first file contains the equivalent model written in C# and the second xml file contains the data from the spreadsheet. The model now can be embedded into any Visual Studio C# project.

Let us now open Visual Studio 2008 and create a new C# console project. Notice that Solver Foundation v2.0 installation creates two project templates in Visual Studio 2008. Let us pick the Solver Foundation Console Application template.

After the project is created, let us add the SupplyChainPlanning.cs and SupplyChainPlanning.xml into the project. We can delete the sample model file created automatically by the template because we are not going to use it. We make sure that the xml file will be always copied to the output directory during compilation since it contains the data we need.

Next, we need to write some glue code to bind the data from XML file to the model. This part is not automatically done at this moment. However, the data binding code is pretty straightforward. We use LINQ to XML in this case.

Note that we have a where clause in building demandForecastPrices and demandForecastUnits. We leave to the readers to experiment why the where clause is needed.

Now let's run the console app. Here is the output. For simplicity, we skip the decision values. We can verify that the objective function value is the same as we have seen in Excel.

Now to illustrate a more advance usage of Solver Foundation in this C# project, let's include a solver registration and use a plug-in solver to solve it.

To use a plug-in solver with Solver Foundation, please make sure you have all the needed DLLs from the plug-in solver vendor. In this example, we will use Gurobi solver to solve this LP model.

First we need to add a config file to the project so that we can register the plug-in solvers. Here is what the app.config file looks like

Notice that we register Gurobi solver as an LP solver here, with Gurobi solver's class, directive class, and parameter class names.

Next, we need to include necessary DLLs into the project so that Solver Foundation can find them. Here is what the project looks like now.

Here we reference GurobiPlugin.dll (plug-in solver wrapper) and add the gurobi20.dll (unmanaged code DLL for the actual solver) to the project. Notice that we set the "Copy to Output Directory" property of gurobi20.dll to "Copy Always" too. These two DLLs are shipped with Solver Foundation v2.0 and can be found under <your program files folder>\ Microsoft Solver Foundation\2.0.2.8632\Plugins.

Now let's run the application again. This time, we will see from the report that Gurobi solver is used and the same objective function value is returned.

To tweak the settings of Gurobi solver, we can further create a Gurobi solver directive and change the settings there. Then we pass the directive instance into Solve call. I will leave this to the readers to experiment.

This sample goes through all steps in deploying an OML model from Excel to Visual Studio. I hope it helps in your application development. Thank you for your time.

Lengning

Try out our F# ODSL and SFS wrapper sample with the newly released F# October CTP (1.9.7.8)

http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/default.aspx

The F# ODSL and SFS wrapper included in Solver Foundation v2.0 utilize the new feature, unit of measure, in F# to facilitate more robust modeling experience. In order to try out the sample, you will need to download the most recent update of F#, v1.9.7.8, from the link above.

Have fun!

Solver Foundation V2.0 is shipped today!

We are pleased to announce the release of Solver Foundation v2.0. This is the fourth on-time commercial release for the product. The Express edition is available now at http://code.msdn.microsoft.com/solverfoundation. The Standard Edition of Solver Foundation v2.0 has released-to-manufacturing, and will be available online via MSDN subscriber downloads the week of 11oct09, and offline world-wide via MSDN in approximately two months later. Our Enterprise edition is also available.

In version 2, we focused on growing our collection of solvers, vastly improving our tooling experience, and introduced the beginnings of what will be our simulation framework. At a high level, Solver Foundation v2.0 has the following new features:

Top level features we are introducing in Version 2.0:

-          Design Tools. We have improved the integration, interchange, and workflow of our design surfaces for Excel, SharePoint, and Visual Studio – modelers will now be able to take models algorithmically designed in Excel and inject this directly into a full-fledged Visual Studio/C# solutions with the press of a “deploy” button. Additionally, a model can be sent directly to SharePoint using our script-safe OMLX format. This is a long-term focus area to make modeling as easy as possible without losing any capabilities for the advanced user.

-          Solver Foundation Services

·         Stochastic Programming and Optimization with Monte Carlo simulation capabilities. The SFS supports random parameters and recourse decisions, allowing for the definition and solution of two-stage stochastic models

·         Submodels.  Our master model can now define and reference submodels, allowing for better encapsulation and reuse

·         Special Ordered Sets.  Introduced SOS1 and increased flexibility in the definition of SOS2 constraints

·         Solver Plug-in SDK improvements to include Special Ordered Sets, more detailed reporting (e.g., IIS), and expanded our solver partner ecosystem to include LINDO Systems

-          Solvers

·         Gurobi version 2.0 Solver is included in our release, and is the default Solver Foundation MIP solver

·         Second Order Conic Programming (SOCP) Solver Extensions to our IPM Solver to support rich constraint modeling (we can now have nonlinear goals and constraints)

·         Extensions to the Simplex Solver to support SOS1 and SOS2 modeling and solving

·         Improved our in-house Mixed Integer Programming Solver

·         Metaheuristics and Global Constraints for our Constraint Solver (developed in conjunction with our friends at MSR Cambridge) to ease and simplify declarative modeling with more powerful constructs

-          Created a new F# Optimization DSL (ODSL) that incorporates units-of-measure work from MSR Cambridge

-          Increased our solver vendor and modeling partner ecosystem to include LKINDO Systems and Princeton Consultants – more information can be found at www.solverfoundation.com

-          Our core DLL is now localized in German. This is the start of our longer term focus to localize all of Solver Foundation in the top languages world-wide

-          A host of other improvements

Optimization domain specific language in F# with units of measure

In Solver Foundation CTP release, we shipped an optimization domain specific language (ODSL) in F#, which embedded Solver Foundation simplex solver for solving linear programming models. In the upcoming version 2 release, we will ship an enhanced version of this ODSL. Here are some of the highlights:

·         Units of measure: in F# numerical quantities can be annotated by a unit such as kilogram, dollar per day. These annotations not only provide additional and explicit documentation on the nature of the quantities involved, but also allow F# to statically check that no mistake is made in the use of these quantities: adding Watt and Newton is incorrect for example.

Units of measures in F# are declared as follows:

The syntax for annotating a numerical value with its measure is shown below:

In our new ODSL, units of measures can be used in modeling a problem, which help modelers to catch errors in the model where incompatible quantities are used in the constraints or goal functions. Here is a simple example of the Petrochem problem.

Note that if quantities such as a were defined to have a measure other than Dollar/Barrel, F# would have caught the error in the goal function where b*vz had the measure Dollar/Day while a*sa did not.

·         Solver Foundation wrapper in F#: this wrapper directly wraps Solver Foundation APIs and does not use F# quotations. With this wrapper, we also enabled units of measure in models that are written against Solver Foundation APIs. Here is the model of the same Petrochem problem written in this wrapper:

The ODSL and the wrapper source code will be shipped in Solver Foundation version 2 as a sample on how to enable F# to solve optimization problems. More details will be available in the release doc. The essence here is that, being a complete .NET solution and CLS compliant, Solver Foundation can be easily embedded in other .NET environments to help our customers to solve their problems in the environment that they are most familiar with.

Version 2 of Solver Foundation contains a number of new features and enhancements. Please also check out Nathan’s blog on simulation and stochastic programming. For more information, please stay tuned for the actual release.

Lengning

Solver Foundation v1.2 is released!

Please check out www.solverfoundation.com for an immediate access to our Express edition. Standard edition will be ready through MSDN subscription in the following days.

It's really exciting to see three releases in five months.

- Lengning

Very good Excel/OML tutorial from Amsterdam Optimization Modeling Group

http://www.amsterdamoptimization.com/msf.html

Solver Foundation website is online

http://www.solverfoundation.com

Official website of Solver Foundation.

Solver Foundation in Action!

Here is a post that describes a recent use case of Microsoft Solver Foundation in real world applications.

http://blogs.msdn.com/pascal/archive/2009/01/13/l-agenda-des-techdays-2009-a-t-enti-rement-construit-avec-microsoft-solver-foundation.aspx

Thank you Pascal for contacting us with the problem and collaborating with us to get the work done in time. It was great fun for us working with you.

Links to other blogs that talk about Microsoft Solver Foundation

1. Alexander Stojanovic is the founder of Microsoft Solver Foundation. Please check out his blog at http://conceptualorigami.blogspot.com/ 
2. Min Wei is the principle engineer of Microsoft Solver Foundation. His blog is available at http://blogs.msdn.com/minwei/
3. Nathan Brixius has put up a nice blog post that aggregates links to other blogs and resources about Microsoft Solver Foundation: http://blogs.msdn.com/natbr/archive/2008/11/15/microsoft-solver-foundation-blogs-and-resources.aspx

- Lengning Liu

Using Solver Foundation to generate Sudoku puzzles, Part III (final)

This is the final post on the Sudoku puzzle generator. We have seen how to generate a Sudoku puzzle by using Microsoft Solver Foundation to repeatedly solve the Sudoku model with different board configurations. The data binding feature in Solver Foundation Services makes the process elegant in the sense that only the data source needs to be updated each time and model does not need to be changed.

In this post, we will integrate the puzzle generation into Excel (we assume Excel 2007 and Visual Studio 2008 are installed) via a new add-in. This new add-in creates a new Ribbon tab in Excel. We will not going into the details of the code this time as it is purely mechanical work of building an Excel add-in.

The main procedure is the event handler that handles the button click event on Generate button.

The highlighted places call the puzzle generator we have created to get a new puzzle and fill in the cells in a specific sheet called “Sudoku” with preset values in the puzzle.

This is the end of this sample. I hope you had fun reading through the posts. The complete sample solution can be downloaded from the download page of Microsoft Solver Foundation website. Please feel free to contact me regarding any questions or feedback on this sample. Thank you in advance.

In the next series of posts, we will take a look at the camera depot sample shipped in Microsoft Solver Foundation V1. That sample embeds Solver Foundation in an ASP.NET web service to recommend an optimal camera configuration based on user’s choices and preferences. On the client side, user can specify his/her choices and preferences using a Silverlight UI. This next sample is written in C#.

- Lengning Liu

Using Solver Foundation to generate Sudoku puzzles, Part II

In our last post, we saw the model for completing a Sudoku board given a particular board configuration. In this post, we will show how to repeatedly use this model to generate a Sudoku puzzle.

Let us first take a look at the main procedure of the puzzle generation.

We start by randomly generating a board configuration that contains only four preset values and computing a solution from that initial board configuration.

Note that in CreateModel, we will use the preset numbers stored in _board via data binding. We skip the error handling case. In reality, given that we only preset three numbers, it is highly unlikely that we get an infeasible initial configuration (meaning that the initial configuration cannot be extended to a complete configuration while satisfying all Sudoku constraints).

Once the model is solved and we get a feasible solution, we can populate the values of aggregated decision variables back to _board (using Property SolutionValueDouble defined in SudokuBoardCell). This is done via the output data binding we specified in the model when we created decision _boardDec. We then use the computed solution as the starting point to generate the actual puzzle. To this end, we create a candidate list of integers that initially contains all the board cells.

Next, we will start removing numbers from the complete board configuration one by one. Remember that we will actually remove a number if and only if, after it is removed, the board configuration has exactly one way to be completed (a.k.a. exactly one feasible solution can be found after the number is removed).

In the while loop, we randomly pick a cell position from the candidate list. Then we use method IsRemovable to test if the number in that position can be removed according to the condition we just mentioned above. If so, we will put 0 in that cell as the PresetValue. Note that we still keep its original value from the solution for the checking purpose later (verifying if user fills in a correct number in this position).

The three major sub-routines involved are GenerateRandomStartingPoint, PopulateSolution, and IsRemovable. We will now show them one by one.

This procedure is straight-forward. We note that we do not use repeated values to avoid obvious conflict in generating the initial board configuration. This means the largest possible value of the input parameter is 8. Another place to note is that, even if the initial starting points are different, we may still end up with the same complete board configuration after the model is solved. We will not worry about this case in this sample though.

PopulateSolution procedure is defined as follows.

We only perform this operation if the solution found is feasible. As we mentioned earlier, we set all cells’ PresetValue to their SolutionValue (rounded version of SolutionValueDouble).

Finally, IsRemovable method is defined as follows.

We first record the original PresetValue in the cell (coordX, coordY). Then we change its PresetValue to 0. Next we call context.Solve() and solution.GetNext() . The call to context.Solve() should always return a feasible solution as we started from a valid complete board configuration. The call to solution.GetNext() tries to compute a second feasible solution. If there is no other feasible solution, SFS will set the Quality of the Solution instance to Infeasible. So we will decide if the PresetValue of the cell should be set to 0 based on solution.Quality.

That’s all we need to generate a random Sudoku puzzle. Pretty easy, isn’t it? It’s worth pointing out that, IsRemovable method is called repeatedly in the main loop. Each time it is called, we need to solve the Sudoku model with a different preset board configuration. By using Solver Foundation Services and its data binding feature, we actually have separated the model from its input data, in this case the preset board configuration. So every time we want to solve the Sudoku model with a different preset board configuration, we do not need to reconstruct the model. The only thing we need to do is to change the data source to which the Parameter instances are bound to in the model. In this example, we only need to change PresetValue (the property to which the Parameter instance is bound to) of the given cell. In other words, the model is generic to all preset board configurations. The separation of model from data is really convenient in such scenarios where the model remains the same while the input data change from time to time.

In the next and the final post, we will briefly show how to build a new Ribbon tab in Excel for this add-in and how to trigger the Sudoku puzzle generation.

- Lengning Liu

Arithmetics on indexes in OML

Here is the link to the original post (thank Shahar for posting the trick). The trick to make arithmetics valid on Decision/Parameter indexes in OML is to declare the Sets on which the indexes are defined as Integers. Here is the OML model that illustrates how arithmetics is done.

Parameter "param" is bound to the spreadsheet that has the following table.

The Excel workbook of this sample is available as the attachment of this post.

- Lengning Liu

Use Scalar Parameters for SFS Data Binding in F#

Parameters in Solver Foundation Services (SFS) provide a convenient way of separating models from their input data. In the MSF-SFSProgrammingPrimer doc included in the release, we have the following example:

Sample 4: Using Parameters for LINQ Data Binding

Often we will want to iteratively run the same model with different data parameters.  Instead of recreating the same model again using different data, you can use a Parameter object.  The Parameter is bound to a database by LINQ, or to any other object which implements IEnumerable<T>.  The current values are pulled from the data source each time the model is run.

Here maxvz and maxsa are two parameters whose values come externally. The model does not need to change when it accepts different values for the two parameters.

In this example, the two parameters are scalar parameters as they do not involve any index sets. Note that the signature of Parameters.SetBinding is as follows:

When there is no indexFields specified, the parameter instance is scalar.

Now the problem in F# is that, F# does not recognize the params attribute in this method and requires any call to Parameter.SetBinding to have three parameters being passed in. Here is a trick to define scalar parameters in F#. The sample code is shown below.

Note that the use of Parameter instances in this example is especially useful because, without the use of Parameters, we will not get shadow pricing in the sensitivity analysis from SFS because in general there is no one-to-one correspondence between a row in the linear model and a constraint in SFS (a constraint in SFS could be aggregated).

 - Lengning Liu