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 FlatZinc solver must be used. Here is a listing of some FlatZinc solvers.

Utilities

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 (mostly decompositions)

Here are some implementations of the global constraints (mostly 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 or test of built-in constraints.

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 from Martin Chlond's wonderful collections at Integer Programming Puzzles [Note: the web page is gone but can be found via Wayback machine: https://web.archive.org/web/*/http://www.chlond.demon.co.uk/academic/puzzles.html].

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 Description : Twelve draughts puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P36)

Coin puzzle Description : Coin puzzle
Source : Mathematical Puzzles of Sam Loyd (P111)

Egg basket puzzle Description : Egg basket puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P136)

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

Fifty puzzle Description : Fifty puzzle
Source : The Puzzles of Sam Loyd (P 54)

Honey division puzzle Description : Honey division puzzle
Source : H E Dudeney - Amusements in Mathematics

Wine cask puzzle Description : Wine cask puzzle
Source : M Kraitchik - Mathematical Recreations (p 31)

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

Mango puzzle Description : Mango puzzle
Source : M Kraitchik - Mathematical Recreations (P32)

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

Lights on puzzle Description : Lights on puzzle
Source : Unknown

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

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

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

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

Jive turkeys Description : Jive turkeys
Source : rec.puzzles

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

Dudeney's bishop placement problem I 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 Description : Dudeney's bishop placement problem II
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

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

Schuh's queen placement problem 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 Description : Dudeney's queen placement problem
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Joshua and his rats 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 Description : The Abbott's Puzzle
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

Non-dominating queens problem Description : Non-dominating queens problem
Source : http://www.cli.di.unipi.it/~velucchi/queens.txt

Enigma Description : Enigma
Source : Herald Tribune circa November 1979 - courtesy of Dr Tito A. Ciriani

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

Book buy puzzle Source: M Kraitchik, Mathematical Recreations(p37), Dover

Shopping puzzle Source: M Kraitchik, Mathematical Recreations(p37), Dover

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

Seven 11
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
* My Z3 page
* My SWI-Prolog page

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