" /> My Constraint Programming Blog: September 2013 Archives

« August 2013 | Main | February 2014 »

September 29, 2013

A first look at Picat programming language

For easy reference, here are the links to My Picat page and to my GitHub repo /picat.

Picat is a new programming language created by Neng-Fa Zhou and Jonathan Fruhman. The specification was published in December 2012. The first official (beta) release was in May 2013. Right from the beginning I liked this language and in this blog post I hope to show why. I should also say that the code shown here are not just for Constraint Programming, but also traditional backtracking (a la Prolog), tabling (memoization), imperative constructs etc, i.e. what makes Picat Picat.

The name Picat is an acronym and is explained in the quote below, borrowed from the Picat site:
Picat is a general-purpose language that incorporates features from logic programming, functional programming, and scripting languages. The letters in the name summarize Picat's features:
  • Pattern-matching: A predicate defines a relation, and can have zero, one, or multiple answers. A function is a special kind of a predicate that always succeeds with one answer. Picat is a rule-based language. Predicates and functions are defined with pattern-matching rules.
  • Imperative: Picat provides assignment and loop statements for programming everyday things. An assignable variable mimics multiple logic variables, each of which holds a value at a different stage of computation. Assignments are useful for computing aggregates and are used with the foreach loop for implementing list comprehensions.
  • Constraints: Picat supports constraint programming. Given a set of variables, each of which has a domain of possible values, and a set of constraints that limit the acceptable set of assignments of values to variables, the goal is to find an assignment of values to the variables that satisfies all of the constraints. The Picat system provides modules for different solvers with the same interface.
  • Actors: Actors are event-driven calls. Picat provides action rules for describing event-driven behaviors of actors. Events are posted through channels. An actor can be attached to a channel in order to watch and to process its events. In the future, Picat will treat threads as channels, and allow the use of action rules to program concurrent threads.
  • Tabling: Tabling can be used to store the results of certain calculations in memory, allowing the program to do a quick table lookup instead of repeatedly calculating a value. As computer memory grows, tabling is becoming increasingly important for offering dynamic programming solutions for many problems such as planning problems.
Of these general features, I have mostly tested pattern-matching, imperative programming constructs, constraints (of course!) and tabling, but have not played much with actors directly and will not mention them much here.

Some general Picat links: Let's start with some simple examples to show these features.

Constraints

First we show how to use constraints with send_more_money.pi, and we clearly see the influences of Prolog: 
import cp.

sendmore(Digits) =>
   Digits = [S,E,N,D,M,O,R,Y],
   Digits in 0..9,

   all_different(Digits),
   S #> 0,
   M #> 0,
          1000*S + 100*E + 10*N + D
   +      1000*M + 100*O + 10*R + E
   #= 10000*M + 1000*O + 100*N + 10*E + Y,
        
   solve(Digits).
Except for the => it looks very much like Prolog, right? I explain the => and how it's different from Prolog's :- later on and will also mention some other similarities/differences from/with Prolog.

Another mandatory example is sudoku.pi where we see more differences between traditional Prolog, i.e. the foreach loop: 
import cp.
import util.

go =>
   time2(sudoku(1)).

sudoku(ProblemName) =>
	problem(ProblemName, Board),
	print_board(Board),
	sudoku(3, Board),
	print_board(Board).

sudoku(N, Board) =>
   N2 = N*N,

   Vars = array_matrix_to_list(Board),
   Vars in 1..N2,

   foreach(Row in Board) all_different(Row) end,
   foreach(Column in transpose(Board)) all_different(Column) end.
   foreach(I in 1..N..N2, J in 1..N..N2)
      all_different([Board[I+K,J+L] : K in 0..N-1, L in 0..N-1])
   end,

   solve([ff,down], Vars).

print_board(Board) =>
   N = Board.length,
   foreach(I in 1..N)
      foreach(J in 1..N)
         X = Board[I,J],
         if var(X) then printf("  _") else printf("  %w", X) end
      end,
      nl
   end,
   nl.

problem(1, Data) => 
Data = [
    [_, _, 2, _, _, 5, _, 7, 9],
    [1, _, 5, _, _, 3, _, _, _],
    [_, _, _, _, _, _, 6, _, _],
    [_, 1, _, 4, _, _, 9, _, _],
    [_, 9, _, _, _, _, _, 8, _],
    [_, _, 4, _, _, 9, _, 1, _],
    [_, _, 9, _, _, _, _, _, _],
    [_, _, _, 1, _, _, 3, _, 6],
    [6, 8, _, 3, _, _, 4, _, _]].
What I have understood, these loops constructs was one of the reasons that Neng-Fa Zhou wanted to created a new language, since he wasn't satisfied with the foreach loops he implemented in B-Prolog. [You can compare many of my Picat models/programs with the one I implemented in B-Prolog earlier this year. See my B-Prolog page, e.g. sudoku.pl.] One thing that differs between Picat's foreach loops compared to B-Prolog's (as well as ECLiPSe's and SICStus Prolog's) is that the user don't have to explicitly declare the local (or global) variables which makes it simpler to use and read.

I will describe more CP in Picat below, but first I will describe some other Picat features.

Tabling

Tabling here refers to memoization ("caching the results"). A simple example of tabling is to start with this the standard recursive definition of a Fibonacci number: 
table
fibt(0)=1.
fibt(1)=1.
fibt(N)=F,N>1 => F=fibt(N-1)+fibt(N-2).
This is normally very slow for larger numbers because of the massive number of recursive steps needed. Using the table declaration before the predicate will automatically cache the calculated values and is used in subsequent calls.

An example of it's use is in euler2.pi (Project Euler #2), where the object is to find the sum of all even-valued terms in the sequence which do not exceed four million. Here is one way of implementing this, using list comprehension:q 
euler2 => 
   writeln(sum([F : N in 1..100, F = fibt(N), F < 4000000, F mod 2 =:= 0])).
Finding this sum takes 0.015s (with the overload of starting Picat etc). If we don't table the values then it's much (much!) slower: fibt(100) is 573147844013817084101 (~5.73e+20), which is about the number of recursions steps needed. By the way, here we see that Picat supports big integers as well.

Please note that tabling might in some cases be slower because of the memory overhead involved, so you have to be careful and test it.

Another example of tabling is for dynamic programming, for example calculating the edit distance. This example is from Picat's picat-lang.org/download/exs.pi: 
% computing the minimal editing distance
% of two given lists
table(+,+,min)
edit([],[],D) => D=0.
edit([X|Xs],[X|Ys],D) =>   % copy
    edit(Xs,Ys,D).
edit(Xs,[_Y|Ys],D) ?=>      % insert
    edit(Xs,Ys,D1),
    D=D1+1.
edit([_X|Xs],Ys,D) =>       % delete
    edit(Xs,Ys,D1),
    D=D1+1.
Another example is shortest distance (also from exs.pi): 
% mode-directed tabling
% finding shortest paths on a graph given by the relation edge/3.
table(+,+,-,min) 
sp(X,Y,Path,W) ?=>
    Path=[(X,Y)],
    edge(X,Y,W).
sp(X,Y,Path,W) =>
    Path=[(X,Z)|PathR],
    edge(X,Z,W1),
    sp(Z,Y,PathR,W2),
    W=W1+W2.

index(+,-,-) (+,+,-)
edge(1,2,1).
edge(1,3,2).
edge(2,3,3).
edge(3,2,4).

Imperative programming

Regarding loops, we have already seen the foreach loop in the Sudoku example. Picat has more imperative programming constructs: while loops and assignments.

