Project group: or-tools-discuss

The solver is available via SVN: http://or-tools.googlecode.com/svn/trunk/, and is obtained by the SVN command:

svn checkout http://or-tools.googlecode.com/svn/trunk/ or-tools-read-onlyPlease see AGettingStarted on how to install, required libraries etc.

Documentation: or-tools Wiki

Examples (SVN repository). Many of my models are placed here as well (except for the C++ examples).

There is not yet any tutorial or complete reference of the Python or Java interfaces to the constraints. The Wiki page UsingCPSolverCppAPI lists the C++ version of the methods with some comments. The Python and Java methods are (almost) always the C++ version minus the leading

`Make`

. E.g. the Python version of the C++ method `MakeAllDifferent`

is `AllDifferent`

(in the models: `solver.AllDifferent`

), and the Java version is `makeAllDifferent`

.
See below for my Java models.

See below for my LP/MIP models.

See further below for my C# models.

- 3_jugs_regular.py: 3 jugs problem using
`regular`

constraint. A variant: 3_jugs_regular2.py - a_round_of_golf.py: A round of golf problem (Dell Logic Puzzles)
- all_interval.py: All interval problem (CSPLib problem #7)
- alldifferent_except_0.py: Decomposition of global constraint
`all_different_except_0`

- alphametic.py: General alphametic solver (i.e. problems like "SEND+MORE=MONEY")
- assignment.py: Simple assignment problem
- broken_weights.py: Broken weights puzzle
- bus_schedule.py: Bus scheduling
- car.py: Car sequencing (from Pascal Van Hentenryck "OPL Optimization Programming Language", page 184ff)
- circuit.py: Decomposition of global constraint
`circuit`

- coins3.py: Minimum mumber of coins that allows one to pay exactly any amount smaller than one Euro (from the ECLiPSe book)
- coins_grid.py: Tony Hurlimann's coin grid problem
- coloring_cp.py: Simple map coloring problem, CP version
- combinatorial_auction2.py: Combinatorial auction
- contiguity_regular.py: Decomposition of global constraint
`global contiguity`

(using`regular`

constraint) - costas_array.py: Costas array problem
- covering_opl.py: Set covering (OPL)
- crew.py: Crew allocation problem
- crossword2.py: Simple crossword problem
- crypta.py: Crypta, alphametic problem (standard Prolog benchmark)
- crypto.py: Crypto, alphametic problem (standard Prolog benchmark)
- curious_set_of_integers.py: Curious set of integers (Martin Gardner)
- debruijn_binary.py: "Arbitrary" de Bruijn sequences
- diet1.py: Simple diet problem (optimization of a diet). Variant: diet1_b.py
- discrete_tomography.py: Discrete tomography

Data files: - divisible_by_9_through_1.py: Divisible by 9 through 1 for a "truncated" number. Includes a
`modulo`

decomposition. - einav_puzzle.py: Solving A programming puzzle from Einav. A (slightly) faster variant by Laurent Perron: einav_puzzle2.py
- eq10.py: Eq 10, standard benchmark problem
- eq20.py: Eq 20, standard benchmark problem
- fill_a_pix.py: Fill-a-pix problem.

Data files: - furniture_moving.py: Optimizing furniture moving (Marriott and Stuckey). Contains an experimental decomposition of the global constraint
`cumulative`

- futoshiki.py: Futoshiki puzzle (grid puzzle)
- grocery.py: Grocery problem
- hidato.py: Hidato puzzle. However, hidato_laurent.py is Laurent Perron's much faster (and more elegant) version.
- just_forgotten.py: Just forgotten puzzle (Enigma 1517)
- kakuro.py: Kakuro puzzle
- kenken2.py: KenKen puzzle
- killer_sudoku.py: Killer Sudoku puzzle
- knapsack.py: Simple knapsack problem
- labeled_dice.py: Labeled dice problem, from Jim Orlin's Colored letters, labeled dice: a logic puzzle (follow up: Update on Logic Puzzle)
- langford.py: Langford's number problem (CSPlib problem 24)
- least_diff.py: Least Diff problem (alphametic problem)
- lectures.py: Lectures, schedule problem from Biggs "Discrete Mathematics"
- magic_square.py: Magic square problem
- magic_square_and_cards.py: Magic square and card problem (Martin Gardner)
- map.py: Simple map coloring problem
- marathon2.py: Marathon puzzle (XPress example)
- max_flow_taha.py: Maximum flow problem (Taha)
- max_flow_winston1.py: Maximum flow problem (Winston)
- minesweeper.py: Minesweeper

Data files: - mr_smith.py: Mr Smith problem, logic problem (from IF Prolog)
- nonogram_regular.py: Nonogram solver (using a decomposition of global constraint
`regular`

). Laurent Perron's improved version (uses`table`

in the`regular`

) nonogram_table.py, and later nonogram_table2.py

