My Constraint Programming Blog

Gecode version 3.7.3 has been released.

From the ChangeLog:

This release fixes some small bugs in the FlatZinc interpreter and library.

• Gecode/FlatZinc
  • Additions
    • Added mzn-gecode scripts for conveniently solving MiniZinc models using the Gecode FlatZinc interpreter. (minor)
  • Other changes
    • Removed the print command line option. Instead, for optimization problems, using -a will print all solutions, while not using -a will only print the last one. This is consistent with the G12 FlatZinc command line interface. (minor)
  • Bug fixes
    • Fixed "largest" variable selection strategy for set variables. (minor, thanks to Marco Correia)
    • Fixed the parser for set literals. (minor, thanks to Thibaut Feydy)
    • Integer variables with empty domains result in unsatisfiable models instead of an error message. (minor)
    • Support 0-length array declarations. (minor)

Posted by hakank at 08:12 AM | Permalink

The presentation can be downloaded here: google_talk_20120323.ppt.

In late January this year, I was invited by Laurent Perron - head of the or-tools group - to talk about my view on Constraint Programming and my experience with the or-tools system (I have done quite a few models using the Python, Java, and C# interfaces).

The talk was this Friday (March 23) at the Google's Paris office. It was a lovely day but unfortunately I got a common cold the day before so it was little hard to enjoy all the things Paris can offer.

Friday started with Laurent and me just talking about CP in general, and or-tools in particular and it was really fun and interesting. Later on we where joined by two other guests: Charles Proud'Homme and Nicolas Beldiceanu, both from Ecole des Mines de Nantes and it was great talking with them as well and, above all, listen when they discussed various CP things.

The Google office in Paris was very impressive, very high ceilings and seemed to be build to get lost easily (though neither of us quests got completely lost).

At 1400 I started the talk in front of an audience of about 20 engineers at the Google office (+ the two guests from Ecole des Mines de Nantes) and I think it went quite well considering the cold and all. It was recorded for internal use at Google. I don't know how public it will be but I will blog about this when it has been edited etc. After the 50 minutes talk there was a little Q/A session.

Thanks Laurent for the invitation and a memorable day.

Little more about the talk

The talk was aimed for programmers that don't know very much about Constraint Programming and I especially wanted to convey my own fascination about CP by using this agenda:

• Introducing the principles of CP (very simplified)
• Showing the declarativeness of CP by some code in the high level G12 MiniZinc and then in or-tools Python, C#, and sometimes Java.
• The basic principle of propagation of constraints and domains is shown via a very simple 4x4 Sudoku problem.
• After that, some of - IMHO - the most fascinating concepts in modeling CP where presented:
  • Global constraints
  • Element constraint
  • Reification
  • Bi-directedness
    Note: After the talk Nicolas Beldiceanu commented that this is more known as "reversibility" in the Prolog world.
  • 1/N/All solutions
  • Symmetry breaking

Here is the talk: google_talk_20120323.ppt.

I would like to thank the following for various degrees of comments, suggestions, and encouragement regarding the presentation:

• Magnus Bodin
• Carl Mäsak
• Mikael Lagerkvist
• Christian Schulte
• Laurent Perron
• Alastair Andrew

And a special thanks to Nikolaj van Omme for his very detailed comments.

Posted by hakank at 06:57 AM | Permalink

MiniZinc version 1.5 has been released. It can be downloaded here.

From the NEWS:

G12 MiniZinc Distribution 1.5
-----------------------------

* G12/CPX solver

We have added the solver G12/CPX (Constraint Programming with eXplanations) to the distribution. G12/CPX is the successor to the LazyFD solver. The FlatZinc interface to G12/CPX is named fzn_cpx and MiniZinc models can be solved with G12/CPX using mzn-g12cpx, for example to solve the model foo.mzn using G12/CPX, do

$ mzn-g12cpx foo.mzn

The existing LazyFD solver is now deprecated and will be removed in a future release.

Changes to the MiniZinc language:

* We have added some new built-in functions to assist with formatting complex output: show_int/2, show_float/3, join/2 and concat/1.

* We have added two new built-in functions, show_int/2 and show_float/3, to assist with formatting complex output.

* The built-in annotation is_output/0 is no longer supported.

* The built-in functions sum/1, product/1, forall/1, exists/1, xorall/1 and iffall/1 now also work with multi-dimensional arrays.


Changes to the FlatZinc language:

* We have added two new FlatZinc built-ins: bool_lin_eq/3 and bool_lin_le/3.


Other changes in this release:

* The following new global constraints have been added to the MiniZinc library:
    circuit
    subcircuit

Bugs fixed in this release:

* mzn2fzn now supports flattening expressions containing the built-in operation abort/1.

* mzn2fzn no longer turns optimisation problems that have a fixed objective into satisfaction problems. [Bug #277]

* The FlatZinc interpreter's MIP backend no longer aborts in the presence of a constant assignment to the objective variable. [Bug #319]

* The FlatZinc interpreter's FD backend no longer erroneously reports unsatisfiability in the presence of a constant assignment to the objective variable. [Bug #319]

* mzn2fzn now correctly reports that the built-in fix operation has aborted if given an argument that is not fixed. [Bug #158]

* A bug in mzn2fzn that caused it to not completely flatten array expressions in var array lookups has been fixed. [Bug #318]

* A bug that caused the FlatZinc interpreter to not indicate that search was complete for optimization problems has been fixed.

Quite a few of my MiniZinc models contain is_output (now not supported). I will update to them to the current version as soon as possible.

Posted by hakank at 07:33 AM | Permalink

A paper and an implementation of Search Combinators - a framework to define application-tailored search strategies - has been available.

Paper

The paper is:
Tom Schrijvers, Guido Tack, Pieter Wuille, Horst Samulowitz, Peter J. Stuckey: Search Combinators (ArXiv). Abstract:

The ability to model search in a constraint solver can be an essential asset for solving combinatorial problems. However, existing infrastructure for defining search heuristics is often inadequate. Either modeling capabilities are extremely limited or users are faced with a general-purpose programming language whose features are not tailored towards writing search heuristics. As a result, major improvements in performance may remain unexplored. This article introduces search combinators, a lightweight and solver-independent method that bridges the gap between a conceptually simple modeling language for search (high-level, functional and naturally compositional) and an efficient implementation (low-level, imperative and highly non-modular). By allowing the user to define application-tailored search strategies from a small set of primitives, search combinators effectively provide a rich domain-specific language (DSL) for modeling search to the user. Remarkably, this DSL comes at a low implementation cost to the developer of a constraint solver.
The article discusses two modular implementation approaches and shows, by empirical evaluation, that search combinators can be implemented without overhead compared to a native, direct implementation in a constraint solver.

Implementation

An implementation using MiniZinc and Gecode is available from Gecode's FlatZinc page. The README file describes the tools as:

These two tools [minizinc-to-minizinc pre-compiler and FlatZinc interpreter], together with the G12 mzn2fzn translator, comprise a complete toolchain for solving MiniZinc models using search combinators. The pre-compiler translates a slightly extended version of MiniZinc to standards-compliant MiniZinc. The FlatZinc interpreter was modified to understand search combinators expressed as annotations.

In order to use the tools, you will need the standard mzn2fzn compiler from the G12 MiniZinc distribution, which can be downloaded at http://www.g12.cs.mu.oz.au/minizinc/download.html

Example

Two examples are included in the distribution: golomb.mzn and radiation.mzn. The golomb.mzn is shown here, where the specific changes has been marked:

include "globals.mzn";
include "searchcombinators.mzn";

int: m;
int: n = m*m;

array[1..m] of var 0..n: mark;
array[1..(m*(m-1)) div 2] of var 0..n: differences =
    [ mark[j] - mark[i] | i in 1..m, j in i+1..m];

constraint mark[1] = 0;
constraint forall ( i in 1..m-1 ) ( mark[i] < mark[i+1] );
constraint alldifferent(differences);

% Symmetry breaking
constraint differences[1] < differences[(m*(m-1)) div 2];

solve :: dicho(print(mark,int_search(mark,input_order,assign_lb)),
            mark[m],
            0,200)
            satisfy;

The result using the included data file golomb-10.dzn (m=10) is

{0, 1, 3, 7, 12, 20, 30, 44, 65, 80}
{0, 1, 3, 11, 17, 29, 36, 51, 56, 60}
{0, 1, 6, 10, 23, 26, 34, 41, 53, 55}

I have just started to experiment with this and might return with a longer report.

Posted by hakank at 06:15 PM | Permalink

Jacob Feldman wrote in JSR-331 is now an official standard!:

JSR-331 successfully passed the Final Approval Ballot. The JCP Executive Committee that includes representatives of IBM, RedHat, Fujitsu, Intel, SAP, Eclipse, HP, and others voted “Yes” on the Final Release that we submitted in January. Nobody voted “No” or “Abstained”. I even received personal emails from representatives of Oracle and Twitter who apologized for missing the voting deadline – they congratulated us and wrote they would vote “Yes” too.

...

We currently have 3 working JSR-331 implementations based on these open-sourced CP solvers: Choco, JaCoP, and Constrainer. Several more CP vendors expressed their intention to provide JSR-331 implementations too. I expect that this year we will receive and make publicly available implementations from these teams:

IBM CP Optimizer (Jean-Francois Puget and Paul Shaw)
Cream (Naoyuki Tamura)
JSetL (Federico Bergenti)
JOpt (Nick Coleman).

Congratulations!

Also see:

• JSR-000331 Constraint Programming API (Final Release)
• Jacob's blog post Road to CP Standardization
• Download from OpenRules or JCP
• JSR-331 discussion group

I tested a beta version of JSR-331 a while ago and implemented my standard "learning models". I like this framework, but I haven't yet adapted all my models to the final version so it's a forthcoming project to blog about it in more details. (Two of my models are included in the distribution: YoungTableaux.java and WhoKilledAgatha.java.)

Posted by hakank at 07:36 AM | Permalink

From the announcement of SweConsNet'12 - The Eleventh SweConsNet Workshop:

SweConsNet is the Network for Sweden-based researchers and practitioners of Constraint technology.

Following the previous successful workshops, we would like to announce the 11th SweConsNet workshop, which will take place in Örebro, Sweden on May 14th 2012. The workshop is organized in collocation with the 27th annual workshop of the Swedish Artificial Intelligence Society (SAIS).

The purpose of this workshop is to learn about ongoing research in constraint programming, as well as existing projects and products. We will also discuss the further development of the network, such as a possible widening to other Nordic countries.

The workshop is open to everybody interested in the theory and practice of constraint programming, whether based in Sweden or elsewhere. The scope of the workshop spans all areas of Constraint Programming, and is open to presentations and discussions addressing topics related to both theory and application.

Please forward a link of this page to people who might be interested but are not yet on the SweConsNet mailing list. They can subscribe to it by sending a message to Justin.Pearson at it.uu.se .

We hope for your participation, and highly encourage you to submit a proposal for a presentation of your ongoing work, recent results, or of a relevant discussion topic. There are no paper submissions, reviews, or proceedings, hence recent conference/journal papers may also be presented.

To register, please send a brief statement of intent, and desirably the title and abstract of your talk, to Christian Schulte (cschulte at kth.se). In order to facilitate organization, please notify us of your intention to participate as soon as possible, and at the latest before April 30th, 2012. The workshop does not have a registration fee.

Preliminary list of speakers

• Mats Carlsson, SICS. On the Reification of Global Constraints. Joint Work with: Nicolas Beldiceanu (EMN, Nantes, France), Pierre Flener and Justin Pearson (Uppsala University).
• Roberto Castañeda Lozano, SICS & KTH - ICT. Code Generation is a Constraint Problem. Joint work with: Mats Carlsson (SICS), Frej Drejhammar (SICS), Christian Schulte (KTH - ICT, SICS).
• Maria Andreina Francisco Rodriguez, Uppsala University. Consistency of Automaton-Induced Constraint Decompositions. Joint work with: Pierre Flener and Justin Pearson (Uppsala University).
• Håkan Kjellerstrand. Comparison of >= 14 CP systems - and counting.
• Krzysztof Kuchcinski, Lund University. TBD.
• Federico Pecora, Örebro University. Constraint-based methods for multiple non-holonomic vehicle scheduling and control.

As you see, I plan to compare different CP systems, which will be the systems listed in Common CP Problems. Perhaps also some not yet on that list, candidates are Numberjack, JSR-331, and Scampi.

For a taste of earlier workshops, see SweConsNet:Workshops, and general information about SweConsNet.

Posted by hakank at 05:58 PM | Permalink

I'm very honored to announce that I have been invited by Laurent Perron (Google or-tools) to talk about my view on Constraint Programming at Google, Paris later this month.

The talk will be about Constraint Programming and what is so fascinating about it, including - of course - examples in or-tools (which I have tested and modeled in for the Python, Java - and now lately - C# interfaces). There will also be more general views about CP and perhaps comparisons between different CP systems. The audience will be the engineers at Google (Paris) which makes it an extra challenge (and fun). It will also be really great to meet the or-tools group.

After the event I will blog about the details, including publishing the slides.

Also see: My or-tools page.

Posted by hakank at 09:45 PM | Permalink

For a time I have not blogged about all models I've created, instead just tweeted about them (I'm hakankj at Twitter). And sometimes not even than, just published them directly on my <CP system> pages without any noise.

Well, here I have collect some of these newer and unblogged models in - roughly - time order. Most are in MiniZinc (since I often use MiniZinc for prototyping) but there are also some in other systems. (See Constraint Programming for a list of these CP systems pages.)

• xkcd_among_diff_0.mzn: Xkcd problem using among_diff_0
  This is another approach of the Xkcd "knapsack problem" where the object is to order dishes for an amount of exactly 15.05.
  This version where inspired by a comment in Helmut Simonis presentation Acquiring Global Constraint Models (page 3), where he use the global constraint among_diff_0 ("Count how many variables are different from 0")
  However, my implementation differs in some ways:
  • it use integers instead of floats.
  • it implements a slightly more general approach
  For more about the global constraint among_diff_0: see my MiniZinc model among_diff_0.mzn. Also see xkcd.mzn, my first approach of the problem.
  
  
• monorail.mzn: Monorail puzzle
  From Aaron Iba's Blog Users of my iOS Game Teach Me a Lesson MIT Didn't:

  The object of Monorail puzzles is to complete a closed-circuit loop through all the stations (dots) by drawing rails. The loop must pass through each station exactly once and close back on itself, like an actual monorail system might in a city.

  Problem:
  
      .   .   .   .       1  2  3  4
  
      .   .___.   .       5  6  7  8
          |
      .   .   .   .       9 10 11 12
  
      .   .___.   .      13 14 15 16
   
  Solution:
      .__.___.___.
      |          |
      .  .___.___.
      |  | 
      .  .___.___.
      |          |
      .__.___.___.
  
  

  Also see
  Glenn Iba's site
  • Monorail Support Page
  • The introduction to Glenn Iba's book "Round Trip Puzzles"
  • Intro-long-web.pdf (PDF)
  • Glenn Iba Hamiltonian Cycle Puzzles (PDF)
  
  Problem instances:
  • monorail1.dzn
  • monorail2.dzn
  • monorail3.dzn
  • monorail4.dzn
  • monorail5.dzn
  • monorail6.dzn
  
  
  
• dennys_menu.mzn
  From Mind Your Decisions (about game theory and personal finance) Denny's math commercial:

  So there’s the question: how many different price combinations will total $10 when menu items priced at $2, $4, $6, and $8?

  
  
• Some Rosetta Code implementations of various knapsack problems
  
  • knapsack_rosetta_code.mzn: See Rosetta Code Knapsack_problem/Bounded
  • knapsack_rosetta_code_unbounded.mzn: See Rosetta Code Knapsack_problem/Unbounded
  • knapsack_rosetta_code_unbounded_int.mzn: See Rosetta Code Knapsack_problem/Unbounded (integer version)
  • knapsack_rosetta_code_01.mzn: See Rosetta Code Knapsack_problem/0-1
  
  
  
• Newspaper problem (job-shop)
  Implementations:
  • newspaper0.mzn
  • newspaper.mzn
  
  Problem statement from Snehal Patel's CS course

  There are four students: Algy, Bertie, Charlie and Digby, who share a flat. Four newspapers are delivered to the house: the Financial Times, the Guardian, the Daily Express and the Sun. Each of the students reads all of the newspapers, in particular order and for a specified amount of time (see below). Question: Given that Algy gets up at 8:30, Bertie and Charlie at 8:45 and Digby at 9:30, what is the earliest that they can all set off for college?

       Algy           Bertie        Charlie      Digby
  1st  FT       60    Guardian 75   Express  5   Sun      90
  2nd  Guardian 30    Express   3   Guardian 15  FT        1
  3rd  Express   2    FT       25   FT       10  Guardian  1
  4th  Sun       3    Sun      10   Sun      30  Express   1
  

  Extra requirements: All reads the newspaper in a specific order:

  - Algy order   : - FT, Guardian, Express, Sun
  - Bertie order : - Guardian, Express, FT, Sun
  - Charlie order: - Express, Guardian, FT, Sun
  - Digby order  : - Sun, FT, Guardian, Express
  

  This origin of this problem is from S. French: "Sequencing and Scheduling : an introduction to the mathematics of the job-shop", Ellis Horwood Limited, 1982.
  
  Tim Duncan wrote about it in his paper "Scheduling Problems and Constraint Logic Programming: A Simple Example and its Solution", AIAI-TR-120, 1990, page 5. The paper also includes a program in CHIP solving the problem.)
  
  Two versions differs by that the first (newpaper0.mzn) is not loaded with so much output stuff as the latter (newpaper.mzn).
  
  
• schedule2.mzn
  Problem from Dennis E. Sasha's book "Puzzles for Programmers and Pros", page 131f:

  In which order do you schedule the tasks starting from current
  day 0?:
  Task  T1 takes 4 days with deadline on day 45
  Task  T2 takes 4 days with deadline on day 48
  Task  T3 takes 5 days with deadline on day 25
  Task  T4 takes 2 days with deadline on day 49
  Task  T5 takes 5 days with deadline on day 36
  Task  T6 takes 2 days with deadline on day 31
  Task  T7 takes 7 days with deadline on day 9
  Task  T8 takes 5 days with deadline on day 39
  Task  T9 takes 4 days with deadline on day 13
  Task T10 takes 6 days with deadline on day 17
  Task T11 takes 4 days with deadline on day 29
  Task T12 takes 1 days with deadline on day 19
  

  
  
  
• Some Project Euler problems
  Whenever I learn a new programming language, I tend to solve at least the first - say - 20 Project Euler problems. Unfortunately many of the problems requires arbitrary precision or recursive approaches, and neither has good support in MiniZinc. Here are some of the problems:
  • euler_1.mzn: Problem 1
  • euler_2.mzn: Problem 2
  • euler_9.mzn: Problem 9
  • euler_18.mzn: Problem 18
  • euler_30.mzn: Problem 30
  • euler_39.mzn: Problem 39
  • euler_52.mzn: Problem 52
  
  
  
• hitting_set.mzn
  From MathWorld: VertexCover

  Let S be a collection of subsets of a finite set X. A subset Y of X that meets every member of S is called the vertex cover, or hitting set. The smallest possible such subset for a given graph G is known as a minimum vertex cover (Skiena 1990, p. 218), and its size is called the vertex cover number, denoted tau(G).

  This model some different problem instances, for example those from the cited article above but also from other sources
  
  By the way, this model was implemented after I read the paper There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem by Gary McGuire, Bastian Tugemann, and Gilles Civario. The abstract states: We apply our new hitting set enumeration algorithm to solve the sudoku minimum number of clues problem, which is the following question: What is the smallest number of clues (givens) that a sudoku puzzle may have? [...]
  
• maximal_independent_sets.mzn
  From Wikipedia: Maximal independent set:

  In graph theory, a maximal independent set or maximal stable set is an independent set that is not a subset of any other independent set. That is, it is a set S such that every edge of the graph has at least one endpoint not in S and every vertex not in S has at least one neighbor in S. A maximal independent set is also a dominating set in the graph, and every dominating set that is independent must be maximal independent, so maximal independent sets are also called independent dominating sets.
  
  A graph may have many maximal independent sets of widely varying sizes; a largest maximal independent set is called a maximum independent set.

  The model contains a few problem instances, e.g. those from the above cited Wikipedia article.
  Also see Wikipedia Independent set (graph theory), and compare with the MiniZinc model misp.mzn which use another representation and approach (inspired from GLPK:s model).
  
  
• magic_square_frenicle_form.mzn
  From Wikipedia Frénicle standard form

  A magic square is in Frénicle standard form, named for Bernard Frénicle de Bessy, if the following two conditions apply:
  - the element at position [1,1] (top left corner) is the smallest of the four corner elements; and
  - the element at position [1,2] (top edge, second from left) is smaller than the element in [2,1].

  Activating all these constraints we get the "standard" way of counting the number of solutions:

  (1), 0, 1, 880, 275305224
  

  which is the sequence A006052 from the excellent Online Encyclopedia of Integer Sequence
  
  Without these symmetry constraints the number of solutions are:

  N  #solutions
  -------------
  1     1
  2     0
  3     8
  4  7040
  5  many...
  

  (Counting the number of the solutions of a CP model is a very good way of ensuring that the model is correct, or rather: if the number of the solutions are not the expected, then the model is wrong.)
  
  
• scheduling_with_assignments.mzn
  This was done directly after I've done the newspaper.mzn (see above). It then struck me that most examples I've seen of scheduling in Constraint Programming (especially when demonstrated the works of cumulative), just showed the times of the jobs not the assignments of the workers.
  In this model, both the job assignments and the worker assignments are shown in different way. For example the solution of one of my own standard problem furniture_moving.mzn (from Marriott and Stuckey: "Programming with constraints", page 112f) is shown as

  earliest_end_time: 60
  num_jobs   : 4
  num_workers: 4
  start_time : [0, 0, 30, 45]
  duration   : [30, 10, 15, 15]
  end_time   : [30, 10, 45, 60]
  resource   : [3, 1, 3, 2]
  allow_idle : true
  collect_workers : false
  do_precendences: false
  
  Assignment matrix (jobs/workers):
  Job1: 1 0 1 1
  Job2: 0 1 0 0
  Job3: 1 0 1 1
  Job4: 1 1 0 0
  
  Assignment matrix (workers/jobs):
  Worker1: 1 0 1 1
  Worker2: 0 1 0 1
  Worker3: 1 0 1 0
  Worker4: 1 0 1 0
  
  Time range for the jobs and the assigned worker(s):
  Job1(0..30): 1 3 4 
  Job2(0..10): 2 
  Job3(30..45): 1 3 4 
  Job4(45..60): 1 2 
  
  ....
  
  Schedule: worker(job), timeline: (earliest_end_time: 60)
  Worker: 1:    1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4 
  Worker: 2:    2  2  2  2  2  2  2  2  2  2  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  -  4  4  4  4  4  4  4  4  4  4  4  4  4  4  4 
  Worker: 3:    1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  -  -  -  -  -  -  -  -  -  -  -  -  -  -  - 
  Worker: 4:    1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  -  -  -  -  -  -  -  -  -  -  -  -  -  -  - 
  
  Time:         0  1  2  3  4  5  6  7  8  9  10 1  2  3  4  5  6  7  8  9  20 1  2  3  4  5  6  7  8  9  30 1  2  3  4  5  6  7  8  9  40 1  2  3  4  5  6  7  8  9  50 1  2  3  4  5  6  7  8  9  
  

  The model presents:
  • start time, duration, and end time for all jobs
  • assignment matrix jobs/workers
  • assignment matrix workers/jobs
  • jobs with time range, and the assigned workers
  • schedule (time line in time units) for the jobs, showing the assigned worker
  • schedule (time line) for the workers, showing the time the workers work
  • and last, a Gantt like schedule showing which job each worker is scheduled to to in each time.
  
  The model also have some other "bells & whistles" such as
  • handling precedences
  • modeling as a bin pack problem
  • "collecting workers", which may be useful for certain problem, such as perfect square placements
  
  The two last "features" shows that the job scheduling problem has a family resemblance with bin pack and perfect square placement problem. Unfortunately these are not very fast in this model.
  
  Well, since I plan to blog about this more, including a benchmark, I leave it for now.
  
  Here are the problems instances. They has been taken from various sources:
  • 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)
  
  
  
• equal_sized_groups.mzn
  This is a problem from or-exchange (where many from the area of Operations Research hang out): dividing into roughly equal sized groups, with a sorted list

  I have a problem, and it seems like it should be something that someone has studied before. I have a sorted list of N elements, and I want to divide them into K groups, by choosing K-1 split points between them. There may be elements with the same value, and we want to have items with same value in the same group. Find K groups as close in size to round(N/K) as possible.
  
  For example, divide these 32 elements in to 4 groups of size 8:

   1 1 1 1 2 2 3 3 3 3 3 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 7 8 9 10 10
  

  One solution would be these 3 break points:

   
   1 1 1 1 2 2 | 3 3 3 3 3 3 3 3 | 4 4 4 4 5 5 5 5 5 | 6 6 6 6 7 8 9 10 10
  [            6                 14                 23                    ]
  [    6 elts      8 elts               9 elts              9 elts          ]
   
   1 1 1 1 2 2         = 6 elements,  error = abs(8-6)=2
   3 3 3 3 3 3 3 3     = 8 elements,  error = abs(8-8)=0
   4 4 4 4 5 5 5 5 5     = 9 elements,  error = abs(8-9)=1
   6 6 6 6 7 8 9 10 10 = 9 elements,  error = abs(8-9)=1
   
   total error = 4
  

  Does this look familiar to anyone? I'd like an approximation algorithm if possible.
  
  Thanks, Craig Schmidt

  The model contains some examples and results.
  
  
• houses.mzn
  Problem from a Kanren example: houses.scm

  Taken from _Algebra 1_, Glencoe/McGraw-Hill, New York, New York, 1998 pg. 411, Problem 56
  
  There are 8 houses on McArthur St, all in a row. These houses are numbered from 1 to 8.
  
  Allison, whose house number is greater than 2, lives next door to her best friend, Adrienne. Belinda, whose house number is greater than 5, lives 2 doors away from her boyfriend, Benito. Cheri, whose house number is greater than Benito's, lives three doors away from her piano teacher, Mr. Crawford. Daryl, whose house number is less than 4, lives 4 doors from his teammate, Don. Who lives in each house?

  One thing to note is the use of the global constraint inverse for channeling the each person to the houses and vice versa.
  
  
• Finding an optimal wedding seating chart
  This problem has been implemented in both MiniZinc and or-tools/C#:
  • wedding_optimal_chart.mzn
  • wedding_optimal_chart.cs
  
  The problem is from Meghan L. Bellows and J. D. Luc Peterson Finding an optimal seating chart for a wedding (PDF), via Improbable Research Finding an optimal seating chart for a wedding:

  Every year, millions of brides (not to mention their mothers, future mothers-in-law, and occasionally grooms) struggle with one of the most daunting tasks during the wedding-planning process: the seating chart. The guest responses are in, banquet hall is booked, menu choices have been made. You think the hard parts are over, but you have yet to embark upon the biggest headache of them all. In order to make this process easier, we present a mathematical formulation that models the seating chart problem. This model can be solved to find the optimal arrangement of guests at tables. At the very least, it can provide a starting point and hopefully minimize stress and arguments…

  As mentioned before (e.g. in A matching problem, a related seating problem, and some other seating problems) I'm quite fascinated by this type of seating problems.
  
  And I'm not the only one. After I tweeted about my MiniZinc implementation (wedding_optimal_chart.mzn), Erwin Kalvehagen (with the excellent blog Yet Another Math Programming Consultant showed a GAMS (MIP) model in Weddings and optimal seating . (He also found a bug in my model which was fixed quite easily. Thanks Erwin.)
  
• grime_puzzle.mzn
  This problem was taken from the blog Travels in a mathematical world A puzzle from James Grime about abcdef:

  Today James Grime tweeted this question/puzzle:
  
  Is there a six digit number abcdef such that the following all hold?
  
  a+b+c+d+e+f = y
  ab+cd+ef=10y
  abc+def=100y
  
  
  If not, show why not.
  
  A little tweeting back and forth verified that "ab" means 10a+b not a×b.

  
  
• balanced_brackets.mzn
  This model generates balanced brackets of size m*2. The number of generated solutions for m:

   m        #
   ----------
   1       1
   2       2
   3       5
   4      14
   5      42
   6     132
   7     429
   8    1430
   9    4862
  10   16796
  11   58786
  12  208012
  13  742900
  

  Which - of course - is the Catalan numbers. See OEIS: 1,2,5,14,42,132,429,1430,4862,16796,58786,208012, and the entry for Catalan numbers: A000108.
  
  
• The "8809 = 6" puzzle
  This problem has been encoded in both MiniZinc and or-tools/C# (and was created yesterday):
  • a_puzzle.mzn: MiniZinc implementation
  • a_puzzle.cs: or-tools/C# implementation
  
  The problem seems to have been around for a couple of years, but it wasn't until I read about it in another excellent blog (Michael Lugo's God Plays Dice): A puzzle that I really tried it (and was lucky to solve it direct without any computational aid). The problem was stated thus:

   
  Here’s a puzzle.
  
  8809 = 6
  7662 = 2
  9312 = 1
  8193 = 3
  8096 = 5
  7756 = 1
  6855 = 3
  9881 = 5
  
  2581 = ?
  

  After a few days a mathematical solution came in the blog post: An answer to a puzzle, but then the problem had been expanded a little:

  8809 = 6
  7111 = 0
  2172 = 0
  6666 = 4
  1111 = 0
  3213 = 0
  7662 = 2
  9312 = 1
  0000 = 4
  2222 = 0
  3333 = 0
  5555 = 0
  8193 = 3
  8096 = 5
  7777 = 0
  9999 = 4
  7756 = 1
  6855 = 3
  9881 = 5
  5531 = 0
  
  2581 = ?
  

  The first version of the problem actually has two different solutions (of the unknown "?", represented as x in the models), since some of the variables are under defined. The second version has a unique solution of x, but there are 10 slightly different solutions since one of the variables is (still) under defined, i.e. the x is the same in all these solutions.
  
  The approach in my models was inspired by Michael Lugo's mathematical solution (as an equation system), though the or-tools/C# model implements another version using a matrix to represent the problem.

Posted by hakank at 10:28 AM | Permalink