Microsoft Solver Foundation

Using Plug-in Solvers in Solver Foundation 3.1 for Excel

Nate Brixius — Thu, 15 Sep 2011 22:08:20 GMT

In this post we will show you how to use third-party solvers with the Microsoft Solver Foundation Add In for Excel. We assume that you have installed the Express version of Solver Foundation 3.1 from solverfoundation.com.

There are two steps in the process:

Registering the solvers you want to be able to use in Excel,
Optionally directing that a particular solver should be used to solve a model.

In this post we will show you how to register and provide directives for the Gurobi solver, since it is included in the Solver Foundation installation process. The steps are similar for other solvers.

Registration is done by providing a configuration file. This process is painful (and we hope to make it easier in the future), but you only need to do it once.

Configuration files are a standard mechanism for specifying information about how a .Net application should run. This configuration file has a section that describes the version of Solver Foundation that is installed (the version number for MSF 3.1 is 3.0.2.10889), and a section where plug-in solvers are listed. Here’s what you need to do:

Close Excel.
Open a command shell with administrator privileges: click the Windows start button, type “cmd” in the search box, right click on the “cmd” icon and select “Run as administrator”.
Go to the Solver Foundation installation directory. On many machines, this means typing “cd C:\Program Files\Microsoft Solver Foundation\3.0.2.10889\MsfForExcel”
Create a new text file called MicrosoftSolverFoundationForExcel.dll.config, for example by typing “notepad MicrosoftSolverFoundationForExcel.dll.config”

Paste in the following:

<?xml version="1.0" encoding="utf-8" ?> 
<configuration> 
  <configSections>
    <section name="MsfConfig" 
             type="Microsoft.SolverFoundation.Services.MsfConfigSection, Microsoft.Solver.Foundation, Version=3.0.2.10889, Culture=neutral, PublicKeyToken=31bf3856ad364e35" 
             allowLocation="true" allowDefinition="Everywhere" allowExeDefinition="MachineToApplication" 
             restartOnExternalChanges="true" requirePermission="true" /> 
  </configSections> 
  <MsfConfig>
    <MsfPluginSolvers> 
      <MsfPluginSolver name="gurobi" capability="LP" assembly="GurobiPlugIn.dll" 
                       solverclass="SolverFoundation.Plugin.Gurobi.GurobiSolver" 
                       directiveclass="SolverFoundation.Plugin.Gurobi.GurobiDirective" 
                       parameterclass="SolverFoundation.Plugin.Gurobi.GurobiParams" /> 
    </MsfPluginSolvers> 
  </MsfConfig> 
</configuration>

Save the file and quit.

We have now registered the Gurobi solver to handle linear (LP) models. Once a solver has been registered, it is available for use in the Excel add-in for any spreadsheet. This is because the add-in reads the configuration file every time Excel boots. If you have an error in the configuration file, the add-in will report an error message. (If this doesn’t work, see the note at the end.)

Registered solvers are applied by default when you try to solve a model of the type specified in the config file. So, if you open up the “Supply Chain Planning” sample and click Solve, you can confirm that Gurobi was used by looking at the log:

Sometimes it is useful to change solver-specific settings for better accuracy or performance. This is accomplished by adding a directive to the model, found in the Directives tab. In Solver Foundation 3.1, registered solvers show up in the directives list alongside Solver Foundation’s built-in solvers:

Selecting the GurobiDirective item adds a directive to the model. In the lower portion of the modeling pane you can change any of the solver-specific settings you like. Each solver offers its own settings. For example, GurobiDirective has a Presolve property that controls which types of preprocessing rules are applied to a model before it is solved. Here we are changing the default setting to “None”:

(In Solver Foundation 3.1 when you save a model, third party directive options are not retained. This limitation exists because not all third party directives support saving their information to files. In future releases we hope to include this capability.)

It is possible to add more than one directive to a model. In this case, Solver Foundation will launch both solvers, effectively “racing” them against each other!

Important note for Visual Studio 2010 SP1 Users:

If you tried the preceding steps and no plug-in solvers appear to have been registered, and you did not encounter any error messages, you may have encountered an unfortunate breaking change due to Visual Studio Tools for Office (VSTO) 4.0 SP1. Here are the steps you need to take to get back on the right track:

Run Registry Editor (Start, type in “regedit”, hit Enter)
Navigate to HKEY_CURRENT_USER\Software\Microsoft\Office\
Excel\Addins\MicrosoftSolverFoundationForExcel\Manifest.

You should see something like the following in the right pane:
Double-click on Manifest and add “file:///” to the start of the text.
Click OK, and quit Registry Editor.
Restart Excel.

How to register a third-party solver in Iron Python

Nate Brixius — Wed, 14 Sep 2011 21:31:31 GMT

For years, Solver Foundation has provided the ability to plug-in third party solvers so that they can be used using the same programming model as Solver Foundation’s built-in solvers. In the past, solvers were registered using configuration files, as we have described in previous blog posts.

Solver Foundation 3.1 provides new programming interfaces so that solvers can be registered in code at runtime. This is useful in a number of different scenarios, including in cases where configuration files are hard to specify, as in Iron Python.

The following Iron Python sample code registers the Gurobi solver to handle linear (LP) models. Other solvers are registered in a similar fashion. You should be able to adapt this code to other .Net languages even if you are not familiar with Iron Python: the RegisteredSolvers.Add line is key. (The MSDN documentation for this new method will go live soon.)

import clr
## Bring in Solver Foundation
clr.AddReference("Microsoft.Solver.Foundation")
from Microsoft.SolverFoundation.Services import *

## Some helper functions for Solver Foundation.
def const(i):
    return Term.op_Implicit(i)
def lessequal(term, i):
    return Model.LessEqual(term, const(i))

c = SolverContext()

## Let's add a plug-in solver.
c.RegisteredSolvers.Add(SolverRegistration("gurobi", ## name of the entry (your choice)
  SolverCapability.LP, ## type of model
  "Microsoft.SolverFoundation.Services.ILinearSolver", ## the interface
  "GurobiPlugIn.dll", ## plugin dll 
  "SolverFoundation.Plugin.Gurobi.GurobiSolver", ## the solver class
  "SolverFoundation.Plugin.Gurobi.GurobiDirective", ## the directive class
  "SolverFoundation.Plugin.Gurobi.GurobiParams")) ## solver parameters class

m = c.CreateModel()
x = Decision(Domain.RealNonnegative, "x")
y = Decision(Domain.RealNonnegative, "y")
m.AddDecisions(x, y)
m.AddConstraint("c1", lessequal(x + y, const(5)))
m.AddConstraint("c2", lessequal(const(2) * x + y, const(7)))
m.AddGoal("g", GoalKind.Maximize, x + y)
s = c.Solve()
print s.GetReport()

Microsoft Solver Foundation v3.1 Released

Nate Brixius — Mon, 12 Sep 2011 20:08:58 GMT

Microsoft Solver Foundation 3.1 is now ready for download. Solver Foundation provides a complete system for optimization model specification, connection to data sources, and access to best-of-breed solvers for Excel users and .Net programmers. The Express version is available on the Solver Foundation site [click here], the MSDN and MSDNAA versions will be available soon, and the Enterprise version is available for purchase through Gurobi Optimization.

Here is a partial list of new features:

