"Picat Compared To Other Languages" page could do with a MiniZinc section

[Phil]

Hi all,

I've just come to the world of solvers recently and after having explored them and their own syntaxes or Prolog-skins, found MiniZinc which I was immediately much more enthused about and started learning more deeply.

Well, only now have I also stumbled upon Picat with its own 4 solver modules and seeming BYI-solver support, and found your "Compared To Other Languages" page under "Resources", covering Prolog, Haskell, Python.

I already gathered that Picat is more general-purpose/multi-paradigm than solver-focused MiniZinc — but focusing only indeed on the solvers aspect (assuming the rest of one's overall project is already and will continue to be formulated in another, non-Picat general-purpose PL), how would practicioners with experience in both contrast-and-compare these two co-existing ways to running solvers with their "trending-toward-programmer-friendlier-than-the-solvers-themselves-offer syntax", which they clearly both share? What limitations/capabilities differences come to mind?

[Neng-Fa Zhou]

I am not a MiniZinc programmer, and am not in the position to compare Picat and MiniZinc as modeling languages. One of the differences between MiniZinc and Picat is that MiniZinc is statically typed while Picat is dynamically typed. I am not against types, but I found MiniZinc's type notations unfriendly to me (I recently have been programming in Julia, and I like Julia's type notations). I also found that MiniZinc's treatment of arrays is uncommon.  MiniZinc's capability of allowing non-integer array indexes and even floating integer index bases often causes confusion. Also, MiniZinc's treatment of multi-dimensional arrays is very strange. 

I guess Hakan, who have experiences in both Picat and MiniZinc, is a good person to do the comparison.

Cheers,

NF

[Hakan Kjellerstrand]

As Neng-Fa mentioned, I've written quite a few constraint models in both Picat and MiniZinc (as well as in other constraint systems, see http://www.hakank.org/common_cp_models/ ).

Here's my - quite subjective - comparison of Picat and MiniZinc as systems for modelling constraint models. Note that this also includes things that might be considered non-modelling issues, but are important when trying to solve a problem.

Integrated system

------------------------

Compared to MiniZinc, it cannot be ignored that Picat is an integrated system where the model and both post- and pre-processing can be done in the same system, as well as doing any other (non constraint) stuff that's needed using logic programming, imperative foreach/while loops, functions, list comprehension, etc (though one should be careful in how one mix these with the constraints) . 

In MiniZinc, one has to - for more complex models - pre / post process indata/output in some other system, or even generate the model. The MiniZinc-Python system is a great tool for this, but some of it can be done in any programming language (for example I've written some Picat programs that generate MiniZinc models or data files to be used by MiniZinc models).

Picat is a full fledged programming language, whereas the MiniZinc language is not.

Supported solvers

-----------------------

Picat has four solvers (or eight depending how you count): one CP solver, two SAT solvers (the built-in and the external maxsat), three MIP solvers (the external Cbc, GLPK, and Gurobi), and two SMT solvers (the external z3 and cvc4). They all share the same syntax, and it's easy to change the solver (e.g. changing "import cp." to "import sat."). There are some exceptions, however, for example that the MIP solver is the only solver that can handle float decision variables, and some constraints are only available for the CP or SAT solvers.

Since MiniZinc is a plain modelling language, one has to use a specific FlatZinc solver. Included in the MiniZincIDE package there are some great solvers (e.g. Chuffed, Cbc, Gecode, and - recently - Google OR-tool CP-SAT solver), and there's a lot of other FlatZinc solvers, including the powerful PicatSAT solver. Changing to a different solver is quite simple, either via the IDE or via command line (I almost exclusively use the command line). One drawback of this is that the individual flags to tweak a specific solver are not standardized so one has to check the documentation for each individual solver. Note that the general flags such as -a for getting all solutions, -f for free search etc are standardized in MiniZinc.

Some FlatZinc solvers, such as Gecode, JacoP, Choco, and OptiMathSAT, support non-linear float constraints (though one often needs to tweak the precision) combined with integer based decision variables. Picat's MIP solvers are more restricted.

Constraints

---------------

Even though Picat supports many constraints, the list of supported constraints for MiniZinc is quite impressive. A nice feature is that an individual FlatZinc.solver can override the MiniZinc definition and replace it with a constraint that's tailored for the solver, which speeds up the solution time (though this is not something an ordinary MiniZinc modeller do; it's the task for the solver creator ).

In general, I would say that the MiniZinc language is a bit higher level than Picat's constraint language. For example MiniZinc supports some constraints (syntax sugar) that can make modeling a little easier especially for people new in constraint modelling:

* indexing with decision variables

  Picat's handing of indexing in a list or a matrix when Index and I, J are decision variables

    element(Index, List, Value)

    matrix_element(Matrix, I, J, Value) 

  are easier to state in MiniZinc by the syntax:

    Value = List[Index]

    Value = Matrix[I,J] 

* exists

  MiniZinc has an "exist" function which makes modelling certain things quite easy, e.g. to ensure that there is at least one instance in a list that satisfies a constraint. In Picat, I tend to use use "sum([...]) #>= 1" for this; it works, but exists() is neater,