Problem instances:- nonogram_bear.py
- nonogram_car.py
- nonogram_castle.py
- nonogram_crocodile.py
- nonogram_difficult.py
- nonogram_dragonfly.py
- nonogram_gondola.py
- nonogram_hard.py
- nonogram_hen.py
- nonogram_lambda.py
- nonogram_n4.py
- nonogram_n6.py
- nonogram_nonunique.py
- nonogram_p199.py
- nonogram_p200.py
- nonogram_pbn_9_dom.py
- nonogram_pbn_bucks.py
- nonogram_pbn_cat.py
- nonogram_pbn_dancer.py
- nonogram_pbn_edge.py
- nonogram_pbn_forever.py
- nonogram_pbn_karate.py
- nonogram_pbn_knot.py
- nonogram_pbn_light.py
- nonogram_pbn_merka.py
- nonogram_pbn_mum.py
- nonogram_pbn_petro.py
- nonogram_pbn_skid.py
- nonogram_pbn_swing.py
- nonogram_ps.py
- nonogram_soccer_player.py
- nonogram_t2.py

- nqueens.py: N queens problem.
- nqueens2.py: N queens problem, faster version.
- nqueens3.py: N queens problem, faster than nqueens.py and nqueens2.py
- nontransitive_dice.py: Nontransitive dice
- nurse_rostering.py: Simple nurse rostering using global constraint (decomposition)
`regular`

- olympic.py: Olympic puzzle (alphametic, standard Prolog benchmark)
- organize_day.py: Organize a day, simple scheduling problem (from ECLiPSe)
- p_median.py: P-median problem (from OPL)
- pandigital_numbers.py: Pandigital numbers in "any" base
- perfect_square_sequence.py: Perfect square sequence
- photo_problem.py: Photo problem
- place_number_puzzle.py: Place number puzzle
- post_office_problem2.py: Post office problem (Winston)
- quasigroup_completion.py: Quasigroup completion

Data files: - regexp.py: Generating all strings from a regular expressions
- regular.py: Decomposition of global constraint
`regular`

(experimental). Laurent Perron's improved version: regular_table.py, and later regular_table2.py - rogo2.py: Rogo grid puzzle solver

Problem instances:- rogo_mike_trick.py: Problem from Mike Trick's Operations Research, Sudoko, Rogo, and Puzzles
- rogo_20110106.py: Problem of the day 20110107
- rogo_20110107.py: Problem of the day 20110107