New Solver Foundation Services APIs enable specification of large models with easier to use, faster data binding using LINQ.
Improved SFS performance. Big models are processed in less time using less memory.
A new nonlinear solver based on the Nelder-Mead method, comparable to methods provided in other environments.
Improvements to the hybrid local search solver to support arbitrary goals and constraints.
Numerous improvements to the Solver Foundation add-in for Excel:
- Full support for commercial and open source solvers.
- Sparse parameter support.
- Warm start capabilities for performance and accuracy.
- Better support for named ranges.
- Complete control over all solver options – including third-party solvers.
- Better control over logging and output.
- Faster data binding.
Solver Foundation Services improvements:
- Inline Set definition.
- New SetBinding overloads.
- Support for multiple SolverContexts.
- Better WCF and Windows service support.
Logistic regression sample using the L-BFGS solver.

Solver Foundation also includes the Gurobi 4.5 solver, providing better MIP and MIQP performance. The Standard and Enterprise versions of this release are now permitted to be used in virtualized environments including Windows Azure.

Many of these improvements are based on feedback from the Solver Foundation community. Download the Express version and let us know what you think on the Solver Foundation forum.

- The Solver Foundation Team

Microsoft Solver Foundation 3.1: preview

Nate Brixius — Sun, 28 Aug 2011 21:54:09 GMT

The next release of Solver Foundation, Microsoft Solver Foundation 3.1, will be released next month. The feature set for 3.1 is the result of feedback from numerous partners and customers. This post summarizes some of the improvements.

Improved Nonlinear Programming

Microsoft Solver Foundation 3.1 provides a new NelderMeadSolver class to support nonlinear programming. NelderMeadSolver is suitable for unconstrained or variable-constrained models, and is capable of handling nonconvex or nondifferentiable goals. NelderMeadSolver is the new default nonlinear programming solver for Microsoft Solver Foundation. Microsoft Solver Foundation 3.1 also provides improvements to the hybrid local search solver. Using the HybridLocalSearchModel.CreateNaryFunction you can build models using user-defined functions that contain arbitrary calculations.

SFS and OML Modeling Improvements

Solver Foundation Services (SFS) provides several new methods to make it easier to build large parameterized models. The Set class includes a SetBinding method to make it easier to create sets based on external data. New overloads for SetBinding provide better performance and flexibility. The OML modeling language has been extended to support inline Set definition.

Performance Improvements

Numerous SFS performance improvements have been made to reduce the amount of time and memory consumed, particularly for large and sparse models.

Excel Add-In Improvements

The Excel add-in for Solver Foundation 3.1 includes several new features. The directives tab now supports third-party solvers. You can configure third-party solvers the same way as Solver Foundation’s built-in solvers. You can provide initial values for decisions, improving performance for solvers with warm start capabilities. The Excel add-in now provides sparse parameter support. Previously, values needed to be specified for all possible indexes. This change means that you only need to specify nonzero values. Finally, support for binding to named ranges in Excel has been extended. Finally, the Excel add-in provides more control over what is displayed during a solve operation through the new options dialog.

Gurobi 4.5 Support

Solver Foundation 3.1 includes the Gurobi 4.5 solver. Gurobi 4.5 is the default mixed integer programming (MIP) and mixed integer quadratic programming (MIQP) solver.

Additional Samples

Solver Foundation 3.1 provides additional samples, including a logistic regression solver based on the CompactQuasiNewtonSolver class.

Gurobi 4.5 Connector for Solver Foundation 3.0

Nate Brixius — Fri, 17 Jun 2011 16:58:00 GMT

The Gurobi connector for Solver Foundation has been updated for Gurobi 4.5. You can obtain the connector by visiting the Solver Foundation forum. Here are installation and usage instructions for the connector. These instructions have been verified on 32- and 64-bit versions of Windows 7 using Visual Studio 2010.

Installation

Download the zip file Gurobi 4.5.zip. It contains:

The GurobiPlugin.dll which connects the Gurobi 4.5 solver to Solver Foundation 3.0.
32- and 64-bit versions of the Gurobi 4.5 solver, found in the win32 and win64 directories.
An updated version of the Gurobi Solver Programming Primer.

Extract the zip file to a folder of your choice.
Copy GurobiPlugin.xml and GurobiPlugin.dll into Program Files\Microsoft Solver Foundation\3.0.1.10599\Plugins (or "Plugins (x86)" for 32-bit systems). You may need administrator privileges to perform this action. If you do not know whether your system is 32- or 64-bit, from the Start menu, right click on "Computer" and select "Properties":

4. Select gurobi45.dll from the win32 or win64 folder and copy to the same folder. [corrected 7/28/2011]

Usage

Applications that use Solver Foundation and Gurobi need to be able to access the Solver Foundation assembly, the Gurobi plug-in assembly, and the Gurobi solver. The Solver Foundation assembly is accessed by adding a project reference in Visual Studio. To use Gurobi 4.5 in a Solver Foundation application built from Visual Studio 2010, perform the following additional steps.

Open the project file associated with your application in Visual Studio.
Add a project reference to GurobiPlugin.dll by browsing to the destination folder in Installation Step 3.
Change the configuration file for your application. For example, to make Gurobi the default LP solver for Solver Foundation 3.0, change the app.config file for your project to the following:

<?xml version="1.0" encoding="utf-8" ?>
<configuration>
<configSections>
    <section name="MsfConfig"
             type="Microsoft.SolverFoundation.Services.MsfConfigSection, Microsoft.Solver.Foundation, Version=3.0.1.10599, Culture=neutral, PublicKeyToken=31bf3856ad364e35"
             allowLocation="true" allowDefinition="Everywhere" allowExeDefinition="MachineToApplication"
             restartOnExternalChanges="true" requirePermission="true" />
</configSections>
<MsfConfig>
    <MsfPluginSolvers>
      <MsfPluginSolver name="gurobi" capability="LP" assembly="GurobiPlugIn.dll"
                       solverclass="SolverFoundation.Plugin.Gurobi.GurobiSolver"
                       directiveclass="SolverFoundation.Plugin.Gurobi.GurobiDirective"
                       parameterclass="SolverFoundation.Plugin.Gurobi.GurobiParams" />
    </MsfPluginSolvers>
</MsfConfig>
</configuration>

4. Ensure that the Platform Target for your application is set to Any CPU. This can be verified by right clicking on the project in the Solution Explorer, selecting "Properties", and navigating to the Build tab:

5. Build the application.

6. Copy gurobi45.dll from the destination folder in Installation Step 3 to the output directory for your application. This is typically found under bin\Debug. Copying gurobi45.dll to this location allows the connector to call the solver.

Your application should now be configured to use Gurobi 4.5 with Solver Foundation 3.0. Consult the Gurobi Solver Programming Primer for additional information.

MOSEK connector updated

Nate Brixius — Wed, 27 Apr 2011 14:39:49 GMT

We are pleased to announce an updated Solver Foundation connector to the popular MOSEK solver. MOSEK is designed to solve large-scale linear, mixed integer, and certain types of nonlinear models.