* functions

  MiniZinc supports user defined predicates as well as user defined functions. Statiing constraints as a function can be more natural or easier to use than using constraints as predicates. Picat only supports user defined predicates (Picat functions cannot return a decision variable or a constraint).

It would be great if Picat would also have these features.

Picat's SAT solver supports some great graph based constraints which to my knowledge are not in MiniZinc, e.g.  hcp/3, hcp_grid/1, scc/2, scc/3, and scc_grid/1, See the Picat Guide for more on these constraints.

In MiniZinc, one can create constraints (as predicates or functions as mentioned above), but there's no way to use traditional ("low level"/"imperative") algorithms for speeding up a constraint using the MiniZinc language. In Picat, one can implement constraints using a combination of constraints and for loops/maps etc. See for example Neng-Fa's implementations of the graph constraints mentioned above in the file lib/sat.pi (found in the Picat distribution).

In MiniZinc there is basically one approach of writing a model: one uses "forall" loops (and/or its list comprehension variant) to loop through the elements in the lists/matrices to generate the constraints. In Picat, one can use the loop approach (with a "foreach" loop), using list comprehensions. Or use logic programming - think Prolog + CLP(FD) - which might be more natural depending on the problem. This is the advantage of using a multi-paradigmatic system.

One feature in Picat that I like - though it's only for the CP solver - is that it evaluates the constraints in linear order and does domain reduction "incrementally". This means that one can do some print debugging of the model for checking how the domains are changed etc (debugging a constraint model is hard in any CP system). It also means that it might be possible to speed up the model by rearranging the constraints. e.g. by moving that all_different/1 constraint before that foreach loop instead of after..

Arrays

--------

One drawback of MiniZinc is that the size of the arrays must be declared with a fixed size and it does not support "rugged arrays" (one way to fix this is to create a fixed size matrix with dummy values for the missing values in a row but it can be messy to handle). In Picat there is no such restriction of the arrays/matrices, for example one can create a list (of unknown size) of decision variables via a foreach loop or handling weird shaped matrices.

Note: MiniZinc supports input data in JSON format, which can make input handling a little easier, though it probably means that the input has been created by an external system.

Output

---------

MiniZinc has support for output, but that is quite restricted and thus not especially fun to work with, and this is one other reason one wants to use e.g. MiniZinc-Python. In Picat, it's much easier to write the output of a model, again since everything is integrated.

Summary

-------------

Even though I like MiniZinc - especially the syntax of "element"/"exists" and functions, and for the support of constraints and the diversity of the solvers - I almost always write my constraint models in Picat, because the constraints are integrated within the system so I can use Picat's other great features.

Another thing: One neat thing with Picat is that it's very easy to - beside constraint modelling - test other (non CP) approaches for solving a problem, for example using logic programming, using functions, imperative programming, perhaps together with tabling. And for certain problems, perhaps it's better to use the planning module. MiniZinc is a great system for constraint modelling only, but Picat has many ways to solve a problem.

I should also mention that for my professional consultancy jobs, the customers have requested CP systems other than Picat or MiniZinc (all are Python based). That being said, when modelling in these systems, I occasionally prototype/test more complex constraints in Picat.

Hope this helps

Hakan

--
You received this message because you are subscribed to the Google Groups "Picat" group.
To unsubscribe from this group and stop receiving emails from it, send an email to picat-lang+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/picat-lang/c2d0931e-c2e7-4fea-854f-4bb78c75096fn%40googlegroups.com.

--

Hakan Kjellerstrand
http://www.hakank.org/
http://www.hakank.org/webblogg/
http://www.hakank.org/constraint_programming_blog/
http://twitter.com/hakankj
https://www.facebook.com/hakankj

[Ilya Kudryavtsev]

Hi Hakan, 

Thanks a lot for the very detailed answer to this very interesting question. 

I could be wrong because I'm not a professional in Picat, but I can't find how to specify different vars and value strategies for different vars. For example, If I want to find some structure of the solution first and then random solutions for special vars. In MiniZinc I can do it, and it's relatively easy. 

Thanks,

Ilya

[Hakan Kjellerstrand]

Hi Ilya.

You are right. MiniZinc has more support for stating strategies for decision variables, for example using seq_search() to combine different search strategies on different decision variables. MiniZinc also supports stating different restart parameters (and warm starts).

In Picat, the CP solver does not have this rich repertoire of parameters and options. The other solvers have different parameters, see more on this in the Picat Guide.

One of the reasons I forgot to mention this is that nowadays when I'm modelling in MiniZinc, I tend to experiment with different FlatZinc solvers instead of changing the search strategies for the CP solvers.

There are other differences between MiniZinc and Picat. My list was not meant to be a complete comparison on each and every difference.

/Hakan

To view this discussion on the web visit https://groups.google.com/d/msgid/picat-lang/7b8d39af-e540-4947-9023-3caa9e4355bbn%40googlegroups.com.