My MiniZinc page
This page was created by Hakan Kjellerstrand (hakank@bonetmail.com).
MiniZinc constraint programming system
MiniZinc is a very interesting constraint programming system/modeling language with a high level syntax. 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 2008-06-22.
Blog posts
I have blogged about MiniZinc etc. Some post posts in swedish (also a link to google translation):
- Constraint Programming: Minizinc, Gecode/flatzinc och ECLiPSe/minizinc (google translation from swedish to english: Constraint Programming: Minizinc, Gecode / flatzinc and ECLiPSe / minizinc)
- MiniZinc-sida samt fler MiniZinc-exempel (google translation: MiniZinc-side and more MiniZinc-examples)
- Applikationer med constraint programming, lite om operations research samt nya MiniZinc-modeller (google translation: Applications with constraint programming, a little about operations research and new models MiniZinc)
- Några fler MiniZinc-modeller, t.ex. Smullyans Knights and Knaves-problem (google translation: A few more MiniZinc models, such as Smullyans Knights and Knaves-problem Smullyans Knights and knaves problems)
- MiniZinc/FlatZinc version 0.8 släppt (google translation: MiniZinc / FlatZinc version 0.8 released)
- Nya MiniZinc-modeller, flera global constraints, däribland clique (google translation: New MiniZinc models, several global constraints, including the clique)
- Mats Anderssons tävling kring fotbolls-EM 2008 - ett MiniZinc-genererat tips (google translation: Mats Andersson's competition around the European football championships in 2008 - a MiniZinc-generated tips)
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 (which 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 problem generalized as a predicate.
Some of the models has been commented in my (swedish) blog posts Constraint Programming: Minizinc, Gecode/flatzinc och ECLiPSe/minizinc, MiniZinc-sida samt fler MiniZinc-exempel, Några fler MiniZinc-modeller, t.ex. Smullyans Knights and Knaves-problem.
Initialization of multidimensional arrays
Originally, many these models were written for the older version 0.7. Almost all the models has been converted to MiniZinc version 0.8, with some exceptions noted in the list.
One important difference between version 0.8 and older versions is that initiation of multidimensional arrays has changed.
Older version (0.7.1):
array[1..3, 1..3] of var 1..9: x;
...
x =
[1,2,3,
4,5,6,
7,8,9];
Newer version (0.8 and later):
array[1..3, 1..3] of var 1..9: x;
...
x =
[|1,2,3,
|4,5,6,
|7,8,9|];
Another solution, which is simpler for larger matrices:
array[1..3, 1..3] of var 1..9: x;
...
x =
array2d(1..3, 1..3,
[1,2,3,
4,5,6,
7,8,9];
The developer version of Gecode fz (svn get https://svn.gecode.org/svn/interfaces/flatzinc/trunk) supports the newer 0.8 format, as well as ECLiPSe's minizinc/flatzinc libraries and fzntini.
Puzzles, small and large
- 3_jugs.mzn: 3 jugs problem (as shortest path problem)
- 3_jugs2.mzn: 3 jugs problem (using shortest_path_model.mzn)
- added_corner.mzn: Added corner puzzle
- averbach_1.2.mzn: Example 1.2 i Averbatch & Chein "Problem Solving Through Recreational Mathematics"
- averbach_1.2.mzn: Example 1.3 i Averbatch & Chein "Problem Solving Through Recreational Mathematics"
- averbach_1.2.mzn: Example 1.4 i Averbatch & Chein "Problem Solving Through Recreational Mathematics"
- averbach_1.2.mzn: Example 1.5 i Averbatch & Chein "Problem Solving Through Recreational Mathematics"
- coins_grid.mzn: Coins Grid (Tony Hurlimann)
- coins3.mzn: Minimum mumber of coins that allows one to pay exactly any amount smaller than one Euro
- col_sum_puzzle.mzn: Find out values in a matrix, given column and row sums and some hints.
- crossword.mzn: Crossword solving (standard constraint programming example)
- cur_num.mzn: Curious Number (Dudeney)
- defending_castle.mzn: Defending the Castle (Cut the knot)
- devils_word.mzn: Devil's Word problem (see the Devil's word page)
- donald.mzn: Alphametic puzzle: DONALD + GERALD = ROBERT
- drinking_game.mzn: Drinking game (Marriott & Stuckey)
- einstein_hurlimann.mzn: Einstein puzzle (variant of Zebra puzzle)
- ett_ett_ett_ett_ett__fem.mzn: Alphametic puzzle ETT + ETT + ETT + ETT + ETT = FEM
- fancy.mzn: Mr Greenguest puzzle (Fancy dress puzzle)
- farm_puzzle0.mzn: Farm puzzle, simple model
- farm_puzzle.mzn: Farm puzzle, more general model
- five_brigades.mzn: Five brigades (Dedeney)
- gardner_dinner.mzn: Dinner problem (Martin Gardner)
- heterosquare.mzn: Heterosquare problem
- least_diff.mzn: Least diff problem: What is the smallest difference between two numbers X - Y if you must use all the digits (0..9) exactly once?
- locker.mzn: Locker puzzle.
- M12.mzn: Solving the M12 puzzle
- magic_sequence.mzn: Magic sequence (CSPLib)
- magic_sequence2.mzn: Magic sequence (CSPLib), alternative model
- magic_sequence3.mzn: Magic sequence (CSPLib), alternative model
(Note: don't work in version >= 0.8)
- magic_sequence4.mzn: Magic sequence (CSPLib), alternative model
- marathon.mzn: Marathon puzzle (XPress example)
- money_change.mzn: Simple money change problem
- music_men.mzn: Music men puzzle
- n_puzzle.mzn: N-puzzle, e.g. 8-puzzle, 15-puzzle
- peacableArmyOfQueens.mzn: Peacable Army of Queens
- photo_hkj.mzn: Photo problem
- photo_hkj2_model.mzn: Photo problem model
- photo_hkj2_data1.mzn: Data for photo problem
- photo_hkj2_data2.mzn: Data for photo problem
- place_number.mzn: The Eight Number Puzzle
- puzzle1.mzn: Yet another column/row sum problemi
- raven_puzzle.mzn: "Polyglot puzzle" (from Raven, swedish)
- remarkable_sequence.mzn: Remarkable sequence (from an Alma-0 model)
- safe_cracking.mzn: Safe cracking
- send_more_money.mzn: Alphametic puzzle: SEND + MORE = MONEY
- send_more_money2.mzn: Alphametic puzzle: SEND + MORE = MONEY,,,, alternative model
- send_most_money.mzn: Alphametic puzzle: SEND + MOST = MONEY )and maximize MONEY)
- sequence_2_3.mzn: Simple permutation puzzle
- seseman.mzn: Seseman Convent problem (see Seseman Convent problem)
- seseman2.mzn: Seseman Convent problem, generalized model
- set_puzzle.mzn: Solving SET Puzzles
- smullyan_knights_knaves.mzn: Raymond Smullyan's Knights and Knaves problems
- smullyan_knights_knaves_normals.mzn: Raymond Smullyan's Knights, Knaves, and Normals problems
- smullyan_knights_knaves_normals_bahava.mzn: Raymond Smullyan's Knights, Knaves, and Normals at the Island of Bahava problems
- smullyan_lion_and_unicorn.mzn: Raymond Smullyan's Lion and Unicorn problems
- smullyan_portia.mzn: Raymond Smullyan's Portia problems
- solitaire_battleship.mzn: Solitair Battleship
- sum_to_100.mzn: Five numbers should sum to 100, and all numbers must be divisible by 2 or 5
- talisman_square.mzn: Talisman Square
- tomography.mzn: Discrete Tomography (one color model)
- tomography_n_colors.mzn: Discrete Tomography (n color model)
- three_digit.mzn: Three digit problem
- torn_number.mzn: Torn number puzzle (Dudeney)
- water_buckets1.mzn: Water bucket problem (generalized)
- xkcd.mzn: xkcd's knapsack problem (see the xkcd strip )
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 MiniZinc page, and then to Martin Chlond's solution (in XPress Mosel, or for later solutions AMPL).
Problems: Integer Programming Puzzles section 1
Solutions:
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
(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
(Chlond's solution)
Description : Remainder puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P136)
5 X 5 puzzle
(Chlond's solution)
Description : 5 X 5 puzzle
Source : Unknown
Lights on puzzle
(Chlond's solution)
Description : Lights on puzzle
Source : Unknown
Problems: Integer Programming Puzzles section 2
Solutions:
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: Integer Programming Puzzles section 3
Solutions:
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: Integer Programming Puzzles section 4
Solutions:
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
Operations research, linear programming, integer programming
Non linear problems
Combinatorial problems
- bin_packing.mzn: Bin packing
- color_simple.mzn: Simple coloring of a map (Murty)
- decision_tree_binary.mzn: Binary decision tree
- debruijn_binary.mzn: de Bruijn sequence (graph)
- fix_points.mzn: Number of fix points in an array
- gray_code.mzn: Gray code
- hamming_distance.mzn: Hamming distance
- knapsack.mzn: Knapsack
- knapsack2.mzn: Another knapsack
- langford2.mzn: Langford sequence
- latin_square.mzn: Latin squares
- map.mzn: Simple coloring of a map
- map_stuckey.mzn: Another coloring of a map (Marriott and Stuckey)
- modulo_partition.mzn: Function partitioning
- partial_latin_square.mzn: Partial Latin squares
- partitions.mzn: Integer partitions
- perfect_shuffle.mzn: Perfect shuffle
- pigeon_hole.mzn: Pigeon hole problem (CLP-FD)
- pigeon_hole2.mzn: Another pigeon hole problem
- power_set.mzn: Power set
- quasiGroup7.mzn: Quasi group problem (CSPLib)
- runs.mzn: Number of runs in an array (sequence)
- set_covering.mzn: Set covering, placing of firestations (Winston)
- set_covering2.mzn: Set covering, number of security telephons on a campus (Taha)
- set_covering3_model.mzn: Set covering model
- set_covering3.mzn: Set covering, senators making a committe (Murty)
- set_covering4.mzn: Set covering problem (Lundgren, Rönnqvist, Värbrand "Optimeringslära")
- set_covering4b.mzn: Set covering problem, generalized version of set_covering4.mzn
- set_covering5.mzn: Set covering, work scheduling (Lundgren, Rönnqvist, Värbrand "Optimeringslära")
- set_covering_deployment.mzn: Set covering deployment
- set_partition.mzn: Set partitioning
- shortest_path1.mzn: Shortest path problem, selling/buying a car (Winston)
- shortest_path2.mzn: Shortest path problem (Winston)
- shortest_path_model.mzn: Model for shortest path
- sonet_problem.mzn: SONET problem
- subset_sum.mzn: Subset sum (Murty)
- transpose.mzn: (Square) matrix operations, transpose, scalar addition, scalar multiplication
- tsp_circuit.mzn: Travelling salesperson problem, using circuit predicate
Global constraints
Implementation of some of the global constraints (which are not already implemented in the MiniZinc globals.mzn), inspired by the great collection Global Constraint Catalog. Some global constraints in the catalogue is also modelled.
- all_differ_from_at_least_k_pos.mzn: all_differ_from_at_least_k_pos, all rows in a matrix has values that differs in at least k positions
- all_min_dist.mzn: all_min_dist, all values must have a minimum distance to each other
- alldifferent_cst.mzn: alldifferent_cst, and alldifferent_cst using multiplication instead of addition
- alldifferent_except_0.mzn: alldifferent except 0
- alldifferent_interval.mzn: alldifferent_modulo, all values modulo k shall be different
- alldifferent_modulo.mzn: alldifferent_modulo, all values modulo k shall be different
- alldifferent_on_intersection.mzn: alldifferent_on_intersection
- alldifferent_partition.mzn: alldifferent_partition
- alldifferent_same_value.mzn: alldifferent_same_value
- alldifferent_soft.mzn: alldifferent_soft (alldifferent_soft_ctr and alldifferent_soft_var)
- allperm.mzn: allperm, ensures that the first rows in a matrix is lexically less than all permutation of all other rows
- all_min_dist.mzn: all_min_dist, all pairs in an array have a distance of at least c
- among_diff_0.mzn: among_diff_0, number of values different from 0
- among_interval.mzn: among_interval, number of values in a certain interval
- among_low_up.mzn: among_low_up, the number values in an array matched another array shoule be constrained to low and up
- among_modulo.mzn: among_modulo, the number values in an array where a value modulo quotient = remainder
- among_seq.mzn: among_seq
- and.mzn: and, generalized and (array)
- arith.mzn: arith, enforces that all values in an array is RELOP (equal, not equal, less than, etc) some VALUE
- arith_or.mzn: arith_or
- arith_sliding.mzn: arith_sliding, all sliding sums from 1..j must satisfy RELOP VALUE
- assign_and_counts.mzn: assign_and_counts
- atleast_nvalue.mzn: atleast_nvalue, at least NVAL values are different in an array
- atmost1.mzn: atmost1
- atmost_nvalue.mzn: atmost_nvalue, at most NVAL values are different in an array
- balance.mzn: balance, difference between the least and largest number of occurrences in an array
- between_min_max.mzn: between_min_max, a specific number is between the minimum and maximum value of an array
- bin_packing2.mzn: Bin packing (different from the one above)
- cardinality_atleast: cardinality_atleast
- cardinality_atmost: cardinality_atmost
- cardinality_atmost_partition: cardinality_atmost_partition
- change.mzn: circular change, number of changes in an array
- change_pair.mzn: change_pair
- change_partition.mzn: change_partition
- circular_change.mzn: circular change, number of changes in an array (as change but with wrapping around the corner)
- circuit.mzn: circuit
- clique.mzn: clique
- common.mzn: common, also used_by
- count_ctr.mzn: count, more general than count in MiniZinc's globals.mzn
- counts.mzn: counts
- correspondence.mzn: correspondence
- cycle.mzn: cycle
- decreasing.mzn: decreasing
- derangement.mzn: derangement
- distance_between.mzn: distance between
- global_contiguity.mzn: global contiguity
- inflexions.mzn: inflexions, number of peaks in a sequence
- int_value_precede.mzn: int_value_precede
- k_alldifferent.mzn: k alldifferent (all rows satisfy the alldifferent constraint)
- longest_change.mzn: longest change, size of the longest sub sequence which satisfy a comparison operator (such as !=, <, > etc)
- nchange.mzn: nchange, (also a generalized version nchange_cmp with choice of operators)
- n_partitioning.mzn: n_partitioning
- n_change.mzn: n_change
- nvalue.mzn: nvalue, also: atleast_nvalue and atmost_nvalue
- nvalues.mzn: nvalues
- path_from_to.mzn: path_from_to, find a path from FROM to TO in a graph (incidence matrix)
- period.mzn: period (a sequence must have a period of a specific length)
- precedence.mzn: precedence (the first time we use j is before the first time we use k, for j < k)
- same.mzn: same
- stretch_circuit.mzn: stretch_circuit
(Note: don't work in version >= 0.8)
- stretch_path.mzn: stretch_path
- sum_ctr.mzn: sum ctr
- sum_free.mzn: sum free, also: product_free
Other models
Math, etc.
Back to my homepage
Created by Hakan Kjellerstrand hakank@bonetmail.com