To get started, download the free connector at the Solver Foundation forum, and install MOSEK by visiting mosek.com. The connector supports Microsoft Solver Foundation version 3.0 and MOSEK version 6.0.0.103 and later. To set MOSEK as the default solver, change the configuration file for your dll or application. (More information is available here.)

  <MsfConfig>
    <MsfPluginSolvers>
      <MsfPluginSolver name="mosek"
        capability="LP"
        assembly="MosekMsfPlugin.dll"
        solverclass="SolverFoundation.Plugin.Mosek.MosekInteriorPointSolver"
        directiveclass="SolverFoundation.Plugin.Mosek.MosekInteriorPointMethodDirective"
        parameterclass="SolverFoundation.Plugin.Mosek.MosekInteriorPointSolverParams" />
      <MsfPluginSolver name="mosek"
        capability="MILP"
        assembly="MosekMsfPlugin.dll"
        solverclass="SolverFoundation.Plugin.Mosek.MosekMipSolver"
        directiveclass="SolverFoundation.Plugin.Mosek.MosekMipDirective"
        parameterclass="SolverFoundation.Plugin.Mosek.MosekMipSolverParams" />
      <MsfPluginSolver name="mosek"
        capability="QP"
        assembly="MosekMsfPlugin.dll"
        solverclass="SolverFoundation.Plugin.Mosek.MosekInteriorPointSolver"
        directiveclass="SolverFoundation.Plugin.Mosek.MosekInteriorPointMethodDirective"
        parameterclass="SolverFoundation.Plugin.Mosek.MosekInteriorPointSolverParams" />
    </MsfPluginSolvers>
  </MsfConfig>

This connector has been designed to work with future releases of MOSEK and Solver Foundation by changing the configuration file. For example, if you have the newly released 6.0.0.106 version, add the following section to the <configuration> block:

  <runtime>
    <assemblyBinding xmlns="urn:schemas-microsoft-com:asm.v1">
      <dependentAssembly>
        <assemblyIdentity name="mosekdotnet"
          publicKeyToken="510c00a7f38678b3"
          culture="neutral" />
        <!-- Assembly versions can be redirected in application, 
          publisher policy, or machine configuration files. -->
        <bindingRedirect oldVersion="6.0.0.103" newVersion="6.0.0.106" />
      </dependentAssembly>
    </assemblyBinding>
  </runtime>

This tells Solver Foundation that it is okay to use the newer version of MOSEK.

Download the free connector at the Solver Foundation forum, and visit mosek.com for information on evaluating or purchasing MOSEK.

New Solver Foundation forum and home page

solverfoundation — Tue, 26 Apr 2011 18:47:00 GMT

Soma announced on his blog today that there's a brand new MSDN forum and DevLabs home page for Solver Foundation. The new MSDN forum is a great place to ask questions, share examples, and provide feedback to the team. Visit the MSDN forum at

http://social.msdn.microsoft.com/Forums/en-US/solverfoundation/threads

Solver Foundation has also been added to the TC Labs page. You can learn more about Microsoft Technical Computing from the TC Labs home page, or from modelingtheworld.com. The Solver Foundation homepage on TC Labs is the place to start if you want to learn more about Solver Foundation. Visit the new home page at

http://msdn.microsoft.com/en-us/devlabs/hh145003.aspx

- Solver Foundation Team

New Solver Foundation Forum coming soon

solverfoundation — Fri, 22 Apr 2011 15:21:00 GMT

As announced on the Solver Foundation MSDN forum, over the next few days we'll be rolling out brand-new Solver Foundation sites:

A brand new forum for questions and discussions. It has better search, code formatting, and more.
A new download site (coming soon).

We'll post more information on both sites once they're both live. Thanks for your continued support of Solver Foundation!
- Solver Foundation Team

Video: Modeling with Solver Foundation 3.0

solverfoundation — Tue, 22 Mar 2011 22:11:00 GMT

We've posted a new video that shows how to use the Excel add-in for Solver Foundation 3.0. If you are new to modeling, optimization, or Solver Foundation, we hope you'll find this video useful as you get started.

For more, check out this post on Channel 9.

Sparse Parameters in Solver Foundation 3.0

Nate Brixius — Tue, 25 Jan 2011 16:44:24 GMT

Parameters represent input data for a model. Parameters are most useful when they are associated with Sets. Associating Sets with Parameters allows you define tables (or if you like: vectors and matrices) of data: these are called "indexed parameters". When you use indexed parameters, data can change without having to update the model. A simple example is as follows:

        Set colors = new Set(Domain.Any, "colors");
        Parameter codes = new Parameter(Domain.IntegerRange(0, 2), "codes", colors);
        Tuple<string, int>[] codeData = { Tuple.Create("red", 0), Tuple.Create("green", 1),Tuple.Create("blue", 2) };
        codes.SetBinding(codeData, "Item2", "Item1");

We create a set, pass the set to the Parameter constructor to create an indexed decision with 0-1 entries. The values of a parameter are established through data binding using the SetBinding method shown above. Prior to Solver Foundation 3.0 it was necessary to specify parameter values for all the possible elements of each set used in the parameter. Let’s extend our example to define another Parameter using the same Set.

        Parameter tasteful = new Parameter(Domain.IntegerRange(0, 1), "tasteful", colors);
        Tuple<string, int>[] tasteData = { Tuple.Create("red", 1), Tuple.Create("blue", 1) };
        tasteful.SetBinding(codeData, "Item2", "Item1"); // error when we call Solve

No value was given for "green", so an error will occur when we try to solve a model involving the parameter.

Solver Foundation 3.0 introduced the concept of sparse parameters. This simply means that parameters can be given default values. The parameter takes on the default value for any index combinations not specified in the SetBinding statement. If we modify the previous example the value tasteful[“green”] will be 0.

        tasteful.SetBinding(codeData, "Item2", 0, "Item1"); // default value 0

The documentation for the new SetBinding overload is located here. Unfortunately the Excel add-in does not take advantage of this new functionality. We hope to address this in a future release.

Solving non-linear models with Compact Quasi Newton solver part 2

dudeness — Mon, 06 Dec 2010 18:35:44 GMT

In our last post we described the new API of Solver Foundation 3.0 for non-linear models. In particular we described the new API for the Compact Quasi Newton (CQN) solver. We also showed how to model and solve non-linear models using the solver interface. To do this it is necessary to introduce a delegate for getting the value of your goal function and a delegate for setting the gradient to your function. In today’s post we will see how to use Solver Foundation Services to model your problem, without needing to specify derivatives. Solver Foundation Services uses Automatic Differentiation to specify gradient information, so you don’t have to.

Just like in our last post, we consider the Rosenbrock optimization problem. We will again use a multi-dimensional variant where each variable is coupled just with one other variable.

The steps for modeling and solving non-linear models with Solver Foundation Services are exactly the same as those for any other model type. The model abstraction provided by Solver Foundation Services works just as well. The basic steps are:

1. Create a SolverContext and a model.

2. Define your model. This includes the Decisions and the Goal, which is a function of those Decisions. Note that only unconstrained, unbounded models can be solved with CQN, so no constraints are specified.

3. Solve the model and optionally report the solution.

Let’s see how those steps are carried out with Solver Foundation Services:

1. Create a Solver context and a model.

SolverContext context = SolverContext.GetContext();

Model model = context.CreateModel();

2. Next, you need to define your model. The model always includes definitions for Decision/s and a Goal. In this example it makes sense to use an indexed decision, as the Goal term involves some pattern over some index. We will define a Set, a Decision which is indexed by the Set, and a Goal which will be defined with our function to minimize.

const int dimensions = 100;

const int alpha = 100;

// Create a Set which the decision will be indexed with

Set dimensionsSet = new Set(Domain.IntegerRange(1, dimensions), "set");

