Declarative programming with minizinc

[N9WXU]

I am doing some work with combinatorial optimizers.  It is amazing what happens when you turn over one more rock and see what scurries out.

There is a whole class of programming called declarative programming and I have worked with Haskel enough to be slightly familiar with the concepts.  I just learned about flat zinc and an easier environment called MiniZinc which are completely declarative and can be used to solve optimization problems by describing the constraints a valid solution fits inside.

So here is a quick example of a program to find the smallest area rectangle where the area is 10 times the circumference.

var 1..1000: side1;
var 1..1000: side2;
var float: area;
var float: circumference;

constraint area = side1 * side2;
constraint circumference = 2 * side1 + 2 * side2;
constraint area = 10*circumference;

solve minimize area;


output ["side1 = \(side1)\nside2 = \(side2)\narea = \(area)\ncircumference = \(circumference)\n"];

and here is the output showing every iteration.

side1 = 420
side2 = 21
area = 8820.0
circumference = 882.0
----------
side1 = 220
side2 = 22
area = 4840.0
circumference = 484.0
----------
side1 = 120
side2 = 24
area = 2880.0
circumference = 288.0
----------
side1 = 100
side2 = 25
area = 2500.0
circumference = 250.0
----------
side1 = 70
side2 = 28
area = 1960.0
circumference = 196.0
----------
side1 = 60
side2 = 30
area = 1800.0
circumference = 180.0
----------
side1 = 45
side2 = 36
area = 1620.0
circumference = 162.0
----------
side1 = 40
side2 = 40
area = 1600.0
circumference = 160.0
----------
==========
Finished in 82msec

Obviously this is a trivial example but it turns out there is quite a bit of research and libraries in this field.  For example the google OR-Tools which could be incorporated in your C code.  If you need to optimize something and you can describe what the answer looks like (the constraints) then these tools are pretty good.  Of course these problems are NP-Complete, so solutions can take some time.

Good Luck.

[Orunmila]

This is really cool! Can this tool generate C code that I can use in my applications or does it just solve the problem for me?

[N9WXU]

This tool does three things.

1. Solve the problem
2. helps you learn to think declaratively
3. Helps you develop constraints.

To add code to your project, look at the google OR-Tools.  In those tools you will provide constraints and data sets.  The tools will then do the solving.  I would expect some solutions to take quite a bit of CPU time.

Currently I am taking basic modeling in discrete optimization in Coursera to learn more about this topic.  Training my mind to describe a problem instead of solving it is actually quite hard.

[Orunmila]

I used to do a fair amount of optimization using linear programming, it was a bit of a pain to code up so I had hoped this would make that easier ...

[N9WXU]

I think the C libraries can make linear optimization problems much easier to solve in a system.  But they are a general purpose solution intended for the general class of optimization problems.  There is a good chance that the code you wrote was far simpler and sufficiently optimal for the task at hand due to task specific optimizations.

This story is often the case for embedded systems.  A general purpose solution is nice and easy but too big/slow for an embedded microcontroller.  As the microcontrollers get larger/faster for low costs then these generic or more complete solutions become available.  Interestingly this does not always create a "better" performing solution but it often produces a more reliable, faster to market solution by leveraging more widely developed software that has more hours of operation/debugging on it.