My Essence'/Savile Row page

Essence'/Savile Row

Savile Row is a modelling assistant for CP. It provides a high-level language for the user to specify their constraint problem, and automatically translates that language to the input language of a constraint solver. It is a research tool, so it is designed to be as flexible as possible. It is very easy to add new rules and program new translation pipelines.

During the translation process, Savile Row applies some reformulations to improve the model. At the moment these are quite simple, with the most interesting one being common subexpression elimination (CSE). If the same (or equivalent) expression appears in different parts of a model, CSE replaces the expression with a single variable everywhere it appears. In this way it connects together different parts of the model. This often improves constraint propagation.

Savile Row is the successor to Tailor, developed by Andrea Rendl as part of her PhD. Some of the techniques used by Savile Row (CSE in particular) were invented by Andrea, and are detailed in her PhD thesis.

The authors of Savile Row are Ian Miguel and Peter Nightingale. To report bugs, ask questions, or ask for features, contact Peter: pwn1@st-andrews.ac.uk

...

Constraint Solvers At the moment only Minion is fully supported. Work is in progress on supporting Gecode. Also, work is in progress on supporting the Dominion constraint solver synthesizer.

My Essence'/Savile Row models

• Savile Row don't accept param .. is/be. Use letting .. be instead
• An .eprime model cannot both have a given clause and a letting clause for the same parameter. Either move the letting clauses to a .param file or comment out the given.
• If a model include the letting clause, then the type must be stated (at least for matrices)
• Savile Row requires the stricted allDiff (and not alldiff, alldifferent), forAll (and not forall)
• The automatic flattening of a matrix for use in allDiff, e.g. allDiff(x) (or allDiff(x[..,..])) is no longer supported. Use flatten for this instead, e.g. allDiff(flatten(x)).
• I'm not sure about this, but it seems that the local variables in forAll/exists loops share the (global) name space as the given/letting variables. (E.g. in calculs_d_enfer.eprime I had to change the loop variables from i to i2.)

• a_puzzle.eprime: A Puzzle (the 8809=6,... problem)
• a_round_of_golf.eprime: A Round of Golf logic puzzle
• alldifferent_except_0.eprime: All different except 0 (decomposition)
• alldifferent_except_0b.eprime: All different except 0, using the built-in alldifferent_except
• all_interval.eprime: All interval problem
• among.eprime: "Decomposition" of global constraint among
• assignment.eprime: Simple assignment problem (Winston "Operations Research")
• bales_of_hay.eprime: Bales of Hay problem
• broken_weights.eprime: Broken weights problem
• bus_schedule.eprime: Simple bus scheduling (Taha "Operations Research")
• calculs_d_enfer.eprime: Calculs d'enfer puzzle (alphametic problem)
• circuit.eprime: "Decomposition" of global constraint circuit
• coins3.eprime: Coin problem (minimizing the number of coins to be able to pay exactly 1..99 cents)
• coins_grid.eprime: Coins grid problem (Tony Hurliman)
• combinatorial_auction.eprime: Combinatorial auction
• crosswords.eprime: Simple crossword problem
• crosswords2.eprime: Simple crossword problem (variant of crosswords.eprime)
• debruijn.eprime: de Bruijn sequences (both "classical" and "arbitrary")
  Param files:
  
  • debruijn1.param
  • debruijn2.param
  • debruijn3.param
  • debruijn3b.param
  • debruijn4.param
  • debruijn5.param
  • debruij5b.param
  • debruijn6.param
• diet1.eprime: Simple diet problem
• discrete_tomography.eprime: Discrete tomography.
  Param files:
  
  • discrete_tomography1.param
  • discrete_tomography2.param
  • discrete_tomography3.param
  • discrete_tomography4.param
• divisible_by_9_through_1.eprime: Divisible by 9 through 1 problem (for base <,= 8)
• hidato.eprime: Hidato grid puzzle
  
  • hidato1.param: Problem 1
  • hidato2.param: Problem 2
  • hidato3.param: Problem 3