// Create just one decision, indexed by dimensionsSet

Decision decision = new Decision(Domain.Real, "x", dimensionsSet);

// Add the decision to the model

model.AddDecision(decision);

// Define the goal. Note that we use ForEachWhere operator, as we only want to go throgh half of the indexes

model.AddGoal("theGoal", GoalKind.Minimize, Model.Sum(Model.ForEachWhere(

dimensionsSet, /* the set */

(index) => alpha * (Model.Power((decision[2 * index] - decision[2 * index - 1] * decision[2 * index - 1]), 2)) +

(Model.Power(1 - decision[2 * index - 1], 2)), /* the math expression */

(index) => index <= dimensions / 2 /* the condition */

)));

3. Solve the model with the appropriate directive (for this problem the default call will use the CQN solver as well) and optionally report the solution.

var directive = new CompactQuasiNewtonDirective();

var sol = context.Solve(directive);

var report = sol.GetReport() as CompactQuasiNewtonReport;

// From the report you can get details of the solution such as:

// report.TotalTime;

// report.IterationCount

// Print out all solution information

Console.WriteLine(report);

Running the code, the output is :

===Solver Foundation Service Report===

Date: 12/3/2010 2:40:51 PM

Version: Microsoft Solver Foundation 3.0.1.0 Enterprise Edition

Model Name: DefaultModel

Capabilities Applied: NLP

Solve Time (ms): 39

Total Time (ms): 243

Solve Completion Status: LocalOptimal

Solver Selected: Microsoft.SolverFoundation.Solvers.CompactQuasiNewtonSolver

Directives:

CQN(TimeLimit = -1, Tolerance = 1E-07, IterationsToRemember = 17, IterationLimit = 2147483647)

Solver solution quality: LocalOptima.

Iteration count: 22.

Evaluation call count: 28.

Tolerance difference: -2.63557088810946E-08.

===Solution Details===

Goals:

theGoal: 4.72745153676104E-21

Decisions:

x(2): 1.00000000001197

x(1): 1.00000000000559

x(4): 1.00000000001197

x(3): 1.00000000000559

x(6): 1.00000000001197

x(5): 1.00000000000559

Well, that’s it! All you need to do is define your goal in an abstract, mathematical way, and the rest (including automatic differentiation for the solver) is done by the Solver Foundation Services.

So, it is very easy and more mathematically descriptive to model your non-linear model with Solver Foundation Services. Also, it is easier to use a third party solver if for example you do need to add constraints to your model. What are the disadvantages? In which cases you would better off using the solver API? You should consider using the solver API in one of the following cases:

- Your goal function needs a math operator that is not currently supported in Solver Foundation Services.

- Your model’s dimension (number of Decisions) is very high. Mostly because of the automatic differentiation takes place, using Solver Foundation Services has larger memory footprint, so huge models might benefit from modeling directly against the solver. It depends heavily in the function itself, but around 100,000 Decisions you may consider switching to solver API.

- High dimensionality also effect the time performance, mainly as for the automatic differentiation. If time measure is highly important to you, and your problem is not small, you should at least experiment with the solver API to see if it helps.

-Solver Foundation Team

Solving non-linear models with Compact Quasi Newton solver part 1

dudeness — Mon, 15 Nov 2010 18:58:53 GMT

Several days ago, Microsoft Solver Foundation 3.0 was released, providing new features to build and solve nonlinear models. These features are at the solver, Solver Foundation Services, and modeling levels. Solver Foundation’s Compact Quasi Newton solver handles unconstrained nonlinear models – it has been supported since version 1.0. Before our 3.0 release, the Compact Quasi Newton solver (CQN) had its own API for modeling and solving unconstrained, unbounded, non-linear models, and there was no access to this solver from Solver Foundation Services. In version 3.0, CQN solver uses the same interfaces that any other third party non-linear solver can use for modeling and solving a non-linear model: the INonlinearModel and INonlinearSolver interfaces. In this post we will show you how to model and solve nonlinear models using the new CQN solver API. In some later post we will show how to use Solver Foundation Services to model your problem, without needing to specify derivatives.

In this walkthrough we consider the Rosenbrock optimization problem. The original problem is a simple function with two dimensions (variables) that is often used as a test problem in optimization. The reason we use this function is that it can very easily be expanded to n-dimensions. We will use a multi-dimensional variant when each variable is coupled just with one other variable.

Here are the logical steps you need to take in order to model and solve problem with the CQN solver. These steps apply to any other nonlinear solver (with a few small variations).

1. Create the modeling object.

2. Define your model. This includes the variables, the function to optimize (the goal) and the gradient vector. Note that only unconstrained, unbounded models can be solved with CQN, no constraints are specified.

3. Solve the model and optionally report the solution.

Let’s see how those steps are carried out with the new solver API:

1. Create the solver and parameters. Solver parameters can be used to configure solver behavior.

var solverParams = new CompactQuasiNewtonSolverParams();

var solver = new CompactQuasiNewtonSolver();

2. Next, create the variables. For this sample we are solving the 100 dimensional model, so we create 100 variables. Note that we use null for the variable keys. Keys can be useful if you want to refer to a variable by its key instead of its index. The tradeoff is a bigger memory footprint (to store the keys).
After that, we add a single row for the objective function and register it as a goal. Finally, we define callbacks for function and gradient evaluation.

int dimentions = 100;

int vidRow;

int[] vidVariables = new int[dimentions];

// add variables, using null as the key.

for (int i = 0; i < dimentions; i++)

solver.AddVariable(null, out vidVariables[i]);

//add a row and set it as the minimization goal

solver.AddRow(null, out vidRow);

solver.AddGoal(vidRow, 0, true);

// set the function and gradient evaluators.

solver.FunctionEvaluator = RosenbrockFunction;

solver.GradientEvaluator = RosenbrockGradient;

3. Solve the model and print out the result, using the solver’s ToString() override.

//Solve the model

solver.Solve(solverParams);

Console.WriteLine("== Multidimensional variant of Rosenbrock ==");

Console.WriteLine(solver.ToString());

That’s it. Well, not quite, as the interesting part is the definition of the function and gradient callbacks. Let’s see the definition for them:

/// <summary>

/// Function value callback for first variant of Rosenbrock's function.

/// This is the multidimensional variant of Ronsenbrock when n must be pair

/// f(x) = sum(i, from 1 to N){ [alpha(x(2i) - x(2i-1)^2)^2] + [(1 - x(2i-1))^2] }

/// <param name="model">the model.</param>

/// <param name="rowVid">the row index.</param>

/// <param name="values">the variable values.</param>

/// <param name="newValues">is first evaluator call with those variable values.</param>

/// <returns>the row value</returns>

private static double RosenbrockFunction(INonlinearModel model, int rowVid, ValuesByIndex values, bool newValues) {

const int firstVid = 1;

const int alpha = 100;

double value = 0;

int dimentions = model.VariableCount;

for (int i = firstVid; i <= dimentions / 2; i++) {

value += alpha * (Math.Pow((values[2 * i] - values[2 * i - 1] * values[2 * i - 1]), 2)) + (Math.Pow(1 - values[2 * i - 1], 2));

}

return value;

}

/// <summary>

/// Gradient value callback for the first variant of Rosenbrock's function.

/// This is the multidimensional variant of Ronsenbrock when n must be pair

