When modeling problems, one may come to a formulation that is not directly model-able using the Solver Foundation API, but that may be reformulated as a known Solver Foundation model type (LP, QP, CSP, etc).  Consider certain min-max problems, which with a little thought can become a linear program.

In the current example, consider a min-max problem of the form

minimize max { a_i *x + b_i for all i }

where a_i is a row of a matrix and b is a vector.  This problem doesn’t look like anything that can be modeled using Solver Foundation.  But Solver Foundation can handle the problem when written in the mathematically equivalent form

minimize t

subject to:  a_i *x + b_i <= t for all i

As an example, consider the toy problem where we try to determine the minimum of a one-dimensional non-linear convex function f(x).  We can do this by finding the minimum over a collection tangent lines, that is

minimize max { df(x_i)/dx *(x - x_i) + f(x_i) for all i }

or using our modeling trick

minimize t

subject to:  df(x_i)/dx *(x - x_i) + f(x_i) <= t for all i

where the set i represents a sampling of points.  For a more concrete example, consider the problem f(x) = x + 1/x, which is convex for x > 0.  The minimum is at x = 1, where f(1) = 2.  The collection of tangent lines looks like

where the horizontal axis represents x and the vertical axis represents f(x).  The code to find the minimum is below:

static void Main() {
   SolverContext context = SolverContext.GetContext();
   Model model = context.CreateModel();

   Decision t = new Decision(Domain.Real, "t");
   Decision x = new Decision(Domain.Real, "x");
   model.AddDecisions(t, x);
   model.AddGoal("goal", GoalKind.Minimize, t);

   int i = 0;
   for (double x_i = .1; x_i <= 4; x_i = x_i + .01) {
     model.AddConstraint("constraint_" + i++, derivative(x_i) * (x – x_i) + function(x_i) <= t);
   }

   Solution solution = context.Solve();
   Report report = solution.GetReport();
   Console.WriteLine(report); 
}

 static double function(double x) {
   return x + 1 / x;
}

 static double derivative(double x) {
    return 1 - Math.Pow(x, -2);
}

The output is as follows:

===Solver Foundation Service Report===
Date: 6/1/2010 10:58:26 AM
Version: Microsoft Solver Foundation 2.0.3.0 Enterprise Edition
Model Name: Default
Capabilities Applied: LP
Solve Time (ms): 316
Total Time (ms): 504
Solve Completion Status: Optimal
Solver Selected: Microsoft.SolverFoundation.Solvers.SimplexSolver
Directives: Microsoft.SolverFoundation.Services.Directive
Algorithm: Primal
Arithmetic: Hybrid
Variables: 2 -> 2 + 392
Rows: 392 -> 392
Nonzeros: 783
Eliminated Slack Variables: 0
Pricing (exact): SteepestEdge
Pricing (double): SteepestEdge
Basis: Slack
Pivot Count: 408
Phase 1 Pivots: 391 + 0
Phase 2 Pivots: 16 + 1
Factorings: 12 + 1
Degenerate Pivots: 0 (0.00 %)
Branches: 0
===Solution Details===
Goals:
goal: 2

Decisions:
t: 2
x: 0.994974874371864

As an additional point, note that while t = 2 is an expected result, x is not exactly the expected value of 1.  This is due to the fact that the problem is discretized with a finite series of tangent lines.  In fact, if you zoom in on tangent lines in the neighborhood of the minimum, given our discretization of a tangent line for every .1 in x, you will note that there are actually an infinite number of valid x values between x = .947368 and x = 1.047619.

This code shows how we can use a mathematical trick for solving min-max problems.  However, for the particular example of minimizing a non-linear convex function, here are some reasons why it can’t be generally done:

• it may not be easy to know if the function is convex, or over which domain it’s convex.
• the method requires the user to know a neighborhood where the minimum can be found (in our case between x = .1 and x = 4), as well as a representation of the derivative
• we need enough points to create a realistic envelope.  In multiple dimensions, this could be expensive.