In
early January Laurent Perron announced that or-tools now supports .NET (C#). A few minutes after I read that, I (and probably many others) wrote to him and asked when there will be a support of
Mono (.NET support on Linux, Mac etc). After some week Laurent mailed me to announce that he and Mark Farkas had fixed Mono support as well. Great work!
So, this is what I have done the last weeks: Learning more about C# and modeled some models in or-tools/C#. My models are at my
or-tools/C# page, and most of them has been pushed to the project's SVN:
code.google.com/p/or-tools/source/browse/trunk/csharp/.
This blog post can be seen as the third part in the "First looks" at Google or-tools tools, where the previous two where
A first look at Google CP Solver/Python (Google or-tools) and
A first look at Google or-tools' Java interface. Since much of the things in or-tools/C# works the same as for Python and Java I will here mention more about of the differences from these versions.
or-tools/C#
Google or-tools is Google's Operations Research Tools developed at Google and is an open source (though committing and contribution require special handling). The kernel of the solvers is written in C++, and it now supports Constraint Programming (which is - of course - my main interest here) and Mathematical Programming with support for the external solvers Gurubi, GLPK, CBC, and SCIP/Zib Optimization Suite, and modeling interface for C++, Python, Java, and now .NET/C#.
Syntactic sugar - a first example
The first version of or-tools/C# (.NET) was released about January 19, but didn't have much syntactic sugar; instead the models looked very much like the
Java models which was kind of lucky for me since it made the porting of these models quite easy. However, after a while Laurent added quite a few shortcuts (i.e. syntactic sugar) which made the modeling much easier. During the following weeks, Laurent added more sugaring, some probably after my complaint, suggestions, or - in some case - confusion.
For example: Here is the first version of
least_diff.cs (Least Diff is a simple alphametic optimization problem where the object is to minimize the difference
ABCDEF-FGHIJ where A..J is distinct digits). You can see the SVN history of this model
here.
using System;
using Google.OrTools.ConstraintSolver;
public class LeastDiff
{
private static void Solve()
{
Solver solver = new Solver("LeastDiff");
IntVar A = solver.MakeIntVar(0, 9, "A");
IntVar B = solver.MakeIntVar(0, 9, "B");
IntVar C = solver.MakeIntVar(0, 9, "C");
IntVar D = solver.MakeIntVar(0, 9, "D");
IntVar E = solver.MakeIntVar(0, 9, "E");
IntVar F = solver.MakeIntVar(0, 9, "F");
IntVar G = solver.MakeIntVar(0, 9, "G");
IntVar H = solver.MakeIntVar(0, 9, "H");
IntVar I = solver.MakeIntVar(0, 9, "I");
IntVar J = solver.MakeIntVar(0, 9, "J");
IntVar[] all = new IntVar[] {A,B,C,D,E,F,G,H,I,J};
int[] coeffs = {10000,1000,100,10,1};
IntVar x =
solver.MakeScalProd(new IntVar[]{A,B,C,D,E}, coeffs).Var();
IntVar y =
solver.MakeScalProd(new IntVar[]{F,G,H,I,J}, coeffs).Var();
IntVar diff =
solver.MakeDifference(x,y).VarWithName("diff");
solver.Add(solver.MakeAllDifferent(all));
solver.Add(A > 0);
solver.Add(F > 0);
solver.Add(diff > 0);
OptimizeVar obj = solver.MakeMinimize(diff, 1);
DecisionBuilder db = solver.MakePhase(all,
Solver.CHOOSE_PATH,
Solver.ASSIGN_MIN_VALUE);
solver.NewSearch(db, obj);
while (solver.NextSolution()) {
Console.WriteLine("{0} - {1} = {2} ({3}",
x.Value(), y.Value(), diff.Value(), diff.ToString());
}
Console.WriteLine("\nSolutions: {0}", solver.Solutions());
Console.WriteLine("WallTime: {0}ms", solver.WallTime());
Console.WriteLine("Failures: {0}", solver.Failures());
Console.WriteLine("Branches: {0} ", solver.Branches());
solver.EndSearch();
}
public static void Main(String[] args)
{
Solve();
}
}
After Laurent added some syntactic sugar, the constraint and solve part looks like this which in my book is better and easier to work with: all the
Make* constructs are removed. Also, equality (
==) was sugared after a while but it's not shown here.
// ....
IntVar x = new IntVar[]{A,B,C,D,E}.ScalProd(coeffs).Var();
IntVar y = new IntVar[]{F,G,H,I,J}.ScalProd(coeffs).Var();
IntVar diff = (x - y).VarWithName("diff");
solver.Add(all.AllDifferent());
solver.Add(A > 0);
solver.Add(F > 0);
solver.Add(diff > 0);
OptimizeVar obj = diff.Minimize(1);
DecisionBuilder db = solver.MakePhase(all,
Solver.CHOOSE_PATH,
Solver.ASSIGN_MIN_VALUE);
solver.NewSearch(db, obj);
Here's how to compile and run this model with Mono on a Linux box.
$ export MONO_PATH=$MONO_PATH:/path-to-or-tools/
$ mono-csc /r:Google.OrTools.ConstraintSolver.dll least_diff.cs
$ ./least_diff.exe
....
50123 - 49876 = 247 (diff(247)
Solutions: 30
WallTime: 27ms
Failures: 20
Branches: 83
Performance comparing to Python and Java versions
Since the Python, Java, and C# models use the same engine there is very
little difference between of the performance of models written in these languages, at least
when using the same approach and the same heuristics.
As an example, we can continue with the comparison in
A first look at Google or-tools' Java interface where the
Python and
Java versions of a N-queens problem where benchmarked. The results for (the first solution of) N=8, 100, 1000, and 10000 using the C# model
nqueens.cs is the same as for the other two implementations:
N Failures Branches Wall time Required
memory
-------------------------------------------------------
8 3 9 5ms
100 12 120 10ms
1000 0 996 470ms
10000 0 9999 78923ms 2.1Gb
This is exactly the same result as for Python and Java. Again, this is not surpising since they all use the same underlying solver engine. Comparing Java and C# (using Mono) it seems that the Mono version is slightly faster both in compiling and the time for upstart, though this has not been tested systematic.
The (interesting part of the) model
nqueens.cs is:
IntVar[] q = solver.MakeIntVarArray(n, 0, n-1, "q");
solver.Add(q.AllDifferent());
IntVar[] q1 = new IntVar[n];
IntVar[] q2 = new IntVar[n];
for(int i = 0; i < n; i++) {
q1[i] = (q[i] + i).Var();
q2[i] = (q[i] - i).Var();
}
solver.Add(q1.AllDifferent());
solver.Add(q2.AllDifferent());
DecisionBuilder db = solver.MakePhase(q,
Solver.CHOOSE_MIN_SIZE_LOWEST_MAX,
Solver.ASSIGN_CENTER_VALUE);
LINQ
The nqueens model shown above is a very straightforward implementation, but the interesting part of C# is that we can use LINQ to do array handling in another way using "query comprehensions" (array comprehensions).
Although it was one of my objects to learn more about LINQ, I'm not sure if this is better (= more clear) in this particular case. Anyway, here is one way of stating the constraints using LINQ:
solver.Add(q.AllDifferent());
solver.Add((from i in Enumerable.Range(0, n)
select (q[i] + i).Var()).ToArray().AllDifferent());
solver.Add((from i in Enumerable.Range(0, n)
select (q[i] - i).Var()).ToArray().AllDifferent());
I think that LINQ shines more in
hidato_table.cs (a port of Laurent Perron's Python version
using a
Table/
AllowedAssignments constraint):
public static int[,] BuildPairs(int rows, int cols)
{
int[] ix = {-1, 0, 1};
var result_tmp = (from x in Enumerable.Range(0, rows)
from y in Enumerable.Range(0, cols)
from dx in ix
from dy in ix
where
x + dx >= 0 &&
x + dx < rows &&
y + dy >= 0 &&
y + dy < cols &&
(dx != 0 || dy != 0)
select new int[] {x * cols + y, (x + dx) * cols + (y + dy)}
).ToArray();
// Convert to len x 2 matrix
// ....
return result;
}
It's not as nice as the Python version, since we must also convert to an int[,] matrix because
AllowedAssignments requires this type, but still. (And - of course - there might be another and even simpler version of this that don't require this conversion....)
A side note: one can see how old my C# models are in the use of LINQ, since in later models I tend to use LINQ (and
foreach) much more than in earlier models. Also, the models use a quite restricted part of LINQ: almost only
from,
select, and sometimes
where, but not much of the more fancy stuff that LINQ supports. This is because I use it mostly as a layers of handling
IntVar's where grouping etc is not appropriate (as I have understood it with some experiments).
MakeIntVarMatrix
One thing that is quite nice - and a sign of Laurent's willingness to help lazy programmers such as myself - is
MakeIntVarMatrix. Here is the way one had to do in earlier C#-models to declare an
IntVars matrix (i.e. matrix of decision variables) as well as creating an 1D array (
x_flat) to be used for the search.
IntVar[,] x = new IntVar[r,c];
IntVar[] x_flat = new IntVar[r*c];
for(int i = 0; i < r; i++) {
for(int j = 0; j < c; j++) {
x[i,j] = solver.MakeIntVar(0, 1);
x_flat[i*c+j] = x[i,j];
}
}
(Note: this is still the way one has to make matrices of decision variables in Python and Java.) However, now one can
use these much simpler constructs in C#:
IntVar[,] x = solver.MakeIntVarMatrix(r, c, 0, 1, "x");
IntVar[] x_flat = x.Flatten();
Very handy!
Element
It would not be a complete First look-report if there wasn't any comment about the support of
Element in the tested CP system (see for example
Learning constraint programming - part II: Modeling with the Element constraint). In one way, how
Element is supported can be seen as a proxy of the "expressiveness" of a CP system and its host language. (And this expressiveness is quite important, at least when learning a CP system or perhaps learning CP from the start.)
As with other constraints, Laurent simplified
Element after a while. The Who killed Agatha problem is often a good test how easy it is to use
Element in a system. The C# model
who_killed_agatha.cs has a description of the problem statements.
One of the constraint in this model can be expressed as simple as this in - say - MiniZinc or Comet where
hates is a matrix if
IntVar, and both
the_killer and
the_victim are
IntVar.
% MiniZinc/Comet code
hates[the_killer, the_victim] == 1
This constraint was
at first expressed in C# as the code below, which is a rather faithful port from the Java version (
WhoKilledAgatha.java):
solver.Add(
solver.MakeEquality(
solver.MakeElement(
hates_flat,
solver.MakeSum(
solver.MakeProd(the_killer, n).Var(),
the_victim).Var()).Var(), 1));
After Laurent's sugaring it can now be stated as the much simpler:
solver.Add(hates_flat.Element(the_killer * n + the_victim) == 1);
This is perhaps as good as one can get when it's not possible to state the constraints in the matrix direct by overloading index access (
[,]) of a matrix in the host language. Almost all CP systems embedded in a host programming language requires this kind of handling. (Compare with Gecode that supports constraints directly with the matrix, see
Gecode: Modeling with Element for matrices -- revisited; Christian Schulte fixed this support after my complaints during a CP lecture...)
Decompositions
Another thing that it's nice to have in a CP system it to be able to write decompositions that can be used similar as the built-in constraints where - again - simplified syntax helps much. Here is my standard decomposition of the channeling between an
IntVar array representing digits and and IntVar variable representing the numbers with these digits (see below for a LINQed version)
private static Constraint ToNum(IntVar[] a, IntVar num, int bbase) {
int len = a.Length;
IntVar[] tmp = new IntVar[len];
for(int i = 0; i < len; i++) {
tmp[i] = (a[i]*(int)Math.Pow(bbase,(len-i-1))).Var();
}
return tmp.Sum() == num;
}
It can now be used much as any constraint, as in
pandigital_numbers.cs (yet another alphametic problem). The object is to find all possible multiplications of the form
term1 * term2 = product which use all digits. Here we see how the first term (called
num1) is calculated:
IntVar[] x = solver.MakeIntVarArray(x_len, start, max_d, "x");
// ...
// First term
solver.Add(ToNum((from i in Enumerable.Range(0, len1)
select x[i].Var()).ToArray(),
num1,
bbase));
This is also another example how LINQ can simplify the model.
In
to_num.cs its use is more direct:
IntVar[] x = solver.MakeIntVarArray(n, 0, bbase - 1, "x");
IntVar num = solver.MakeIntVar(0, (int)Math.Pow(bbase, n) - 1, "num");
solver.Add(x.AllDifferent());
solver.Add(ToNum(x, num, bbase));
As an afterthought: The constraint
ToNum could be written like this instead
using LINQ:
// ...
int len = a.Length;
return (from i in Enumerable.Range(0, len)
select (a[i]*(int)Math.Pow(bbase,len-i-1)).Var()
).ToArray().Sum() == num;
Mathematical programming
There is also support for Mathematical programming in or-tools (there is also much support for linear programming that I haven't tested much in my earlier or-tools projects). I have just tested this with three simple models which solves almost the same problem using different approaches: then Volsay problem (from OPL).
- volsay.cs: Volsay LP problem (using "Natural API")
- volsay2.cs: Volsay LP problem, using arrays for representing the data
- volsay3.cs: Volsay LP problem, arrays/matrices with components added.
The first model (
volsay.cs) looks like this using the "Natural API" for stating the constraints:
// ...
Solver solver = new Solver("Volsay",
Solver.CLP_LINEAR_PROGRAMMING);
Variable Gas = solver.MakeNumVar(0, 100000, "Gas");
Variable Chloride = solver.MakeNumVar(0, 100000, "Cloride");
Constraint c1 = solver.Add(Gas + Chloride <= 50);
Constraint c2 = solver.Add(3 * Gas + 4 * Chloride <= 180);
solver.Maximize(40 * Gas + 50 * Chloride);
int resultStatus = solver.Solve();
if (resultStatus != Solver.OPTIMAL) {
Console.WriteLine("The problem don't have an optimal solution.");
return;
}
Console.WriteLine("Objective: {0}", solver.ObjectiveValue());
Console.WriteLine("Gas : {0} ReducedCost: {1}",
Gas.SolutionValue(),
Gas.ReducedCost());
// ...
Search, labeling
Searching and labeling are very much the same in C# as in Python and Java. As can be seen in the Least Diff model above, the C# interface use a simplified way of stating the optimization variable:
OptimizeVar obj = solver.MakeMinimize(diff, 1);
But otherwise it was no surprises compared to the Python and Java models.
Not tested (yet)
There are some things I have yet to test for C#, especially Nonogram using
DefaultSearch, where the Python version was quite fast after some tweaking:
Google CP Solver: A much faster Nonogram solver using DefaultSearch. Perhaps I will port this to C# as well. Also, there are certain MIP models in or-tools/Python that perhaps will be converted to C#.
Summary
I like this .NET/C# interface to or-tools, much because there is more syntactic sugar than in Java version making it easier to write models, especially when prototyping models; though with Python, been the VHLL language it, is can be even easier. It was quite easy to port from my earlier Java and Python models, especially from the Java models since Java and C# are very similar on the host language level and they use almost exactly the same way of stating the constraint API. Though it took some more time to LINQ'ing these models.
There where very few models where I have any real problems porting from Python/Java, though I had to search for certain things, for example the best way of converting matrices written in Java/Python to C#'s matrices; often it required a change to jagged arrays especially when using
Element on a row/column.
When writing models in C# for or-tools I found extremely few bugs, which is a sign of the stability of the support for external programming languages in or-tools.
Also, this was my first serious project to use Mono/C# and I'm impressed how smooth Mono is. This has given me a much better ground for developing more C# models/programs.
Also see
See earlier writings about or-tools, in the category
google_cp_solver (which was the name I earlier used for or-tools), and my
Google or-tools page which has quite a few Python, Java, and now C# models. My page
Common constraint programming problems shows listings of the models that is implemented in other CP systems.
For more information about or-tools:
My or-tools/C# models
Here are all the (about 100) published or-tools/C# models so far. Most of them are ports from the Java or Python models, and most are also at the SVN:
code.google.com/p/or-tools/source/browse/trunk/csharp/. Note that Laurent Perron has simplified and/or beautified some of these models. Thanks for this Laurent!
- 3_jugs_regular.cs: 3 jugs problem using
regular constraint.
- a_round_of_golf.cs: A round of golf problem (Dell Logic Puzzles)
- alldifferent_except_0.cs: Decomposition of global constraint
alldifferent_except_0
- all_interval.cs: All interval problem
- assignment.cs: Simple assignment problem
- bus_schedule.cs: Bus scheduling (Taha)
- circuit.cs: Decomposition of global constraint
circuit
- circuit2.cs: Decomposition of global constraint
circuit which also extracts the path.
- coins3.cs: Minimum mumber of coins that allows one to pay exactly any amount smaller than one Euro (from the ECLiPSe book)
- coins_grid.cs: Tony Hurlimann's coin grid problem
- combinatorial_auction2.cs: Combinatorial auction
- contiguity_regular.cs: Decomposition of global constraint
global contiguity (using a decomposition of regular constraint)
- contiguity_transition.cs: Decomposition of global constraint
global contiguity (using the built-in TransitionConstraint)
- costas_array.cs: Costas' array problem
- covering_opl.cs: Set covering (OPL)
- crew.cs: Crew allocation problem
- crossword.cs: Simple crossword problem
- crypta.cs: Crypta, alphametic problem (standard Prolog benchmark)
- crypto.cs: Crypto, alphametic problem (standard Prolog benchmark)
- curious_set_of_integers.cs: Curious set of integers (Martin Gardner)
- debruijn.cs: Classical or "arbitrary" de Bruijn sequences (useful for generating all de Bruijn sequences)
- diet.cs: Simple diet (minimization) problem.
- discrete_tomography.cs: Discrete tomography
Data files (same as for Python)
- divisible_by_9_through_1.cs: Divisible by 9 through 1 for a "truncated" number. Also includes a decomposition of a
modulo constraint.
- dudeney.cs: Dudeney Numbers
- fill_a_pix.cs: Fill-a-pix problem.
Data files (same as for Python above):
- furniture_moving.cs: Optimizing furniture moving (Marriott and Stuckey). Contains a decomposition of the global constraint
cumulative.
- futoshiki.cs: Futoshiki puzzle (grid puzzle)
- golomb_ruler.cs: Golomb ruler
- grocery.cs: Grocery problem
- hidato_table.cs: Hidato puzzle (a port of Laurent Perron's Python model hidato_table.py, from the or-tools/Python distribution)
- just_forgotten.cs: Just forgotten puzzle (Enigma 1517)
- kakuro.cs: Kakuro puzzle
- kenken2.cs: KenKen puzzle
- killer_sudoku.cs: Killer Sudoku puzzle
- labeled_dice.cs: Labeled dice problem, from Jim Orlin's Colored letters, labeled dice: a logic puzzle (follow up: Update on Logic Puzzle)
- langford.cs: Langford's number problem (CSPlib problem 24)
- least_diff.cs: Least difference problem (minimize the difference of ABCDE-FGHIJ)
- lectures.cs: Lectures, schedule problem from Biggs "Discrete Mathematics"
- magic_sequence.cs: Magic sequence
- magic_square.cs: Magic squares problem
- magic_square_and_cards.cs: Magic square and card problem (Martin Gardner)
- map.cs: Simple map coloring.
- map2.cs: Simple map coloring. Alternative version using a matrix to represent the neighbors.
- marathon2.cs: Marathon puzzle (XPress example)
- minesweeper.cs: Minesweeper
Data files (same as for Python and Java above)
- mr_smith.cs: Mr Smith problem, logic problem (from IF Prolog)
- nontransitive_dice.cs: Nontransitive dice
- nqueens.cs: N-queens problem.
- nurse_rostering_regular.cs: Simple nurse rostering using global constraint (decomposition)
regular
- nurse_rostering_transition.cs: Simple nurse rostering using global constraint (using the built-in
TransitionConstraint)
- olympic.cs: Olympic puzzle (alphametic, standard Prolog benchmark)
- pandigital_numbers.cs: Pandigital numbers in "any" base
- partition.cs: Partition problem
- perfect_square_sequence.cs: Perfect square sequence
- photo_problem.cs: Photo problem (Mozart/Oz)
- place_number_puzzle.cs: Place number puzzle
- post_office_problem2.cs: Post office problem (Winston)
- quasigroup_completion.cs: Quasigroup completion
Data files (same as for Python and Java above)
- scheduling_speakers.cs: Scheduling speakers (Rina Dechter)
- secret_santa.cs: Secret santa problem
- secret_santa2.cs: Secret santa problem II (optimizing "santa distance")
- send_more_money.cs: SEND+MORE=MONEY alphametic problem
- send_more_money2.cs: SEND+MORE=MONEY using scalar product
- send_most_money.cs: SEND+MOST=MONEY, where we maximize MONEY and then show all solution with MONEY maximized
- seseman.cs: Solving the Seseman convent problem
- set_covering.cs: Set covering, placing of firestations (Winston)
- set_covering2.cs: Set covering, number of security telephons on a campus (Taha)
- set_covering3.cs: Set covering, senators making a committe (Murty)
- set_covering4.cs: Set covering (and set partition), work scheduling (Lundgren, Roennqvist, Vaerbrand "Optimeringslaera")
- set_covering_deployment.cs: Set covering deployment
- set_covering_skiena.cs: Set covering problem (Steven Skiena)
- set_partition.cs: Set partition
- ski_assignment.cs: Ski assignment problem
- stable_marriage.cs: Stable Marriage problem (from Van Hentenryck's OPL book and some more problem instances)
- strimko2.cs: Strimko puzzle (Latin squares with "streams")
- sudoku.cs: Sudoku solver
- survo_puzzle.cs: Survo puzzle
Data files (same as for Python and Java above:
- to_num.cs: Channeling between a number and an array (useful for some alphametic problems)
- traffic_lights.cs: Traffic lights problem (CSPLib problem 16)
- volsay.cs: Volsay LP problem, LinearSolver (from OPL)
- volsay2.cs: Volsay LP problem, using arrays, LinearSolver (from OPL)
- volsay3.cs: Volsay LP problem, with components, LinearSolver (from OPL)
- who_killed_agatha.cs: Who killed agatha? (The Dreadsbury Mansion Murder Mystery, an automated reasoning problem)
- xkcd.cs: Solving the xkcd Knapsack problem
- young_tableaux.cs: Young tableaux and partitions
- zebra.cs: Zebra problem (Lewis Caroll)