by Peter Villadsen
November 2013
In an area known as Operational Research (O.R.), there are many problems and solutions that are applicable to enterprise resource planning (ERP). O.R. began at the end of World War II. Initially it was used to solve logistical problems, and it has expanded to address a broad spectrum of problems. One area of progress for O.R. concerns problems that involve so many possible combinations as potential answers that they cannot be solved by brute force calculation.
This essay helps you to:
- Recognize the types of problems that O.R. can solve; and
- Understand the C# code that you can write to leverage O.R.
The basic installation of Microsoft Dynamics AX 2012 includes a .NET managed library that is extremely well suited for solving the problems in the O.R. domain. Use of the library requires no extra expenses, no extra licenses to accept, and no extra installation steps. The library is called the Microsoft Solver Foundation (MSF). It is not too difficult to negotiate the learning curve, and the results it can provide will impress you.
1 The simple transportation problem
We start the discussion with a very simple problem called the transportation problem. There are a set of producers of beer, and there are a set of consumers of beer. The producers have a production capacity in units of crates per day. The consumers demand a certain amount of beer. There is a cost to transporting the beer from the producers to the consumers. The objective is to arrange the shipping such that the cost is minimized, while still satisfying the demands of consumers and not exceeding the capacity of the producers.
Let’s take a minute to write these rules a little more formally:
Where:
- costi,j — is the (non-negative) cost of transporting one item from i to j; and
- xi,j — is the number of items to move from i to j; and
- demandj — is the demand at consuming site j; and
- capacityi — is the capacity of producing site i.
The result that we are looking for is the matrix xi,j , which is the number of crates to move from producer i to consumer j.
1.1 OML code model to describe the problem
The MSF library allows you to express the problems you want to solve in a declarative language called Optimization Modeling Language (OML). I stress the point that scripts in this language do not tell the computer how to solve the problem. Instead, OML merely describes the problem to solve. Let’s look at the preceding transportation problem as expressed in OML:
Model[
Parameters[Sets,Producers,Consumers],
Parameters[Reals[0,Infinity],
Capacity[Producers],
Demand[Consumers],
Cost[Producers,Consumers]],
Decisions[Reals[0,Infinity],x[Producers,Consumers],TotalCost],
Constraints[
TotalCost == Sum[{i,Producers},{j,Consumers},Cost[i,j]*x[i,j]],
Foreach[{i,Producers}, Sum[{j,Consumers},x[i,j]]
Foreach[{j,Consumers}, Sum[{i,Producers},x[i,j]]>=Demand[j]]
],
Goals[Minimize[TotalCost]]
]
If you compare the OML to the original problem formulation in mathematical notation, you will find many similarities. The results we are looking for are the decisions. The input parameters for the model are the costs, demands, and capacities. The constraints describe what the solution must satisfy. The goal states that we wish to minimize the total cost.
1.2 Paste the OML code as a string in C#
A C# method to load this model would look something like:
public class TransportationModel // C#
{
///
/// Create model by adding decisions, constraints and goals. This version works by
/// passing the OML model (as a string) to the LoadModel method that will then
/// create the model. The data is bound to the model thereafter.
///
///The solver context from which the model is created.
/// The model, ready for solving after data binding.
public Model CreateModelFromOML(SolverContext context)
{
string modelSource = @"
Model[
Parameters[Sets,Plants,Markets],
Parameters[Reals,Capacity[Plants],Demand[Markets],Cost[Plants,Markets]],
Decisions[Reals[0,Infinity],x[Plants,Markets],TotalCost],
Constraints[
TotalCost == Sum[{i,Plants},{j,Markets},Cost[i,j]*x[i,j]],
Foreach[{i,Plants}, Sum[Foreach[{j,Markets},x[i,j]]],
Foreach[{j,Markets}, Sum[{i,Plants},x[i,j]]>=Demand[j]] // Shorthand form.
],
Goals[Minimize[TotalTransportationCost -> TotalCost]]
]";
context.LoadModel(FileFormat.OML, new StringReader(modelSource));
return context.CurrentModel;
}
...
}
You will need to add a reference to the Microsoft.Solver.Foundation.dll, typically found in the …Clientbin directory.
Before we continue discussing the solver and its context parameter, let’s mention data binding. You see no data binding in the CreateModelFromOML method. In other words, there is no declaration of the costs, demands, and capacities. We see that the OML model defines only the model of the problem, and that the OML does not define the data. We need another way to provide data.
1.3 Data binding for the OML model
First, here is how we would call the preceding CreateModelFromOML method:
namespace TransportationDemoSupport
{
using Microsoft.SolverFoundation.Services;
using Microsoft.SolverFoundation.Common;
class Program
{
static void Main(string[] args)
{
var tp = new TransportationModel();
SolverContext context = new SolverContext();
Model model = tp.CreateModelFromOML(context);
if (model != null)
{
tp.DataBind(model);
var solution = context.Solve();
var report = solution.GetReport(ReportVerbosity.All);
}
}
}
}
Next we must write the DataBind method. We must provide values for the parameters, so let’s start by retrieving the values from the model we defined in OML:
public Model DataBind(Model model)
{
var demandParameter = model.Parameters.Where(
p => p.Name.StartsWith("Demand")).First();
var capacityParameter = model.Parameters.Where(
p => p.Name.StartsWith("Capacity")).First();
var costParameter = model.Parameters.Where(
p => p.Name.StartsWith("Cost")).First();
... // Code inside this method continues below.
}
Obviously “Demand”, “Capacity”, and “Cost” are the names used in the model. But so far there is no data associated with these names.
Next in this DataBind method we must call the SetBinding method on the parameters to set their values. There are many overloads for this method, so there are many choices on how to provide the values. We start the discussion with a simple example using anonymous types:
public Model DataBind(Model model)
{
... // Code inside this method continues from above.
capacityParameter.SetBinding(new[] {
new { supply = 200.0, name = "Chicago" },
new { supply = 30.0, name = "New York" } }, "supply", "name");
demandParameter.SetBinding(new[] {
new { demand = 50.0, name = "Philadelphia" } }, "demand", "name");
costParameter.SetBinding(new[] {
new {distance=200.0, producer="Chicago", consumer="Philadelphia"},
new {distance=300.0, producer="New York", consumer="Philadelphia"},
}, "distance", "producer", "consumer");
return model;
}
In the calls to the SetBinding method for the capacity and demand parameters, we are using anonymous types to express sequences of objects which each contain two named values (‘supply, name’, and ‘demand, name’). The framework will use reflection calls to these bi-value objects to get the values.
The costParameter is a little more complicated. It is a sequence of tri-value objects. Each object captures the locations for a producer and consumer, plus the distance between the two locations. The sample data are a little contrived for simplicity.
1.4 Report the solution
In the preceding Main method, the call to get a report is:
var report = solution.GetReport(ReportVerbosity.All);
The call produces a report in plain text which displays solution. A copy of the report is pasted in next (after I removed a few pieces of uninteresting data for clarity).
===Solver Foundation Service Report===
Version: Microsoft Solver Foundation 3.0.2.10919 Enterprise Edition
Model Name: DefaultModel
Capabilities Applied: LP
Solve Time (ms): 169
Total Time (ms): 353
Solve Completion Status: Optimal
Solver Selected: Microsoft.SolverFoundation.Solvers.SimplexSolver
…
===Solution Details===
Goals:
TotalTransportationCost: 10000
Decisions:
x(Chicago, philadelphia): 50
x(New York, philadelphia): 0
TotalCost: 10000
The reports shows that it took less than two tenths of a second to calculate the optimal solution for this problem by using the simplex solver. The optimal solution, incurring a cost of 10000, is the transportation of 50 crates of beer from Chicago to Philadelphia, and zero crates from New York.
2 LINQ for binding to AX data
The preceding approach to data binding does not provide the power we need to use OML and the Microsoft Solver Foundation in our AX work. We do not want to write lots of tedious code to obtain and assign data from AX by using either the .NET Business Connector or AX services. A much better approach is to use LINQ for AX in our C# code. (For background information about LINQ for AX, see http://msdn.microsoft.com/library/jj677293.aspx).
By using LINQ for AX we can reference table of data in AX with great ease and succinct code. Let’s imagine there are tables that store the values we need. We need a table called Cities that defines the cities that produce and consume beer. The Cities table has the following fields:
CITYNAME, COUNTRY, LATITUDE, LONGITUDE, STATE
To keep the example unrealistically simple, let’s say that the distances between the cities will serve as the only costing factor. The crates of beer will be shipped by trucks, each with a capacity. We would add criteria to make sure we filled the trucks to capacity. This spares our example the complexity of unit cost differences in scenarios where we might ship only one crate on a given truck, instead of filling the truck to capacity.
2.1 Rewrite the DataBind method
Now that we have the cities data ready, we need a way to calculate the distances between the cities, based on their latitude and longitude. For this calculation we use the Haversine formula, as explained in http://mathforum.org/library/drmath/view/51879.html. This algorithm is encoded into the static Distance method in the DistanceBetweenLocations class.
We will now present the new DataBind method. The few var declarations at the start of the method are identical to those in the earlier code example for the DataBind method. But now after the var declarations we use LINQ queries to access the data from AX:
public Model DataBind(Model model)
{
var demandParameter = model.Parameters.Where(
p => p.Name.StartsWith("Demand")).First();
var capacityParameter = model.Parameters.Where(
p => p.Name.StartsWith("Capacity")).First();
var costParameter = model.Parameters.Where(
p => p.Name.StartsWith("Cost")).First();
QueryProvider provider = new AXQueryProvider(null);
QueryCollection consumers = new QueryCollection(provider);
QueryCollection producers = new QueryCollection(provider);
QueryCollection cities = new QueryCollection(provider);
// Bind data to the parameters using LINQ to AX.
var tempCities = (from city in cities
select new
{
RecId = city.RecId,
CityName = city.CityName,
Latitude = city.Latitude,
Longitude = city.Longitude
}).ToArray();
var capacityQuery = from city in tempCities
from p in producers
where p.cityRecId == city.RecId
select new {
supply = Convert.ToDouble(p.Capacity),
name = city.CityName };
capacityParameter.SetBinding(capacityQuery, "supply", "name");
var demandQuery = from city in tempCities
from c in consumers
where c.cityRecId == city.RecId
select new {
demand = Convert.ToDouble(c.Demand),
name = city.CityName };
demandParameter.SetBinding(demandQuery, "demand", "name");
var producerCityLocations = from city in tempCities
from producer in producers
where city.RecId == producer.cityRecId
select new {
; Name = city.CityName,
Latitude = city.Latitude,
Longitude = city.Longitude };
var consumerCityLocations = from city in tempCities
from consumer in consumers
where city.RecId == consumer.cityRecId
select new {
Name = city.CityName,
Latitude = city.Latitude,
Longitude = city.Longitude };
// Cost.
var costQuery =
from producer in producerCityLocations
from consumer in consumerCityLocations
select new
{
distance = DistanceBetweenLocations.Distance(
consumer.Latitude,
consumer.Longitude,
producer.Latitude,
producer.Longitude),
producing = producer.Name,
consuming = consumer.Name
};
costParameter.SetBinding(costQuery, "distance", "producing", "consuming");
return model;
}
In the example above, we start by reading the whole Cities table into memory, into the tempCities array. Reading the whole table improves the speed of queries in the subsequent code. It also helps us in debugging. But if your table contains a lot of data, you might instead need to perform multiple smaller reads from the table, incurring a slight overhead. The point is that the LINQ solution does not rely on the optimization of reading the whole Cities table.
2.2 WPF control to host a Bing map
Now we have what we need to use the model from AX. To make things a little more interesting and easier to demo, I have used this code from a form which shows a Bing map with the cities, and which also shows the solution.
This is all made very easy by using the managed control host to host a WPF control (the Bing maps control). This feature has always been a little under-appreciated and under hyped. It really is extremely useful whenever you want to present data in an interesting way in an AX form. You can download the Bing maps control from http://www.microsoft.com/en-us/download/details.aspx?id=27165.
3 Network model
The preceding example model is a simple case. You can easily expand it to the network model, where limits are placed on the amount of goods shipped, and equations maintain that nothing is ever lost in the grid. You can find interesting examples here:
http://www.me.utexas.edu/~jensen/ORMM/models/unit/network/subunits/distribution/index.html
These problems are solved just as the simple example we have just shown.
3.1 Assignment problem
One of the interesting special cases of the network problem is the assignment problem. The definition of this problem reads as follows:
There are a number of agents and a number of tasks. Each agent must be assigned exactly one task, and each task must be assigned exactly one agent. Any agent can be assigned to perform any task. The costs incurred may vary depending on particular attributes of the agent and task in each paring. The challenge is to choose the agent-task assignments that minimize the total cost.
The standard example used to illustrate this problem is that of a set of workers and a set of jobs performed by the workers. The cost of personi doing jobj is input to the algorithm. Some people are better at a particular job, so their cost is smaller than for someone who is not yet skilled at that particular job. The solution is a boolean matrix that maps each job onto a machine such that the minimal cost is incurred.
Another embodiment of this problem is the taxi company problem. There is a set of customers and a set of taxis to serve them. The cost of a trip is a function of the distance that an available taxi is from the customer. The objective is to minimize that cost.
3.2 Knapsack problem
Another problem that often occurs is the knapsack problem. Imagine you have a knapsack of a certain maximum weight capacity. The challenge is to pack the knapsack with items having as much total monetary value as possible without exceeding the weight capacity of the knapsack.
The equations are:
The first equation says that we should maximize the monetary value of the content in the knapsack (vi is the value of the ith item, and xi is the count of that item to bring). The second equation says that the cost of each item (or number of items) cannot exceed the constraint W, where W is the capacity of the knapsack. In our example, the cost is the weight that you have to carry, and W is the maximum weight that you are willing to accept.
There are three flavors of knapsack problems:
We illustrate the difference with an example shown in Wikipedia (http://en.wikipedia.org/wiki/Knapsack_problem). Here the limiting factor here is the weight capacity of the knapsack (W=15kg). There are five types of items: the green, gray, blue, yellow, and orange types. There are many items available of each type. The weight and monetary value is written on each item.
The solutions are as follows:
- 0-1: yellow, blue, gray, orange.
(value 10$ + 2$ + 2$ + 1$ = 15$; weight = 4 + 2 + 1 + 1 = 8kg) - Unbounded: 3 yellow and 3 gray boxes.
(value 3*10$ + 3*2$ = 16$; weight = 3*4 + 3 * 1 = 15kg)
Again, it is useful to look at what this looks like in OML:
Model[
Parameters[Sets, items],
Parameters[Integers[0,Infinity],
Cost[items], Value[items], W
],
Decisions[Integers[0,1], x[items]], // Either it is included, or it isn't.
Decisions[Integers, TotalCost, TotalValue]
Constraints[
TotalCost == Sum[{i,items}, x[i]*Cost[i]],
TotalValue == Sum[{i,items},x[i]*Value[i]],
TotalCost <= W
],
Goals[Maximize[TotalValue]]
]
You can convert the above OML model into the Bounded or Unbounded knapsack problem by changing the definition of the x decision variable. As with all of the examples in this area, the problem statement is an abstraction of the problems that you would apply this to in real life.
You would use the same procedure as described above to do the data binding.
3.3 Traveling salesman
The traveling salesman problem is a classic that rears its head in many interesting places. The description is simple enough:
- A salesman has customers who are placed in different cities.
- He must visit each of his customers exactly once.
- Then he must return to where he started.
The challenge is to devise the cheapest itinerary, given the cost of transportation between the cities.
Research into this area has been intensive because the cost of calculating the result for many cities is high. It is an interesting problem because it is not really possible to solve it using brute-force approaches. The number of possible itineraries is a function of the factorial of the cities to be visited, which very quickly gets out-of-hand. The bits accompanying this blog entry provide a solution expressed in OML, and a test-bed with a form to show the results on a map. I have adapted the solution from some excellent work by Nathan Brixus in http://nathanbrixius.wordpress.com/2009/04/27/solving-traveling-salesman-problems-using-solver-foundation/.
Conclusion
There are many more interesting examples of O.R. problems that can be solved by using the Microsoft Solver Foundation library. You can find some very interesting samples here: http://msdn.microsoft.com/en-us/library/ff524501(v=vs.93).aspx. The samples map to interesting business scenarios, all of which would be above and beyond most developers to solve using X++ code. The source code for the samples shown here can be found here: http://blogs.msdn.com/cfs-file.ashx/__key/communityserver-blogs-components-weblogfiles/00-00-00-86-72/5381.PrivateProject_5F00_TechnicalConference2012-_2800_1_2900_-_2D00_-Copy.xpo
I hope this has been a useful blog entry, one that shows you how to get started in this interesting field. There are many things to learn, but a lot of benefits to reap.
.