Solving optimization problems with Microsoft Solver Foundation

• Download sources (C# and Excel) - 45.1 KB

Introduction

How many times in your career have you had to solve optimization problems? I am pretty sure not a lot. More or less everyone’s heard something about it: queen’s problems, traveling salesman problems and so on, but in reality, I have never seen any salesman who asked for a software to optimize his traveling path. I believe this is the reason why Microsoft Solver Foundation - .NET library that’s designed for solving optimization problems is not that popular. I experienced a couple of cases when companies building software that required solving simple optimization problems went to 3rd parties for the development of those modules for one simple reason – they didn’t know anything about Microsoft Solver Foundation. If you Google it you will find pretty poor official documentation with samples and couple of nice articles that show you the basic usage, but not linked to real world problems. In this article, I want to show a very typical real-world optimization problem and solution that can be used in food industry.

Although optimization tasks are more mathematical than typical development, I proceed with the fact that the world of IT has changed over the past five years. More and more developers are trained on their own bypassing universities where optimization and higher mathematics are taught. I decided not to use any formulas to describe the optimization functions. Instead, I will use C# syntax. I also will not go deep into details to explain the algorithms that are used by Microsoft Solver Foundation. First of all, I am not a guru of those algorithms, and this is pretty boring. The big advantage of Solver Foundation is that you can focus on modeling and development and do not have to care how the algorithms work.

Basic terms

Although this is an article for developers from a developer, I have to explain some basic terms.

In application development optimization is increasing performance while maintaining the functionality of your application. Functionality is a constraint for the optimization, you cannot sacrifice basic functionality to speed it up. Technologies that are used in the application (they can decrease or increase performance, but impact functionality as well) are decisions, and maximizing of performance is our goal. Optimization in business or production has the same structure – you have to maximize of minimize some value that’s described by a function that used parameters that you have to find and that are limited by constraints. The combination of input parameters, constraints, decisions, and goals represent the model.

Constraints and goals are defined by functions. Constraint function has to return true or false; goal function has to return numeric value to optimize.

In the mathematical world, functions have different types. For our optimization task it is important to know if the function is linear or non linear, this affects the accuracy and speed of optimization as different algorithms are used.

Linear function is a function that can be drawn on a graph with a straight line. Mathematics definition for linear function is f(x) = ax+b where a and b are static values. In C# it looks like:

public int LinearFunction(int x)
{
    return 10 * x + 2;
}

A function can also accept multiple arguments and then it looks like this:

public int LinearFunction(int x, int y, int z)
{
    return 30 * x + 20 * y + 10 * z;
}

Not linear function, by definition, is a function that can’t be presented on a graph with a straight line. Examples:

public int CuadraticFunction(int x)
{
	return x*x;
}
public double NotLinearFunction(double x, double y, double z)
{
	return (30*x+20*y+10*z)/(x+y+z);
}

Microsoft Solver Foundation is .NET tool for modeling, optimization, and simulation that you can download from official Microsoft website. It has four editions:

1. Express – free for evaluation purposes. You can download it from product website
2. Standard – available for MSDN subscribers (I use this one)
3. Enterprise – you have to request a quotation for it from Microsoft (well, if you can tell me how much does it cost I will appreciate)
4. Academic – for MSDN Academic Alliance subscribers

Express and Standard versions have some limitations (for number of processor cores, number of parameters and so on), you can read more about this there.

The Microsoft Solver Foundation includes:

1. .NET library Microsoft.Solver.Foundation.dll that can be used with any CLR language for modeling, simulation, and optimization in code
2. Excel plug-in. After installing this plug-in, you will be able to build your model and solve problems directly in Excel with OML (Optimization Model Language).

In my experience, it is much faster to build and test your model in Excel and then code it with C# and VB.NET, because of easier manipulation with test data, so in examples below I will use both methods – C# and OML.

Before we start I will add a fly in the ointment – Solver Foundation is not a panacea. It is good enough for typical tasks that can be solved with standard algorithms. In case your model doesn’t match any of the algorithms used by Solver Foundation you can always try to solve with Local Search Algorithm – in fact (almost) random enumeration of possible values for decisions, but it is not accurate, it is pretty slow and I would not rely on it for critical processes.

Case

Company “Milk for Life” has a processing plant for raw milk. Farms are delivering raw cow milk to the plant where it is getting processed and sorted in a three storage tanks:

1. TK-001_Hight - For high-quality milk with high content of fat
2. TK-002_Regular - For regular milk
3. TK-001_Low - For low-fat milk

Every type of milk has different cost and the company is trying to sell cheaper milk as much as possible.

Also, the plant has two tanks with additives – Heavy cream and Skim. Every time when a new portion of milk is added to the storage tank, the laboratory analyzes three main parameters: density (kg\l), fat content (%), SNF – solid not fat (%).

The company itself doesn’t pack and sell the milk on retail market but makes blends for other companies into tank cars. Every customer creates an order for some quantity of milk with specific quality that are defined in maximum-minimum limits for each quality argument: Density, Fat, and SNF.

We assume that the company does not have production planning and starts order handling when the truck arrives at the plant.

The company has a manufacturing execution system (MES) that is integrated with:

1. Truck registration system. From this system, MES receives information about the new order – quantity of loadout and quality parameters
2. Laboratory. MES receives actual quality of product in every storage tank
3. Automation system. MES gets current quantity from level meters of storage tanks. MES has to send to automation system how much of each component from every tank has to be dosed for blending.

The cost of milk in each tank configured in MES system. The goal of MES system is to calculate the dosage of each component to meet requirements of product quality and ordered quantity by using as much as possible cheaper components.

When milk is dosed and mixed into truck tank quality parameters are calculating as a weighted average of attribute values based on loaded quantity from each tank.

var loadedFromTK1 = 200;
var loadedFromTK2 = 300;
var loadedFromTK3 = 100;

var attributeInTK1 = 0.5;
var attributeInTK2 = 0.7;
var attributeInTK3 = 1.2;

var attributeInBlend = (loadedFromTK1*attributeInTK1 + loadedFromTK2*attributeInTK2 +
                        loadedFromTK3*attributeInTK3)/(loadedFromTK1 + loadedFromTK2 + loadedFromTK3);

To build our model we have to define:

1. Input parameters
2. Decisions (output)
3. Constrains
4. Goals

Input parameters

Parameters and decisions in Solver Foundation can be:

1. Keyed value list
   .NET analogy is Dictionary<,> and, like in dictionary parameter key can be composite (like when you use a structure as dictionary key).
2. Indexed value list
   .NET analog is an array. You can access for value with index.
3. Single value
   Single variable value

A parameter value can be only simple type:

1. Integer
2. Nonnegative Integer
3. Integer Range
4. Real
5. Nonnegative Real
6. Real Range
7. Boolean

For parameters with a ranged type, you can specify static upper bound and lower bound.

For the keyed parameters you have to define unique structure – set. Set keeps a list of keys for your parameters that can be shared but only with parameters that have the same keys. For example, the quantity of product and cost of the component in the tank the key is the same – tank name, so set can be shared between those parameters.

First, we have to define our parameters:

1. Quantity for each tank (pQuantities)
2. Cost of liter of milk in each tank (pComponentCosts)
3. Quality attributes for each tank (pTankQualityAttributes)
4. Requested loadout quantity (pLoadoutQuantity)
5. Minimum value for each quality attribute in order (pOrderMaximumQualityAttributes)
6. Maximum value for each quality attribute in order (pOrderMinimumQualityAttributes)

So, let’s start with the simplest ones – quantity and cost for each tank. Let’s start in Excel and later we will move it to C# code. In Excel I have the following structure:

First of all, we create set in Solver Foundation and call it “sTankNames”.

The domain is the type of indexer. In our case, it is a string type, so we select “Any”. By the way – you can also use indexes in constraints and goals of your model (an example if you want to make a special calculation on even values).

Next step – define parameters “pQuantities” and “pComponentCosts”.

1. Create parameter and name it
2. Select data type – in our case “pQuantities” is an integer (level meters are not that accurate to measure quantity precisely than liter) and “pComponentCost” is nonnegative real.
3. Setup binding.

To setup binding for keyed parameter, you have to select the type of the indexer (set) and a column for the key values. Once finished you have to select a column for the parameter values.

For quality parameters we can do the same – create a parameter for each quality attribute: Density, Fat content, and SNF, but in this case if the company decides to add another quality attribute we need to rebuild our model. Instead of this we will create a parameter (pTankQualityAttributes) with a composite key – tank name and attribute name. In the Binding Editor for sets configuration for the first row we select “sTankNames” as set and “Tank Name” as the column name for binding, on the second row we select “sQualityAttributes” as set and “Attribute Name” as column.

In the same way we create set “sQualityAttributes” and Real Nonnegative parameters “pOrderMinimumQualityAttributes”, “pOrderMaximumQualityAttribute” for the requested bounds of quality attributes in order. If your sets are not consistent (e.g., you can select sTankNames set for pOrderMaximumQualityAttribute) the Binding Editor will allow you to do this, but you will get an error during model solving.

The loadout quantity represents a single value. In the Binding Editor for Table\Range selection, we select a single cell and do not associate it with any set.

Currently, our OML Model looks like this:

Model[
  Parameters[
    Sets[Any],
    sTankNames,
    sQualityAttributes
  ],
  Parameters[
    Reals[0, Infinity],
    pQuantities[sTankNames],
    pComponentCosts[sTankNames],
    pOrderMaximumQualityAttributes[sQualityAttributes],
    pOrderMinimumQualityAttributes[sQualityAttributes],
    pTankQualityAttributes[sTankNames, sQualityAttributes]
  ],
  Parameters[
    Integers[0, Infinity],
    pLoadoutQuantity
  ]
]

And now we do the same with C# code. To start with a model we have to create a project and add a reference for Microsoft.Solver.Foundation.dll assembly.

For the demo I will use following classes as input for the solver:

public static void SolveBlend(List<Tank&rt tanks, Order order)
{
    var context = SolverContext.GetContext(); // Initialize solver
    var model = context.CreateModel(); // Create model

    // Initialize sets
    var sTankNames = new Set(Domain.Any, "sTankNames");
    var sQualityAttributes = new Set(Domain.Any, "sQualityAttributes");

    // Initialize parameters
    var pQuantities = new Parameter(Domain.IntegerNonnegative,
        "pQuantities",
        sTankNames);
    var pComponentCosts = new Parameter(Domain.RealNonnegative, "pComponentCosts", sTankNames);
    var pTankQualityAttributes = new Parameter(Domain.RealNonnegative, "pTankQualityAttributes",
        sTankNames, sQualityAttributes);
    var pOrderMaximumQualityAttributes = new Parameter(Domain.RealNonnegative, "pOrderMaximumQualityAttributes",
        sQualityAttributes);
    var pOrderMinimumQualityAttributes = new Parameter(Domain.RealNonnegative, "pOrderMinimumQualityAttributes",
        sQualityAttributes);
    var pLoadoutQuantity = new Parameter(Domain.IntegerNonnegative, "pLoadoutQuantity");

    // Set bindings for parameters
    pQuantities.SetBinding(tanks,
        tank => tank.QuantityInTank,
        tank => tank.Name);
    pComponentCosts.SetBinding(tanks,
        tank => tank.ProductCost,
        tank => tank.Name);
    pTankQualityAttributes.SetBinding(tanks.SelectMany(tank => tank.QualityAttributes.Select(attribute => new
    {
        TankName = tank.Name,
        AttributeName = attribute.Name,
        attribute.Value
    })),
        attribute => attribute.Value,
        attribute => attribute.TankName,
        attribute => attribute.AttributeName);
    pOrderMaximumQualityAttributes.SetBinding(order.QualityAttributes,
        attribute => attribute.Maximum,
        attribute => attribute.Name);
    pOrderMinimumQualityAttributes.SetBinding(order.QualityAttributes,
        attribute => attribute.Minimum,
        attribute => attribute.Name);
    pLoadoutQuantity.SetBinding(order.LoadoutQuantity);

    // Add parameters into model
    model.AddParameter(pQuantities);
    model.AddParameter(pComponentCosts);
    model.AddParameter(pTankQualityAttributes);
    model.AddParameter(pOrderMaximumQualityAttributes);
    model.AddParameter(pOrderMinimumQualityAttributes);
    model.AddParameter(pLoadoutQuantity);
}

Decisions (output)

In our case we have to decide how much product we have to dose from each storage tank.

In Excel Solver Foundation plug-in the process of defining decisions is similar to parameters. We can reuse “sTankNames” set for decision “dQuantityToLoadout” and bind it to “Output” column. C# code for decision definition is following:

// Initialize decision
var dQuantityToLoadout = new Decision(Domain.RealNonnegative, "dQuantityToLoadout", sTankNames);

//Set binding: as you can see for decision biding is different from parameters.
//    You have to specify property name instead of lambda
dQuantityToLoadout.SetBinding(tanks, "LoadoutQuantity", "Name");

// Add decision into model
model.AddDecision(dQuantityToLoadout);

Constraints

When all our inputs and outputs have been set up, we should define constraints. Constraints and goals are described in functions, and you have to get used to the fact that functions in C#, Solver Foundation for .NET and OML have a different syntax. In Solver Foundation for .NET every operation is defined as a static method of Model class, OML has is own syntax, but for example, in OML you multiply two values by using “*” symbol, in .NET version you should do it with the Product method of the Model class. To make it easier for you I made the table with different operations and how they are done in C#, OML and Solver Foundation for .NET.

1. Sum of all dosed components should be the same as requested quantity from the order.

C# description for reference:

order.LoadoutQuantity == tanks.Sum(tank => tank.LoadoutQuantity)

Sum[
  {tankName, sTankNames},
  dQuantityToLoadout[tankName]
] == pLoadoutQuantity

model.AddConstraint("cLoadoutQuantity",
    Model.Equal(
        Model.Sum(
            Model.ForEach(sTankNames,
                tankName => dQuantityToLoadout[tankName]
            )
        ),
        pLoadoutQuantity
    )
);

2. We cannot dose more of a component than the quantity in the tank:

C# description for reference:

tanks.All(tank => tank.LoadoutQuantity <= tank.QuantityInTank)

Foreach
[
  {tankName, sTankNames},
  dQuantityToLoadout[tankName]
=pQuantities[tankName]
]

model.AddConstraint("cTankQuantity",
   Model.ForEach(sTankNames,
      tankName =>
         Model.LessEqual(
            dQuantityToLoadout[tankName],
             pQuantities[tankName]
       )
    )
)

3. Quality of the blend has to meet customer expectations

As defined in requirements, the value of quality attribute after blending weighted average of attribute values based on loaded quantity from each tank.

C# description for reference:

order.QualityAttributes.All(
    attribute =>
        (tanks.Sum(tank => tank.LoadoutQuantity*tank.QualityAttributes[attribute.Name].Value)/
         order.LoadoutQuantity) <= attribute.Maximum) &&
order.QualityAttributes.All(
    attribute =>
        (tanks.Sum(tank => tank.LoadoutQuantity * tank.QualityAttributes[attribute.Name].Value) /
         order.LoadoutQuantity) >= attribute.Minimum);

Foreach
[
  {qualityAttribute, sQualityAttributes},
  pOrderMinimumQualityAttributes[qualityAttribute]
=
  Sum
  [
    {tankName, sTankNames},
    dQuantityToLoadout[tankName] *
    pTankQualityAttributes[tankName, qualityAttribute]
  ] / pLoadoutQuantity
  <=pOrderMaximumQualityAttributes[qualityAttribute]
]

model.AddConstraint("cOrderQuality",
Model.ForEach(sQualityAttributes,
  qualityAttribute =>
    Model.LessEqual(
      pOrderMinimumQualityAttributes[qualityAttribute],
        Model.Quotient(
          Model.Sum(
            Model.ForEach(sTankNames,
              tankName =>
                Model.Product(dQuantityToLoadout[tankName],
                pTankQualityAttributes[tankName, qualityAttribute])
              )
            ),
          pLoadoutQuantity
        ),
      pOrderMaximumQualityAttributes[qualityAttribute]
    )
  )
);

Goal

Our goal is to minimize total cost of components that are used for blending.

tanks.Sum(tank => tank.LoadoutQuantity*tank.CostOfProduct + 20)

To be more realistic I added 20$ for each component dosing, as normally production is also trying to minimize the number of used equipment, first of all, because in food production every pipe has to be cleaned before next use, which takes time and money.

Sum
[
 {tankName, sTankNames},
 dQuantityToLoadout[tankName]
* pProductCosts[tankName] + 20
]

model.AddGoal("gMinimizeTotalCost", GoalKind.Minimize,
  Model.Sum(
    Model.ForEach(sTankNames,
      tankName=>Model.Sum(
        Model.Product(
          dQuantityToLoadout[tankName],
          pProductCosts[tankName]
        ),
        20
      )
    )
  )
);

Run the solver

Now if we run our solver and check data that we specified in a binding for the decision we will see out result – the quantity of the components that we have to take from each storage tank to make our perfect blend.

When we check the report of solving we can find some useful information about how solving was done:

===Solver Foundation Service Report===
Date: 4/10/2017 7:12:34 PM
Version: Microsoft Solver Foundation 3.0.2.10889 Standard Edition
Model Name: DefaultModel
Capabilities Applied: LP
Solve Time (ms): 0
Total Time (ms): 0
Solve Completion Status: Optimal
Solver Selected: Microsoft.SolverFoundation.Solvers.SimplexSolver
Algorithm: Primal
Arithmetic: Hybrid
Variables: 5 -> 5 + 5
Rows: 10 -> 5
Nonzeros: 30
Eliminated Slack Variables: 0
Pricing (exact): SteepestEdge
Pricing (double): SteepestEdge
Basis: Slack
Pivot Count: 10
Phase 1 Pivots: 7 + 0
Phase 2 Pivots: 3 + 0
Factorings: 5 + 1
Degenerate Pivots: 0 (0.00 %)
Branches: 0
===Solution Details===
Goals:
gMinimizeTotalCost: 2018.68902439024

As we can see in this report, the model that we made can be solved with linear programming (LP) and Solver Foundation solved it with simplex method which is basic algorithm for solving these kinds of models. In our case Solver Foundation selected this method automatically, but we can also specify preferred method by using directives. As an example, we can configure Solver Foundation to use the interior point method that is also capable of solving our model, but most probably the result will be less accurate then when you let solver decide.

Not linear model

Our previous model is good until we have enough of product in our storage tanks to loadout. Let’s imagine that the new truck came to the plant with an order for a quantity of 3000 liters. If we try to solve it our solution result will be “Infeasible” – Solver Foundation cannot solve our model with given inputs.

Different companies have their rules for these situations, but in most of the cases, they just try to deliver as much as possible. But how they can know the quantity that they can deliver? Is it 2000 liters? 2500? 2800? Well, we can help to decide.

Let’s take our first model as a base and modify it to the new requirements. First of all requested loadout quantity is not equal to the sum of components, but less or equal now.

Sum[
  {tankName, sTankNames},
  dQuantityToLoadout[tankName]
] <= pLoadoutQuantity

model.AddConstraint("cLoadoutQuantity",
    Model.LessEqual(
        Model.Sum(
            Model.ForEach(sTankNames,
                tankName => dQuantityToLoadout[tankName]
                )
            ),
        pLoadoutQuantity
        )
    );

The next change is calculation of the quality parameter after blending. In our original problem we knew exact quantity for loadout and we could do calculation of weighted average based on static value:

tanks.Sum(tank =>
    tank.LoadoutQuantity*tank.QualityAttributes[attributeName].Value)/order.LoadoutQuantity 

Now the loadout quantity is sum of components that limited on the maximum value, but it depends on decision values:

tanks.Sum(tank => tank.LoadoutQuantity*tank.QualityAttributes[attributeName].Value)/tanks.Sum(tank =>
    tank.LoadoutQuantity) 

Foreach
[
 {qualityAttribute, sQualityAttributes},
 pOrderMinimumQualityAttributes[qualityAttribute]
=
 Sum
 [
  {tankName, sTankNames},
  dQuantityToLoadout[tankName] *
  pTankQualityAttributes[tankName, qualityAttribute]
 ] /
 Sum
 [
  {tankName, sTankNames},
  dQuantityToLoadout[tankName]
 ]
 <=pOrderMaximumQualityAttributes[qualityAttribute]
]

model.AddConstraint("cOrderQuality",
Model.ForEach(sQualityAttributes,
  qualityAttribute =>
    Model.LessEqual(
      pOrderMinimumQualityAttributes[qualityAttribute],
        Model.Quotient(
          Model.Sum(
            Model.ForEach(sTankNames,
              tankName =>
                Model.Product(dQuantityToLoadout[tankName],
                pTankQualityAttributes[tankName, qualityAttribute])
              )
            ),
          Model.Sum(
            Model.ForEach(sTankNames,
              tankName =>
                dQuantityToLoadout[tankName]
              )
            )
        ),
      pOrderMaximumQualityAttributes[qualityAttribute]
    )
  )
);

We also have to change our goal – now we want to maximize loadout quantity instead of minimizing cost.

Sum
[
 {tankName, sTankNames},
 dQuantityToLoadout[tankName]
]

model.AddGoal("gMaximizeLoadoutQuantity", GoalKind.Maximize,  Model.Sum(
    Model.ForEach(sTankNames,
        tankName =>
            dQuantityToLoadout[tankName]
        )
    ));

And that is it. We run our solver and get dosing quantity for each tank to loadout as much as possible of product to the customer.

===Solver Foundation Service Report===
Date: 4/11/2017 4:29:17 PM
Version: Microsoft Solver Foundation 3.0.2.10889 Standard Edition
Model Name: DefaultModel
Capabilities Applied: NLP
Solve Time (ms): 4936
Total Time (ms): 4939
Solve Completion Status: LocalOptimal
Solver Selected: Microsoft.SolverFoundation.Solvers.HybridLocalSearchSolver
Step count: 1330568.
Violation: 0
===Solution Details===
Goals:
gMaximizeLoadourQuantity: 2398.59558418811

Now the business is happy and can make loadout. Well, not really.

The function in the constraint that we used for calculating of the blending quality is not linear anymore. In fact, we divide in this function two unknown values, and this function cannot be displayed as a straight line on the graph. In this case, the simple method that we used to minimize cost is not applicable and solver selected generic hybrid local search algorithm. I didn’t find any information on how Microsoft implemented it, but I guess it is one of the generic algorithms that’s widely used in machine learning. And because this algorithm is based on iterations of tries and faults it is not very accurate and not very fast. This method is very generic and can solve any model, you can also try to add in this model a goal to minimize cost as well, Solver Foundation allows you to have multiple goals in the model, but the result of this will be far different with what you can see if you execute the model with simple method. My advice is not to count on the result of solving the problem with hybrid local search method in critical processes. For our case it is fine if maximum loadout quantity will be +\- 100 liters, but even then to calculate the real doings for the blend we have to take the maximum quantity and just pass it into our first model to get the best component dosing. With the assumption that in most cases plant has enough product to loadout, I would do the following logic in an application:

Conclusions

Beside the case that I show in this article there are many more scenarios where optimization can be applied. Microsoft Solver Foundation is also not limited with linear and not linear programming, there are much more interesting things that you might do with it. I hope this article was interesting to my colleagues from the manufacturing sphere and others who are looking to implement optimization tasks in their businesses.