- safe_cracking.py: Safe cracking puzzle (from Oz primer)
- secret_santa.py: Secret santa problem
- secret_santa2.py: Secret santa problem II (optimizing "santa distance")
- send_more_money_any_base.py: SEND+MORE=MONEY in "any" base
- send_more_money_scalar_product.py: SEND+MORE=MONEY using scalar products
- send_most_money.py: SEND+MOST=MONEY (maximize MONEY)
- scheduling_speakers.py: Scheduling speakers (Rina Dechter)
- seseman.py: Seseman Convent problem. Variant: seseman_b.py
- set_covering.py: Set covering, placing of firestations (Winston)
- set_covering2.py: Set covering, number of security telephons on a campus (Taha)
- set_covering3.py: Set covering, senators making a committe (Murty)
- set_covering4.py: Set covering (and set partition), work scheduling (Lundgren, Roennqvist, Vaerbrand "Optimeringslaera")
- set_covering_deployment.py: Set covering deployment
- set_covering_skiena.py: Set covering problem (Steven Skiena)
- set_partition.py: Set partition
- sicherman_dice.py: Sicherman dice
- ski_assignment.py: Ski assignment problem
- stable_marriage.py: Stable Marriage problem (from Van Hentenryck's OPL book and some more problem instances)
- strimko2.py: Strimko puzzle (Latin squares with "streams"). Some data files:
- subset_sum.py: Subset sum problem (Katta G. Murty)
- sudoku_4x4.py: Sudoku, simple 4x4 problem
- survo_puzzle.py: Survo puzzle

Data files: - toNum.py: Converts inter to/from an array of digits
- traffic_lights.py: Traffic lights problem (CSPLib problem 16)
- who_killed_agatha.py: Who killed agatha? (The Dreadsbury Mansion Murder Mystery, an automated reasoning problem)
- word_square.py: Word square
- young_tableaux.py: Young tableaux and partitions
- xkcd.py: xkcd knapsack problem

2011-03-29: Blogged about it in A first look at Google or-tools' Java interface

To simplify my life, all examples has been placed in the package

`com.google.ortools.constraintsolver.samples`

. Some (if not all) models is also available at the SVN repository .
- AllDifferentExcept0.java: A decomposition of the global constraint
`alldifferent_except_0`

- AllInterval.java: All interval problem (CSPLib #7)
- Circuit.java: A decomposition of the global constraint
`circuit`

- CoinsGrid.java: Tony Hurlimann's coin grid problem
- CoveringOpl.java: Set covering (OPL)
- Crossword.java: Simple crossword problem
- DeBruijn.java: "Arbitrary" de Bruijn sequences
- Diet.java: Simple diet optimization problem
- DivisibleBy9Through1.java: Divisible by 9 through 1 for a "truncated" number. Includes a
`modulo`

decomposition. - LeastDiff.java: Least difference problem (minimize the difference of ABCDE-FGHIJ, where all digits A..J are different)
- MagicSquare.java: Magic Square
- Map.java: Simple map coloring problem
- Map2.java: Simple map coloring problem, alternative version
- Minesweeper.java: Minesweeper solver (uses the same data file as for the Python model minesweeper.py, see above)
- NQueens.java: n-queens problem
- NQueens2.java: n-queens problem, faster version
- QuasigroupCompletion.java: Quasigroup completion (uses the same data file as for the Python model quasigroup_completion.py, see above)
- SendMoreMoney.java: Solve SEND+MORE=MONEY
- SendMoreMoney2.java: Solve SEND+MORE=MONEY (5 different encodings).
- SendMostMoney.java: Solve SEND+MOST=MONEY, and show all solutions with maximal value of MONEY.
- Seseman.java: Seseman convent problem.
- SetCovering.java: Set covering, placing of firestations (Winston)
- SetCovering2.java: Set covering, number of security telephons on a campus (Taha)
- SetCovering3.java: Set covering, senators making a committe (Murty)
- SetCovering4.java: Set covering (and set partiton), work scheduling (Lundgren, Roennqvist, Vaerbrand "Optimeringslaera")
- SetCoveringDeployment.java: Set covering deployment
- StableMarriage.java: Stable Marriage problem (from Van Hentenryck's OPL book and more problem instances)
- Strimko2.java: Strimko puzzle (Latin squares with "streams").
- Sudoku.java: Sudoku
- SurvoPuzzle.java: Survo puzzle (uses the same data file as for the Python model survo_puzzle.py, see above)
- ToNum.java: Converts inter to/from an array of digits
- WhoKilledAgatha.java: Who killed agatha? (The Dreadsbury Mansion Murder Mystery, an automated reasoning problem)
- Xkcd.java: Xkcd knapsack problem.
- YoungTableaux.java: Young tableaux and partitions

- 3_jugs_mip.py: 3 jugs problem, MIP version
- assignment6_mip.py: Assignment problem (from GLPK), MIP version
- blending.py: Blending problem (from OPL), MIP version
- coins_grid_mip.py: Tony Hurlimann's coin grid problem, MIP version
- coloring_ip.py: Simple map coloring problem, MIP version
- diet1_mip.py: Simple diet problem (optimization of a diet), MIP version
- game_theory_taha.py: Game theory, 2 person, zero-sum game. LP version
- knapsack_mip.py: Knapsack problem (from GLPK), MIP version
- least_square.py: Solving a fourth grade least square equation, LP version
- magic_square_mip.py: Magic square problem, MIP version
- production.py: Production planning problem, LP version (from OPL)
- stigler.py: Stigler's 1939 diet problem (from GLPK)
- sudoku_mip.py: Sudoku solver, MIP version
- volsay.py: Volsay LP problem (from OPL)
- volsay2.py: Volsay LP problem, using arrays (from OPL)
- volsay3.py: Volsay LP problem, with components (from OPL)

Please note that I'm developing these programs in Mono (under Ubuntu Linux 11.10, 64-bit); they will hopefully also run on other .NET/Mono platforms. Quite a few are rather faitful ports from the Java versions, and some (but not that faithful ports) from the Python models.

Many (if not all) of these models has been pushed to the or-tools SVN

For compiling and running these models using Mono, something like this should work:

$ export OR_TOOLS=../or-tools/svn/or-tools-read-only $ export MONO_PATH=$MONO_PATH:$OR_TOOLS $ mono-csc -lib:$OR_TOOLS /r:Google.OrTools.ConstraintSolver.dll model.cs $ ./model.exe

- 3_jugs_regular.cs: 3 jugs problem using
`regular`

constraint. - a_puzzle.cs: The "8809 = 6 ..." puzzle (See God plays dice: A puzzle)
- a_round_of_golf.cs: A round of golf problem (Dell Logic Puzzles)
- alldifferent_except_0.cs: Decomposition of global constraint
`alldifferent_except_0`

- all_interval.cs: All interval problem
- appointment_scheduling_set.cs: Appointment scheduling (set approach, random generating the problem instances ) (from the Stack Overflow question: Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction))
- assignment.cs: Simple assignment problem
- broken_weights.cs: Broken weights puzzle
- bus_schedule.cs: Bus scheduling (Taha)
- circuit.cs: Decomposition of global constraint
`circuit`

- circuit2.cs: Decomposition of global constraint
`circuit`

which also extracts the path. - coins3.cs: Minimum mumber of coins that allows one to pay exactly any amount smaller than one Euro (from the ECLiPSe book)
- coins_grid.cs: Tony Hurlimann's coin grid problem
- combinatorial_auction2.cs: Combinatorial auction
- contiguity_regular.cs: Decomposition of global constraint
`global contiguity`

(using a decomposition of`regular`

constraint) - contiguity_transition.cs: Decomposition of global constraint
`global contiguity`

(using the built-in`TransitionConstraint`

) - costas_array.cs: Costas array problem
- covering_opl.cs: Set covering (OPL)
- crew.cs: Crew allocation problem
- crossword.cs: Simple crossword problem
- crypta.cs: Crypta, alphametic problem (standard Prolog benchmark)
- crypto.cs: Crypto, alphametic problem (standard Prolog benchmark)
- curious_set_of_integers.cs: Curious set of integers (Martin Gardner)
- debruijn.cs: Classical or "arbitrary" de Bruijn sequences (useful for generating
**all**de Bruijn sequences) - diet.cs: Simple diet (minimization) problem.
- discrete_tomography.cs: Discrete tomography

Data files (same as for Python) - divisible_by_9_through_1.cs: Divisible by 9 through 1 for a "truncated" number. Also includes a decomposition of a
`modulo`

constraint. - dudeney.cs: Dudeney Numbers
- einav_puzzle.cs: Solving A programming puzzle from Einav. (This is a port of Laurent Perron's optimized version: einav_puzzle2.py)
- fill_a_pix.cs: Fill-a-pix problem.

Data files (same as for Python above): - furniture_moving.cs: Optimizing furniture moving (Marriott and Stuckey). Contains a decomposition of the global constraint
`cumulative`

. - futoshiki.cs: Futoshiki puzzle (grid puzzle)
- golomb_ruler.cs: Golomb ruler
- grocery.cs: Grocery problem
- hidato_table.cs: Hidato puzzle (a port of Laurent Perron's Python model hidato_table.py, from the or-tools/Python distribution)
- just_forgotten.cs: Just forgotten puzzle (Enigma 1517)
- kakuro.cs: Kakuro puzzle
- kenken2.cs: KenKen puzzle
- killer_sudoku.cs: Killer Sudoku puzzle
- labeled_dice.cs: Labeled dice problem, from Jim Orlin's Colored letters, labeled dice: a logic puzzle (follow up: Update on Logic Puzzle)
- langford.cs: Langford's number problem (CSPlib problem 24)
- least_diff.cs: Least difference problem (minimize the difference of ABCDE-FGHIJ)
- lectures.cs: Lectures, schedule problem from Biggs "Discrete Mathematics"
- magic_sequence.cs: Magic sequence
- magic_square.cs: Magic squares problem
- magic_square_and_cards.cs: Magic square and card problem (Martin Gardner)
- map.cs: Simple map coloring.
- map2.cs: Simple map coloring. Alternative version using a matrix to represent the neighbours.
- marathon2.cs: Marathon puzzle (XPress example)
- max_flow_taha.cs: Maximum flow problem (Taha)
- max_flow_winston1.cs: Maximum flow problem (Winston)
- minesweeper.cs: Minesweeper

Data files (same as for Python and Java above) - mr_smith.cs: Mr Smith problem, logic problem (from IF Prolog)
- nontransitive_dice.cs: Nontransitive dice
- nqueens.cs: N-queens problem.
- nurse_rostering_regular.cs: Simple nurse rostering using global constraint (decomposition)
`regular`

- nurse_rostering_transition.cs: Simple nurse rostering using global constraint (using the built-in
`TransitionConstraint`

) - olympic.cs: Olympic puzzle (alphametic, standard Prolog benchmark)
- p_median.cs: P-median problem (from OPL)
- pandigital_numbers.cs: Pandigital numbers in "any" base
- partition.cs: Partition problem
- partition_into_subsets_of_equal_values.cs: Subset partitions (problem from the Stack Exchange Q: Partitioning set into subsets with respect to equality of sum among subsets).
- partition_into_subsets_of_equal_values2.cs: A variant which randomizes the problem instance.
- partition_into_subsets_of_equal_values3.cs: Pre-calculate the sum in each subset (
`s.Sum() div num_subsets`

) - perfect_square_sequence.cs: Perfect square sequence
- photo_problem.cs: Photo problem (Mozart/Oz)
- picking_teams.cs: Picking teams where the objective is to minimize the difference of total strength of each team.
- picking_teams2.cs: Picking teams where the objective is to minimize the difference of total strength of each team. Additional: arbitrary number of teams and a more liberal handling of the number of team members (and the sum of team points).
- place_number_puzzle.cs: Place number puzzle
- post_office_problem2.cs: Post office problem (Winston)
- quasigroup_completion.cs: Quasigroup completion

Data files (same as for Python and Java above) - regex.cs: Generating all strings from a regular expressions
- rogo2.cs: Rogo grid puzzle solver

Data files: - scheduling_speakers.cs: Scheduling speakers (Rina Dechter)
- secret_santa.cs: Secret santa problem
- secret_santa2.cs: Secret santa problem II (optimizing "santa distance")
- send_more_money.cs: SEND+MORE=MONEY alphametic problem
- send_more_money2.cs: SEND+MORE=MONEY using scalar product
- send_most_money.cs: SEND+MOST=MONEY, where we maximize MONEY and then show all solution with MONEY maximized
- seseman.cs: Solving the Seseman convent problem
- set_covering.cs: Set covering, placing of firestations (Winston)
- set_covering2.cs: Set covering, number of security telephons on a campus (Taha)
- set_covering3.cs: Set covering, senators making a committe (Murty)
- set_covering4.cs: Set covering (and set partition), work scheduling (Lundgren, Roennqvist, Vaerbrand "Optimeringslaera")
- set_covering_deployment.cs: Set covering deployment
- set_covering_skiena.cs: Set covering problem (Steven Skiena)
- set_partition.cs: Set partition
- sicherman_dice.cs: Sicherman dice
- ski_assignment.cs: Ski assignment problem
- stable_marriage.cs: Stable Marriage problem (from Van Hentenryck's OPL book and some more problem instances)
- stable_marriage_random.cs: Stable Marriage problem, randomized problem instances (based on stable.marriage.cs)
- strimko2.cs: Strimko puzzle (Latin squares with "streams")
- subset_sum.cs: Subset sum problem (Katta G. Murty)
- sudoku.cs: Sudoku solver
- sudoku_4x4.cs: Sudoku solver (simple 4x4 problem)
- survo_puzzle.cs: Survo puzzle

Data files (same as for Python and Java above: - to_num.cs: Channeling between a number and an array (useful for some alphametic problems)
- traffic_lights.cs: Traffic lights problem (CSPLib problem 16)
- volsay.cs: Volsay LP problem, LinearSolver (from OPL)
- volsay2.cs: Volsay LP problem, using arrays, LinearSolver (from OPL)
- volsay3.cs: Volsay LP problem, with components, LinearSolver (from OPL)
- wedding_optimal_chart.cs: Finding an optimal seating chart for a wedding (see Improbable Research: Finding an optimal seating chart for a wedding)
- who_killed_agatha.cs: Who killed agatha? (The Dreadsbury Mansion Murder Mystery, an automated reasoning problem)
- word_square.cs: Word square
- xkcd.cs: Solving the xkcd Knapsack problem
- young_tableaux.cs: Young tableaux and partitions
- zebra.cs: Zebra problem (Lewis Caroll)

Also, see my other pages about constraint programming systems:

* My Constraint Programming Blog, especially the Google CP Solver category

* Constraint Programming

* Common constraint programming problems

* My MiniZinc page

* 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 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