The Fibonacci example shown above (Project Euler #2, using the list comprehension) has the drawback of a hard coded limit that checks all N in the range 1..100; this range was found by some experimentation and it's not the smallest range. In Picat it's also possible to use a while loop for this (though not as nice looking as the list comprehension version). This is traditional imperative programming. It also shows an example of (re)assignments using the := operator: 
euler2b => 
  I = 1,
  Sum = I,
  F = fibt(I),
  while (F < 4000000) 
     if F mod 2 == 0 then
        Sum := Sum + F
     end,
     I := I + 1,
     F := fibt(I)
  end,
  writeln(Sum).
This version also calculates the solution in 0.015s.

More Constraint Programming

Here are some more examples of CP in Picat.

Element constraint

In Picat, as in B-Prolog (and in many other CP systems), the element constraint (List[Ith]=Value) has to be written explicitly using the predicate element(Ith, List, Value) when Ith is a decision variables. However, if Ith is a plain integer, in Picat it can be stated more naturally as List[Ith] = Value or List[Ith] #= Value if List is a list of decision variables.

Older readers of this blog might remember that I sometimes whine how hard it is to write matrix element in different CP systems, and this applies to Picat as well. For example, in circuit.pi I would like to use this construct but it's not allowed: 
foreach(I in 2..N)
  % this is not allowed
  Z[I] = X[Z[I-1]]
end
Instead, one have to rewrite it. Here's my version: 
import cp. 

% ...

foreach(I in 2..N)
   Z1 #= Z[I-1],
   element(Z1,X,X2),
   Z[I] #= X2
end,
In stable_marriage.pi a more general version, matrix_element, is used: 
matrix_element(X, I, J, Val) =>
  element(I, X, Row),
  element(J, Row, Val).
This version (using two element) can be very good sometimes, but depending on the type of the variables some of these variants might be used; sometimes I have to test them all. Also, they are never active at the same time, but deactivated by comments (as shown in the example): 
import cp.

% ...

matrix_element(X, I, J, Val) =>
  element(I, X, Row),
  element(J, Row, Val).

% matrix_element(X, I, J, Val) =>
%   nth(I, X, Row),
%   element(J, Row, Val).

% matrix_element(X, I, J, Val) =>
%   freeze(I, (nth(I, X, Row),freeze(J,nth(J,Row,Val)))).

% matrix_element(X, I, J, Val) =>
%   freeze(I, (element(I, X, Row),freeze(J,element(J,Row,Val)))).
The freeze(X, Call) predicate delays the call to Call until X becomes a non-variable term.

alldifferent_except_0

Picat supports reifications with the nice syntax I expect from a high level CP system. Note that #/\ is "and" for FD variables. Here is the alldifferent_except_0 constraint (see alldifferent_except_0.pi for the full model): 
import cp.

alldifferent_except_0(Xs) =>
   foreach(I in 1..Xs.length, J in 1..I-1)
      (Xs[I] #!= 0 #/\ Xs[J] #!= 0) #=> (Xs[I] #!= Xs[J])
    end.

N-queens

Below are some different implementations of N-queens, taken from nqueens.pi. 
import cp.

queens3(N, Q) =>
   Q=new_list(N),
   Q in 1..N,
   all_different(Q),
   all_different([$Q[I]-I : I in 1..N]),
   all_different([$Q[I]+I : I in 1..N]),
   solve([ff],Q).

% Using all_distinct instead
queens3b(N, Q) =>
    Q=new_list(N),
    Q in 1..N,
    all_distinct(Q),
    all_distinct([$Q[I]-I : I in 1..N]),
    all_distinct([$Q[I]+I : I in 1..N]),
    solve([ff],Q).

queens4(N, Q) =>
   Q = new_list(N),
   Q in 1..N,
   foreach(A in [-1,0,1])
      all_different([$Q[I]+I*A : I in 1..N])
   end,
   solve([ff],Q).
Note that in queens3 we have to use $Q[I]-I (i.e. prepended with a $) since since it's an expression that should be evaluated ("escaped").

Now we can do some benchmark on different variants (the model nqueens.pi also includes some variants not shown here) with different N for some of the variants. This is merely to show a use of the meta predicates (time2, once, and call). 
go3 => 
   Ps = [queens3=1000, queens3b=1000, queens4=100,queens5=100, queens6=13],
   foreach(P=N in Ps) 
      printf("%w(%d)\n", P, N),
      time2(once(call(P,N,Q))),
      writeln(Q),
      nl
   end.
queens3(1000) takes 4s and 2 backtracks, queens3b takes 9.9s and 0 backtracks. Not extremely fast, but quite good.

While we're at it, here is one way of benchmarking the time and number of backtracks for one of the methods (predicate queen3_all in nqueens.pi) for getting all the solutions for N from 2 to 14. statistics/2 is used to get the number of backtracks and run time for each run: 
go2 => 
   foreach(N in 2..14) 
      statistics(backtracks, Backtracks),
      statistics(runtime, [_, _Runtime1]),
      queens3_all(N, Solutions),
      Len=Solutions.length,
      statistics(backtracks, Backtracks2),
      B = Backtracks2 - Backtracks,
      Backtracks := Backtracks2,
      statistics(runtime, [_, Runtime2]),
      writef("N:%3d %10d solutions (%d backtracks, %d millis)\n", N, Len, B, Runtime2)
   end.
The result: 
N:  2          0 solutions (1 backtracks, 0 millis)
N:  3          0 solutions (2 backtracks,k 0 millis)
N:  4          2 solutions (5 backtracks, 0 millis)
N:  5         10 solutions (13 backtracks, 0 millis)
N:  6          4 solutions (39 backtracks, 0 millis)
N:  7         40 solutions (107 backtracks, 0 millis)
N:  8         92 solutions (383 backtracks, 0 millis)
N:  9        352 solutions (1477 backtracks, 4 millis)
N: 10        724 solutions (5715 backtracks, 4 millis)
N: 11       2680 solutions (24475 backtracks, 48 millis)
N: 12      14200 solutions (116081 backtracks, 232 millis)
N: 13      73712 solutions (588949 backtracks, 1340 millis)
N: 14     365596 solutions (3195965 backtracks, 7472 millis)

Magic square

This is a magic squares implementation in Picat, taken from magic_square.pi. One thing to notice is the use of rows(), columns(), diagonal1(), and diagonal2() from the util module. 
import cp.
import utils.

magic2(N,Square) =>
   writef("\n\nN: %d\n", N),
   NN = N*N,
   Sum = N*(NN+1)//2,% magical sum
   writef("Sum = %d\n", Sum),

   Square = new_array(N,N),
   Square in 1..NN,

   all_different(Square),

   foreach(Row in Square.rows()) Sum #= sum(Rows) end,
   foreach(Column in Square.columns()) Sum #= sum(Column) end,

   % diagonal sums
   Sum #= sum(Square.diagonal1()),
   Sum #= sum(Square.diagonal2()),

   % Symmetry breaking
   Square[1,1] #< Square[1,N],
   Square[1,1] #< Square[N,N],
   Square[1,1] #< Square[N,1],
   Square[1,N] #< Square[N,1],

   solve([ffd,updown],Square),

   print_square(Square).

Magic sequence

Another standard CP problem is magic_sequence.pi: 
import cp.

magic_sequence(N, Sequence) =>
   writef("\n%d: ",N),
   Sequence = new_list(N),
   Sequence in 0..N-1,
   foreach(I in 0..N-1) count(I,Sequence,#=,Sequence[I+1]) end,
   N #= sum(Sequence),
   Integers = [ I : I in 0..N-1],
   N = scalar_product(Integers, Sequence),
   solve([ff], Sequence).

scalar_product(A, X) = Product => 
   Product #= sum([S : I in 1..A.length, S #= A[I]*X[I]]).
Note that I tend to use count(Var, Vars, Relation, N) instead of the built-in global_cardinality(List, Pairs) since it's more natural for me.

Least diff problem, optimization

The Least diff problem is a simple optimization problem in Picat: Minimize the difference between ABCDE-FGHIJ where the letters A..J are distinct integers (in the domain 0..9). 
import cp.

least_diff(L,Diff) =>
  L = [A,B,C,D,E,  F,G,H,I,J],
  L in 0..9,

  all_different(L),

  X #= 10000*A + 1000*B + 100*C + 10*D + E,
  Y #= 10000*F + 1000*G + 100*H + 10*I + J,

  Diff #= X - Y,
  Diff #> 0,
  solve([$min(Diff)], L).
The interesting part is the objective $min(Diff) (note the "$") which defines the objective value.

For more advanced models one can use the $report(Goal) to show the progress of the objective. Here is an example from einav_puzzle.pi: 
   solve($[min(TotalSum), report(printf("Found %d\n", TotalSum)), ffd],Vars),
Without report(Goal) the solution is only shown after the solver has finished the search which may take considerable time.

Global constraint table

Picat has a table constraint: the in construct (in is also used to define the domain of a decision variables). Here is a simple example using table constraint: traffic_lights.pi (CSPLib #16) which use the list Allowed to state which combinations are allowed. 
import cp.

traffic_lights_table(V, P) =>
  N  = 4,
  % allowed/1 as a table (translated)
  Allowed = [(1,1,3,3),
                (2,1,4,1),
                (3,3,1,1),
                (4,1,2,1)],
   
   V = new_list(N),
   V in 1..N,
   P = new_list(N), 
   P in 1..N,
   foreach(I in 1..N, J in 1..N)
      JJ = (1+I) mod N,
      if J #= JJ then
         VI = V[I], PI = P[I],
         VJ = V[J], PJ = P[J],
         % Table constraint
         (VI, PI, VJ, PJ) in Allowed
      end
   end,
   Vars = V ++ P,
   solve(Vars).
The use of in - as a table constraint - requires that the values are integers so we have to translate to/from integers in this version. The model (traffic_lights.pi) also contain some other approaches of this problem that don't use the table constraint.

Another example of table constraint is hidato.pi (though it's not very efficient).

Global constraints

Picat supports the most common global constraints as shown in the list below. See Picat Guide, section 11.5 for details.
  • all_different(List)
  • all_distinct(List)
  • assignment(List) (a.k.a. inverse)
  • circuit(List)
  • count(Value,List,Rel,N)
  • cumulative(Starts,Durations,Resources, Limit)
  • diffn(RectangleList)
  • disjunctive_tasks(Tasks)
  • element(I,List, V)
  • global_cardinality(List, Pairs) (I tend to use this not so much since it's not as natural as using count/4)
  • neqs(NegList)
  • serialized(Starts,Durations)
  • subcircuit(List)
  • in used as the global constraint table (not to be confused with tabling=
In the module cp_utils.pi, I have also defined some other useful decompositions of global constraints:
  • matrix_element (some different versions)
  • to_num
  • latin_square
  • increasing
  • decreasing
  • scalar_product (with a relation)
  • alldifferent_except_0
  • nvalue
  • nvalues
  • global_cardinality(Array, GccList)
  • lex2, lex2eq, lex_less, lex_lesseq, lex_greater, lex_greatereq, lex_less2 (alternative hack)
Labeling: Most of the standard variable and value heuristics are supported, though I miss random variants. Some of the examples above show how to label the variables in the solve predicate. Here the ff is first-fail variable labeling, and down means that a variable is labeled from the largest value to the smallest. 
solve([ff,down], Vars)
See the Picat Guide documentation for more description of the options to solve and other solver options.

Pattern matching

Pattern matching is Picat is more influenced by the pattern matching in functional programming than by Prolog's unification. This may confuse some programmers with a Prolog background.

Here is a definition of quick sort which shows some of the pattern matching constructs of Picat, and also shows how to define functions, i.e. predicates with return value. 
qsort([])    = L => L = [].
qsort([H|T]) = L => L = qsort([E : E in T, E =< H]) ++ [H] ++
                        qsort([E : E in T, E > H]).
The two functions drop and take (standard in functional programming) can be defined as: 
drop(Xs,0) = Xs.
drop([],_N) = [].
drop([_X|Xs],N) = drop(Xs,N-1).

take(_Xs,0) = [].
take([],_N) = [].
take([X|Xs],N) = [X] ++ take(Xs,N-1).
Reverse can be defined as: 
reverse(L1,L2) => my_rev(L1,L2,[]).
my_rev([],L2,L3) => L2 = L3.
my_rev([X|Xs],L2,Acc) => my_rev(Xs,L2,[X|Acc]).
As will be mentioned again below, the matching between different variables - or part of variables - is often done in the body and not in the rule part. Here is an example from 99_problems.pi showing that (the problem is "% P09 (**): Pack consecutive duplicates of list elements into sublists.") 
% pack(L1,L2) :- the list L2 is obtained from the list L1 by packing
%    repeated occurrences of elements into separate sublists.
%    (list,list) (+,?)

pack([],Y) => Y = [].
pack([X|Xs],[Z|Zs]) => transfer(X,Xs,Ys,Z), pack(Ys,Zs).
pack(X1,Z1) => X1=[X|Xs],Z1=[Z|Zs],transfer(X,Xs,Ys,Z), pack(Ys,Zs).
There are more comments about pattern matching below.

Nondeterminism and other Prolog influences (and differences)

Some of the examples above show clear influences from Prolog. Here we list some more influences (and differences).

Picat has - as Prolog has - support for nondeterminism using a backtracking mechanisn to test different predicates as will be seen below. This is a really great feature in Picat and is one of the reason I like Picat so much. Or rather: it is the combination of the backtracking possibility together with the imperative features, support for constraint programming etc that I really like in Picat.

member

The nondeterministic member predicate in Picat works as in Prolog, i.e. can be used both as a test for membership and also for generating all the elements: 
Picat> member(2, [1,2,3])
yes
Picat> member(4, [1,2,3])
no
Picat> member(X, [1,2,3])
   X=1;
   X=2;
   X=3;
   no
As in Prolog we can get the next solution with a ; (semicolon) in the Picat shell.

This double nature version of member can be defined in Picat as: 
member(X,[Y|_]) ?=> X=Y.
member(X,[_|L]) => member(X,L)
In this definition we see two features of Picat:
  • pattern matching: the pattern [Y|_] matches any list and "extracts" the first elements Y to be matched against X in the first clause.
  • backtracking: The first rule is defined as a backtrackable rule using ?=> (the prepending "?" is the marker for backtrackable rules) and makes the call nondeterministic. The last rule in a definition should be stated as non-backtrackable, i.e. => (without the ?).
This predicate now works in the same way as the built-in member/2.

Predicate facts

Predicate facts are bodyless definitions akin to Prolog's "data definition" (but be careful to take this too literary).

Predicate facts are prepended by index declararion to make them accessible as data (and this is one difference from Prolog). For example, here is a stripped down version of the transitive closure example transitive_closure.pi (ported from B-Prolog program transitiveRight.pl): 
top ?=> 
    reach(X,Y),
    writeln([X,Y]),
    fail.
top => true.

% Transitive closure right
table
reach(X,Y) ?=> edge(X,Y).
reach(X,Y)  => edge(X,Z),reach(Z,Y).

% the graph
index(-,-)
edge(1,2).
edge(1,3).
edge(2,4).
edge(2,5).
edge(3,6).
% ....
Note the use table to cache the reach predicate. In this simple example it is not needed, but for other applications it might be a great advantage.

append

append in Picat is also nondeterministic as in Prolog. Here is an example where we get the different X and Y that makes up the list [1,2,3,4]. Collecting all the results is done with findall which will be discussed a little more below: 
Picat> Z=findall([X,Y], append(X, Y, [1,2,3,4]))    
Z = [[[],[1,2,3,4]],[[1],[2,3,4]],[[1,2],[3,4]],[[1,2,3],[4]],[[1,2,3,4],[]]]
As with member, we can define it on our own: 
append(Xs,Ys,Zs) ?=> Xs=[], Ys=Zs.
append(Xs,Ys,Zs) => Xs=[X|XsR], append(XsR,Ys,Zs).

findall

As we saw an example above findall in Picat works much as in Prolog. One difference is that findall in Picat is a function, i.e. returns a value and that is why it was assigned to the Z variable above.

Other nondeterministics predicates

Here are the built-in nondeterministic predicates in Picat. They are mostly wrappers to the underlying B-Prolog predicates.
  • between(From, To, X)
  • append(X,Y,Z)
  • append(W,X,Y,Z)
  • member(Term, List)
  • select(X, List, ResList)
  • find(String, Substring, From, To)
  • find_ignore_case(String, Substring, From, To)
  • repeat
  • permutation(List, Perm)
  • nth(I, List, Val)
  • indomain(Var) (CP)
  • indomain_down(Var) (CP)
  • solve(Vars) (CP)
  • solve(Options, Vars) (CP)
  • statistics(Name,Value)
One can also note that - in contrast to Prolog - length is a "plain" predicate and do not creates a list. It just returns the length of the list (array, structure). (For defining av new list one have to use new_list(Length) instead.)

The nondeterministic predicates are great when they are needed, but don't overuse them. The Picat documentation generally recommend to write functions rather than predicates since functions are easier to debug since they return exactly one value.

An advince to Prolog addicts

In general, Prolog addicts should be a little careful when trying to direct write Prolog code in Picat. Sometimes it work very well to write it as in Prolog (with some minor modifications) but sometimes it don't work. The biggest gotcha is probably pattern matching - as mentioned above - which look much like Prolog's unification but is more like the pattern matching used in functional languages such as Haskell.

SAT-solver

Picat also support solving problems using a SAT solver using almost exactly the same code as using the CP solver. The only thing one might need to change is 
import cp.
to 
import sat.
However, the SAT solver don't support all the global constraints from the CP solver, but it might be worth testing sometimes, since it can be very fast compared to a CP approach. [Still, I tend to rely on CP since then I can get all the solutions - or two - which is not possible with the SAT solver used in Picat.]

Also, I haven't use the SAT solver very much. See Neng-Fa's (and others) use at Projects sections, e.g. numberlink_b.pi and mqueens.pi (it is one of the problems from the CP-2013 Model and Solve Competition).

Planning

One of the things I really like in Picat is that it is now easy to implement certain planning problems. I first wrote a small planning module (bplan.pi, inspired by Hector J. Levesque's version "Thinking as Computation", a rather new Prolog AI book). Neng-Fa later build a much richer module planner with a lot of different variants both optimality versions (best_plan*) and non-optimality versions, both bounded and unbounded, and both with and without costs.

The planning module is quite simple to use:
  • Define the action predicates (the legal moves): action(FromState, ToState, Move, Cost)
  • Define the initialization state (the first FromState)
  • Define the goal state(s)/definition: final(State) that check if the goal state has been reached.
  • call the plan* predicate with the appropriate arguments
A simple example is the M12 problem (test_planner_M12.pi) which has
  • two actions: merge (perfect shuffle) and reverse
  • initial state (the problem instance), e.g. [8,11,6,1,10,9,4,3,12,7,2,5]
  • the goal state: [1,2,3,4,5,6,7,8,9,10,11,12]
Here is the code for the planner part. Using the table directive is often a booster in these kind of planning problems, but not always: 
go =>
  Init = [8,11,6,1,10,9,4,3,12,7,2,5],
  time(best_plan_downward(Init, Plan)),
  writeln(Plan),
  writeln(len=Plan.length),
  nl.

final(Goal) => Goal=[1,2,3,4,5,6,7,8,9,10,11,12].

table
% merge move
action([M1,M12,M2,M11,M3,M10,M4,M9,M5,M8,M6,M7], To, M, Cost) ?=>
   Cost=1, M=m,To=[M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12],Cost=1.
% reverse move
action([M12,M11,M10,M9,M8,M7,M6,M5,M4,M3,M2,M1], To,M, Cost) => 
   Cost=1, M=r,To=[M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12],Cost=1.
As mentioned above, it's important to declare the first action with ?=> so it is backtrackable, i.e. that if that clause fails it will backtrack and test the next rule.

Picat finds the shortest solution (27 steps) in 1.8s: [m,m,m,r,m,m,m,r,m,m,m,m,r,m,r,m,r,m,m,r,m,m,r,m,m,m,r] where "m" refers to the merge action/move, and "r" to the reverse action/move.

For a maze problem, the action (move) is simply defined as 
action(From,To,Move,Cost) => 
   maze(From,To),
   Move = [From,To],
   Cost = 1.
where maze(From,To) defines which nodes that are connected. And that is about as simple as it could be.



For these kind of "straight" planning problems it's - IMHO - much easier to use this approach in Picat that using Constraint Programming. However, if the problem has a lot of extra constraints then CP might be both easier to write and faster.

My other planning models are here, mostly quite simple standard problems. Neng-Fa has written more advanced programs, shown at the Projects page. One neat example is his solution of the Doubleclock problem from the CP-2013 competition: doubleclock.pi which solves each of the five problem instances in about 0.1s (except for #4 which takes 0.6s).

File handling

Here is an example that use file handling (and some string handling) in Picat. It's the Project Euler problem #96 where the object is to sum the 3-digit number found in the top left corners of fifty Sudoku problems. See euler96.pi for the full encoding. 
import util.
import cp.

% ...

euler96 =>
  Sudokus = read_file("sudoku.txt"),
  Total = 0,
  foreach(S in Sudokus) 
     Solved = sudoku(3, S),
     Total := Total + [Solved[1,J].to_string() :
                        J in 1..3].flatten().parse_term()
  end,
  println(Total),
  nl.

convert(Sudoku) = [[ R.to_integer() : R in Row] : Row in Sudoku].

sudoku(N, Board) = Board2 =>
  % see above

read_file(File) = Sudokus => 
   FD = open(File),
   Sudokus = [],
   Sudoku = [],
   C = 0,
   while (not at_end_of_stream(FD))
      Line = read_line(FD),
      if once(find(Line, "Grid",1,_To)) then
         if C > 0 then Sudokus := Sudokus ++ [Sudoku.convert()] end,
          Sudoku := [],
          C := C + 1
      else
          Sudoku := Sudoku ++ [Line]
      end
   end,
   % the last
   Sudokus := Sudokus ++ [Sudoku.convert()],
   close(FD).
It solves the problem in 0.03s.

This way of handling files is much easier than in standard Prolog, but perhaps not as easy as in more agile programming languages. However, Picat also have some "slurp" variants that reads the complete file into a variable: read_file_bytes, read_file_lines, and read_file_terms.

Structure and Map (hash table)

Picat has a construct for creating a structure - new_struct (a kind of poor mans OOP "object"), though I don't use this much. Here is a small example: 
Picat> S = new_struct(point,3), Name = S.name, Len = S.length
S = point(_3b0,_3b4,_3b8)
Name = point
Len = 3
A data structure that I use much more is the inevitable map (hash table): 
Picat> M = new_map([one=1,two=2]), M.put(three,3), One = M.get(one)
Here is a longer example (from one_dimensional_cellular_automata.pi) which use a map (Seen) to detect fixpoint and cycles in the evolution of the patterns, i.e. if we seen the pattern before. It use new_map() for creating the map, has_key(S) for checking if pattern S already exists in the map, and put(S,1) to add the pattern S to the map. Also note the definition of the rules as predicate facts. 
go =>
     %    _ # # # _ # # _ # _ # _ # _ # _ _ # _ _
     S = [0,1,1,1,0,1,1,0,1,0,1,0,1,0,1,0,0,1,0,0],
     All = ca(S),
     foreach(A in All) println(A.convert()) end,
     writeln(len=All.length),
     nl.

convert(L) = Res =>
    B = "_#",
    Res = [B[L[I]+1] : I in 1..L.length].

ca(S) = All => 
   Len = S.length,
   All := [S],
   Seen = new_map(), % detect fixpoint and cycle
   while (not Seen.has_key(S))
      Seen.put(S,1),
      T = [S[1]] ++ [rule(sublist(S,I-1,I+1)) : I in 2..Len-1] ++ [S[Len]],
      All := All ++ [T],
      S := T
   end.

% the rules
index(+)
rule([0,0,0]) = 0. % 
rule([0,0,1]) = 0. %
rule([0,1,0]) = 0. % Dies without enough neighbours
rule([0,1,1]) = 1. % Needs one neighbour to survive
rule([1,0,0]) = 0. %
rule([1,0,1]) = 1. % Two neighbours giving birth
rule([1,1,0]) = 1. % Needs one neighbour to survive
rule([1,1,1]) = 0. % Starved to death.

Strings

There are some support for strings in Picat, such as
  • ++ (for list/string concatenation)
  • atom_chars(Atom)
  • find(String, Substring,From,To) (nondet)
  • find_ignore_case(String, Substring,From,To)
  • join(Tokens)
  • join(Tokens,Separator)
  • number_chars(Num)
  • parse_term(String)
  • split(String)
  • split(String, Separators)
  • to_atom(String)
  • to_binary_string(Int)
  • to_lowercase(String)
  • to_uppercase(String)
  • to_string(Term)
Unfortunately there is not yet any support for regular expressions (I use regexps quite much in other programming languages for my "daily programming") and I hope that will come soon enough. However, since a string is (just) an array of characters much of the general list handling can be used for manipulating strings.

Other features in Picat

Picat has many other features not much mentioned in this blog post, for example:
  • debugging and trace, akin to Prolog's debug facilities
  • os module for handling files and directories (see above for some file reading)
  • math module for standard math functions. I tend to use only primes(Int), prime(Int) and the random* predicates from this module.
There are also many other useful predicates that is not mentioned here. See the Picat User's Guide for more about these.

Missing in Picat

Since Picat is such a new programming language there are some missing features that will - hopefully - come later, though I don't know the exact time lines.

MIP solver

A forthcoming project is to add a MIP solver to Picat.

C/Java interface

Another planned project is to add C and/or Java interface to Picat. Then it will probably be easier to add features such as regular expressions, http/tcpip access etc.

Some other utilities

Here are some few utilities that I tend to use.

Get N solutions, given a goal Goal

Sometimes one just want to find some specificed number of solutions, for example for debugging purposes. There is not built-in support for this in Picat, so I've written this following simple ersatz predicate. It use the global get_global_map for putting and checking the number of solutions so far; if the number of solutions are not yet reached it fails which give a new solution. 
get_n_solutions(Goal, N) =>
  printf("Get %d solutions:\n", N),
  get_global_map().put(solcount,1), 
  time2(Goal), % run the Goal
  C = get_global_map().get(solcount),
  if C < N then get_global_map().put(solcount,C+1), fail end.

Running Picat, start parameters

When running Picat programs/models, I often want to test with different predicates. Picat just support one start parameter, main, which is called by the picat executable. Let's call the program program1.pi to the discussion more concrete. 
main => go.

go =>
  println("This is a Picat program.").

go2 =>
  println("This is another predicate.").
When running the Picat program like this: 
  $ picat program1.pi
Picat checks if the predicate main is defined and if so calls it, which in this case calls the go predicate.

However, there is no current support of calling the go2 predicate (i.e. predicates not defined in the main predicate) via the command line. Therefore I've done this Linux shell script (picat_run) for that. Note: you should to change the path in PICAT_ME. 
#!/bin/sh
#
# This is just a wrapper for running the 
#    picat run_program.pi picat_program arg1 [arg2]
#
PICAT_ME=/home/hakank/picat/me
RUN_PROGRAM=${PICAT_ME}/run_program.pi
if [ "$#" -eq 1 ]; then
   picat $RUN_PROGRAM $@ go
else
   picat $RUN_PROGRAM $@
fi
If running without a parameter it runs with the go predicate (which is my default predicate name).

The shell program runs the Picat program run_program.pi, simply defined as: 
main([Program|Goals]) =>
   println(program=Program),
   % compile and load the program
   cl(Program), 
   foreach(Goal in Goals) 
     nl,
     % convert the goal string to an atom
     G = parse_term(Goal), 
     println(goal=Goal),
     G.call()
   end.
Using this we can now run the go2 predicate: 
  $ picat_run program1.pi go2
The magic is done with cl(Program) (which compiles and loads the program) and parse_term(Goal) which converts the Goal (the parameter string from the command line) to an atom G which is then called via call.

Right now this can use only handle simple predicates (with constants as arguments), but cannot execute code that involves variables etc. I hope that later version of Picat will have this as a built-in parameter.

Project Euler benchmark

Whenever a new version of Picat is out, I test and benchmark it with my 50 Euler programs. Here is one way of testing this (test_euler.pi) 
go =>
  Skip1 = ["euler67.pi","euler.pi","euler_utils.pi","test_euler.pi",
           "euler51.pi","euler66.pi","euler96.pi"],
  Skip = new_map([(S=1) : S in Skip1]), 
  Timeout = 10000, % 10s timeout
  Programs = [PP : PP in listdir("."), 
              match(PP, "euler"), 
              match(PP, ".pi")].sort(),
  Fails = [],
  foreach(P in Programs) 
     if not Skip.has_key(P) then
       printf("Testing %w\n", P),
       cl(P),
       time_out(time(go), Timeout, Status),
       println(status=Status),
       if status==Timeout then
           Fails := Fails ++ [P]
       end,
       nl
     end
  end,
  println(fails=Fails),
  nl.

match(String, Substring) => once(find(String,Substring,_,_)).
The interesting part is in bold, i.e. the loading and testing the program as well as the timeout check.

To be honest, I often do these tests with another program instead, which also checks that the the correct answers are shown and also reports different other things. Since I don't want to display the solutions to the Project Euler problems this program is not public. Sorry about that.

FlatZinc solver

Neng-Fa started to write a FlatZinc solver (originally a translation of his FlatZinc solver i B-Prolog) some weeks before the MiniZinc Challenge and I helped a bit with testing and added some functionality. Interestingly, Picat was the only logic programming based submission this year. However, it didn't go very well: in fact we came last in all the different categories. Well, it was fun doint this and to be in the challenge. The FlatZinc solver can be downloaded from the Projects page.

My contributions to Picat

Picat was originally created by Neng-Fa Zhou and Jonathan Fruhman. After the release in May this year, I have done some contributions to the code as well as bug reports, suggestions etc, and are now sometimes mentioned as one of the Picat developers/collaborators. Note that I just develop things in Picat, not in the C or B-Prolog level. Some of the modules I've contributed that are in the Picat distribution are:
  • util.pi: One of the utilities modules
  • picat_lib_aux.pi: Utilities used by other modules
  • apl_util.pi: Utilities inspired by the languages APL and K. Most of this is as a proof-of-concept.
  • set_util.pi: Set utilities (ported from Neng-Fa's set utilities in B-Prolog)
Also, many of the Project Euler programs above #20 at the Project page are mine. See also my own collection where I have different variants for the problems below #20.

And see below for a list of the almost 400 public Picat programs/models I've done so far.

Models

Here are all my current public Picat models/programs. They are also available from my Picat page and my GitHub repo. I have categorized them in different groups since I guess that Picat might attract different target groups.

Constraint Programming

Here are models that mainly use Constraint Programming (import cp.).

Project Euler problem

Here are some solutions for the Project Euler problems:
Total time for running all problems #1..#50 is < 14 seconds (on my Linux Ubuntu 12.04, 8 core Intel i7 CPU 930@2.80GHz). Some programs contains several alternative solutions.

test_euler.pi: Simple Picat program for testing all the Project Euler programs (#1..#50).

Rosetta Code problem

Picat solutions for some Rosetta Code problems.

Miscellaneous problem

Here are some other programs, modules, utilities, e.g. standard Prolog/GOFAI examples etc.

Posted by hakank at 08:10 PM |

September 28, 2013

CP2013: Jacob Feldman blogs about the CP Solver workshop

In his blog post After CP-2013 Jacob Feldman writes about the workshop CP Solvers: Modeling, Applications, Integration, and Standardization (CPSOLVERS). He summarizes the workshop in general and some of the discussions we had, and also mentions the CP Solver Catalog (that he initiated some months before the conference).

Jacob has a plea about the details of the discussions:
It’s hard for me to reproduce all answers and I want to invite all CPSOLVERS-2013 panelists and other CP practitioners to provide their answers as comments to this post.
I also agree with Jacob's end paragraphs:
Overall, I think the workshop has actually provided us with an industrial overview of CP products that was its main objective. We plan to get such overviews every 4 years – so I hope to see many authors of current and brand new CP tools at CPSOLVERS-2017.

P.S. I want to thank CP-2013 organizers for their constant support and a great organization of the conference.

Posted by hakank at 11:00 AM |

September 27, 2013

Charles Prod'homme blogs about developing Choco

One week ago, Charles Prod'homme (one of the main developers of the Choco CP system) started the blog Within a Constraint Solver. His first blog post was this:
With this blog I would like to share the good and bad ideas we've had (and have) while developing our constraint solver. As we almost started from scratch, there could be articles about every part of the solver. If you don't know what Constraint Programming is, wikipedia is a good start point.

Since 2008, I've been working on Choco, a Java library for constraint programming. Articles from this blog will mostly talk about the choices made from the version 2 to version 3, but not only.
Welcome to the CP blog sphere, Charles!

A side note: Some days before Charles started his blog, I held a talk at CP-2013 Workshop CP Solvers: Modeling, Applications, Integration, and Standardization, and one of the things I mentioned was that it would be great if there where more CP bloggers to explain what Constraint Programming is and why we are so fascinated by it. I'm not sure is there is some cause and effect here or just a happy coincidence. :-)

If you are interested, here is my talk: CP Solvers/Learning Constraint Programming, and here's Charles' talk at the workshop: Choco3: an Open Source Java Constraint Programming Library.

Posted by hakank at 07:22 PM |

CP-2013: Presentation slides from the talks

The presentation slides for many CP-2013 talks are now available from the Schedule page.

Posted by hakank at 07:01 PM |

September 23, 2013

CP2013: Photos from the conference

After a failing publishing some of my CP-2013 photos at my Google+ page, I have now collected them all at a special page: hakank.org/constraint_programming/cp2013/pictures/. They have been collected per day,: Please note:
  • The photos are large and are simply scaled at the presentation page. Click on the photo to get a larger version with proper ratio.
  • Many of the photos are not good but still kept since they are mementos. It's mostly because I didn't realized that using maximum zoom on my camera easily give distortions, especially with unsteady hands. Sorry about that.
  • They are not labeled in any way, though they all have time stamps which might give some clues of the target.
And if you study the slides that I photographed, you get a hint in what areas of CP I'm most interested in. :-)

Posted by hakank at 07:49 PM |

September 22, 2013

CP2013: Ian Gent blogs about the Lightning Model and Solve Competition

Ian Gent, a member of the winning team (Mano) in the First International Lightning Model and Solve Competition this conference, has just published a blog post about how and why he and his team won: How I became one of the three "best optimizers in the world".

Ian writes very interesting details about how the team approached the problems, why they decided to solve all problems by hand, etc. I like Ian's conclusions:
What Have We Learnt For Constraint Programming?

One word. Modelling.

To expand, Modelling is hard.

To expand, we need better tools to make it easier to model constraint problems quickly. Every group should have been able to use a simple constraints tool to model the easier problems (like queens) and then get on with the other ones.

This is what I take away, and it's nice that this is research that we in St Andrews are already doing, so I hope we can push this harder after this experience.
As one of the organizers of the competition, I also thank Ian for this comments about what we can do better the next time. [This means that I have read it, but will not promise anything. :-)]

Also, see my summary of the competition: CP-2013: The Conference Day 3 (Thursday) and CP-2013: Competition problems, rules, and instances.

Posted by hakank at 09:11 PM |

September 21, 2013

CP-2013: The Conference Day 4 (Friday)

Friday, Day 4 (last day

After yesterday's quite hectic agenda, today was was - for me at least - a much more relaxed day. Though the organizers and the organge guys was busy to the last minute.

First, I would like to thank all the organizers and the "volunteers" [the quotes was official] for a really well organized and interesting conference. It was my first CP-conference so I didn't really know what to expect, but it was just fun being there, both for the talks but also to meet and discuss CP with the leading experts in the field (or just listening to their discussions).

So, the day was fun and started with the invited talk by Torsten Schaub on ASP (Answer Set Programming), which is a paradigm different from CP in details but quite close in goals and some principles. The system mentioned was Potassco. You can see more about it at my Answer Set Programming page.

After Torsten's talk was the Modeling track with very interesting talks, and I especially liked the CP systems talks : Ozgur Akgun talked about Automated Symmetry Breaking and Model Selection in Conjure. More about Conjure is here.

After that Daniel Fontaine talked about "Model Combinatorics for Hybrid Optimization" in Objective-CP (sorry there is no link to Objective-CP yet) and then Kevin Leo about "Globalizing Constraint Models", a project which tries to automatically make more efficient MiniZinc models.

The tutorial by Phil Kilby about CP for Vehicle Routing Problems was very inspiring. He explained a general CP model which can solve many of the different VRP problems. Really interesting and important stuff.

Last session for the day, and the conference, was "Global Constraints and Conflicts" with four talks which - I have to admit - sometimes was a bit over my head. Though I think that the results they showed was quite impressive.

And the conference is now all. Again, thanks for organizing this! And thanks to all wonderful, inspiring, and bright people in the CP world.

This is last daily report blog post as the CP-2013's official blogger. Hope you have enjoyed it as much as I when writing it; blogging is a great way to digest things. Feel free to contact me in CP related matters: hakank@gmail.com.

Oh, I almost forgot today's first greetings with e-contacts (with a slightly extended meaning of e-contacts): Torsten Schaub, Toby Walsh, Christopher Mears, Roland Yap, Thibaut Feydy.

Posted by hakank at 12:29 AM |

September 20, 2013

CP-2013: Competition problems, rules, and instances

Here are the CP-2013 competition problems (with some small corrections by Peter Stuckey): cp2013_competition_20130919.pdf. The rules might also be interesting to read to see the conditions of the competition: cp2013_competition_rules_20130919.pdf. The problem instances are here: cp2013_competition_instances_20130919.zip and are named as "problem_instance.dzn", where instance 0 is the instance that's shown in the problem documentation.

If you have a nice model (in CP or some other paradigm) that solves the competition instances on any of the problems, feel free to mail me at hakank@gmail.com. If I got more than a few models/programs, I might put them on a web page.

Have fun!

Update 2013-09-24: The problem document, the rules, and the instances has now been added to the competition page. Thanks, Guido.

Posted by hakank at 11:20 PM |

September 19, 2013

CP-2013: The Conference Day 3 (Thursday)

Thursday, Day 3

Today was an exciting and hectic day. It started with Pascal Van Hentenryck and Laurent Michel presented Objective-CP, a CP system (in progress) built in Objective-C. It looked very versatile and flexible so it will be really fun testing it, even though I haven't written a single line of code in Objective-C. (Right after I read the paper I ordered a book in Objective-C just to be prepared.)

One other talk I enjoyed very much today was Tias Guns ACP Doctoral Research Award talk: "Declarative Pattering Mining Using Constraint Programming". The system he built is CP4IM (which I tested some year ago and it's impressive work).

I have to admit that I skipped some of the other talks since I was preparing (both mentally and technically) for the penultimate event of the day, namely:

The hectic part of the day was the competition (formally: First International Lightning Model and Solve Competition), since I was one of the organizers, together with Peter Stuckey and with a huge amount of technical/practical help by Farshid Hassani Bijarbooneh. Peter wrote the problems and the checkers for the problems and I wrote the framework for reading the submission files (in MiniZinc data format, .dzn) to be fed into Peter's checkers. (I also wrote code for detecting if any of the teams should trying to "beat the system" in certain ways, but all the teams behaved very honourably).

It was a fun competition, although perhaps a bit too hard problems. Later on - I'm not sure when hopefully this Friday or Saturday - we will publish the problems somewhere so anyone can see what the teams was exposed to. I will of course then blog about it. Later: And here are the problems (with some corrections by Peter): cp2013_competition_20130919.pdf (PDF). I also think that the rules can be interesting to read: cp2013_competition_rules_20130919.pdf.

Here is the table of the teams that got at least one point, i.e. submitted at least one correct solution. There where four teams - not mentioned below - that didn't got any points. In all there where 10 competing teams.
IdTeamPointsTeam membersMedal
7Mano71 (Competition winner! )Allan Van Gelder, Ian Gent, Ian MiguelGold
4Be Cool and Friends57 Pierre Schaus, Renauld Hartert, Jean-Noël MonetteSilver
8CO447 Valentin Mayer-Eichberger, Johannes Waldemann, Sebastian WillBronze
1Lazy Guy39 Andreas Schutt, Thibault Feydy, Geoffrey Chu-
5Monash26 Kevin Leo, Guido Tack, Christopher Mears-
10Other6 Gabriel Hjort Blinell, Roberto Castañeda Lozano, Mohammed Siala-

Congratulations to the medallists! And especially to the winners: team Mano, who - interestingly enough - solved the problems only by hand (as indicated by their team name).

And thanks to all the other teams that attended the competition!

After the competition it was a very pleasant Banquet Dinner, with lots of interesting discussions as well as both formal and not so formal speeches.

Handshakes (with the people I've had just e-contacts with before) : Andreas Schutt, David Rijsman, Ian Miguel.

Tomorrow, I'm especially looking forward to the invited talk about ASP by Torsten Schaub. (I tested ASP somewhat some year ago: see My ASP page; it's quite fun to model in ASP, different and fun.). Another talk that will be interesting is Ozgur Akgun who will talk about "Automated Symmetry Breaking and Model Selection in Conjure".

Posted by hakank at 11:55 PM |

September 18, 2013

CP-2013: The Conference Day 2 (Wednesday)

Wednesday, Day 2

Today started and ended with two very inspiring talks, both showing how to use optimization for important issues, and both also showed the need for multi-disciplicary approaches for these kind of projects, i.e. not only CP or optimization in general but also machine learning, simulation, agent-based modeling (all areas in which I've been interested in on and off, especially machine learning/data mining).

Michaela Milano started the day with the invited talk Optimization for Policy Making: the Cornerstone for an Integrated Approach where the general goal is to build a policy making system (decision support) for energy consumption.

The last lecture was Pascal Van Hentenryck's exiting public lecture Decide Different! about many projects he and his collegues at NICTA (Australia) and other universities was involved in, such as disaster recovery. He also showed two interesting example of optimization in crowd funding and similar systems.

A related aside: Pascal is also behind the very interesting Coursera online Course Discrete Optimization. I have not yet seen all the lectures, but the one about Dynamic Programming and Constraint Programming was excellent, especially for introducing CP. (I will later see the rest of the course, Local search and Integer programming, and perhap be more serious and do some of the homeworks). [In his wonderful introduction lecture, Pascal showed Kidney Exchange as an example of a hard discrete optimization, and that inspired me to write a small MiniZinc model to solve these kind of problems, though it cannot at all handle the huge number of people that is required: about 80000 people is of a need of a kidney. My model solves a problem with 500 people (randomly generated) fairly simple, and 1000 with some more sweat.]

Some other interesting talks today: In the Search track Geoffrey Chu talked about "Dominance Driven Search" (yet another approach that might lead us to a powerful black box solving?), and Marc Shoenauer talked about Bandit-based Search for CP (which - to be honest - was more interesting than I first anticipated). Jean-Charles Régin's talk about Embarrassingly Parallel Search showed a way which seems to be a good way to do massive parallel search (though I'm definitely not an expert in this area).

Ian Gent and Lars Kotthoff held a kind of iconoclastic tutorial about recomputation, which may very well be the future way of doing repeatable experiments in computer science (and surely in other disciplines that use computer experiments). It seems to be quite easy both to submit an experiment to the site and especially to install and redo the experiment. See http://www.recomputation.org/ for more information. The tag line for the blog/project is If we can compute your experiment now, anyone can recompute it 20 years from now. Six of the accepted papers has their experiment at Recomputation.org, see here. For a simple demo experiment, see Our First Experiment: A Chess Puzzle.

My favorite talk from the Global Constraint track was "Solving String Constraints: The Case for Constraint Programming", where Pierre Flener presented the paper by Jun He et.al. The paper compared a CP approach with dedicated solver such as Hampi, Kaluza and Sushi for certain string constraint benchmark. The CP solver dominated these solvers completely. (I actually played with Hampi this summer missed much of the things I'm used to with a CP solver.)

Tomorrow (Thursday) will be interesting. It starts with a presentation of a new CP system: Objective-CP (a CP solver written in Objective-C) and ends with the First International Lightning Model and Solve Competition . I'm also looking forward to Tias Guns' ACP Doctoral Research Award: "Declarative Pattern Mining using Constraint Programming". Oh, sorry. The day actually ends with the Conference Banquet.

(Greeting list today: Barry Hurley, Geoffrey Chu, Laurent Michel.)

Posted by hakank at 09:31 PM |

CP-2013: Photos so far (I)

Here are some of my CP-2013 photos so far (Google+ album), taken from my POV.

[Later: I've got some complaints that the link to the photos don't work. Sorry about that. Perhaps it's required that one is a Google+ user to look at the album? I will post these at my site, but that will be after the conference.]

Even later: See CP2013: Photos from the conference for links to the photos.

Posted by hakank at 06:40 AM |

September 17, 2013

CP-2013: The real Conference Day 1 (Tuesday)

Tuesday, September 17

This is the first "real" day of the Conference. Yesterday, the workshop and doctoral program day, was the zeroth day.

Let me first say I'm sorry that I mislead you yesterday. The talks by Jun He and Pascal are not until tomorrow, Wednesday. That blog post is changed now. Also, it should probably be called "Day 0" but changing that would destroy the links.

And as of this morning, I'm the official offical conference blogger (yesterday I was only the inofficial official conference blogger). As you've already seen it's not about everything at the conference, just a report of what I happen to like or have noticed - as always on my blogs.

Here are some highlights from today.

These following two talks by Peter Stuckey I've really looked forward to:

First Peter's Invited talk "Those who forget the past are condemned to repeat it." The final words was "The Search is Dead. Long Live Proof". A very interesting and provocative talk; and the research is very interesting too, of course. It will very interesting to following this. As a modeler it would be nice with this as ground for a black box solver (at least in my dreams).

And then his report about MiniZinc challenge 2013 results. Here's the medals:

MedalFixedFreeParOpen
GOLD opturion opturion or-tools or-tools
SILVER or-tools or-tool choco choco
BRONZE gecode iz_plus opturion opturion

Congratulations to all!!

This year Opturion CPX and or-tools did really well. As Peter said: The king [Gecode] is dead, Long Live the King. Gecode finally knocked of its perch of winning ALL previous gold medals.

As in later years, the chuffed solver was actually the best solver in both fixed and free category but since it's a G12 solver it can't get any official place. However, or-tools was better than chuffed in the parallel class (and open) this year (with chuffed as second).

If you wonder how the FlatZinc solver by Neng-Fa Zhou and me (the Picat solver) did, it came last in all categories, which was not especially surprising for me; I'm glad we got some points. We'll try to do better the next year (and this is - as Peter mentioned - one of the purposes of the challenge).

Here is the URL from Peter's talk to the result page: http://www.minizinc.org/challenge2013/results2013.html [later: this link works now.]

Related: MiniZinc Challenge Medals 2008-2012

Peter also mentioned the competition at this conference : Lightning Model and Solve competition. The registration form is at the boards. After just some hours there where already about 10 registered. That's great!

Before lunch there was also the three Best Papers talks. All was perhaps not in my forte but really worthwhile listening to.

After the lunch, I went strictly to the left column in the program: first the Applications track, and then the Bin Packing track. One of my two favorite talks where Helmut Simonis' talk about an application of Model Seeker (the last year I blogged about it in Beldiceanu and Simonis: A Model Seeker). The other talk was Andrea Rendl's about Balancing Bike Balancing System. I like these kind of practical applications (and which are not very hard to understand.)

It was interesting to learn that CP was used to calculate orbits in chaotic systems; a long time ago I read some popular science books - as well as some not-so-popular books - about this, and played with quite a few chaos systems

(I didn't attend the ACP General Assembly.)

The scheduled day ended with a reception drink at Östgöta nation. I hope everyone else had lovely discussions and made new contacts.

Assorted things

I was asked about notes from the panel discussion at CP Solver workshop yesterday. Unfortunately we didn't take any notes, but I hope to collect the highlights later this week.

Today's people greet (i.e. the one I've only e-communicated with before and today at least shaked hands with): Narendra Jussien, Barry O'Sullivan, Andrea Rendl, Peter Nightingale. There are still some left to greet. I also made some new friends, and this is actually one of the reason I'm attending this conference. It was mostly CP solver guys and should be to no surprise to the followers of this blog.

Finally, for you you who don't know me earlier: I'm the guy that sometimes wearing an eye patch. Please don't worry, it's just because I don't have a lens in my left eye after an unsuccessful cataract operation this May, and sometimes too much light tend to confuse my small brain. Eventually this will be fixed with a special contact lens.

Posted by hakank at 10:54 PM |

September 16, 2013

CP-2013: Conference Day 1: Workshops

Today was the first day [later: zeroth day] of the CP-2013 conference: The Doctorial program and Workshops day.

The venue, Uppsala University main building, is a very old (the oldest in Scandinavia, from late 15th century of so) and is beautiful and very impressive (though the quarter bell should perhaps be fixed since it's off by some minutes).

When we arrived at the morning, we met a lot of CP guys with wonderful orange T-shirts (designed by Joseph Scott) which indicate the tech and handy persons, those who do everything behind the scenes, i.e. just makes everything work. This is much appreciated!

As mentioned earlier, I was co-organizing the CP Solver workshop (the presentations are available via the link), and did also a talk (CP Solvers/Learning Constraint Programming), and was also responsible for the "5 minutes left" warning messages (a much helpful feature for the talkers I guess) so I didn't attend other workshops (from what I heard they where great as well).

Our workshop was quite well visited (perhaps in part because almost all speakers was in the audience but there are of course many non-talkers in the audience). I liked the mix of the talks: commercial systems and open source systems, old system and newer systems, and all talkers have some point of view that was interesting. The workshop ended with a hour long Panel Discussion - moderated by Hemut Simonis - with many interesting general discussions about the role and future(s) of CP solvers.

And from a personal point, it was really great to be able to at least greet to some I've only had electronic communication with earlier: Jacob Feldman, Chris Kuip, Victor Zverovich, Peter Stuckey, Pascal Van Hentenryck, Toshimitsu Fujiwara, Jean-Guillaume Fages, Guido Tack, Pierre Schaus.

The (scheduled) day ended with with a "Welcome drink" in the Chancellor room with a lot of old portrait painting (what I understood, this is one of the largest collection in Scandinavia). In all this first day was attended by about 100, about half of the total.

Tomorrow (Tuesday) is the first "real" conference day. Some of the talks I'm looking forward to are:
  • Peter J. Stuckey's Invited talk: "Those Who Cannot Remember the Past are Condemned to Repeat it"
  • Peter J, Stuckey: "MiniZinc Challenge results"
  • Jun He, et.al: "Solving String Constraints: The Case for Constraint Programming" [later: sorry, wrong day]
  • Pascal Van Hentenryck Invited Public Lecture: "Decide Different" [later: sorry, wrong day]

Posted by hakank at 09:43 PM |

September 14, 2013

CP-2013: Conference blogging

In a few days it's time for CP-2013 (The 19th International Conference on Principles and Practice of Constraint Programming), in Uppsala, Sweden.

During the conference, I will:
  • blog (at this blog)
  • tweet, at hakankj, using the tag #cp2013 (not all the hits are about the real CP-2013 conference though). Some tweets will probably also be tagged with #copr.
  • and perhaps also at Google+
I don't know when, how often or how much this reporting will be. It will be just from my own perspective and not a full report on every talk. Hopefully it will convey that I have looked forward to this conference a long time, both listening to the talk (of course), and also to finally meet all the great guys I've just have had mail contact with - or just read about - since I started to be interested in constraint programming (in 2008).

I'm quite sure there will be other that blog/tweet/etc about and during the conference.

Some especially interesting things that I'm looking forward to (for miscellaneous reasons): This will be a fun week!

Here are some useful links:

Posted by hakank at 12:41 PM |