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 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.
- The MiniZinc distribution contains the following solvers:
- Gecode/FlatZinc. Requires that Gecode is installed.
- The ECLiPSe Constraint Programming System
library(minizinc) (and library(flatzinc) provides 3 different solvers which corresponds to ECLiPSe's "normal" solvers:
* fzn_ic, see library(ic)
* fzn_fd, see library(fd)
* fzn_eplex, see library(eplex), which in turn can use different solvers, e.g. the commercial Cplex, XPress-MP, or the open source COIN solvers symclp, clpcbc.
- SICStus Prolog (from version 4.0.5 and onward): Zinc interface - library(zinc)
- JaCoP (Java Constraint Programming solver): Fz2jacop
- Google or-tools
- SCIP (Solving Constraint Integer Programs)
- fzntini. A SAT solver based on Tinisat.
- fzn2smt: Using SMT/SAT.
- Neng-Fa Zhou's BProlog solver, newer version for MiniZinc Challenge 2012: flatzinc2012.pl
- Picat, section "MiniZinc Challenge" (this was the version we submitted to MiniZinc Challenge 2013)
- Mistral 2.0
- Numberjack
- MiniCSP clause learning CSP solver (based on MiniSAT)
- fz_izplus (note: the web page is in Japanese)
- MinisatID: SAT/Lazy solver
- Opturion CPX Optimizer: CP/SAT solver
- Chuffed by Geoff Chu
- OscaR/CBLS Backend for MiniZinc by Gustav Björdal and Jean-Noël Monette
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:
2014-12-09: MiniZinc 2.0 is now officially released. Sme of the models below use features from this version, especially functions and some syntactic sugar.
Puzzles, small, and large
- 1d_rubiks_cube.mzn: 1D Rubik's cube (including GAP code for solving the problem using group theory)
- 1d_rubiks_cube2.mzn: 1D Rubik's cube (including GAP code for solving the problem using group theory). This version use only permutations arrays.
- 225_divisor.mzn: Smallest number divisible by 225 that consists of all 1s and 0s
- 3_coins.mzn: 3 coins (THT), in exactly 3 flips make HHH or TTT
- 3_jugs.mzn: 3 jugs problem (as shortest path problem)
- 3_jugs2.mzn: 3 jugs problem (using shortest_path_model.mzn)
- 3_jugs2_all.mzn: 3 jugs problem (using shortest_path_model.mzn), searches for all solutions (which happens to be unique)
- 18_hole_golf.mzn: A golf (i.e. shortest program) version of random 18-hole golf generation.
- a_card_trick_1.mzn: A card placement problem by Donald Preece (via Peter Cameron's blog post A card trick, 1)
- a_puzzle.mzn: The "8809 = 6 ..." puzzle (See God Play Dice: A puzzle)
- a_round_of_golf.mzn: A round of golf puzzle (Dell Logic Puzzles)
- abc_endview.mzn: ABC End View grid puzzle (a.k.a. "Easy as ABC", "Last Man Standing")
- added_corner.mzn: Added corner puzzle
- ages2.mzn: Ages problem from CTK Insights When Two Wrongs Make One Right
- alphametic2mzn.pl: Alphametic 2 Mzn. A Perl program converting alphametic puzzles to a MiniZinc model, including optimizing a variable. Examples:
perl alphametic2mzn.pl "SEND+MORE+MONEY"
perl alphametic2mzn.pl "SEND+MOST+MONEY" MOST max
(maximizing the MOST variable)
- allocating_developments.mzn: Allocating developments
- anniversaries.mzn: Anniversaries (Logic4Fun)
- another_kind_of_magic_square.mzn: Another kind of magic square (from "Fun with Numb3ers": Another kind of magic square)
- arch_friends.mzn: Arch friends puzzle (Dell Logic Puzzles)
- archery_puzzle.mzn: Archery puzzle (Sam Loyd)
- arithmetic_ring.mzn: Arithmetic ring problem
- arrow.mzn: Simple grid problem (from the Swedish blog post Pilen [translated "Arrow"])
- artificial_intelligence.mzn: Alphametic problem (from Erwin Kalvelagen Alphametics (3))
- atom_smasher.mzn: Digital Atom Smasher. Alphametic problem: sqrt(ATOM) = A + TO + M
- autoref.mzn: Auto referential puzzle
- averbach_1.2.mzn: Example 1.2 in Averbach & Chein "Problem Solving Through Recreational Mathematics"
- averbach_1.3.mzn: Example 1.3 in Averbach & Chein "Problem Solving Through Recreational Mathematics"
- averbach_1.4.mzn: Example 1.4 in Averbach & Chein "Problem Solving Through Recreational Mathematics"
- averbach_1.5.mzn: Example 1.5 in Averbach & Chein "Problem Solving Through Recreational Mathematics"
- babysitting.mzn: Babysitting puzzle (Dell Logic Puzzles)
- bales_of_hay.mzn: Bales of hay puzzle
- bananas.mzn: Bananas problem.
- bank_card.mzn: Bank card puzzle
- barrels.mzn: Barrels problem (From September Magic Contest 2014)
- before_and_after.mzn: Before and After (Logic4Fun)
- bertand_russell_puzzle.mzn: Bertrand Russell puzzle
- binary_puzzle.mzn: Binary puzzle
- binary_sudoku.mzn: Binary Sudoku
- binero.mzn: Binero grid puzzle (from Scampi)
- birthdays_2010.mzn: A simple birthday puzzle of my own, based on a coincidence of my and my brother's birth years.
- blueberry_muffins.mzn: Blueberry muffins problem (Brown Buffalo Logic Puzzles)
- breaking_news.mzn: Breaking news puzzle (Dell Logic Puzzles)
- bridge_and_torch_problem.mzn: Bridge and torch problem, crossing a bridge with a torch (a.k.a. The Midnight Train, and Dangerous crossing).
Data files:
- broken_weights.mzn: Broken weights problem
- buckets.mzn: Buckets problem (minimizing differences of masses in four buckets)
- building_blocks.mzn: Building blocks (Dell Logic Puzzles)
- bus.mzn: Bus puzzle (from rec.puzzles FAQ)
- calculs_d_enfer.mzn: Calculs d'enfer puzzle (from the NCL manual)
- calculs_d_enfer2.mzn: Calculs d'enfer puzzle (from the NCL manual), alternative model
- candies.mzn: Candies problem (from HackerRank)
- candles.mzn: Odometer problem from Cat Talk
- cashier_change.mzn: Cashier change problem (coin problem)
- calvin_puzzle.mzn: Calvin puzzle
- chandelier_balancing.mzn: Chandelier balancing (PuzzlOR)
- climbing_stairs.mzn: Climbing stairs
- coins_grid.mzn: Coins Grid (Tony Hurlimann)
- combination_locks.mzn: Combination locks (PuzzlOR)
- coins3.mzn: Minimum mumber of coins that allows one to pay exactly any amount smaller than one Euro
- coins3b.mzn: Minimum mumber of coins that allows one to pay exactly any amount smaller (here we also decide about the denominations of the coins)
- coins_problem.mzn: Minimum mumber of coins that allows one to pay exactly any amount smaller than one Euro (alternative solution based on OPL code)
- coins_41_58.mzn: Minimize number of coins - with the same amount of the different denominations - that sums to 41.58 GBP
- col_sum_puzzle.mzn: Find out values in a matrix, given column and row sums and some hints.
- congress.mzn: Congress puzzle (from XPress Mosel)
- cookie_bake_off.mzn: Cookie bake off (PuzzlOr)
- countdown.mzn: CountDown Game
- cube_sum.mzn: Sum a number with the minimum number of different cubes
- crossfigure.mzn: Crossfigure problem (CSPLib problem 21)
- crossword.mzn: Crossword solving (standard constraint programming example)
- crossword2.mzn: Crossword solving (standard constraint programming example), more general approach
- crossword_bratko.mzn: Crossword solving (example from Bratko "Prolog Programming for Artificial Intelligence", 4th edition)
- MiniZinc crossword page: This is a collection of 72 problem instances (from Gecode's crossword model). The model, general approach and benchmark is described in the blog post Crossword construction in MiniZinc using table constraints - a small benchmark on "72 Gecode problems"
- crypt_reversed.mzn: Crypt reversed puzzle: x + reversed(x) = z where all different(x) and all_different(z) (Requires MiniZinc 2.0)
- crypta.mzn: crypta, alphametic problem (standard Prolog benchmark)
- crypto.mzn: crypto, alphametic problem (standard Prolog benchmark), constraint programming model
- crypto_ip.mzn: crypto, alphametic problem (standard Prolog benchmark), integer programming model
- cur_num.mzn: Curious Number (Dudeney)
- defending_castle.mzn: Defending the Castle (Cut the knot)
- dennys_menu.mzn: Denny's Menu problem (How many combinations of $2,$4,$6,$8 will give $10?)
- devils_word.mzn: Devil's Word problem (see the Devil's word page)
- digital_roots.mzn: Digital roots
- digits_of_the_square.mzn: Digits of the square problem
- dimes.mzn: Dimes puzzle (rec.puzzles FAQ)
- dinner.mzn: A dinner problem
- dividing_the_spoils.mzn: Dividing the spoils (Sam Loyd)
- divisible_by_7.mzn: Divisible by 7 (Sam Loyd)
- divisible_by_1_to_1.mzn: Find a number divisible by 1 through 9 (for a "truncated" number)
- divisible_by_9_through_1.mzn: divisible by 9 through 1 for a "truncated" number
- divisors_ending_in_0_to_9.mzn: Divisors ending in 0 to 9
- domino.mzn: Solitaire Domino (placing of Domino tiles)
domino2.mzn: Solitaire Domino (placing of Domino tiles), faster version.
Data:
- domino0.dzn: Gecode's example 0
- domino1.dzn: Gecode's example 1
- domino2.dzn: Gecode's example 2
- domino3.dzn: Gecode's example 3
- domino4.dzn: Gecode's example 4
- domino5.dzn: Gecode's example 5
- domino_ecl.dzn: ECLiPSe's example (from domino.ecl)
- domino_sicstus_a.dzn: SICStus' example (from dominoes.ecl, instance "a")
- domino_sicstus_51.dzn: SICStus' example (from dominoes.ecl, instance 51)
- domino_sicstus_71.dzn: SICStus' example (from dominoes.ecl, instance 71)
- domino_sicstus_72.dzn: SICStus' example (from dominoes.ecl, instance 72)
- domino_sicstus_81.dzn: SICStus' example (from dominoes.ecl, instance 81)
- domino_sicstus_82.dzn: SICStus' example (from dominoes.ecl, instance 82)
- domino_sicstus_91.dzn: SICStus' example (from dominoes.ecl, instance 91)
- domino_sicstus_101.dzn: SICStus' example (from dominoes.ecl, instance 101)
- domino_sicstus_111.dzn: SICStus' example (from dominoes.ecl, instance 111)
- domino_sicstus_121.dzn: SICStus' example (from dominoes.ecl, instance 121)
- domino_sicstus_181.dzn: SICStus' example (from dominoes.ecl, instance 181)
- domino_sicstus_182.dzn: SICStus' example (from dominoes.ecl, instance 182)
- domino_sicstus_201.dzn: SICStus' example (from dominoes.ecl, instance 201)
- domino_sicstus_221.dzn: SICStus' example (from dominoes.ecl, instance 221)
- domino_sicstus_251.dzn: SICStus' example (from dominoes.ecl, instance 251)
- domino_vaderlind_1.dzn: Problem 1 from Paul Vaderlind's Swedish puzzle book "Vaderlinds specialblandning: Sudoku, Kakuro och andra rutiga tankelekar" (tr. ~ "Vaderlind's special brew: Sudoku, Kakuro, and other squared thought games")
- domino_vaderlind_2.dzn: Problem 2 from Paul Vaderlind's Swedish puzzle book "Vaderlinds specialblandning: Sudoku, Kakuro och andra rutiga tankelekar"
- domino_vaderlind_3.dzn: Problem 3 from Paul Vaderlind's Swedish puzzle book "Vaderlinds specialblandning: Sudoku, Kakuro och andra rutiga tankelekar"
- domino_simonis.dzn: Problem from Helmut Simonis' "Dominoes as a Constraint Problem", page 1
- domino_glaeser.dzn: Problem from "Thinking Mathematically", p. 172
- donald.mzn: Alphametic puzzle: DONALD + GERALD = ROBERT
- donald2.mzn: Alphametic puzzle: DONALD + GERALD = ROBERT (using carries)
- drinking_game.mzn: Drinking game (Marriott & Stuckey)
- drive_ya_nuts.mzn: Drive Ya Nuts puzzle (rotated "nuts")
- dudeney_numbers.mzn: Dudeney numbers (inspired by Pierre Schaus' Google CP/Python code in Dedeney numbers)
- einav_puzzle.mzn: Solving the A programming puzzle from Einav
- eliza_pseudonym7.mzn: Eliza Pseudonym of Puzzlania 7
- einstein_hurlimann.mzn: Einstein puzzle (variant of Zebra puzzle)
- einstein_opl.mzn: Einstein puzzle (variant of Zebra puzzle, from an OPL model)
- enclosed_tiles.mzn: Enclosed tiles (from Stack Overflow How do I write a program to find the tiles that are completely enclosed?)
- Enigma problems (originally from New Scientist Magazine). Also see Jim Randell's blog Enigmatic Code - Programming Enigma Puzzles for many problems and solutions.
- equation.mzn: Solve the problem
11x11=4; 22x22=16; 33x33=?
(four interpretations)
- ett_ett_ett_ett_ett__fem.mzn: Alphametic puzzle ETT + ETT + ETT + ETT + ETT = FEM
- Project Euler problems:
- exodus.mzn: Exodus problem (Dell Logic Puzzle)
- family_riddle.mzn: Family riddle
- fair_xmas_duty_2014.mzn: Fair Xmas duty 2014 (Swedish holidays)
- farmer_and_cows.mzn: Farmer and cows problem
- farmer_and_cows_mip.mzn: Farmer and cows problem (MIP approach)
- fancy.mzn: Mr Greenguest puzzle (Fancy dress puzzle)
- farm_puzzle0.mzn: Farm puzzle, simple model
- farm_puzzle.mzn: Farm puzzle, more general model
- fill_a_pix.mzn: Fill-a-pix puzzle.
Data files:
- fill_in_the_squares.mzn: Fill in the squares (Brainjammer problem)
- five_brigades.mzn: Five brigades (Dudeney)
- five_elements.mzn: Five elements problem (Charles W. Trigg)
- five_floors.mzn: Five floors problem (Dinesman)
- five_statements.mzn: Five statements problem (logic problem)
- five_translators.mzn: Five translators (set version)
- five_translators2.mzn: Five translators, matrix 0/1 version
- four_islands.mzn: Four islands puzzle (Dell Logic Puzzles)
- four_same_friends.mzn: Four same friends problem
- four_trees.mzn: Four trees problem (Logic4Fun)
- fractions.mzn: Fractions, alphametic problem (standard Prolog benchmark)
- franklin_8x8_magic_square.mzn: Benjamin Franklin's 8x8 Magic Square
- funny_dice.mzn: Funny dice problem (Sunday Times teaser 2739)
- futoshiki.mzn: Futoshiki puzzle
- gardner_two_plus_two.mzn: Martin Gardner's TWO+TWO=FOUR problem
- general_store.mzn: General store problem (Sam Loyd)
- golf_puzzle.mzn: Golf puzzle (Sam Loyd)
- good_burger_puzzlor.mzn: Good Burger (PuzzlOR)
- greatest_combination.mzn: Greatest combination problem (from StackOverflow Solving Prolog puzzle)
- grid_puzzle.mzn: Grid puzzle (from StackOverflow Riddle in Prolog)
- grime_puzzle.mzn: See Travels in a Mathematical World Blog A puzzle from James Grime about abcdef)
- grocery2.mzn: Grocery problem, alternative version
- guards_and_apples.mzn: Guards and apple problem
- guards_and_apples2.mzn: Guards and apple problem (variant)
- handshaking.mzn: Halmo's handshake problem
- hanging_weights.mzn: Hanging weights puzzle
- hardy_1729.mzn: Hardy's 1729 problem
- harry_potter_seven_potions.mzn: Harry Potter's seven potions problem
- hidato.mzn: Hidato puzzle
- hidato_exists.mzn: Hidato puzzle, same as above but it use
exists
which is less efficient
- hidato_table.mzn: Hidato puzzle, using a
table
constraint.
- hidato_table2.mzn Hidato puzzle, can also solve non-rectangular problems.
- houses.mzn (from Algebra 1, Glencoe/McGraw-Hill, 1998 via kanren)
- huey_dewey_louie.mzn: Huey, Dewey, Louie, logical problem from Marriott & Stuckey "Programming in Constraints"
- heterosquare.mzn: Heterosquare problem
- how_old_am_i.mzn: How old am I (from Choco)
- hundred_doors_unoptimized.mzn: 100 doors problem, unoptimized (array version) (Rosetta code)
- hundred_doors_unoptimized2.mzn: 100 doors problem, unoptimized (array version, alternative model) (Rosetta code)
- hundred_doors_optimized.mzn: 100 doors problem, optimized (set version) (Rosetta code)
- hundred_doors_optimized_array.mzn: 100 doors problem, optimized (array version) (Rosetta code)
- hundred_fowls.mzn: Hundred Fowls puzzle
- high_iq_problem.mzn: "High IQ problem"
- its_a_tie.mzn: "It's a tie" problem (Dell Logic Puzzles)
- jellybeans.mzn: Jellybeans
- jobs_puzzle.mzn: Jobs puzzle (an automated reasoning problem, TPTP #19)
- kakuro.mzn: Kakuro puzzle
- kakuro2.mzn: Kakuro puzzle, alternative representation of the hints.
- kakuro3.mzn: Kakuro puzzle, simple version (inspired by BProlog's model)
- kaprekars_constant.mzn: Kaprekar's Constant
- kaprekars_constant2.mzn: Kaprekar's Constant (calculate the fixpoint for different lengths)
- kenken2.mzn: KenKen puzzle
- killer_sudoku.mzn: Killer Sudoku puzzle
- killer_sudoku2.mzn: Killer Sudoku puzzle, alternative representation of the hints
- kordemskys_palindrome_problem.mzn: Kordemsky's Palindrome problem
- krypto.mzn: Krypto puzzle (combine given numbers to an objective using the four basic arithmetic operations)
- labeled_dice.mzn: Labeled dice, from Jim Orlin "Colored letters, labeled dice: a logic puzzle"
- language_round_table.mzn: Languages spoken at a round table (from Stack overflow: A prolog program that reflects people sitting at a round table)
- latin_square_card_puzzle.mzn: Latin square card puzzle
- 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?
- least_diff1.mzn: Least diff problem: simpler version.
- lecture_series.mzn: Lecture series puzzle (Dell Logic Puzzles)
- letter_square.mzn: Letter square problem (Vaderlind).
Data files:
- library_books.mzn: Library books (Logic4Fun)
- lights_out.mzn: Lights out puzzle
- lights_out_all.mzn: Variant of Lights out puzzle (flip all cells in row and column)
- limerick_primes.mzn: Limerick Primes (see John D. Cook: Limerick Primes). A more declarative version: limerick_primes2.mzn
- loading_pair_of_dice.mzn: Loading a pair of dice (by cheating)
- locker.mzn: Locker puzzle.
- local_art_theft.mzn: Local Art Theft problem.
- local_art_theft1.mzn: Local Art Theft problem. A much more verbose model.
- logic_puzzle_aop.mzn: Logic puzzle (from The Art of Prolog)
- lost_at_sea.mzn: Lost at Sea (PuzzlOR)
- lucky_number.mzn: Lucky numbers (see God Plays Dice What is the origin of Kirillov's lucky number problem)
- m_queens_on_n_board.mzn: M queens on a N x N board
- M12.mzn: Solving the M12 puzzlea
- M12b.mzn: Solving the M12 puzzle. A variant using just permutations.
- magic.mzn: Magic square, integer programming (GLPK)
- magic3.mzn: Magic sequence, 3 x 3 (this formulations is from a standard Prolog benchark)
- magic4.mzn: Magic sequence, 4 x 4 (this formulations is from a standard Prolog benchark)
- magic_modulo_number.mzn: Magic modulo number (from Scampi)
- magic_sequence.mzn: Magic sequence (CSPLib)
- magic_sequence2.mzn: Magic sequence (CSPLib), alternative model
- magic_sequence3.mzn: Magic sequence (CSPLib), alternative model
- magic_sequence4.mzn: Magic sequence (CSPLib), alternative model
- magic_series.mzn: Magic series
- magic_square.mzn: Magic squares
- magic_square_function.mzn: Magic squares using some extra function (requires MiniZinc 2.0)
- magic_square_associate.mzn: Associative Magic squares
- magic_square_frenicle_form.mzn: Magic squares with symmetry breaking (Frénicle standard form)
- magic_square_primes.mzn: Magic squares with only prime numbers
- magic_square_water_retention.mzn: Magic squares water retention problem
- mamas_age.mzn: Mama's age (Dudeney)
- manasa_and_stones.mzn: Manasa and Stones problem
- marathon.mzn: Marathon puzzle (XPress example), MIP model
- marathon2.mzn: Marathon puzzle (XPress example), CP model
- message_sending.mzn: Message sending puzzle (cf all_paths_graph.mzn)
- minesweeper.mzn: Minesweeper puzzle
- minesweeper_inverse.mzn: Minesweeper "inverse" problem (given the bombs, calculate the number of neighbours)
- minesweeper_model.mzn: Minesweeper puzzle, general model to be used with the following problems:
- miss_manners.mzn: Miss Manners' seating problem (standard benchmark for rule engines). Data:
- mislabeled_boxes.mzn: Mislabeled boxes (theorem proving problem, TPTP #12)
- missing_digit.mzn: Missing digit probblem
- money_change.mzn: Simple money change problem
- monks_and_doors.mzn: Eight monks and four doors
- monorail.mzn: Monorail puzzle (Grand Tour).
Data:
- movement_puzzle.mzn: Movement puzzle (1d array)
- moving_coins.mzn: Moving coins in a triangle (generalized model)
- mr_smith.mzn: Mr Smith problem (IF Prolog)
- muddle_management.mzn: Muddle management (Logic4Fun)
- multipl.mzn: Unknown multiplication (standard Prolog benchmark)
- multiplicative_sequence.mzn: Multiplicative sequence
- murder.mzn: Murder puzzle
- music_men.mzn: Music men puzzle
- n_puzzle.mzn: N-puzzle, e.g. 8-puzzle, 15-puzzle
- narcissistic_numbers.mzn: Narcissistic numbers
- number_of_regions.mzn: Number of regions (Vaderlind, Guy, Larson: "The Inquisitive Problem Solver", problem 21)
- number_puzzle.mzn: A number puzzle (of some kind)
- numbrix.mzn: Numbrix (cf Hidato), MIP model
- numeric_keypad.mzn: Numeric keypad problem
- nonogram.mzn: Nonogram, a.k.a. Painting by numbers. Also, see "nonogram_regular.mzn" and "nonogram_create_automaton.mzn" below.
- nonogram_regular.mzn: Nongoram, a.k.a. Painting by numbers. This version uses the
regular
constraints and is much faster than nonogram.mzn.
Note that the data models must be in a specific format (listing the finite states for the regular
constraint, converted (for example) by the Perl program make_nonogram_automata.pl. Below is a list of data instances with the proper format. The data files used with nonogram_regular.mzn is the "*_aut.dzn" version. Also, see "nonogram_create_automaton.mzn" below.
- nonogram_create_automaton.mzn: Nonogram solver. This version uses the
regular
constraints and is much faster than nonogram.mzn.
In contract to nonogram_regular.mzn it creates the automata from the Nonogram patterns (clues), so no preprocessing step is needed. The data file used is the files shown above for "nonogram_regular.mzn" with no "_aut" in its name.
- nonogram_create_automaton2.mzn: Nonogram solver. A version of nonogram_create_automaton.mzn that calculates the states as par variables (not decision variables). Note: It is the recommended model, especially for solvers that have an optimized version of the
regular
constraint.
Data files: besides the data files above, there is now a dedicated page for Nonogram problems: MiniZinc: Nonogram problem instances in .dzn format (from JaCoP's distribution) .
- nonogram_gchq.mzn: Nonogram GCHQ problem with fixed black cells. From Can you solve the British spy agency’s ridiculously difficult Christmas puzzle?
- number_generation.mzn: Number generation (cf Devil's word)
- number_square.mzn: Recreational mathematics (Pascal Van Hentenryck: "The OPL Optimization Programming Language")
- numberlink.mzn: Numberlink grid puzzle
Instances:
- OandX.mzn: Three Dimensional Nought and Crosses (Tic-Tac-Toe) (Williams)
- odd_even_sequences.mzn: Odd/even sequence (from Presh Talwalkar How many odd-even sequences are there?)
- office_blocked.mzn: Office blocked (Logic4Fun)
- office_blocked2.mzn: Office blocked, alternative approach (Logic4Fun)
- olympic.mzn: Olympic problem (standard Prolog benchmark)
- one_off_digit.mzn: One off digit problem (Richard Wiseman)
- pair_divides_the_sum.mzn: Pair divides the sum problem
- pandigital_numbers.mzn: Pandigital numbers (any base <= 10)
- party_mixing.mzn: Party mixing (mixing people at different tables),
- party_mixing2.mzn: simpler version (skipping the matrix)
- peacableArmyOfQueens.mzn: Peacable Army of Queens
- perfect_square_sequence.mzn: Perfect square sequence
- philosophical_railway.mzn: Philosophical railway
- 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: Placing Number Puzzle
- place_number2.mzn: Placing Number Puzzle, alternative approach. Also includes a 12-number problem.
- place_number3.mzn: Placing Number Puzzle, a more general approach than place_number.mzn and place_number2.mzn
- planet_colonization_puzzlor.mzn: Planet Colonization (PuzzlOR problem)
- primes_in_a_circle.mzn: Primes in a circle
- puzzle1.mzn: Yet another column/row sum problem
- pyramid_of_numbers.mzn: Pyramid of numbers (Rosetta code)
- queens3.mzn: n-queens problem
- queens4.mzn: n-queens problem, using alldifferent
- queens_and_knights.mzn: Queens and Knights
- queens_diversity.mzn: n-queens diversity problem
- queens_ip.mzn: n-queens problem, integer programming model (GLPK)
- queens_viz.mzn: n-queens problem, using CP-Viz
- raven_puzzle.mzn: "Polyglot puzzle" (from Raven, swedish)
- remarkable_sequence.mzn: Remarkable sequence (from an Alma-0 model), i.e Langford problem n=9, k=3.
- reveal_the_mapping.mzn: Reveal the mapping (from David Bolton: Programming Contest 46 - Reveal the Mapping)
- reverse_multiples.mzn: Reverse multiples
- rock_star_dressing_problem.mzn: Rock star dressing problem
- rogo.mzn: Rogo grid puzzle, rogo2.mzn (faster version with symmetry breaking)
Problem instances:
- rogo3.mzn: Rogo grid puzzle, a yet faster version using
table
constraint for the connections and some other improvements. Note that this version also use the "Best" points (which has been added to the problem files). Data files:
- rook_path.mzn: Rook path (on a square matrix)
- rotating_discs.mzn: Rotating discs (from Jean-Luis Lauriere's ALICE paper, page 84f)
- rotation.mzn: Nokia's "rotation puzzle"
- rotation2.mzn: Nokia's "rotation puzzle", using just permutation arrays.
- rubiks_cube.mzn: Rubik's cube, find the optimal number of moves. Using only the 6 permutations representing the moves, and their inverses.
- safe_cracking.mzn: Safe cracking
- samurai_puzzle.mzn: Samuraï grid puzzle
- seating_plan.mzn: Seating plan (Daniel L. Dudley, The Nut Cracker suit #1)
- secret_santa.mzn: Secret Santa problem
- secret_santa2.mzn: Another Secret Santa problem
- self_referential_quiz.mzn: Self-referential quiz
- self_referential_sentence.mzn: Self-referential sentence
- send_more_money.mzn: Alphametic puzzle: SEND + MORE = MONEY
- send_more_money2.mzn: Alphametic puzzle: SEND + MORE = MONEY, alternative model
- send_more_money_any_base.mzn: Alphametic puzzle: SEND + MORE = MONEY, in any base
- send_more_money_ip.mzn: Alphametic puzzle: SEND + MORE = MONEY, integer programming model (GLPK)
- send_most_money.mzn: Alphametic puzzle: SEND + MOST = MONEY (maximize MONEY)
- sequence_2_3.mzn: Simple permutation puzzle
- sequence_puzzle.mzn: Sequence puzzle (from StackOverflow: What's a more efficient implementation of this puzzle?)
- seseman.mzn: Seseman Convent problem (see Seseman Convent problem)
- seseman2.mzn: Seseman Convent problem, generalized model
- skyscraper.mzn: Skyscraper puzzle
- spy_girls.mzn: Spy girls problem
- 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
- soccer_puzzle.mzn: Soccer puzzle
- sokoban.mzn: Sokoban problem
- solitaire_battleship.mzn: Solitaire Battleship
- spinning_disks.mzn: The spinning disks problem from Skeptic's Play
- state_name_puzzle.mzn: State name puzzle (from Rosetta Code: )
- strata.mzn: Strata grid puzzle
- strimko.mzn: Strimko puzzle (Latin squares with "streams")
Some data files:
- strimko2.mzn: Strimko puzzle (Latin squares with "streams"). This variant uses an easier instance representation than strimko.mzn
Some data files:
- students_and_languages.mzn: Students and Languages problem (Antoni Niederlinski)
- subsets_100.mzn: Subsets 100 (rec.puzzles FAQ)
- successive_number_problem.mzn: Successive number problem (from God Plays Dice: A cute number theory puzzle)
- sudoku_alldifferent.mzn: Sudoku, using the global constraint
alldifferent
.
In the directory sudoku problems2 are all the 91 Sudoku problems (of different dimensions: 9x9, 16x16, and 25x25) from Gecode's Sudoku model sudoku.cpp.
- sudoku_gcc.mzn: Sudoku, using the global cardinality constraint.
sudoku_gcc_model.mzn, this is a general Sudoku to be included from a Sudoku problem instance. In the directory sudoku problems are all the 91 Sudoku problems (of different dimensions: 9x9, 16x16, and 25x25) from Gecode's Sudoku model sudoku.cpp.
- sudoku_ip.mzn: Sudoku, integer programming (GLPK)
- sudoku_multi.mzn: Multi-Sudoku (two connected Sudokus)
- sudoku_multi2.mzn: Multi-Sudoku (two connected Sudokus), a slightly different approach of connecting the two grids
- sudoku_pi_2008.mzn: Pi Day Sudoku 2008
- sudoku_pi.mzn: Pi Day Sudoku 2009
- sudoku_pi_2010.mzn: Pi Day Sudoku 2010
- sudoku_pi_2011.mzn: Pi Day Sudoku 2011
- sudoku_pi_day_2015.mzn: Pi Day Sudoku 2015
- sudoku_25x25_250.mzn: Sudoku 25 x 25 problen (very hardcoded, from a Prolog benchmark)
- sultans_children.mzn: Sultan's children problem
- sum_first_and_last.mzn: Sum first and last (grid puzzle) Requires MiniZinc 2.0
- sum_to_100.mzn: Five numbers should sum to 100, and all numbers must be divisible by 2 or 5
- sumbrero.mzn: Sumbrero puzzle
- survo_puzzle.mzn: Survo puzzle
- table_of_numbers.mzn: Table of numbers problem (from Fun With Num3ers Table of numbers with 5 rows and 5 columns)
- takuzu.mzn: Takuzu grid puzzle
- talisman_square.mzn: Talisman Square
- tantalizer_487_number_system.mzn: Tantalizer 487: Number System
- ten_statements.mzn: From Richard Wiseman It's the Friday Puzzle! (2012-07-20)
- the_bomb.mzn: The bomb, logical puzzle (Janko "Die Bombe")
- the_family_puzzle.mzn: The family puzzle (from Drools Puzzle Round 2: The Family Puzzle)
- the_interns.mzn: The Interns problem (theorem proving problem, TPTP #18)
- tennis_problem.mzn: Tennis problem (Jean-Loius Laurière)
- tennis_tournament.mzn: Tennis tournament scheduling
- thick_as_thieves.mzn: Thick as thieves (Logic4Fun)
- thirteen_link_chain_puzzle.mzn: The 13-Link Chain Puzzle (just additions) (inpired by NY Times 'Wordplay' The 13-Link Chain Puzzle), Second approach (still just additions): thirteen_link_chain_puzzle2.mzn, Third approach: thirteen_link_chain_puzzle3.mzn (both additions and subtractions which is closer to the stated problem)
- three_digit.mzn: Three digit problem
- tickTackToe.mzn: Tick Tack Toe (Tic Tac Toe)
- tictactoe_avoidance.mzn: Tic-tac-toe avoidance (on a NxN board, place NxN-N 'X's without making three-in-a-row in any direction. Inspired by Richard Wiseman's It's the Friday Puzzle 20131115)
- timeslots_for_songs.: Timeslot problem (from Stack Overflow: What category of combinatorial problems appear on the logic games section of the LSAT?)
- timpkin.mzn: Mrs Timpkin's age problem (Dudeney)
- tomography.mzn: Discrete Tomography (one color model)
- tomography_n_colors.mzn: Discrete Tomography (n color model)
- torn_number.mzn: Torn number puzzle (Dudeney)
- triangles.mzn: Triangles problem
- tunapalooza.mzn: Tunapalooza puzzle (Dell Logic Puzzles)
- twelve_statements.mzn: Twelve statements puzzle
- twin_letters.mzn: Twin letters
- uzbekian_puzzle.mzn: Uzbekian puzzle
- virtual_chess_tournament.mzn: Virtual Chess Tournament problem (from OpenRules Blog (Jacob Feldman) Fisher vs. Kasparov vs. Karpov
- war_or_peace.mzn: War or peace problem (Alma-0)
- water_buckets1.mzn: Water bucket problem (generalized)
- who_killed_agatha.mzn: Who killed agatha? (The Dreadsbury Mansion Murder Mystery, a automated reasoning problem, TPTP #1)
- wijuko.mzn: Wijuko grid puzzle
- wiseman_problem_20131129.mzn: Problem from Richard Wiseman 20131129
- wolf_goat_cabbage_lp.mzn: Wolf, goat, cabbage problem (a.k.a. river crossing problem) using a LP model. Shows all (2) solutions.
- word_golf.mzn: Word golf (word chain)
- word_golf_n3.mzn: 3 letter words for Word golf
- word_golf_n4.mzn: 4 letter words for Word golf
- word_square.mzn: Word square: square matrix cross words (fill the whole square with unique words). (Data files: word_len3.mzn, word_len4.mzn, word_len5.mzn)
- wwr.mzn: alphametic problem: WRONG + WRONG = RIGHT
- xkcd.mzn: xkcd's knapsack problem (see the xkcd strip for the problem)
- xkcd_among_diff_0.mzn: xkcd's knapsack problem using the global constraint
among_diff_0
(inspired by Helmut Simonis presentation Acquiring Global Constraint Models on CP2011)
- zebra_inverse.mzn: Zebra puzzle, using global constraint
inverse
instead of all_different
- zebra_ip.mzn: Zebra puzzle, integer programming model (GLPK)
Operations research, linear programming, integer programming, scheduling
- assignment.mzn: Assignment problem (Winston)
- assignment2.mzn: Assignment problem (Winston's swimming team example)
- assignment2_2.mzn: Assignment problem (Winston's swimming team example, expanded)
- assignment3.mzn: Assigment problem (Winston, celebreties on an island)
- assignment4.mzn: Yet another assigment problem
- assignment5.mzn: Yet another assigment problem
- assignment6.mzn: Assigment problem (GLPK:s example assign.mod)
- assignment_model.mzn: Assigment problem (model)
- best_host.mzn: Best host problem (from PuzzlOR)
- blending_problem.mzn: Blending problem
- bridges_to_somewhere.mzn: Bridges to Somewhere (from PuzzlOR)
- building_a_house.mzn: Simple scheduling problem: building a house (from OPL)
- building_a_house2.mzn: Simple scheduling problem: building a house (from Mozart/Oz)
- building_a_house_model.mzn: Simple scheduling problem: building a house, generalized model of the two examples above. Data files:
- bus_scheduling.mzn: Bus scheduling (Taha)
- bus_scheduling_csplib.mzn: Bus driver scheduling (CSPLib problem 22). Data files:
- capital_budget2.mzn: Capital Budget (Winston)
- chessset.mzn: Chess set problem (XPress)
- choose_your_crew.mzn: Choose your crew (from PuzzlOR)
- coloring_ip.mzn: Map coloring, integer programming (inspired by the GLPK model color.mod)
- company_competition.mzn: (Christmas) Company Competition Problem: Mixing teams
- constraint.mzn: Optimizing a constraint (Williams)
- contiguity_mip.mzn: Contiguity constraint (MIP, using floats)
- contiguity_mip2.mzn: Contiguity constraint (using random 0/1)
- contractor_costs.mzn: Contractor costs (Sam Loyd)
- crew.mzn: Crew scheduling (Gecode)
- crossbar.mzn: Crossbar problem (Prolog benchmark problem)
- critical_path1.mzn: Critical Path (Winston)
- cutting_stock_winston.mzn: Cutting stock problem (Winston)
- diet1.mzn: Diet problem (standard OR example)
- eyedrop_optimize.mzn: Optimize the time (hour) a number of different eye drops should be taken on a day (disperse each type as much as possible)
- eyedrop_optimize2.mzn: Optimize the time (hour) a number of different eye drops should be taken on a day (disperse each type as much as possible). This version don't use temporary varibles which makes it (much) faster for some solvers.
- fixed_charge.mzn: Fixed charged problem (OPL)
- facility_location_problem.mzn: Facility location problem
- football.mzn: Buying soccer players (lp_solve mailing list)
- freight_transfer.mzn: Freight Transfer (John Hooker)
- furniture.mzn: Furniture problem (best combination of offers to buy furnitures)
- furniture_moving.mzn: Optimizing furniture moving (Marriott and Stuckey)
- gap.mzn: Generalized Assignment Problem (GLPK, AMPL)
- giapetto.mzn: Simple optimization problem of maximizing profit
- hitchcock_transporation_problem.mzn: Hitchcock-Koopmans transportation problem
- home_improvement.mzn: Home improvement (from PuzzlOR)
- ice_cream.mzn: Ice cream production given monthly demand.
- integer_programming1.mzn: Simple integer programming problem
- investment_problem.mzn: Investment problem (constraint programming version)
- investment_problem_mip.mzn: Investment problem (MIP version)
- jobshop.mzn: Job-Shop Scheduling Problem, general approach. jobshop2.mzn outputs more informations.
Data files
- jssp.mzn: Job-Shop Scheduling Problem (GLPK) (this is the MT06 problem instance)
- knapsack_investments.mzn: Knapsack (investment) problem (Lundgren, Rönnqvist, Värbrand: Optimeringslära)
- kraftwerk_ticket_problem.mzn: Kraftwerk ticket problem
- lager.mzn: Stock model (Swedish)
- least_square_optimeringslara_286.mzn: Least sqauare (Lundgren, Rönnqvist, Värbrand: Optimeringslära)
- lightmeal.mzn: Lightmeal problem (Colmerauer)
- lightmeal2.mzn: Lightmeal problem (Colmerauer), integer programming version (and more general than lightmeal.mzn)
- make_a_good_burger.mzn: Make a Good Burger problem
- matchmaker.mzn: Matchmaker problem (from PuzzlOr)
- max_activity.mzn: Scheduling activities for kids (from StackOverflow Need help for defining appropriate constraints)
- max_activity2.mzn: Scheduling activities for kids, added 0 scores (from StackOverflow Need help for defining appropriate constraints)
- max_cut.mzn: Maximum cut problem (GLPK)
- max_flow_taha.mzn: Maximum flow problem (Taha)
- max_flow_winston1.mznMaximum flow problem (Winston)
- maxflow.mzn: Maximum flow problem (GLPK)
- mceverywhere.mzn: McEverywhere problem (PuzzlOR)
- mfasp.mzn: Minimum Feedback Arc Set Problem (GLPK)
- mfvsp.mzn: Minimum Feedback Vertex Set Problem (GLPK)
- misp.mzn: Maximum Independent Set Problem (GLPK) (cf maximal_independent_sets.mzn)
- movie_stars.mzn: Movie Stars (from PuzzlOR)
- mvcp.mzn: Minimum Vertex Cover Problem (GLPK)
- nadel.mzn: B.A. Nadel's construction problem
- newspaper0.mzn: Scheduling newspapers reading (French '82, Duncan '90), this is a simplified version of newspaper.mzn since it's quite overloaded with presentations stuff.
- newspaper.mzn: Scheduling newspapers reading (French '82, Duncan '90)
- number_of_days.mzn: Number of days problem (knapsack)
- nurse_rostering_with_availability.mzn: Scheduling (here nurse rostering) with an availability matrix (from Reconciling Scheduled shifts with availabilities)
- or_matching.mzn: Matching of OR'ers (problem from the Nigel Lewis' Cupids with Computers)
- or_matching2.mzn: Matching of OR'ers (see above), MIP model.
- or_seating.mzn: Seating placement of OR'ers (inspired by Nigel Lewis' Cupids with Computers)
- organize_day.mzn: Scheduling, organizing a day (ECLiPSe)
- patient_no_21.mzn: Patient No. 21 (From PuzzlOR)
- pert.mzn: PERT problem (van Hentenryck)
- popsicle_stand.mzn: Popsicle stand problem (PuzzlOR)
- post_office_problem.mzn: Post office problem (Winston)
- post_office_problem2.mzn: Post office problem, generalized model (Winston)
- product_configuration.mzn: Product configuration (John Hooker)
- relief_mission.mzn: Relief mission (from PuzzlOR)
- rostering.mzn: Rostering problem (Regin)
- schedule1.mzn: Scheduling using cumulative constraint (Sicstus)
- schedule2.mzn: Scheduling problem, yet another (from Shasha "Puzzles for Programmers and Pros", page 131f)
- scheduling_bratko.mzn: Scheduling problem from Ivan Bratko "Prolog - programming for Artificial Intelligence", example 1
- scheduling_bratko2.mzn: Scheduling problem from Ivan Bratko "Prolog - programming for Artificial Intelligence", example 2
- scheduling_chip.mzn: Scheduling problem from Nicolas Beldiceanu & Evelyne Contejean "Introducing Global Constraints in CHIP", page 3
- scheduling_with_assignments.mzn: Scheduling with assignments of the workers (and a lot of different outputs such as assignment matrices, schedules, and timelines for jobs as well as for the workers in a Gantt-like manner). It also supports precedences, enforcing non-idleness for the workers (flag
allow_idle=false
, see #10, Graham's bicycle assembly problem), and also enforce that the tasks must be done by "nearby" workers (collect_workers=true
, see #14, perfect square placement).
Data files:
- scheduling_with_assignments1.dzn: From Marriot & Stuckey "Programming with Constraints", page 112f (furniture moving)
- scheduling_with_assignments2.dzn: From Ivar Bratko: "Prolog - - Programming for Artificial Intelligence", 3rd edition, page 329ff. Includes precedences.
- scheduling_with_assignments3.dzn: Problem from Global constraints catalog (cumulative)
- scheduling_with_assignments4.dzn: From SICStus' documentation
- scheduling_with_assignments5.dzn: A harder test.
- scheduling_with_assignments6.dzn: From the OPL scheduling model (sched_intro.mod, building a house). Includes precedences.
- scheduling_with_assignments7.dzn: Another hard test.
- scheduling_with_assignments8.dzn: Much harder test.
- scheduling_with_assignments8b.dzn: Variant of scheduling_with_assignments8.dzn with precedences (is solved much faster).
- scheduling_with_assignments9.dzn: From Andreas Schutt, Thibaut Feydy, Peter J. Stuckey, Mark G. Wallace: "Explaining the cumulative propagator", page 2 (with precedences)
- scheduling_with_assignments10.dzn: Bicycle assembly problem (from R.L. Graham "Combinatorial Scheduling Theory")
- scheduling_with_assignments10b.dzn: Bicycle assembly problem (from R.L. Graham "Combinatorial Scheduling Theory"), variant: we don't allow idleness of the workers
- scheduling_with_assignments10c.dzn: Bicycle assembly problem (from R.L. Graham "Combinatorial Scheduling Theory"), variant: we don't allow idleness of the workers and increase to 3 teams
- scheduling_with_assignments10d.dzn: Bicycle assembly problem (from R.L. Graham "Combinatorial Scheduling Theory"), variant: we don't allow idleness of the workers and decrease the duration times with one units each
- scheduling_with_assignments11.dzn: Another problem from R.L. Graham "Combinatorial Scheduling Theory"
- scheduling_with_assignments12.dzn: Scheduling a dinner party (from Robert A. McGuigan: "Scheduling Problems and Bin Packing")
- scheduling_with_assignments13.dzn: Service of a plane (from Joseph Malkevitch: "Is it on Time?")
- scheduling_with_assignments14.dzn: A small perfect square placement problem, 14x14 (using
collect_workers=true
)
- scheduling_with_assignments14b.dzn: Harder perfect square placement problem, 112x112 (using
collect_workers=true
)
- scheduling_with_assignments15.dzn: Yet another problem from R.L. Graham "Combinatorial Scheduling Theory"
- scheduling_with_assignments16.dzn: Bin packing as a scheduling problem.
- scheduling_with_assignments16b.dzn: Bin packing as a scheduling problem (larger example).
- scheduling_with_assignments16c.dzn: Bin packing as a scheduling problem (simpler variant of scheduling_with_assignments16b.dzn).
- scheduling_with_assignments16d.dzn: Bin packing as a scheduling problem
- scheduling_with_assignments16e.dzn: Bin packing as a scheduling problem (minimize the number of disks for backup files); smaller variant where the sizes has been divided by 10: scheduling_with_assignments16e2.dzn
- scheduling_with_assignments16f.dzn: Bin packing as a scheduling problem (from R.L. Graham "Combinatorial Scheduling Theory")
- scheduling_with_assignments16g.dzn: Bin packing as a scheduling problem (printing business cards, from Stack Overflow)
- scheduling_with_assignments17.dzn: Simple scheduling example
- scheduling_with_assignments18.dzn: Scheduling of ship loading (from CHIP)
- scheduling_with_assignments19.dzn: Rectangle placement problem
- scheduling_with_assignments20.dzn: Grilling hamburgers problem
- scheduling_with_assignments21.dzn: Small example from "Handbook of Scheduling" (8 jobs and 3 workers)
- scheduling_with_multiple_workers.mzn: Scheduling with parallel machines.
- scheduling_speakers.mzn: Scheduling speakers (Rina Dechter)
- scheduling_speakers_optimize.mzn: Scheduling speakers with optimization objective (from Stack Overflow Optimizing working scheduling MiniZinc code - constraint programming)
- scheduling_speakers_optimize2.mzn: Scheduling speakers with optimization objective, faster model (from Stack Overflow Optimizing working scheduling MiniZinc code - constraint programming)
- scheduling_speakers_optimize3.mzn: Scheduling speakers with optimization objective, faster model with dual matrix (from Stack Overflow Optimizing working scheduling MiniZinc code - constraint programming)
- shopping_basket.mzn: Optimize a shopping basket with delivery costs. (Problem from StackOverflow How to use constraint programming for optimizing shopping baskets?)
- shopping_basket2.mzn: Optimize a shopping basked with delivery costs. Different representation where to buy the items. (Problem from StackOverflow How to use constraint programming for optimizing shopping baskets?)
- shopping_basket5.mzn: Optimize a shopping basket with delivery costs. A variant of shopping_basket2.mzn with a larger example (29 items and 37 shops) and other improvements. (Problem from StackOverflow How to use constraint programming for optimizing shopping baskets?)
- shopping_basket6.mzn: Optimize a shopping basket with delivery costs. A much faster variant of shopping_basket5.mzn. (Problem from StackOverflow How to use constraint programming for optimizing shopping baskets?)
- ski_assignment_problem.mzn: Ski assignment problem
- smallest_winning_electoral.mzn: Least amount of land that will make you President (2012 USA election) (From David Curran What is the least amount of land that will make you President? and Matthew Yglesias (Slate) The Geographically Smallest Winning Electoral College Map)
- smallest_winning_electoral2.mzn: Becoming President with 22% of the Votes (From David Curran Becoming President with 22% of the Votes
- social_golfers1.mzn: Social golfers (OPL)
- sportsScheduling.mzn: Sport scheduling
- spp.mzn: Shortest path problem, integer programming (GLPK)
- stable_marriage.mzn: Stable marriage
- stuckey_assignment.mzn: Assignment problem (Marriott and Stuckey)
- stuckey_seesaw.mzn: Balancing on a seesaw (Marriot and Stuckey)
- survivor.mzn: Survivor problem (from PuzzlOr)
- talent.mzn: Talent example (OPL)
- teambuilding.mzn: Teambuilding (OPL)
- timetable.mzn: Timetable of courses (from Alma-0)
- transportation.mzn: Transportation problem (ECLiPSe)
- transportation2.mzn: Transportation problem, generalized model
- tsp.mzn: Travelling Salesman Problem, integer programming (GLPK)
- transshipment.mzn: Transshipment problem (Winston)
- urban_planning.mzn: Urban planning (from PuzzlOr August 2013 Urban Planning)
- weights.mzn: Combine barbell/dumbbell weight plates.
Data files (for my current home gym):
- work_shift_problem.mzn: Work shift scheduling problem (from SAS/OR 9.22 User's Guide)
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:
- G12/mip (not all non linear constraints
- ECLiPSe/ic, ECLiPSe/eplex
- Gecode
- JaCoP
- ages.mzn: Ages problem from Tony Hurlimann
- aprice.mzn: Agricultural pricing (Willams: "Model building in MP")
- arbitrage_loops.mzn: Arbitrage loops (currencies)
Data files:
- birthday_paradox.mzn: Birthday paradox (birthday problem)
- blending.mzn: Blending problem (OPL)
- box.mzn: Design a box
- building_design.mzn: Building design
- catenary.mzn: Catenary (shape of hanging chain)
- celsius_fahrenheit.mzn: Conversion from/to degree Celsius to/from degree Fahrenheit
- circle_intersection.mzn: Circle intersection (ECLiPSe)
- circling_squares.mzn: Circling the Squares (Dudeney)
- cookie_bake_off2.mzn: Cookie bake off (PuzzlOr)
- curve_fitting1.mzn: Curve fitting 1 (Williams)
- curve_fitting2.mzn: Curve fitting 2 (Williams)
- curve_fitting3.mzn: Curve fitting 3, least squares (Williams)
- cyclohexane.mzn: Cyclohexane problem (Dudeney)
- dea.mzn: Data Envelopment Analysis (DEA) model (GLPK example)
- decent.mzn: Decentralization (Williams)
- diet2.mzn: Diet problem, larger (GLPK example)
- dirichlet.mzn: Dirichlet problem (triangle problem)
- dynamical_optimization1.mzn: Dynamical optimization
- eq10.mzn: Problem with 10 equation (standard constraint programming problem)
- fixed_charged_transportation_problem.mzn: Fixed charged transportation problem
- food.mzn: Food manufacture problem (GLPK, AMPL)
- food2.mzn: Food manufacture problem, with extra constraints (GLPK, AMPL)
- game_theory_taha.mzn: Game theory, zero sum game (Taha, Operations Research)
- games.mzn: Simple game theory example (Vanderbei "Linear Programming - Foundations - and Extensions", page 147ff)
- golden_search.mzn: Golden search
- golden_spiral.mzn: Golden spiral (logarithmic spiral, Gecode)
- laplace.mzn: Laplace problem (from CLP(R))
- markov_chains.mzn: Markov chain of market shares (from "Statistisk Dataanalys")
- markov_chains_taha.mzn: Markov chains (fertlizer example from Taha "Operations Research")
- mortgage.mzn: Mortgage (standard constraint programming problem)
- nonlin2.mzn: Non linear problem (Taha)
- nonlin_cylider.mzn: Creating a cylinder (from the ECLiPSe book)
- numerica_p19.mzn: From Numerica book, page 19
- numerica_p20.mzn: From Numerica book, page 20 (finding intersection)
- numerica_p21.mzn: From Numerica book, page 21 (array version of intersection problem)
- numerica_p23.mzn: From Numerica book, page 23 (a robot kinematic application)
- numerica_p24.mzn: From Numerica book, page 24 (neurophysiology)
- option_trading.mzn: Option trading
- p_median.mzn: P-median problem (OPL)
- plan.mzn: Planning model (GLPK)
- polygon.mzn: Polygon (OPL)
- portfolio_optimization.mzn: Portfolio optimization (SAS)
- prod0.mzn: Optimization problem (AMPL)
- rosenbrock.mzn: Rosenbrock function
- spreadsheet.mzn: Simple spreadsheet problem
- stigler.mzn: Original Stigler's 1939 diet problem (GLPK)
- stuckey_finite_element.mzn: Finite element (Marriott, Stuckey: Programming in Constraint, 191ff)
- transp.mzn: Transportation problem (GLPK)
- transp1.mzn: Transportation problem (OPL)
- volsay.mzn: Volsay problem (OPL)
- volsay2.mzn: Volsay problem, with arrays (OPL)
- volsay3.mzn: Volsay problem, with components (OPL)
- voltage_divider.mzn: Voltage divider problem problem from Marriott & Stuckey "Programming in Constraints"
- wilkinson.mzn: Wilkinson problem
Combinatorial problems
- 3sum.mzn: 3SUM problem (general approach)
- all_interval.mzn: All interval problem (series), (CSPLib problem 7)
- all_interval1.mzn: All interval problem, different approach
- all_interval2.mzn: All interval problem, different approach
- all_interval3.mzn: All interval problem, different approach
- all_interval4.mzn: All interval problem, different approach
- all_interval5.mzn: All interval problem, different approach
- all_interval6.mzn: All interval problem, different approach
- all_paths_graph.mzn: (All) paths from a graph presentation (cf message_sending.mzn)
- appointment_scheduling.mzn: Appointment scheduling, matrix approach (see Stack Overflow Q: Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction) ).
- appointment_scheduling_set.mzn: A set based approach to the appoiintment scheduling problem (see above). appointment_scheduling_set2.mzn is a version which use data files:
(Perl one-liner to generate data files ($n is N, $c is the limit for including a person in the time slot):
$ perl -e '$n = 10; $c = 0.6; print "n=$n;\ns=[\n"; for (1..$n) { print "{"; for (1..$n) { if (rand(1)>=$c) { print "$_," } } print "},\n"}; print "];\n"'
)
- average_avoiding.mzn: Average avoiding (from StackOverflow Arrange an array such that the average of 2 numbers does not lie between them)
- balanced_brackets.mzn: Generate balanced brackets
- balanced_matrix.mzn: Balanced matrix
- bin_packing_me.mzn: Bin packing (2010-10-12: this was called bin_packing.mzn but renamed due to name clash with a file with the same name in the MiniZinc distribution)
- bin_packing2.mzn: Bin packing (different from the one above)
- bpp.mzn: Bin packing (GLPK example, but not using the "z heuristic")
- bracket_partitioning.mzn: Bracket partitioning, optimize the number of brackets (problem from StackOverflow: Set partitioning with constraints java)
- car.mzn: Car sequencing problem (OPL)
- car.mzn: Car painting problem (from SAS/OR User's Guide)
- carpool_fairness.mzn: Carpool fairness
Problem instances:
- checker_puzzle.mzn: Checker puzzle (from MathOverflow Placing checkers with some restrictions)
- choosing_teams.mzn: Choosing teams (inspired by Enumerating the ways of choosing teams in a group of players)
- choosing_teams2.mzn: Choosing teams (inspired by Enumerating the ways of choosing teams in a group of players), different - and somewhat faster - approach than choosing_teams.mzn
- color_simple.mzn: Simple coloring of a map (Murty)
- combinatorial_auction.mzn: Simple combinatorial auction problem (compare with the set covering/set partition problem in set_covering4b.mzn)
- conference.mzn: Conference problem (from "Constraint Programming with Alice")
- config.mzn: Configuration problem (from OPL)
- cookie_monster_problem.mzn: Cookie Monster Problem (from Richard Green The Cookie Monster Problem at Google+)
- costas_array.mzn: Costas array (based on Barry O'Sullivan's model)
- decision_tree_binary.mzn: Binary decision tree
- debruijn_binary.mzn: de Bruijn sequence (graph)
- debruijn2d.mzn: 2D de Bruijn torus/arrays/matrices
- debruijn2d_2.mzn: 2D de Bruijn torus/arrays/matrices, improved version
- debruijn2d_3.mzn: 2D de Bruijn torus/arrays/matrices, can handle non-square matrices and sub-matrices
- debruijn_no_repetition.mzn: de Bruijn sequence with no repeating values (a.k.a Kautz sequences)
- dominating_set.mzn: Dominating set problem
- exact_cover_dlx.mzn: Implements the exact set cover example in Wikipedia's and Knuth's_Algorithm_X
- exact_cover_dlx_matrix.mzn: Implements the exact set cover example in Wikipedia's and Knuth's_Algorithm_X. This version use a matrix representation instead of sets.
- examination_scheduling.mzn: Examination scheduling (from Noppon Choosri: "Using grid puzzle to solve constraint-based scheduling problem")
- fair_split_into_3_groups.mzn: Fair split into 3 groups (from Stack Overflow What is an algorithm to split a group of items into 3 separate groups fairly?)
- finding_celebrities.mzn: Finding celebrities at a party (indicence matrix).
- finding_celebrities2.mzn: Finding celebrities at a party, using only set constraints.
- fix_points.mzn: Number of fix points in an array
- generalized_knapsack_problem.mzn: Generalized knapsack problem
- graceful_labeling.mzn: Graceful labeling problem
- graph_degree_sequence.mzn: Degree sequence for graphs, both matrix and edge representation
- graph_partition.mzn: Graph partitioning (example from Pascal Van Hentenryck, Laurent Michel: "Constraint-based local search", page 6f)
- gray_code.mzn: Gray code
- hamming_distance.mzn: Hamming distance
- hitting_set.mzn: Hitting set
- itemset_mining.mzn: Itemset mining (both Closed and Maximal Frequent Itemset Mining)
- maximal_independent_sets.mzn: Maximal independent sets (cf misp.mzn)
- K4P2GracefulGraph.mzn: K4P2 Graceful Graph
- K4P2GracefulGraph2.mzn: K4P2 Graceful Graph (more general model)
- k_consecutive_integers.mzn: k consecutive integers (Stack Overflow: k consecutive integers constraint)
- kidney_exchange.mzn: Simple kidney exchange model (inspired by Pascal Van Hentenryck's introduction to the Coursera Course "Discrete Optimization")
- kidney_exchange2.mzn: Kidney exchange model
Faster version: kidney_exchange_model.mzn:
Data files:
- kiselman_semigroup_problem.mzn: Kiselman's Semigroup problem.
- knapsack_problem.mzn: Knapsack problem
- knapsack1.mzn: Knapsack problem
- knapsack2.mzn: Another knapsack problem
- knapsack_rosetta_code_01.mzn: Knapsack problem, 0/1 (Rosetta code)
- knapsack_rosetta_code_unbounded.mzn: Knapsack problem (float), Unbounded (Rosetta code)
- knapsack_rosetta_code_unbounded_int.mzn: Knapsack problem Unbounded, integer version of knapsack_rosetta_code_unbounded.mzn (Rosetta code)
- knapsack_rosetta_code_bounded.mzn: Knapsack problem, bounded (Rosetta code)
- lams_problem.mzn: Lam's problem (CSPLib problem 25)
- langford2.mzn: Langford's number problem (k=2) (CSPLib problem 24)
- langford_generalized.mzn: Langford's number problem, (k >= 2) (CSPLib problem 24)
- latin_square.mzn: Latin squares
- lectures.mzn: Lectures, schedule problem from Biggs "Discrete Mathematics"
- lichtenstein_coloring.mzn: Coloring problem: Lichtenstein's communes and exclaves
- logical_design.mzn: Logical design (Williams)
- map.mzn: Simple coloring of a map
- map2.mzn: Simple coloring of a map (using symmetry breaking with precedence/1)
- map_stuckey.mzn: Another coloring of a map (Marriott and Stuckey)
- map_coloring_with_costs.mzn: Map coloring (of South America) where each color has a cost
- minimal_subset_of_columns.mzn: Finding minimal subset of columns that make rows in a matrix unique (Stack Overflow)
- maximum_density_still_life.mzn: Maximum density still life
- maximum_subarray.mzn: Maximum subarray (Rosetta code)
- minsum.mzn: Minsum problem
- movie_scheduling.mzn: Movie scheduling (Steven Skiena)
- modulo_partition.mzn: Function partitioning
- nontransitive_dice.mzn: Nontransitive dice
- ordering_a_list_of_lists.mzn: Ordering a list of lists (from Stack Overflow Ordering a list of lists subject to constraints)
- ormat_game.mzn: Ormat game (from bit-player The Ormat game).
Data files with all the overlays of appropriate size. There are n! overlay matrices for problems of size n x n. (These files has been generated by ormat_game_generate.mzn and some post-processing.)
ormat_game_nodel.mzn: Ormat game model, which is included in the follling problem instances from the bit-player article.
ormat_game_mip_nodel.mzn: Ormat game model, MIP version (quite fast for the optimization problem with a MIP solver). These following problem instances includes this MIP model.
- parallel_resistors.mzn: Parallel resistors problem problem from Marriott & Stuckey "Programming in Constraints"
- partial_latin_square.mzn: Partial Latin squares
- partitions.mzn: Integer partitions
- partition_into_subset_of_equal_values.mzn: Subset partitions (problem from the Stack Exchange Q: Partitioning set into subsets with respect to equality of sum among subsets).
- partition_into_subset_of_equal_values2.mzn, a version with some larger problem instances.
- partition_into_subset_of_equal_values3.mzn, pre-calculate the sum in the subsets (somewhat faster)
- perfect_shuffle.mzn: Perfect shuffle
- pigeon_hole.mzn: Pigeon hole problem (CLP-FD)
- picking_teams.mzn: Picking teams (where the objective is to minimize the differences in total strength of each team). picking_teams2.mzn: This version takes a data file as input. picking_teams_rand.dzn: A data file with random strengths (for n = 300). picking_teams_generate.pl: Perl program for generating a data file with a strength array.
- pigeon_hole2.mzn: Another pigeon hole problem
- portfolio_optimization2.mzn: Portfolio optimization (from Xpress-Mosel)
- power_set.mzn: Power set
- power_set2.mzn: Power set as a predicate (alternative version)
- power_set3.mzn: Power set as a predicate (alternative versions)
- quasiGroup3Idempotent.mzn: Quasigroup existence problem 3(CSPLib)
- quasiGroup3NonIdempotent.mzn: Quasigroup existence problem 3 (CSPLib)
- quasiGroup4Idempotent.mzn: Quasigroup existence problem 4(CSPLib)
- quasiGroup4NonIdempotent.mzn: Quasigroup existence problem 4(CSPLib)
- quasiGroup5Idempotent.mzn: Quasigroup existence problem 5(CSPLib)
- quasiGroup5NonIdempotent.mzn: Quasigroup existence problem 5(CSPLib)
- quasiGroup6.mzn: Quasigroup existence problem 6 (CSPLib)
- quasiGroup7.mzn: Quasigroup existence problem 7 (CSPLib)
- quasigroup_completion.mzn: Quasigroup completion problem
- quasigroup_completion_model.mzn: Quasigroup completion problem, model used by the following instances:
- ramsey_partition.mzn: Ramsey partition problem
- random_function.mzn: Random generator function, defines
random_int
and random_float
which returns arrays of "random" ints/floats. Requires MiniZinc v2.*
- random_function_test.mzn: Tests
random_int
and random_float
defined in random_function.mzn. Requires MiniZinc v2.*
- random_generator.mzn: Random generator, generates a
var int
array of random integers given a seed
- random_generator2.mzn: Random generator II, generates an
int
array of random integers given a seed (i.e. it can be used directly in the array declaration)
- random_set.mzn: Random generator III, generates a random set of int (either as
var set of int
or via array/set comprehension)
- rehearsal.mzn: Rehearsal problem (Barbara M. Smith)
- restaurant_scheduling.mzn: Restaurant scheduling (PuzzlOR)
- runs.mzn: Number of runs in an array (sequence)
- sat.mzn: Satisfiability Problem, integer programming (GLPK)
- satisfy.mzn: Satisfiability Problem (Alma-0)
- seating_arrangements.mzn: Seating arrangements problem. Problem from Texas Action Group: Seating arrangements: Problem
Problem instances from Texas Action Group Seating arrangements: Solutions (the solutions are in Answer Set Programming)
- seating_row.mzn: Seating placement, row (e.g. "movie theater seating") (a "minimal code" version: seating_row1.mzn)
- seating_table.mzn: Seating placement, table (circular)
- scanner_problem.mzn: Scanner problem
- 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_covering6.mzn: Set covering, problem from Nathan Brixius' blog post Don't be a hero when trying to solve set covering problems (2010-06-19)
- set_covering_deployment.mzn: Set covering deployment
- set_covering_opl.mzn: Set covering (OPL)
- set_covering_skiena.mzn: Set covering (Skiena)
- set_packing.mzn: Set packing
- set_partition.mzn: Set partitioning
- set_partition_stackoverflow.mzn: Set partition problem (from StackOverflow fast and simple constraint programming involving vectors (arrays))
- 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
- shortest_path_model_all.mzn: Model for shortest path, for showing all solutions (assuming an added constraint in the calling model)
- sicherman_dice.mzn: Sicherman dice problem
- smuggler_knapsack.mzn: Smuggler's knapsack (Marriott and Stuckey: "Programming with Constraints")
- sonet_problem.mzn: SONET problem
- steiner.mzn: Steiner triplet problem
- subset_plus_2.mzn: Subset problem: How many subsets S={1..10} union S+2 == {1..12} (from God plays dice Bitwise set trickery)
- subset_sum.mzn: Subset sum (Murty)
- temporal_reasoning.mzn: Temporal reasoning (Apt)
- tourist_site_competition.mzn: Tourist site competition (Pierre Flener)
- traffic_lights.mzn: Traffic lights problem (CSPLib problem 16)
- traffic_lights_table.mzn: Traffic lights problem (CSPLib problem 16), same as traffic_lights.mzn except that is use the global constraint tabl
- transpose.mzn: (Square) matrix operations, transpose, scalar addition, scalar multiplication
- tsp_circuit.mzn: Travelling salesperson problem, using circuit predicate
- tsptw.mzn: Travelling salesperson problem with time windows
- two_dimensional_channels.mzn: Two-dimensional constrained channels (all interiour cells must have m 1 neighbours in a NxN 0/1 matrix)
- uniform_dice.mzn: Uniform dice
- wedding_optimal_chart.mzn: Finding an optimal seating chart for a wedding (see Improbable Research: Finding an optimal seating chart for a wedding)
- young_tableaux.mzn Young tableaux
- young_tableaux_stack_overflow.mzn Young tableaux, model adapted to answer the Stack Overflow question Young tableaux in C
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.
- 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_equal_me.mzn: all_equal
- all_min_dist.mzn: all_min_dist, all values must have a minimum distance to each other
- alldifferent_consecutive_values.mzn: alldifferent_consecutive_values
- alldifferent_cst.mzn: alldifferent_cst, and alldifferent_cst using multiplication instead of addition
- alldifferent_except_0_me.mzn: alldifferent except 0 (This predicate is now included in the MiniZinc distribution)
- alldifferent_explain.mzn: alldifferent with "explanations" (with a set of duplicated values)
- 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_pairs.mzn: defines all_different_pairs, increasing_pairs, decreasing_pairs, and the function pairs
- 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
- 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
- assign_and_nvalue.mzn: assign_and_nvalues
- atleast_nvalue.mzn: atleast_nvalue, at least NVAL values are different in an array
- atmost1_me.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
- balance_interval.mzn: balance_interval, difference between the least and largest number of occurrences in intervals in an array
- balance_modulo.mzn: balance_modulo, difference between the least and largest number of occurrences of the equivalience classes modulo an integer
- balance_partition.mzn: balance_partition, difference between the least and largest number of occurrences in partitions
- between_min_max.mzn: between_min_max, a specific number is between the minimum and maximum value of an array
- binary_tree.mzn: Binary tree
- bipartite.mzn: Bipartite graph
- 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_test.mzn: circuit
- circuit_path.mzn: Extracting the path from a circuit
- clique.mzn: clique
- common.mzn: common, also used_by
- common_interval.mzn: common_interval
- common_modulo.mzn: common_modulo
- common_partition.mzn: common_partition
- cond_lex_cost.mzn: cond_lex_cost
- cond_lex_less.mzn: cond_lex_less, cond_lex_lesseq, cond_lex_greater, cond_lex_greatereq
- consecutive_values.mzn: consecutive_values
- contains_array.mzn: contains ("in" for arrays)
- contiguity_regular.mzn: global_contiguity (using regular constraint)
- count_ctr.mzn: count, more general than count in MiniZinc's globals.mzn
- counts.mzn: counts
- correspondence.mzn: correspondence
- cumulative_test.mzn: Test of cumulative (defined in globals.mzn)
- cumulative_test_mats_carsson.mzn: Another test of cumulative (small example from one of Mats Carlsson's lecture)
- cycle_test2.mzn: Cycle constraint (counts the number of cycles in an array)
- cycle_test3.mzn: Cycle constraint (requires MiniZinc 2.0)
- decreasing_me.mzn: decreasing
- derangement.mzn: derangement
- differs_from_at_least_k_pos.mzn: differs_from_at_least_k_pos
- diffn_me.mzn: diffn, (with three different representations of the orthotopes)
- discrepancy.mzn: discrepancy
- discjuntive.mzn: disjunctive
- distance_between.mzn: distance_between
- distance_change.mzn: distance_change
- domain.mzn: domain
- domain_constraint.mzn: domain_constraint
- element_greatereq.mzn: element_greatereq
- element_lesseq.mzn: element_lesseq
- element_matrix.mzn: element_matrix
- element_product.mzn: element_product
- element_sparse.mzn: element_sparse
- elementn.mzn: elementn
- elements.mzn: elements
- elements_alldifferent.mzn: elements_alldifferent
- equivalent.mzn: equivalent
- gcd_lcm.mzn: Decomposition of
gcd(a,b,GCD)
and lcm(a,b,LCM)
(not very efficient if all variables are decision variables)
- geost_test.mzn: Test of built-in
geost
constraint (requires MiniZinc 2.0)
- global_cardinality_no_loop.mzn: global_cardinality_no_loop
- global_cardinality_with_costs.mzn: global_cardinality_with_costs
- global_cardinality_table.mzn: global_cardinality, using a table with the occurrences
- global_contiguity.mzn: global_contiguity
- global_contiguity2.mzn: global_contiguity (different approach)
- imply.mzn: imply
- inflexions.mzn: inflexions, number of peaks in a sequence
- in_interval.mzn: in_interval
- in_relation.mzn: in_relation
- in_same_partition.mzn: in_same_partition
- in_set.mzn: in_set (cf the built in "in")
- increasing_except_0.mzn: increasing_except_0
- indexed_sum.mzn: indexed_sum
- int_value_precede.mzn: int_value_precede
- inter_distance.mzn: inter-distance (from Quimper)
- inverse_within_range.mzn: inverse within range
- ith_pos_different_from_0.mzn: ith pos different from 0
- k_alldifferent.mzn: k alldifferent (all rows satisfy the alldifferent constraint)
- k_same.mzn: k_same
- k_same_modulo.mzn: k_same_modulo
- lex2_me.mzn: lex2
- lex_alldifferent.mzn: lex_alldifferent
- lex_between.mzn: lex_between
- lex_chain_less.mzn: lex_chain_less
- lex_different.mzn: lex_different
- lex_greater_me.mzn: lex_greater
- longest_change.mzn: longest change, size of the longest sub sequence which satisfy a comparison operator (such as !=, <, > etc)
- max_index.mzn: max_index, (also the extension max_index_val)
- max_m_in_row.mzn: Max m in row (ensure that there are max m consecutive values in an array) [Note: This is a simpler variant of stretch_path, see below.]
- max_n.mzn: max_n
- max_nvalue.mzn: max_nvalue
- max_size_set_of_consecutive_var.mzn: max_size_set_of_consecutive_var
- maximum_modulo.mzn: maximum_modulo
- min_index.mzn: min_index, (also the extension min_index_val)
- min_max_sets.mzn: Minimum and maximum of a set
- min_n.mzn: min_n
- min_nvalue.mzn: min_nvalue
- minimum_except_0.mzn: minimum_except_0
- minimum_greater_than.mzn: minimum_greater_than
- minimum_modulo.mzn: minimum_modulo
- minimum_weight_alldifferent.mzn: minimum_weight_alldifferent
- nchange.mzn: nchange, (also a generalized version nchange_cmp with choice of operators)
- nclass.mzn: nclass
- n_partitioning.mzn: n_partitioning
- n_change.mzn: n_change
- my_nvalue.mzn: nvalue, also: atleast_nvalue and atmost_nvalue (note: nvalue is defined in globals.mzn, hence the name my_nvalue)
- next_greater_element.mzn: next_greater_element
- next_element.mzn: next_element
- not_all_equal.mzn: not_all_equal
- not_in.mzn: not_in
- npair.mzn: npair
- nvalue_on_intersection.mzn: nvalue_on_intersection
- nvalues.mzn: nvalues
- nvalues_except_0.mzn: nvalues_except_0
- open_alldifferent.mzn: open_alldifferent
- open_among.mzn: open_among
- open_atleast.mzn: open_atleast
- open_atmost.mzn: open_atmost
- open_global_cardinality.mzn: open_global_cardinality
- open_global_cardinality_low_up.mzn: open_global_cardinality_low_up
- orth_link_ori_siz_end.mzn: orth_link_ori_siz_end
- orth_on_the_ground.mzn: orth_on_the_ground
- 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)
- my_precedence.mzn:
precedence
(the first time we use j is before the first time we use k, for j < k). Also includes the variant precedence_all
with the extra constraint that all values in lb(a)..ub(a)
must be in a
.
- product_ctr.mzn: product_ctr
- range_ctr.mzn: range_ctr
- roots_test.mzn: Test of roots (defined in globals.mzn)
- same.mzn: same
- same_and_global_cardinality.mzn: same_and_global_cardinality
- same_and_global_cardinality_low_up.mzn: same_and_global_cardinality_low_up
- same_interval.mzn: same_interval
- same_modulo.mzn: same_modulo
- same_modulo.mzn: Scalar product
- separate_zeros.mzn: Copy an array but place all zeros (or some specific value) first (or last)
- shift.mzn: shift
- sliding_sum_me.mzn: sliding_sum
- sliding_time_window.mzn: sliding_time_window
- sliding_time_window_from_start.mzn: sliding_time_window_from_start
- smooth.mzn: smooth
- soft_all_equal_ctr.mzn: soft_all_equal_ctr
- soft_same_var.mzn: soft_same_var
- sort_permutation.mzn: sort_permutation
- sortedness.mzn: sortedness (Note: MiniZinc 2 has a
sort/1
function)
- stretch_circuit.mzn: stretch_circuit
- stretch_path.mzn: stretch_path
- strictly_decreasing.mzn: strictly_decreasing. Also strictly_increasing and decreasing
- subsequence.mzn: subsequence
- subsequence_sum.mzn: subsequence sum
- sum_ctr.mzn: sum ctr
- sum_free.mzn: sum free, also: product_free
- sum_of_weights_of_distinct_values.mzn: sum_of_weights_of_distinct_values
- sum_set.mzn: sum set
- symmetric.mzn: symmetric
- symmetric_alldifferent.mzn: symmetric_alldifferent
- to_num.mzn: Channeling a number and an array of digits (for some base, default 10). Requires MiniZinc 2 (
to_num
is a function).
- twin.mzn: twin
- weighted_sum.mzn: weighted_sum (as
scalar_product
in the catalogue)
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
Back to my homepage
Created by Hakan Kjellerstrand hakank@gmail.com