Microsoft Solver is an awesome tool that can help you solve constraint satisfaction problems, also known as “CSP”. CSP are mathematical problems defined as a set of objects whose state must satisfy a number of constraints. The concept is really simple: put in a box the following ingredients:
- A set of one or more constraints (your limitations)
- A set of one or more decisions to take (your questions)
- A goal to reach (or your ideal solution)
With these 3 elements, the solver will tell you what are the best decisions to take in order to meet your constraints and reach your goal. Doesn’t sound clear enough? Let’s take a few examples.
One of the famous examples is the map coloring problem. Let’s say you want to color the map of Australia. Each state should have a different color from its neighboring states color. In case of Australia, that would mean that New South Wales color should be different from Queensland, South Australia should be different than Northern Territory, etc. you get the idea.
To solve such a problem, you could define constraints (set of possible colors to use), decisions (what color should I use for a given state?) and a set of goals (QLD color should be different from NSW, etc.). You can then run the solver which will try to figure out the best solution possible.
The result might be a working solution or an unfeasibility (if you have only 2 possible colors for instance, the goals can’t be met).
That is what a solver can do for you.
Another typical use case is schedule management. Let’s say you have to prepare a schedule for a school with X rooms, Y teachers, Z classes. Setting up a time table for teachers, students and room reservation can soon reveal to be a nightmare to solve, let alone optimization. In that case, a solver might be a good choice over implementing the logic yourself. Same kind of approach can be applied to seat booking, production management, logistics, etc.
Implementation in C#: The trading company example
You just started your trading company, you import and export containers by boat. Each container has a limit weight of 1,000 Kilograms (1 ton) and as a small company which just started, you can’t afford to buy more than $5,000 of merchandise per container. Your company identified 3 products which looks interesting to import:
Cost (USD) | Sell price (USD) | Weight (Kg) | |
Chair | 20 | 60 | 4 |
Table | 150 | 250 | 8 |
Cupboard | 260 | 400 | 10 |
The obvious question that comes to your mind now is the following: What is the optimal product mix for your container to take the best profit while matching your two constraints, which are a $5,000 budget for your purchases and a limit of 1,000 Kilograms for your container. Let’s write a C# app for that!
Enters Microsoft Solver Foundation
First of all, download MS Solver Foundation here and create a new Visual Studio project (.Net 4.5). For the sake of simplicity, we will make a Console application, we just need to solve our problem, no need for a beautiful user interface here. Once the project is created, you can now add a reference to your newly downloaded DLL (Microsoft.Solver.Foundation.dll).
Step #1: What are the decisions to take?
Our first task is to define what we want to optimize, if you remember the beginning of this article, this is what we called “Decisions” to take. In our case, we have 3 decisions to take, how many chairs, tables and cupboard should we buy.
To enable the solver do its job, we need to give him a domain of possible values. For each decision, we can only have a positive integer (we can’t buy half of a table). This translates to the following code:
var solver = SolverContext.GetContext(); var model = solver.CreateModel(); var decisionChair = new Decision(Domain.IntegerNonnegative, "Chair"); var decisionTable = new Decision(Domain.IntegerNonnegative, "Table"); var decisionCupboard = new Decision(Domain.IntegerNonnegative, "Cupboard"); model.AddDecision(decisionChair); model.AddDecision(decisionTable); model.AddDecision(decisionCupboard);
Step #2: What are the constraints?
Next, we will define and add our constraints to our solver. We have two constraints, a budget constraint and a weight constraint. The following code is pretty simple and straightforward.
// Our costs var chairCost = 20; var tableCost = 150; var cupboardCost = 260; // Our sell prices var chairSellprice = 60; var tableSellprice = 250; var cupboardSellprice = 400; // We have a budget of $5000 var maxBudget = 5000; // We define the expression of our cost and add the constraint that our costs shouldn't exceed our budget model.AddConstraint("Budget", chairCost * decisionChair + tableCost * decisionTable + cupboardCost * decisionCupboard <= maxBudget); var chairWeight = 4; var tableWeight = 8; var cupboardWeight = 10; // We have a capacity var maxWeight = 500;
// We define the expression of our weight and add the constraint that our weight shouldn’t exceed the allowed weight
model.AddConstraint(“Weight”, chairWeight * decisionChair + tableWeight * decisionTable + cupboardWeight * decisionCupboard <= maxWeight);
Step #3: What is our goal?
Finally, we need to tell the solver what we want to do here. Clearly, we are trying to optimize our profit for a single container given our constraints. We need to define what the (simple) formula for our profit is and tell the solver that we want to maximize it. This translates with the following code.
// Add a goal (we have only one here, but we can imagine a set of different goals) model.AddGoal("BestProfit", GoalKind.Maximize, (chairSellprice - chairCost) * decisionChair + (tableSellprice - tableCost) * decisionTable + (cupboardSellprice - cupboardCost) * decisionCupboard);
Final step: Make the magic happen to get our answer!
We can now finally call the Solve() method which will try to solve our problem (i.e. Figure out the best decisions to take) given our constraints and goal.
This can lead to an “unfeasibility” in case you gave a problem that is impossible to solve. It could lead to a “feasible” output, meaning your problem is solved but probably not optimal. Eventually, it can lead to an “optimal” output which means that the best solution is mathematically guaranteed. This quality level can be accessed via the solution.Quality parameter. Here’s the code:
// Solve our problem var solution = solver.Solve(); // Get our decisions double nbOptimalChairs = decisionChair.GetDouble(); double nbOptimalTables = decisionTable.GetDouble(); double nbOptimalCupboards = decisionCupboard.GetDouble(); Console.WriteLine("Solution found with a quality considered : " + solution.Quality.ToString()); Console.WriteLine("You should purchase {0} chairs", nbOptimalChairs); Console.WriteLine("You should purchase {0} tables", nbOptimalTables); Console.WriteLine("You should purchase {0} cupboards", nbOptimalCupboards); double weightUsed = nbOptimalChairs * chairWeight + nbOptimalTables * tableWeight + nbOptimalCupboards * cupboardWeight; double budgetRequired = nbOptimalChairs * chairCost + nbOptimalTables * tableCost + nbOptimalCupboards * cupboardCost; Console.WriteLine("Weight used : {0} kg", weightUsed); Console.WriteLine("Budget required : $" + budgetRequired); Console.ReadLine();
Finally, this code give us the following output :
We can see that the problem was solved with an optimal quality, with 94 chairs, 3 tables and 10 cupboards. We used the 500kg available per container and our budget constraint is met too.