Jaa

Solver Foundation TSP Part II: Directives, Solver Plugins, Model Libraries

  • Artikkeli

Here is my as-promised "part 2" to my traveling salesman sample. My goal is not to try and do any "production level" modeling, but instead "point the way" by highlighting different aspects of Solver Foundation's architecture. This time I want to talk about directives, plug-in solvers, and model reusability. The Solver Foundation architecture provides the ability to plug-in other solvers to handle one or more problem types. As of version 1.1, the Gurobi solver is Solver Foundation's default MIP (mixed integer programming) solver. Gurobi is a high-performance solver which is capable of taking on industrial strength problems, so my piddling little TSP example is no match for it. Gurobi has a number of parameters that can be set to tune solver performance - you set them by means of Directives. First, let's modify our code to turn on logging. Change the context.Solve() call to:

       GurobiDirective gurobiDirective = new GurobiDirective();
      gurobiDirective.OutputFlag = true;
      Solution solution = context.Solve(gurobiDirective);

Each plug-in solver also defines its own directives - therefore the full power and flexibility of plug-in solvers are available to you as a programmer. In this case I have just flipped on the logging bit - here's what I see.

 Optimize a model with 185 Rows, 380 Columns and 1199 NonZeroes
Presolve removed 1 rows and 185 columns
Presolve time: 0.30s
Presolved: 184 Rows, 195 Columns, 832 Nonzeros
Objective GCD is 1

Root relaxation: objective 2.783286e+03, 36 iterations, 0.02 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0  2783.2857    0   14          -  2783.2857     -      -    0s
     0     0  3006.1964    0   29          -  3006.1964     -      -    0s
     0     0  3006.1964    0   29          -  3006.1964     -      -    0s
     0     0  3006.1964    0   25          -  3006.1964     -      -    0s
     0     0  3006.1964    0   25          -  3006.1964     -      -    0s
H    0     0                       6029.0000  3006.1964  50.1%     -    0s
     0     0  3006.1964    0   25  6029.0000  3006.1964  50.1%     -    0s
H    0     2                       3805.0000  3006.1964  21.0%     -    0s
     0     2  3006.1964    0   25  3805.0000  3006.1964  21.0%     -    0s
*   75    54              29       3644.0000  3077.0000  15.6%   8.2    0s
*  129    80              27       3381.0000  3077.0000  8.99%   8.7    0s
*  158    62              30       3323.0000  3077.0000  7.40%   8.1    0s

Cutting planes:
  Learned: 3
  Gomory: 1
  MIR: 3

Explored 1231 nodes (5693 simplex iterations) in 0.69 seconds
Thread count was 2 (of 2 available processors)

Optimal solution found (tolerance 1.00e-04)
Best objective 3.3230000000e+03, best bound 3.3230000000e+03, gap 0.0000%

For large models it is sometimes useful to tweak the solver options for performance. For example, if I wanted to spend a slightly larger amount of time doing MIP heuristics, and I wanted to eliminate presolve, then I can set those options easily:

       gurobiDirective.Heuristics = 0.1;
      gurobiDirective.Presolve = PresolveLevel.None;

There is a full reference in the Gurobi Solver Programming Primer that ships with Solver Foundation. My point is that you do not get a "least common denominator" solution - you get all the bells and whistles.

Gurobi is just one example - there are a wide range of plug-ins available, covering most of the popular LP and MIP solvers - check out solverfoundation.com for the full list. To use a plug-in solver, you need to: 1) install the solver (duh), 2) change your exe.config or web.config to point to the solver. No code changes are required. You can find additional documentation on the default MIP directives and the third-party Solver configuration in the SFS Programming Primer.

Last thing - modern programming languages like C# are cool because they promote reusability and maintainability. Don't forget about that when you are writing SFS code. It's common for models in a particular vertical (say, finance or transportation) to have common "blocks" of goals or constraints that are re-used over and over again. It's pretty easy to build reusable model libraries using extension methods. For example, take the assignment constraints in my TSP example. I could factor them out:

   public static class ModelingExtensions {
    public static void AssignmentConstraintsNoDiag(this Model model, Set s, Decision assign) {
      model.AddConstraint("A1", Model.ForEach(s, i => Model.Sum(Model.ForEachWhere(s, j => assign[i, j], j => i != j)) == 1));
      model.AddConstraint("A2", Model.ForEach(s, j => Model.Sum(Model.ForEachWhere(s, i => assign[i, j], i => i != j)) == 1));
    }
  }

Now I can just say model.AssignmentConstraintsNoDiag(city, assign). I could add other variations inside of ModelingExtensions as well. I think this aspect of Solver Foundation has not gotten enough attention - maybe because it doesn't make for a cool demo!

Comments