Using the Term class to build models in Solver Foundation

  • Article

I'd like to spend the next couple posts on "everyday" use of Solver Foundation Services for model building.  In many models it is necessary to build up goals and constraints programmatically.  In Solver Foundation this is done using the Term class.  At first, trying to figure out how to do this can be tricky. Hopefully this post helps somebody out there.

I want to focus on the APIs themselves right now - in a future post I will use these APIs in a worked-out example.  Terms come into play when defining goals and constraints on a Model object:

 public Constraint AddConstraint(string name, Term constraint);
public Goal AddGoal(string name, GoalKind direction, Term goal);

The Term class does not have a constructor.  You can build Terms using:
 
Constants.   Bools, ints, doubles are implicitly converted into constant terms.  Constants by themselves are usually not very interesting goals or constraints…
 
Parameters and decisions.  Parameters or decisions are terms.  Every meaningful constraint or goal will always contain at least one decision!

 model.AddGoal("goal", GoalKind.Minimize, x + y);

Operators.   Term has operator overloads for most common arithmetic and logic operators.  In particular, <, >, !=, and so on are often used in constraints:

 model.AddConstraint("c1", x + y >= 5);
model.AddConstraint("c2", color[0, 0] != color[0, 1]);

Static methods on Model.   The Model class has a bunch of static methods that provide mathematical, logical, and type conversion functions.  The OML reference has a complete listing.  A few highlights:

  • AsInt: converts a boolean term into a 0/1 value.
  • Pow: raises a term to a power.
  • AllDifferent: True if all the terms are different from each other.

Foreach, ForeachWhere and Sum.   Actually these should be included in the previous category, but I list them separately because they are so important.  Foreach and ForeachWhere  are special because they work with Sets.  Sets allow you to create indexed (list- or table-valued) decisions or parameters.  Most of the models you think of will probably involve Sets. After specifying the set to iterate over, you then need to specify a function that maps members of the sets to Terms.  This is typically done using anonymous functions. In the case of ForeachWhere, you also provide a function that represents the filter.
 
Here's a silly example - suppose you want you're running a restaurant and you want to make sure that all the tables near windows have at least 4 chairs.  If you had an indexed parameter "nearWindow" and decision "chairs", then the constraint could be written as follows.

 model.AddConstraint("c", Model.ForEachWhere(tables, t => 
  chairs[t] >= 4, t => nearWindow[t]));

Sum is often used to wrap a Foreach or ForeachWhere.   (The usage is a little different from OML.)

You can build up all kinds of different goals and constraints using these building blocks. Sometimes figuring out how to express the model you have in mind can be difficult. I will avoid making this post a long fluffy sermon - except to say that the techniques for writing good code apply to writing good SFS code too. In particular, you can encapsulate calls to SFS methods inside of classes and methods.  In this post I talked about using extension methods to do just that.

In my next post I will show how to get good performance using these APIs. Creating Terms means allocating memory, and it is (unfortunately) easy to build models that have a lot of bloat. Keeping a few simple facts in mind will help to avoid this pitfall.