Jump to content
 
N9WXU

Declarative programming with minizinc

Recommended Posts

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.

  • Like 2
  • Helpful 1

Share this post


Link to post
Share on other sites

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?

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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 ...

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


 


×
×
  • Create New...