My MiniZinc page

(The original of this file is http://www.hakank.org/minizinc/index.html.)

This page was created by Hakan Kjellerstrand (hakank@gmail.com).

Also, see my My Zinc page which includes information about and models for G12 Zinc.

MiniZinc constraint programming system

[MiniZinc]

MiniZinc is a very interesting constraint programming system/modeling language with a high level syntax. From the MiniZinc page:
MiniZinc is a medium-level constraint modelling language. It is high-level enough to express most constraint problems easily, but low-level enough that it can be mapped onto existing solvers easily and consistently. It is a subset of the higher-level language Zinc. We hope it will be adopted as a standard by the Constraint Programming community.

FlatZinc is a low-level solver input language that is the target language for MiniZinc. It is designed to be easy to translate into the form required by a solver.

Some important links:
Solvers
In order to solve a problem stated in the MiniZinc modeling language, a solver must be used. The following solvers were available as of 2010-03-16.

Utilities

mzn_show.pl

Perl program
mzn_show.pl
Since version 1.0 MiniZinc don't support the output [] anymore in the external solvers (e.g. all except the minizinc solver), and it can be hard to see structured output, e.g. matrices. This program gives the result somewhat nicer output. I blogged about the program (first version) here: Miscellaneous news.

Usage: solver problem.mzn | mzn_show.pl "{parameter}"

The parameters are:
- {tr:from:to:}: translate digit to another digit/character
- {trvar:var:from:to:}: translate digit to another digit/character for a specific variable var
- {trtr:from_string:replacement_string:}: translates all digits in from_string to the corresponding digit/character in replacement_string (inspired from the Unix tr command)
- {trtrvar:var:from_string:replacement_string:}: as trtr but for a specific variable var - {nospaces}: don't show space after character
- {noprintf}: don't try to be clever with printf stuff
- {noresult}: don't print the numerical result (just the translations)
- {nonogram}: shortcut for {trtr:12: #} {nospace} {noresult}

Example: for showing a nicer picture of a Nonogram:
flatzinc nonogram_create_automaton2.fzn | mzn_show.pl "{tr:1: :} {tr:2:#:} {nospace}"
Where the {tr:from:to:} means translate digit from to character to, and {nospace} means that no spaces are shown after each digit/character.

This is now probably better written with trtr:
flatzinc nonogram_create_automaton2.fzn | mzn_show.pl "{trtr:12: #:} {nospace}"

mzn.pl

I have also created a Perl program for handling all the different solvers from the command line, as well as changing the model parameters etc. The program may be obtained upon request by mailing me (hakank@gmail.com).

Emacs mode

minizinc.el is a simple MiniZinc (major) mode for Emacs, heavily based on the Prolog model prolog.el (written by Masanobu UMEDA); to be honest I mostly replaced "Prolog" with "MiniZinc" and some other adjustments. The file still have the interactive mode etc but that will (of course) not work for MiniZinc since it don't work like Prolog. I mostly use it for syntax highlightning and commenting.

My MiniZinc models

The following is a list of (some of) my models: simple puzzles and not so simple puzzles, standard operation research / integer programming examples, and some global constraints (that are not in the MiniZinc globals.mzn). Some are just examples of modelling in MiniZinc.

Almost all models are commented with sources or inspirations, and quite a few have the main constraints generalized as a predicate.

All files (models, datafiles, etc) are (or will be) available at the Github repository: github.com/hakank/hakank/tree/master/minizinc.

Contents

The models are collected in the following categories:

Puzzles, small, and large

Operations research, linear programming, integer programming, scheduling

Non linear and/or float variables problems

Thus includes some MIP problems. Note: Not all CP solvers can handle float variables. As of writing (2014-05-20) these solvers are the one I've tested and that can manage some/many/most of these models:

Combinatorial problems

Global constraints (decompositions)

Here are some implementations of the global constraints (as decompositions) which are not already implemented in the MiniZinc globals.mzn, described in the great collection
Global Constraint Catalog. Here are also some decompositions not in the catalogue.

Name clashes: If there exists a file in default directory with the same name as one of the global constraints defined in "global.mzn", there will be a name clash. If that happens, just rename the file in the default directory to something else, e.g. constraint_me.mzn.

Martin Gardner's Puzzles and Problems

Here are some models based on Martin Gardner's problem and puzzles (or presented/popularized by him), or related to Martin Garder festivities such as Gathering 4 Gardner, Celebration Of Mind etc.

Martin Chlond's Integer Programming Puzzles

Below are MiniZinc models of (almost) all puzzles of Martin Chlond's wonderful collections of
Integer Programming Puzzles. The collection is separated in four sections where the problems is presented
* Integer Programming Puzzles section 1
* Integer Programming Puzzles section 2
* Integer Programming Puzzles section 3
* Integer Programming Puzzles section 4

The models below are presented first with a link to my MiniZinc model, and then to Martin Chlond's solution (in XPress Mosel, or for later solutions AMPL).

Problems from Integer Programming Puzzles section 1
Models:
Twelve draughts puzzle (Chlond's solution)
Description : Twelve draughts puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P36)

Coin puzzle (Chlond's solution)
Description : Coin puzzle
Source : Mathematical Puzzles of Sam Loyd (P111)

Egg basket puzzle (Chlond's solution)
Description : Egg basket puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P136)

Evens puzzle (slightly different approach: Evens puzzle 2 ) (Chlond's solution)
Description : Evens puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P8)

Fifty puzzle (Chlond's solution)
Description : Fifty puzzle
Source : The Puzzles of Sam Loyd (P 54)

Honey division puzzle (Chlond's solution)
Description : Honey division puzzle
Source : H E Dudeney - Amusements in Mathematics

Wine cask puzzle (Chlond's solution)
Description : Wine cask puzzle
Source : M Kraitchik - Mathematical Recreations (p 31)

Knight domination puzzle - all squares threatened (Chlond's solution)
Description : Knight domination puzzle - all squares threatened
Source : M Kraitchik - Mathematical Recreations (P256)

Mango puzzle (Chlond's solution)
Description : Mango puzzle
Source : M Kraitchik - Mathematical Recreations (P32)

Remainder puzzle (alternative model: Remainder puzzle 2) (Chlond's solution)
Description : Remainder puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P136)
5 X 5 puzzle (alternative model: 5 X 5 puzzle v 2) (Chlond's solution)
Description : 5 X 5 puzzle
Source : Unknown

Lights on puzzle (Chlond's solution)
Description : Lights on puzzle
Source : Unknown

Problems from Integer Programming Puzzles section 2
Models:
Clarke's tobacconist (Chlond's solution)
Description : Clarke's tobacconist
Source : Clarke, L.H., (1954), Fun with Figures, William Heinemann Ltd.

Tommy's Birthday Coins (Chlond's solution)
Description : Tommy's Birthday Coins
Source : Clarke, L.H., (1954), Fun with Figures, William Heinemann Ltd.

Lewis Carroll coin puzzle (Chlond's solution)
Description : Lewis Carroll coin puzzle
Source : Wakeling, E., (1995), Rediscovered Lewis Carroll Puzzles, Dover.

Dudeney's tea mixing problem (Chlond's solution)
Description : Dudeney's tea mixing problem
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Jive turkeys (Chlond's solution)
Description : Jive turkeys
Source : rec.puzzles

Public School Problem (Chlond's solution)
Description : Public School Problem
Source : Clarke, L.H., (1954), Fun with Figures, William Heinemann Ltd.

Dudeney's bishop placement problem I (Chlond's solution)
Description : Dudeney's bishop placement problem I
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Dudeney's bishop placement problem II (Chlond's solution)
Description : Dudeney's bishop placement problem II
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Kraitchik's queen placement problem (Chlond's solution)
Description : Kraitchik's queen placement problem
Source : Kraitchik, M., (1942), Mathematical Recreations, W.W. Norton and Company, Inc.

Schuh's queen placement problem (Chlond's solution)
Description : Schuh's queen placement problem
Source : Schuh, F., (1943), Wonderlijke Problemen; Leerzam Tijdverdrijf Door Puzzle en Speel, W.J. Thieme & Cie, Zutphen.

Dudeney's queen placement problem (Chlond's solution)
Description : Dudeney's queen placement problem
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Joshua and his rats (Chlond's solution)
Description : Joshua and his rats
Source : Sole, T., (1988), The Ticket to Heaven, Penguin Books


Problems from Integer Programming Puzzles section 3
Models:
The Abbott's Puzzle (Chlond's solution)
Description : The Abbott's Puzzle
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

The Abbott's Window (Chlond's solution)
Description : The Abbott's Window
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

The First Trial (Chlond's solution)
Description : The First Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Second Trial (Chlond's solution)
Description : The Second Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Third Trial (Chlond's solution)
Description : The Third Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Fourth Trial (Chlond's solution)
Description : The Fourth Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Fifth Trial (Chlond's solution)
Description : The Fifth Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Sixth Trial (Chlond's solution)
Description : The Sixth Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

Werewolves II (Chlond's solution)
Description : Werewolves II
Source : Smullyan, R., (1978), What is the Name of this Book?, Prentice-Hall

Werewolves IV (Chlond's solution)
Description : Werewolves IV
Source : Smullyan, R., (1978), What is the Name of this Book?, Prentice-Hall

Earthlings (Chlond's solution)
Description : Earthlings
Source : Poniachik, J. & L., (1998), Hard-to-solve Brainteasers, Sterling

Equal Vision (Chlond's solution)
Description : Equal Vision
Source : Poniachik, J. & L., (1998), Hard-to-solve Brainteasers, Sterling


Problems from Integer Programming Puzzles section 4
Models:
On the road (Chlond's solution)
Description : On the road
Source : Poniachik, J. & L, (1998), Hard-to-solve Brainteasers, Sterling

The Riddle of the Pilgrims (Chlond's solution)
Description : The Riddle of the Pilgrims
Source : Dudeney, H.E., (1949), The Canterbury Puzzles, 7th ed., Thomas Nelson and Sons.

The Logical Labyrinth (Chlond's solution)
Description : The Logical Labyrinth
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The gentle art of stamp-licking (Chlond's solution)
Description : The gentle art of stamp-licking
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

The crowded board (Chlond's solution)
Description : The crowded board
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Non-dominating queens problem (Chlond's solution)
Description : Non-dominating queens problem
Source : http://www.cli.di.unipi.it/~velucchi/queens.txt

Enigma (Chlond's solution)
Description : Enigma
Source : Herald Tribune circa November 1979 - courtesy of Dr Tito A. Ciriani

Price change puzzle (Chlond's solution)
Source: M Kraitchik, Mathematical Recreations (p 33-35), Dover

Book buy puzzle (Chlond's solution)
Source: M Kraitchik, Mathematical Recreations(p37), Dover

Shopping puzzle (Chlond's solution)
Source: M Kraitchik, Mathematical Recreations(p37), Dover

Book discount problem (Chlond's solution)
Source: J. & L. Poniachik, Hard-to-Solve Brainteasers (p16), Sterling

Seven 11 (Chlond's solution)
Source: alt.math.recreational


Models based on Martin Chlond's Puzzle articles in Informs Transations on Education

And here is some other models of recreational mathematics created by Martin Chlond, published in the Puzzle section of
Informs Transations on Education (an open operations research journal).

Other models

Math, utils, etc.

Also, see my other pages about constraint programming systems:
* My Constraint Programming Blog, especially the MiniZinc/Zinc category
* Constraint Programming
* Common constraint programming problems
* My Zinc page
* My JaCoP page
* My JaCoP/Scala page
* My Choco page
* My Gecode/R page
* My Comet page
* My Gecode page
* My ECLiPSe page
* My Tailor/Essence' page
* My SICStus Prolog page
* My Google CP Solver page
* My OscaR page
* My JSR-331 page
* My Numberjack page
* My AIMMS+CP page
* My B-Prolog page
* My Choco3 page
* My Picat page

Back to my homepage
Created by Hakan Kjellerstrand hakank@gmail.com