• jobs_puzzle.eprime: Jobs puzzle (standard Automatic Resoning problem)
• just_forgotten.eprime: Just forgotten puzzle (Enigma 1517)
• kakuro.eprime: Kakuro grid puzzle
• killer_sudoku.eprime: Killer Sudoku
• knapsack.eprime: Simple knapsack problem
• labeled_dice.eprime: Labeled dice problem
• langford2.eprime: Langford's number problem
• leastDiff.eprime: Least diff, alphametic problem
• map_coloring.eprime: Simple map coloring (Van Hentenryck, OPL book)
• map_coloring2.eprime: Simple map coloring, more general approach
• marathon.eprime: Marathon logic puzzle
• minesweeper.eprime: Minesweeper puzzle, general model to be used with the following problems:
  • minesweeper0.param
  • minesweeper1.param
  • minesweeper2.param
  • minesweeper3.param
  • minesweeper4.param
  • minesweeper5.param
  • minesweeper6.param
  • minesweeper7.param
  • minesweeper8.param
  • minesweeper9.param
  • minesweeper_basic3.param
  • minesweeper_basic4.param
  • minesweeper_basic4x4.param
  • minesweeper_config_page2.param
  • minesweeper_config_page3.param
  • minesweeper_german_Lakshtanov.param
  • minesweeper_splitter.param
  • minesweeper_wire.param
• nqueens.eprime: N-queens problem
• organize_day.eprime: Organize a day (simple scheduling problem)
• pancake_sorting.eprime: Pancake sorting
  Param files
  • pancake_sorting1.param
  • pancake_sorting2.param
• photo_problem.eprime: Photo problem (from Mozart/Oz)
• place_number_puzzle.eprime: Place number puzzle
• quasigroup_completion.eprime: Quasigroup completion
  Param files:
  • quasigroup_completion1.param
  • quasigroup_completion2.param
  • quasigroup_completion3.param
  • quasigroup_completion4.param
  • quasigroup_completion5.param
  • quasigroup_completion6.param
  • quasigroup_completion7.param
  • quasigroup_completion8.param
  • quasigroup_completion9.param
• scheduling_speakers: Scheduling speakers (Rina Dechter)
• schur.eprime: Schur problem
• secret_santa.eprime: Secret Santa problem
• seseman.eprime: Seseman Convent problem (see Seseman Convent problem)
• send_more_money_any_base.eprime: SEND+MORE=MONEY (any base)
• send_most_money.eprime: SEND+MOST=MONEY (maximising MONEY)
• set_covering.eprime: Set covering problem
• set_covering2.eprime: Set covering problem
• set_covering3.eprime: Set covering problem
• set_covering4.eprime: Set covering problem
• set_covering5.eprime: Set covering problem
• set_covering6.eprime: Set covering problem
• set_covering_deployment.eprime: Set covering deployment
• set_covering_opl.eprime: Set covering (from an OPL example)
• set_partition.eprime: Set partition problem
• sicherman_dice.eprime: Sicherman dice
• ski_assignment.eprime: Ski assignment problem
• subset_sum.eprime: Subset sum
• stable_marriage.eprime: Stable marriage problem
  
  • stable_marriage1.param: Problem instance from Pascal Van Hentenryck
  • stable_marriage2.param: Problem instance from MathWorld
  • stable_marriage1.param: Problem instance 3
• survo_puzzle.eprime: survo_puzzle
  Param files:
  • survo_puzzle1.param
  • survo_puzzle2.param
  • survo_puzzle3.param
  • survo_puzzle4.param
  • survo_puzzle5.param
  • survo_puzzle6.param
• to_num.eprime: Convert (bidirectionally) between a number and a array of digits.
• traffic_lights.eprime: Traffic light problem (CSPLib problem #16)
• who_killed_agatha.eprime: Who killed agatha? (The Dreadsbury Mansion Murder Mystery, an automated reasoning problem)
• xkcd.eprime: xkcd problem (see the xkcd strip for the problem)
• young_tableaux.eprime: Young tableaux and partition
• zebra.eprime: Zebra puzzle (using values 0..4)
• zebra_1_5.eprime: Zebra puzzle (using values 1..5)