Mathias Brandewinder on .NET, F#, VSTO and Excel development, and quantitative analysis / machine learning.
by Mathias 16. July 2011 00:43

While most of my posts tend to focus on software development, my background is in optimization. Unfortunately, I don’t get to use these two skillsets together too often, because most projects require fairly basic modeling, and because the tools they require do not always integrate well together.

Luckily, the project I am currently working on involved performing some optimization, from within a .NET application,  which gave me an opportunity to investigate the Microsoft Solver Foundation, which comes with a free solver and provides a framework for leveraging existing commercial solvers.

What is a solver? In a nutshell, it is an algorithm designed to identify optimal input values to maximize a function, while satisfying constraints. Certain classes of problems can be solved very efficiently using known algorithms, while others require the use of heuristics – but in general, if you find yourself asking “what is the best combination of values for this situation”, chances are, a solver is the tool you should be using.

Rather than go into theory, let’s look at an illustration, which will hopefully give you a sense for what the Microsoft Solver Foundation can do for you, and how you can leverage it in your .NET applications.

The problem: cheap imports from Gadgetistan

Old-TruckImagine the following situation. You are an enterprising individual, and realize that there is good money to be made by importing goods from the Republic of Gadgetistan, the neighboring country. You break the piggybank, invest in an old truck, drive over there and get ready to buy a truckload of the local specialties, Widgets, Sprockets and Gizmos.


The truck didn’t come cheap, so you have only 200 Rublars (the official currenty of Gadgetistan) left in your wallet – this is your Budget Constraint.

The truck user manual is very clear – the Capacity of your truck is 500 Kilograms. One pound more, and your wonderful truck could collapse in a sad heap of scrap metal. This is your Capacity Constraint.

A bit of market research yielded the following information about the main product: the buying Cost, the reselling Price, and the Weight for a unit of each of the main goods from Gadgetistan.

  Cost (Rublars) Price (Rublars) Weight (Kgs)
Widget 10 30 50
Sprocket 15 30 20
Gizmo 25 60 80

Your problem at that point is simple: how many units of each product should you carry in your truck, to make the most of your trip?

Finding a solution with the Microsoft Solver Foundation

We will solve the problem with a simple Console application. First, let’s create a Console project, SolverLab, targeting the .NET 4.0 framework, and setting the target to the full .NET 4.0 profile (and not the client profile).

FullProfile

Next, go to the Microsoft Solver Foundation page, download the Solver Foundation v3.0 – DLL only, add the corresponding dll to the project, and add a reference to the project:

ProjectWithReferences

We are now set to write our optimization program.

Our first step is to define what input variables the Solver is trying to optimize; in optimization speak, this is called “Decision Variables”. In our example, we have 3 decisions: the quantity or Widgets, Sprockets and Gizmos – which we’ll rename here to A, B and C, for the sake of conciseness.

This is how this looks in code (which will require adding using Microsoft.SolverFoundation.Services; in the code file):