/// f(x) = sum(i, from 1 to N){ [alpha(x(2i) - x(2i-1)^2)^2] + [(1 - x(2i-1))^2] }

/// </summary>

/// <param name="model">the model.</param>

/// <param name="rowVid">the row index.</param>

/// <param name="values">the variable values.</param>

/// <param name="newValues">is first evaluator call with those variable values.</param>

/// <param name="gradient">the gradient values (set by the user).</param>

private static void RosenbrockGradient(INonlinearModel model, int rowVid, ValuesByIndex values, bool newValues, ValuesByIndex gradient) {

const int firstVid = 1;

const int alpha = 100;

int dimentions = model.VariableCount;

for (int i = firstVid; i <= dimentions / 2; i++) {

gradient[2 * i - 1] = (4 * alpha * values[2 * i - 1] * (values[2 * i - 1] * values[2 * i - 1] - values[2 * i]) + 2 * values[2 * i - 1] - 2);

gradient[2 * i] = (2 * alpha * -1 * (values[2 * i - 1] * values[2 * i - 1] - values[2 * i]));

}

There are few types and concepts worth mentioning.

- ValuesByIndex – This type allows you to map from a variable index to underlying solver value. The values argument represent the current values for the variables when the callback is called, so the function and gradient callbacks can get the values in order to compute the function value and the gradient values. If for example there is a variable with index x, values[x] is the current value of x. The gradient argument represents the gradient value associated with each variable, so if for example there is a variable with index x, gradient[x] represent the value of df/dx. Gradient evaluator uses gradient argument to set the right value for the gradient.

- Index allocation convention – There is a convention for how the CQN solver allocates variable and row indexes. By convention variables get indexes from 1 ... VariableCount, in the order they were added. The only row (the goal) will always get the index 0. You can rely on this convention in your callbacks to access variable and row indexes without having to do any bookkeeping. In fact, notice that we did not use the vidVariables array after creating the variables, and we could have even omitted it altogether.

- bool newValues – This Boolean flag indicates if this is first evaluator call with those variable values. This can be used to make the computation of gradients in your evaluator more efficient, as long as you have some computation on the function callback, which can be carried over to be used when computing the gradient. For each point, CQN solver always calls the function evaluator first followed by gradient evaluator. Therefore this Boolean will always be true when function evaluator is called, and false when gradient evaluator is called. In this sample code we did not take advantage of this flag.

With that in mind, the rest is straightforward. The function evaluator gets back the value of the function in the current point, and the gradient evaluator sets the values for the gradient.

Running the code, the output is :

== Multidimensional variant of Rosenbrock ==

Minimize problem

Dimensions = 100

Variable indexes:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10...

Starting point = 0, 0, 0, 0, 0, 0, 0, 0, 0, 0...

Solution quality is: LocalOptima

Number of iterations performed: 22

Number of evaluation calls: 28

Finishing point =1.00000000000559, 1.00000000001197, 1.00000000000559, 1.00000000001197, 1.00000000000559, 1.00000000001197, 1.00000000000559, 1.00000000001197, 1.00000000000559, 1.00000000001197...

Finishing value =4.72745153676104E-21

All of this information can also be programmatically accessed from the solver through methods or properties.

The code for this sample is a modification of code provide as a sample project in your document directory under “…\Documents\Microsoft Solver Foundation\Samples\Solvers\C#\CQN”.

In the next post, we will consider the following question: how would you model Rosenbrock function optimization using the Solver Foundation Services? (Hint: easily, naturally and with no gradient definition!)

-Solver Foundation Team

Microsoft Solver Foundation v3.0 Released

solverfoundation — Wed, 10 Nov 2010 20:53:02 GMT

We pleased to announce the release of Microsoft Solver Foundation v3.0. The Express edition is available at http://code.msdn.microsoft.com/solverfoundation. The Standard and Academic Editions of Solver Foundation v3.0 will soon be available online via MSDN and MSDNAA subscriber downloads.

Microsoft Technical Computing’s Solver Foundation provides a complete system for model specification, connection to data sources, and access to best-of-breed solvers for Excel users and .Net programmers. Version 3.0 greatly extends the range of real-world models that can be modeled and solved by Solver Foundation, in particular those involving nonlinear expressions. Here is a partial list of new features:

A new hybrid local search solver designed to tackle nonlinear models including nonconvex and/or nondifferentiable functions.
Mixed integer quadratic programming (MIQP) plug-in support. The just-released Gurobi 4.0 solver is the default MIP and MIQP solver for Solver Foundation.
Full plug-in support for nonlinear and mixed-integer nonlinear solvers, making Solver Foundation the ideal platform for solver experimentation and innovation.
Access to many new third-party solvers using the new KNITRO and Frontline Solver Platform SDK plug-ins.
The Compact Quasi-Newton solver is fully accessible from OML and SFS - without the need for specifying gradient information.
18 new OML operators: If, Exp, Log, Floor, Ceiling, Sin, Cosh, ArcTan, etc.
Automatic differentiation (forward and backward).
Solver Foundation Services improvements:
- Solver selection
- Sparse parameters
- Multiple model support
- Better C# export
- Extended exception object model

The only system requirement for using Solver Foundation is .Net 4.0. Excel 2007 or Excel 2010 is required to use the Excel add-in. Try out the Express version and let us know what you think!

The Solver Foundation Team

Solver Foundation at INFORMS 2010

Nate Brixius — Fri, 05 Nov 2010 22:12:00 GMT

The Solver Foundation team will once again be at the INFORMS annual meeting, this year in Austin, Texas. We will be showcasing our upcoming release featuring nonlinear optimization, mixed integer quadratic programming, new OML operators, SFS improvements, and much more. Drop by our presentation on Sunday - click here for more details.

During the conference we will release Solver Foundation 3.0 to the web. The Express version will be available on our MSDN site, with the Standard version available for MSDN subscribers shortly thereafter.

See you in Austin!

The next release of Solver Foundation

solverfoundation — Wed, 29 Sep 2010 16:20:17 GMT

The Solver Foundation team has been hard at work on our next release. We want to take a break from the action to share some details about we plan to ship. Our focus is to broaden the range of real-world models that can be created, solved and analyzed using Solver Foundation Services (SFS) and OML. Here are some of the features we plan to include:

A new local search solver that covers the full expressiveness of SFS.
The Compact Quasi-Newton solver will fully accessible from OML and SFS - without the need for specifying gradient information.
18 new OML operators: If, Exp, Log, Floor, Ceiling, Sin, Cosh, ArcTan, etc.
Full plug-in support for nonlinear and mixed-integer nonlinear solvers. Metaheuristic and gradient-based solvers alike can be easily plugged into Solver Foundation.
Automatic differentiation support.
New plug-in solvers.
Mixed integer quadratic programming (MIQP) plug-in support.
Improved exception object model, including programmatically accessible location information.
Solver Foundation Services improvements, including multiple model support.
Improved Excel add-in data binding support.

The next version of Solver Foundation will require .Net 4.0, because it takes advantage of new .Net 4.0 features. Existing Solver Foundation code, OML models, and plug-in solvers will continue to work without changes.

We will update the blog and MSDN forum with more information about the release as we draw closer to our November release.

- Solver Foundation Team

Gurobi 3.0 Plug-in for Microsoft Solver Foundation 2.1

solverfoundation — Thu, 16 Sep 2010 21:52:26 GMT

Solver Foundation developers can update their environment to use the latest solver from Gurobi. In the Downloads area of the MSDN gallery site, the files:

Gurobi 3.0 Solver and Plug-In for Microsoft Solver Foundation - 32-bit
Gurobi 3.0 Solver and Plug-In for Microsoft Solver Foundation - 64-bit

are now online and ready for use. The download includes an updated solver along with installation instructions and an update to the Gurobi-SolverProgrammingPrimer.

The Solver Foundation Team

VBA integration for Solver Foundation

Nate Brixius — Wed, 30 Jun 2010 15:15:36 GMT

In Solver Foundation 2.1 we added very basic support for VBA in the Excel Add-In. By obtaining the MSF add-in COM object you can call Solve, which has the same effect as clicking the “Solve” button in the Solver Foundation Ribbon:

Here is a code sample:

Sub CallSolve()
  ' Get the MSFForExcel COM object
  Dim oAddin As COMAddIn
  Dim oCOMFuncs As Object
  Set oAddin = Application.COMAddIns("MicrosoftSolverFoundationForExcel")
  Set oCOMFuncs = oAddin.Object
 
  ' Solve
  oCOMFuncs.Solve
 
End Sub

To access solver results you can write VBA code to access the data in the “Solver Foundation Results” sheet. For cases where the VBA Solve method is insufficient, we recommend writing a VSTO add-in, which allows you to access the full power of Solver Foundation. The Sudoku sample (Documents\Microsoft Solver Foundation\Samples\SolverFoundationServices\VB.NET\Sudoku) shows you how to build a VSTO add-in that uses Solver Foundation.

Simpler Data Binding using LINQ and extension methods

Nate Brixius — Tue, 29 Jun 2010 04:15:00 GMT

In this post we introduce some utility methods to make it easier to work with arrays in Solver Foundation programs. Most real models involve either input parameters or output decision variables that involve collections. For example, in an investment portfolio optimization model we may have an input parameter that represents the mean return for each potential investment in the portfolio. In such a case the mean return may be stored in an array of doubles. In the Solver Foundation model, we’d define a Set for the investment types, and then define a parameter “meanReturn” that is indexed by that set. Then we would call SetBinding to associate the array with the Parameter. But have a look at the signature for Parameter.SetBinding:

void SetBinding<T>(IEnumerable<T> binding, string valueField, params string[] indexFields);

It’s not at all obvious what to do! The first entry should obviously be the array (since arrays implement IEnumerable), but what should we fill in for the “valueField”? If I had an array of objects, I would fill in the name for the property on the object that returned the mean return. But in this case I have an array of doubles. One way to handle this problem would be to transform the array of doubles into an array of objects with the right type. But it’s a pain to do this each time I want to bind to an array. So why not write some utility methods that automatically do this work? Here goes:

    /// <summary>Bind an indexed parameter to an IEnumerable of values.
    /// </summary>
    public static void SetBinding(this Parameter parameter, IEnumerable<double> data) {
      parameter.SetBinding(ToIEnumerable(data), "Value", "Key");
    }

    private static IEnumerable<KeyValuePair<int, T>> ToIEnumerable<T>(IEnumerable<T> vector) {
      return vector.Select((d, index) => new KeyValuePair<int, T>(index, d));
    }

I have added a method called SetBinding. The “this” before the first argument means that SetBinding is an extension method, which means we can call it as if it were a member of the Parameter class. The body of the method calls a utility function called ToIEnumerable. ToIEnumerable simply does a LINQ Select on the data, transforming it into an IEnumerable of (key, value) pairs. Now we’ve got what we want! We pass it into SetBinding, specifying “Value” and “Key” for the value and index fields, respectively.

Notice that I can do the same thing for scalar parameters (parameters with 0 indexes) and “matrix parameters” (parameters with 2 indexes). A similar issue exists for getting results. Sometimes I just want to get an array of doubles corresponding to the values for a 1-indexed Decision. Using LINQ it’s easy to pull the values out of the Decision.GetValues method and push them into an array. I can wrap all of this stuff into a new class – here it is. (Note that some of the standard argument checking has been left out for brevity):

using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Linq.Expressions;
using Microsoft.SolverFoundation.Common;
using Microsoft.SolverFoundation.Services;

namespace SolverFoundation.Samples {
  /// <summary>Helper methods for Parameter and Decision data binding.
  /// </summary>
  public static class BindingUtilities {

    /// <summary>Bind a parameter to a scalar value.
    /// </summary>
    public static void SetBinding(this Parameter parameter, double data) {
      parameter.SetBinding(ToIEnumerable(data), "Value");
    }

    /// <summary>Bind an indexed parameter to an IEnumerable of values.
    /// </summary>
    public static void SetBinding(this Parameter parameter, IEnumerable<double> data) {
      parameter.SetBinding(ToIEnumerable(data), "Value", "Key");
    }

    /// <summary>Bind an indexed parameter to a table.
    /// </summary>
    public static void SetBinding(this Parameter parameter, IEnumerable<IEnumerable<double>> data) {
      parameter.SetBinding(ToIEnumerable(data), "Item3", "Item1", "Item2");
    }

    /// <summary>Gets the values for a decision with one index Set.
    /// </summary>
    /// <returns>An IEnumerable containing the values.</returns>
    /// <remarks>The values are returned ordered by index.</remarks>
    public static IEnumerable<double> GetValuesByIndex(this Decision decision) {
      // GetValues returns the values in order of index --> no need to sort.
      return decision.GetValues().Select(r => Convert.ToDouble(r[0]));
    }

    /// <summary>Gets the values for a decision with two index Sets.
    /// </summary>
    /// <returns>An IEnumerable containing the values, grouped by the first index.</returns>
    /// <remarks>The values are returned ordered by index.</remarks>
    public static IEnumerable<IEnumerable<double>> GetValuesByFirstIndex(this Decision decision) {
      // GetValues returns the values in order of index --> no need to sort.
      return decision.GetValues().GroupBy(r => r[1]).Select(g => g.Select(r => Convert.ToDouble(r[0])));
    }

    private static IEnumerable<KeyValuePair<int, T>> ToIEnumerable<T>(T value) {
      return new KeyValuePair<int, T>[] { new KeyValuePair<int, T>(0, value) };
    }

    private static IEnumerable<KeyValuePair<int, T>> ToIEnumerable<T>(IEnumerable<T> vector) {
      return vector.Select((d, index) => new KeyValuePair<int, T>(index, d));
    }

    private static IEnumerable<Tuple<int, int, T>> ToIEnumerable<T>(IEnumerable<IEnumerable<T>> matrix) {
      var m = matrix.Select((row, i) => row.Select((cell, j) => new Tuple<int, int, T>(i, j, cell)));
      var cells = from cell in m.SelectMany(c => c) select cell;
      return cells;
    }
  }
}

Once I have this class, life is much simpler whenever I want to bind parameters to arrays (or lists). For example, here is a C# program that builds and solves the portfolio optimization model I introduced earlier. I have obnoxiously put four lines in large bold type to show you where the utility functions are called. Very simple!

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.SolverFoundation.Services;

namespace SolverFoundation.Samples {
  public class QuadraticPortfolioSample {
    public static double[] Solve(double required, double[] meanReturn, double[][] covar) {
      SolverContext context = SolverContext.GetContext();
      Model model = context.CreateModel();

      Set I = new Set(Domain.Any, "I");
      Set J = new Set(Domain.Any, "J");

      Parameter requiredReturn = new Parameter(Domain.Real, "RequiredReturn");
      Parameter mean = new Parameter(Domain.Real, "Mean", I);
      Parameter cov = new Parameter(Domain.Real, "Cov", I, J);
      model.AddParameters(requiredReturn, mean, cov);

      Decision allocation = new Decision(Domain.RealRange(0, 1), "Allocation", I);
      Decision portfolioYield = new Decision(Domain.RealNonnegative, "Yield");
      model.AddDecisions(allocation, portfolioYield);

      model.AddConstraint("c1", (portfolioYield >= requiredReturn));
      model.AddConstraint("c2", (Model.Sum(Model.ForEach(I, i => allocation[i])) == 1));
      model.AddConstraint("c3", (Model.Sum(Model.ForEach(I, i => (mean[i] * allocation[i]))) == portfolioYield));
      model.AddGoal("Variance", GoalKind.Minimize,
        Model.Sum(Model.ForEach(I, i => Model.ForEach(J, j => Model.Product(cov[i, j], allocation[i], allocation[j]))))
        );

      requiredReturn.SetBinding(required);
      mean.SetBinding(meanReturn);
      cov.SetBinding(covar);

      var solution = context.Solve();
      return allocation.GetValuesByIndex().ToArray();
    }
  }
}

Now it’s a breeze to call this method to solve portfolio optimization models. Look:

    private static void TryIt() {
      QuadraticPortfolioSample m = new QuadraticPortfolioSample();
      double requiredReturn = 0.06;
      double[] meanReturn = { .1322, .0824, .0903, .0873, .0629, .0910 };
      var covar = new double[][] {
        new double[] {0.006650561,    0.000261280,    0.000217891,    0.003089108,    0.000137570,    0.002071282},
        new double[] {0.000261280,    0.000062715,    0.000048178,    0.000326722,    -0.000043052,    0.000131168},
        new double[] {0.000217891,    0.000048178,    0.000037676,    0.000321380,    -0.000031673,    0.000118690},
        new double[] {0.003089108,    0.000326722,    0.000321380,    0.014783517,    0.001100947,    0.003924335},
        new double[] {0.000137570,    -0.000043052,    -0.000031673,    0.001100947,    0.000372023,    0.000307163},
        new double[] {0.002071282,    0.000131168,    0.000118690,    0.003924335,    0.000307163,    0.001310528}
      };

      // the following line is awesome in its simplicity.
      double[] allocation = QuadraticPortfolioSample.Solve(requiredReturn, meanReturn, covar);
      for (int i = 0; i < allocation.Length; i++) {
        Console.WriteLine("{0}\t{1}", i, allocation[i].ToString("P"));
      }
    }

Let us know if you find these utility methods useful!

Use indices instead of keys to reference model elements

solverfoundation — Tue, 22 Jun 2010 17:47:01 GMT

In the 2.1 release of Microsoft Solver Foundation, there is a bug in the sample plug-in for the XpressMPSolver. For improved performance variable/row keys are no longer specified by Solver foundation services when creating LinearModel object. In order to work correctly, the source for the XpressMPSolver plug-in should be modified to use indices instead of keys.

The following code in XpressMPSolver.cs (from line 567) in method BuildModel()

if (!IsGoal(GetIndexFromKey(entry.Key)) &&
    !IsSOS1Row(GetIndexFromKey(entry.Key)) &&
    !IsSOS2Row(GetIndexFromKey(entry.Key))) {

need to be changed as below to fix the issue:


if (!IsGoal(entry.Index) &&
    !IsSOS1Row(entry.Index) &&
    !IsSOS2Row(entry.Index)) {

Alternatively, download the source code from http://code.msdn.microsoft.com/Project/Download/FileDownload.aspx?ProjectName=solverfoundation&DownloadId=12842

Microsoft Solver Foundation Customer Feedback Survey

solverfoundation — Tue, 08 Jun 2010 18:02:10 GMT

The Solver Foundation team is interested in your experience with the product. Please complete the short survey linked to below and share your thoughts on the current release and prioritization of areas for future releases.

Thanks for your time!

http://www.surveymonkey.com/s/M57DS8S

Relaxing mixed integer models with Solver Foundation

Nate Brixius — Mon, 07 Jun 2010 22:17:00 GMT

Mixed integer programming (MIP) models are one of the most commonly formulated Solver Foundation model types. “Mixed” refers to the fact that such models contain both integer and continuous (real) decision variables. People frequently want to solve the “relaxation” of a MIP model: the model where all variables are assumed to be real. It’s a simple matter to solve the relaxation with Solver Foundation by adding a little logic to supply the right Domain for each Decision. Here is a simple example of a MIP model:

    private void Production() {
      SolverContext context = SolverContext.GetContext();
      Model model = context.CreateModel();

      Decision xs = new Decision(Domain.IntegerNonnegative, "Number_of_small_chess_boards");
      Decision xl = new Decision(Domain.IntegerNonnegative, "Number_of_large_chess_boards");
      model.AddDecisions(xs, xl);

      Constraint constraintBoxWood = model.AddConstraint("BoxWood", 1 * xs + 3 * xl <= 200);
      Constraint constraintLathe = model.AddConstraint("Lathe", 3 * xs + 2 * xl <= 160);

      model.AddGoal("Profit", GoalKind.Maximize, 5 * xs + 20 * xl);

      Solution sol = context.Solve();
      Report report = sol.GetReport();
      Console.WriteLine(report);
    }

The xs and xl decisions have domain “IntegerNonnegative”. In Visual Studio, highlight one of the domain statements and right click to extract a new method:

Call the method GetDomain. Now, let’s add an automatic property that determines whether we’re going to solve the relaxation. If this property is true, then GetDomain should return RealNonnegative instead of IntegerNonnegative:

    public bool SolveRelaxation { get; set; }

    private Domain GetDomain() {
      return SolveRelaxation ? Domain.RealNonnegative : Domain.IntegerNonnegative;
    }

Here is a simple Main method for a console application. If the user supplies any command-line arguments then the relaxation is solved instead of the original problem.

    static void Main(string[] args) {
      Program p = new Program();
      p.SolveRelaxation = args.Length > 0;
      p.Production();
    }

This simple logic can be wrapped in a class so that it can be used whenever you like.

Math Modeling Tricks: Absolute Values

solverfoundation — Wed, 02 Jun 2010 19:51:32 GMT

In a previous post, we discussed modeling tricks for min-max problems. From there, it is simple to handle absolute values as well. Consider a problem of the form

minimize Abs( a * x + b)

where a is a row vector and x is a column vector. This problem is equivalent to

minimize max{ a * x + b, - (a * x + b) }

Or, using the trick from the previous post

minimize t

subject to: a * x + b <= t

-(a * x + b) <= t

Math Modeling Tricks: Min-Max Problems

solverfoundation — Tue, 01 Jun 2010 20:41:10 GMT

When modeling problems, one may come to a formulation that is not directly model-able using the Solver Foundation API, but that may be reformulated as a known Solver Foundation model type (LP, QP, CSP, etc). Consider certain min-max problems, which with a little thought can become a linear program.

In the current example, consider a min-max problem of the form

minimize max { a_i *x + b_i for all i }

where a_i is a row of a matrix and b is a vector. This problem doesn’t look like anything that can be modeled using Solver Foundation. But Solver Foundation can handle the problem when written in the mathematically equivalent form

minimize t

subject to: a_i *x + b_i <= t for all i

As an example, consider the toy problem where we try to determine the minimum of a one-dimensional non-linear convex function f(x). We can do this by finding the minimum over a collection tangent lines, that is

minimize max { df(x_i)/dx *(x - x_i) + f(x_i) for all i }

or using our modeling trick

minimize t

subject to: df(x_i)/dx *(x - x_i) + f(x_i) <= t for all i

where the set i represents a sampling of points. For a more concrete example, consider the problem f(x) = x + 1/x, which is convex for x > 0. The minimum is at x = 1, where f(1) = 2. The collection of tangent lines looks like

where the horizontal axis represents x and the vertical axis represents f(x). The code to find the minimum is below:

static void Main() {
   SolverContext context = SolverContext.GetContext();
   Model model = context.CreateModel();

   Decision t = new Decision(Domain.Real, "t");
   Decision x = new Decision(Domain.Real, "x");
   model.AddDecisions(t, x);
   model.AddGoal("goal", GoalKind.Minimize, t);

   int i = 0;
   for (double x_i = .1; x_i <= 4; x_i = x_i + .01) {
     model.AddConstraint("constraint_" + i++, derivative(x_i) * (x – x_i) + function(x_i) <= t);
   }

   Solution solution = context.Solve();
   Report report = solution.GetReport();
   Console.WriteLine(report);
}

static double function(double x) {
   return x + 1 / x;
}

static double derivative(double x) {
    return 1 - Math.Pow(x, -2);
}

The output is as follows:

===Solver Foundation Service Report===
Date: 6/1/2010 10:58:26 AM
Version: Microsoft Solver Foundation 2.0.3.0 Enterprise Edition
Model Name: Default
Capabilities Applied: LP
Solve Time (ms): 316
Total Time (ms): 504
Solve Completion Status: Optimal
Solver Selected: Microsoft.SolverFoundation.Solvers.SimplexSolver
Directives: Microsoft.SolverFoundation.Services.Directive
Algorithm: Primal
Arithmetic: Hybrid
Variables: 2 -> 2 + 392
Rows: 392 -> 392
Nonzeros: 783
Eliminated Slack Variables: 0
Pricing (exact): SteepestEdge
Pricing (double): SteepestEdge
Basis: Slack
Pivot Count: 408
Phase 1 Pivots: 391 + 0
Phase 2 Pivots: 16 + 1
Factorings: 12 + 1
Degenerate Pivots: 0 (0.00 %)
Branches: 0
===Solution Details===
Goals:
goal: 2

Decisions:
t: 2
x: 0.994974874371864

As an additional point, note that while t = 2 is an expected result, x is not exactly the expected value of 1. This is due to the fact that the problem is discretized with a finite series of tangent lines. In fact, if you zoom in on tangent lines in the neighborhood of the minimum, given our discretization of a tangent line for every .1 in x, you will note that there are actually an infinite number of valid x values between x = .947368 and x = 1.047619.

This code shows how we can use a mathematical trick for solving min-max problems. However, for the particular example of minimizing a non-linear convex function, here are some reasons why it can’t be generally done:

it may not be easy to know if the function is convex, or over which domain it’s convex.
the method requires the user to know a neighborhood where the minimum can be found (in our case between x = .1 and x = 4), as well as a representation of the derivative
we need enough points to create a realistic envelope. In multiple dimensions, this could be expensive.

Programmatically access report data

solverfoundation — Thu, 27 May 2010 16:36:00 GMT

Solver Foundation Version 2.1 introduced a new API class called LinearReport that allows programmatic access of the report data. You can use this class to retreive sensitivity and infeasibility information.

Let’s discuss with a simple model:

SolverContext context = SolverContext.GetContext();
Model model = context.CreateModel();

      //decisions
      Decision xs = new Decision(Domain.RealNonnegative, "Number_of_small_chess_boards");
      Decision xl = new Decision(Domain.RealNonnegative, "Number_of_large_chess_boards");

model.AddDecisions(xs, xl);

      //constraints
      Constraint constraintBoxWood = model.AddConstraint("BoxWood", 1 * xs + 3 * xl <= 200);
      Constraint constraintLathe = model.AddConstraint("Lathe", 3 * xs + 2 * xl <= 160);

//Goals
model.AddGoal("Profit", GoalKind.Maximize, 5 * xs + 20 * xl);

Solution sol = context.Solve();
Report report = sol.GetReport();

To get the LinearReport, typecast report with LinearReport

LinearReport lpReport = report as LinearReport;

The following image shows some of the methods on the LinearReport that can used to retrieve sensitivity and infeasibility properties.

The following code demonstrates how to get the shadow prices of constraint constraintBoxWood from the example:

IEnumerable<KeyValuePair<string,Rational>> prices = lpReport.GetShadowPrices(constraintBoxWood);

or to get the shadow prices of all constraints:

IEnumerable<KeyValuePair<string, Rational>> prices = lpReport.GetAllShadowPrices();

Both of the above methods return pairs of each individual constraint’s name and its shadow price.

Also when a model is infeasible, you can get the list of infeasible constraints:

IEnumerable<string> infeasibleConstraints = lpReport.GetInfeasibilitySet();

GetInfeasibilitySet returns the list of constraint names that make the model infeasible

For more examples, refer to DietProblem and ColumnGeneration samples (as part of the installation) that demonstrate how to access infeasibility and sensitivity data programmatically.

Using Microsoft Solver Foundation with a WCF service application and .NET Framework 3.5

solverfoundation — Thu, 20 May 2010 21:03:00 GMT

When using the .NET Framework 3.5, a workaround is required to use a WCF service application with Solver Foundation. Without this workaround, the application may cause a configuration exception: "exePath must be specified when not running inside a stand alone exe". The workaround involves creating a web service to wrap the service application. NOTE: this workaround is not required for users of .NET Framework 4.

For example, consider a WCF service application OptimizationService that uses MSF with a contract Solve. Here is a code sample that illustrates this with a simple optimization problem:

[OperationContract]

public string Solve() {

SolverContext context = SolverContext.GetContext();

//decisions

Decision xs = new Decision(Domain.RealNonnegative, "Number_of_small_chess_boards");

Decision xl = new Decision(Domain.RealNonnegative, "Number_of_large_chess_boards");

model.AddDecisions(xs, xl);

//constraints

Constraint constraintBoxWood = model.AddConstraint("BoxWood", 1 * xs + 3 * xl <= 200);

Constraint constraintLathe = model.AddConstraint("Lathe", 3 * xs + 2 * xl <= 160);

//Goals

model.AddGoal("Profit", GoalKind.Maximize, 5 * xs + 20 * xl);

Solution sol = context.Solve();GetContext();

Model model = context.CreateModel();

Report report = sol.GetReport();

return sol.GetReport().ToString();

}

Now to use OptimizationService from any application, create a ASP.Net web service OptimizationWebService that defines a web method Solve. The web method Solve invokes the WCF service OptimizationService defined above.

[WebMethod]

public string Solve() {

//Direct call to service

OptimizationService service = new OptimizationService();

string value = service.Solve();

//or Call to a proxy client

//OptimizationServiceClient client = new OptimizationServiceClient();

//string value = client.Solve();

return value;

}

Now any client code can call the web service to access the WCF application service.