One of soon-to-starts projects uses linear programming for some optimizations. As it is not very familiar topic to me I started looking for examples and tools so I am prepared better when action starts. In this posting I will show you how to solve simple linear programming tasks using Microsoft Solver Foundation – free math package available by DevLabs.

Linear programming is used in many real-life calculations: business, economy, transportation, energy, telecommunications, manufacturing etc. The goal is holy: to make optimal decisions and save resources like money, time and materials.

Prerequisites

• Some version of Visual Studio
• Microsoft Solver Foundation
• Microsoft Solver Foundation documentation
• Big cup of coffee

What is linear programming?

Linear programming is specific case of mathematical programming or optimization. There is linear function we want to maximize or minimize, there are some constraints and non-negative variables. Practically this is how it goes:

1. We have function to be maximized: 
   
   f(x,y) = c₁x₁ + c₂x₂. 
2. We have constraints like: 
    
   a₁x₁ + b₁x₂ <= d₁, 
   a₂x₂ + b₂x₂ <= d_2. 
3. Non-negative variables: 
    
   x₁ >= 0, 
   x₂ >= 0.

Based on this information we will find the maximum value. We can do it graphically but we can also calculate the value. On graph above the grey area is called feasible region. Somewhere on the lines that draw this area are points where maximum values are located.

Example exercises

I found some good linear programming exercises from Brunel University home page.

1. A company makes two products (X and Y) using two machines (A and B). Each unit of X that is produced requires 50 minutes processing time on machine A and 30 minutes processing time on machine B. Each unit of Y that is produced requires 24 minutes processing time on machine A and 33 minutes processing time on machine B. 
   
   At the start of the current week there are 30 units of X and 90 units of Y in stock. Available processing time on machine A is forecast to be 40 hours and on machine B is forecast to be 35 hours. 
   
   The demand for X in the current week is forecast to be 75 units and for Y is forecast to be 95 units. Company policy is to maximize the combined sum of the units of X and the units of Y in stock at the end of the week. 
   
   Formulate the problem of deciding how much of each product to make in the current week as a linear program. Solve this linear program graphically. 
2. A carpenter makes tables and chairs. Each table can be sold for a profit of £30 and each chair for a profit of £10. The carpenter can afford to spend up to 40 hours per week working and takes six hours to make a table and three hours to make a chair. Customer demand requires that he makes at least three times as many chairs as tables. Tables take up four times as much storage space as chairs and there is room for at most four tables each week. 
   
   Formulate this problem as a linear programming problem and solve it graphically.

You can find more exercises like this when searching from web.

Using Microsoft Solver Foundation

Now let’s solve one exercise using Microsoft Solver Foundation. The API it is offering is not very familiar to developers who build usual web applications and it takes some math to understand how and why it is built this way. But still it is not something complex, it’s just a little bit different.

Exercise from Vitutor. A store has requested a manufacturer to produce pants and sports jackets.

For materials, the manufacturer has 750 m2 of cotton textile and 1,000 m2 of polyester. Every pair of pants (1 unit) needs 1 m2 of cotton and 2 m2 of polyester. Every jacket needs 1.5 m2 of cotton and 1 m2 of polyester.

The price of the pants is fixed at $50 and the jacket, $40.

What is the number of pants and jackets that the manufacturer must give to the stores so that these items obtain a maximum sale?

First we have to find out what is the function to maximize and what are the constraints. It’s like described above.

Let’s suppose x = number of pants and y = number of jackets.

1. Function to maximize: 
   
   f(x, y) = 50x + 40y 
2. Constraints (check out Vitutor page for good explanations): 
   
   2x + 3y <= 1500, 
   2x + y <= 1000 
3. Non-negative variables: 
   
   x >= 0, 
   y >= 0.

Now we have all information in place based on what we know and it’s time to write some code.

We create Windows console application and create reference to Microsoft.SolverFoundation.Services assembly that is located in the following place on your hard disk:

c:\Program Files (x86)\Reference Assemblies\Microsoft\Framework\.NETFramework\v4.0\Microsoft.Solver.Foundation.dll

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

namespace LinearProgrammingSFS 
{
     class Program
    {
         static void Main(string[] args)
         {
             // Create solver context and model
            SolverContext context = SolverContext.GetContext();
             Model model = context.CreateModel();

             // Create decision for objective function
            Decision x = new Decision(Domain.RealNonnegative, "pants");
             Decision y = new Decision(Domain.RealNonnegative, "jackets");
             model.AddDecisions(x, y);

 
             // Add constraints
             model.AddConstraints("production",
               2 * x + 3 * y <= 1500,
               2 * x + y <= 1000);

             // Add non-negative variables
            model.AddConstraints("nonnegative",
               x >= 0,
               y >= 0);

             // Add goal - what we want to maximize
            model.AddGoal("cost", GoalKind.Maximize,
               50 * x + 40 * y);


             Solution solution = context.Solve(new SimplexDirective());
             Report report = solution.GetReport();
             Console.WriteLine("result: " + solution.Goals.First().ToDouble());
             Console.WriteLine("x: {0}, y: {1}", x.ToDouble(), y.ToDouble());
             Console.Write("{0}", report);
             Console.ReadLine();
         }
     } }

If we run this program we will get the following output:

The first two lines in output give us solution: manufacturer has to make 375 pants and 250 jackets to earn $28.750 that is maximally possible. All the other output is Solver Foundation report about calculation made.

Conclusion

Microsoft Solver Foundation is set of math tools that allows you to solve some mathematical problems you face in real-world applications. Although the API it provides is not very similar to what many of us have seen before it is still simple enough to get started with it when math side is clear. In this posting we solved simple linear programming task. When we got preparation work done we wrote some simple lines of code to get answers we were looking for. Microsoft Solver Foundation is wider platform for different calculations and before writing math manually I suggest you to take a look at what Solver Foundation has to offer.