static void Main(string[] args)
{
   var solver = SolverContext.GetContext();
   var model = solver.CreateModel();

   var decisionA = new Decision(Domain.IntegerNonnegative, "QuantA");
   var decisionB = new Decision(Domain.IntegerNonnegative, "QuantB");
   var decisionC = new Decision(Domain.IntegerNonnegative, "QuantC");

   model.AddDecision(decisionA);
   model.AddDecision(decisionB);
   model.AddDecision(decisionC);

We instantiate a solver, create a model, and declare 3 decision variables, which we add to the model. Note that for each decision, we define a Domain: the domain specifies the “range” that is valid for the parameter. In our case, we want the answer to be a positive integer (we cannot buy half-sprockets). There are other alternatives, such as Real Numbers or Booleans, Nonnegative or unconstrained.

Next, we need to define what we are trying to optimize – the Goal, also often called the Objective function. Here we want to maximize our profit, that is, for each product, units x (price – cost), which we express in code as:

var costA = 10d;
var costB = 15d;
var costC = 25d;

var priceA = 30d;
var priceB = 30d;
var priceC = 60d;

model.AddGoal("Goal", GoalKind.Maximize, 
   (priceA - costA) * decisionA + 
   (priceB - costB) * decisionB + 
   (priceC - costC) * decisionC);

We create variables for the cost and price of each product, and simply add a Goal to the model, specifying what we are trying to do (Maximize), and directly type in the expression for our goal. In general, the Solver works with Terms (more on this in our next post), but it also accepts strings which will be parsed as OML  expressions. I found it to be very flexible in accepting human-readable, free-form strings, and making sense of them.

Finally, we need to add the two Constraints to the program, following a similar pattern to the Goal definition:

var budget = 200d;
model.AddConstraint("Budget", 
   costA * decisionA + 
   costB * decisionB + 
   costC * decisionC <= budget);

var weightA = 50d;
var weightB = 20d;
var weightC = 80d;
var capacity = 500d;
model.AddConstraint("Weight", 
   weightA * decisionA + 
   weightB * decisionB + 
   weightC * decisionC <= capacity);

And we are set – we can now let the solver work its magic, and search for 3 quantities which will give us the best profit, while being under budget and keeping our truck intact:

var solution = solver.Solve();

Console.WriteLine("A " + decisionA.GetDouble());
Console.WriteLine("B " + decisionB.GetDouble());
Console.WriteLine("C " + decisionC.GetDouble());

Console.ReadLine();

Calling solver.Solve() will resolve the current model, and set the Decisions to their optimal value (if such a value is found) – and when we run the program, the following solution shows up: 5 Widgets, 8 Sprockets and 1 Gizmo.

Solution

We can check that the constraints are satisfied:

Capacity: 5 x 50 + 8 x 20 + 1 x 80 = 490 <= 500

Budget: 5 x 10 + 8 x 15 + 1 x 25 = 195 <= 200

The Profit of our solution comes out to be 5 x (30 – 10) + 8 x (30 – 15) + 1 x (60 - 25) = 255. It’s certainly a nice margin – but how do we know we can’t do better?

In this situation, we could brute-force every possible combination, and check whether there is anything better. That would work out because it’s a small problem, but clearly wouldn’t be convenient with a larger problem. Fortunately, the Solution returned by the solver has a property, Quality, which provides some information about what to expect from the solution, as an enum: Optimal, Feasible, Unfeasible, Unknown, Unbounded…

var solution = solver.Solve();        
Console.WriteLine(solution.Quality);

In this case, the solution happens to be Optimal, which means that it is guaranteed to be the best possible. Possibly, other solutions could be just as good, but no solution can be better. How the solver knows that would go beyond the scope of that post (the problem happens to fit a certain structure, for which a perfect solution can be derived); suffice it to say that if the solution has been found, it can be simply feasible – meaning that it is a solution, but cannot be guaranteed to be the best – or optimal, meaning that it is guaranteed to be the best possible.

That’s it for today! Hopefully, this brief introduction will have given you a taste of what a solver can do for you. Next time, we’ll dig deeper into how to achieve stronger integration with your .NET code, by creating optimization models dynamically, and solving problems that follow the same template for any arbitrary inputs.

Comments

7/16/2011 12:53:53 AM #

trackback

First steps with the Microsoft Solver Foundation

You've been kicked (a good thing) - Trackback from DotNetKicks.com

DotNetKicks.com | Reply

7/24/2011 11:17:28 AM #

trackback

Create optimization programs dynamically with C# and the Microsoft Solver Foundation

Create optimization programs dynamically with C# and the Microsoft Solver Foundation

Clear Lines Blog | Reply

8/8/2011 8:17:48 AM #

pingback

Pingback from blog.cwa.me.uk

The Morning Brew - Chris Alcock  » Afternoon Tea - Monday 8th August

blog.cwa.me.uk | Reply

7/5/2012 11:23:03 AM #

pingback

Pingback from starfootballlive.newpatriotmedia.com

Usain Bolt withdraws from Monaco meet | Star Football Live

starfootballlive.newpatriotmedia.com | Reply

8/18/2012 9:53:59 PM #

pingback

Pingback from arlvin.wordpress.com

Building An Optimization Application – Quotation Processing Part 1 « Arlvin's Blog

arlvin.wordpress.com | Reply

12/9/2012 2:25:35 AM #

Dalibor

Hello Mathias,

I hope this message will reach you and that you will have a minute to answer my question. I am trying to use MS Solver for a scheduling problem. For now, I am trying to learn how to write constraints correctly. For example, I would like the solution's domain to be a range between 0 and 86400 (integer). I just want it to return me the highest value in the range, such that it is uneven one. So, I tried:

Decision sec = new Decision(Domain.IntegerNonnegative, "seconds");
model.AddDecision(sec);
model.AddConstraints("limits", 0 <= sec <= 86400);
model.AddConstraints("uneven", sec % 2 == 1);

But the last line cannot compile because there is no modulo operator defined ("Error  1  Operator '%' cannot be applied to operands of type 'Microsoft.SolverFoundation.Services.Decision' and 'int'). There is a Mod operator defined for the OML, and an OML expression can be passed to the AddConstraint method, but I don't know how to format the oml-string correctly. How could I define this correctly?

Thanks and regards from Switzerlan,
Dalibor

Dalibor Switzerland | Reply

12/9/2012 1:04:52 PM #

Mathias

Hi Dalibor,
That's an interesting question - and unfortunately, I don't have an answer. Looking briefly at the Terms and TermModelOperation classes, (msdn.microsoft.com/.../...vices.term(v=vs.93).aspx and msdn.microsoft.com/.../...peration(v=vs.93).aspx), I didn't see Modulo listed, which is odd - as you pointed out, you would expect it to be supported, if it's supported from the OML side of things. I assume this question on StackOverflow is yours? stackoverflow.com/.../microsoft-solver-foundation-modulo-operator , if not you probably want to follow it. You might want to try the Solver forum (social.msdn.microsoft.com/.../threads), or even reach out to Nathan Brixius, who used to be on the Solver team and might be able to shed some light.
Sorry I couldn't be directly helpful - and best of luck!
Mathias

Mathias | Reply

7/24/2013 7:58:33 AM #

Adam

Hello Mathias,

I'm a management science student at UTSA and was hoping you can help me with this simple example. I'm trying to retrieve the objective coefficient ranges, but I'm getting incorrect values.

=======================================================================================
           var solver = SolverContext.GetContext();
            var model = solver.CreateModel();

            var Sweater_F = new Decision(Domain.RealNonnegative, "Sweater_F");
            var Sweater_FB = new Decision(Domain.RealNonnegative, "Sweater_FB");
            var Tshirt_F = new Decision(Domain.RealNonnegative, "Tshirt_F");
            var Tshirt_FB = new Decision(Domain.RealNonnegative, "Tshirt_FB");

            model.AddDecision(Sweater_F);
            model.AddDecision(Sweater_FB);
            model.AddDecision(Tshirt_F);
            model.AddDecision(Tshirt_FB);

            model.AddGoal("Goal", GoalKind.Maximize,
                          Sweater_F * 90
                          + Sweater_FB * 125
                          + Tshirt_F * 45
                          + Tshirt_FB * 65);

            model.AddConstraint("Processing_Time",
                                Sweater_F*0.1
                                + Sweater_FB*0.25
                                + Tshirt_F*0.08
                                + Tshirt_FB*0.21 <= 72);

            model.AddConstraint("Budget",
                                Sweater_F*36
                                + Sweater_FB*48
                                + Tshirt_F*25
                                + Tshirt_FB*35 <= 25000);

            model.AddConstraint("Truck_Capacitiy",
                                Sweater_F*3
                                + Sweater_FB*3
                                + Tshirt_F*1
                                + Tshirt_FB*1 <= 1200);

            model.AddConstraint("Blank_Sweaters",
                                Sweater_F*1
                                + Sweater_FB*1
                                + Tshirt_F*0
                                + Tshirt_FB*0 <= 500);

            model.AddConstraint("Blank_Tshirts",
                                Sweater_F*0
                                + Sweater_FB*0
                                + Tshirt_F*1
                                + Tshirt_FB*1 <= 500);

            Solution solution = solver.Solve(new SimplexDirective { GetSensitivity = true, GetInfeasibility = true });

            LinearReport report = ((LinearReport)solution.GetReport());

            //sweater_F GoalCoefficientSensitivity
            Console.WriteLine(Sweater_F.Name + ": " + + Sweater_F.GetDouble());
            Console.WriteLine("Current: " + report.GetGoalCoefficientSensitivity(Sweater_F, new object[0]).Value.Current);
            Console.WriteLine("Upper Bound: " + report.GetGoalCoefficientSensitivity(Sweater_F, new object[0]).Value.Upper.ToDouble());
            Console.WriteLine("Lower Bound: " + report.GetGoalCoefficientSensitivity(Sweater_F, new object[0]).Value.Lower.ToDouble());
            Console.WriteLine("");

            //sweater_FB GoalCoefficientSensitivity
            Console.WriteLine(Sweater_FB.Name + ": " + Sweater_FB.GetDouble());
            Console.WriteLine("Current: " + report.GetGoalCoefficientSensitivity(Sweater_FB, new object[0]).Value.Current);
            Console.WriteLine("Upper Bound: " + report.GetGoalCoefficientSensitivity(Sweater_FB, new object[0]).Value.Upper.ToDouble());
            Console.WriteLine("Lower Bound: " + report.GetGoalCoefficientSensitivity(Sweater_FB, new object[0]).Value.Lower.ToDouble());
            Console.WriteLine("");


            //tShirt_F GoalCoefficientSensitivity
            Console.WriteLine(Tshirt_F.Name + ": " +Tshirt_F.GetDouble());
            Console.WriteLine("Current: " + report.GetGoalCoefficientSensitivity(Tshirt_F, new object[0]).Value.Current);
            Console.WriteLine("Upper Bound: " + report.GetGoalCoefficientSensitivity(Tshirt_F, new object[0]).Value.Upper.ToDouble());
            Console.WriteLine("Lower Bound: " + report.GetGoalCoefficientSensitivity(Tshirt_F, new object[0]).Value.Lower.ToDouble());
            Console.WriteLine("");

            //tShirt_FB GoalCoefficientSensitivity
            Console.WriteLine(Tshirt_FB.Name + ": " + Tshirt_FB.GetDouble());
            Console.WriteLine("Current: " + report.GetGoalCoefficientSensitivity(Tshirt_FB, new object[0]).Value.Current);
            Console.WriteLine("Upper Bound: " + report.GetGoalCoefficientSensitivity(Tshirt_FB, new object[0]).Value.Upper.ToDouble());
            Console.WriteLine("Lower Bound: " + report.GetGoalCoefficientSensitivity(Tshirt_FB, new object[0]).Value.Lower.ToDouble());
            Console.WriteLine("");
            Console.ReadLine();
=================================================================================

Sweater_F: upper bound should be 101.9230769 but it returns 130
                       lower bound should be 50 but it returns -95
Sweater_FB: upper bound should be 138.2142857 but it returns 160
                          lower bound should be 113.0769231 but it returns 25
Tshirt_F: upper bound should be 1E+30 but it returns 55.333333
                   lower bound should be 40.88888889 but it returns 45
Tshirt_FB: upper bound should be 75.33333333 but it returns infinity
                     lower bound should be -1E+30 but it returns 54.66666

Adam United States | Reply

Add comment




  Country flag

biuquote
  • Comment
  • Preview
Loading



Comments

Comment RSS