Andrew Cooke | Contents | Latest | RSS | Twitter | Previous | Next


Welcome to my blog, which was once a mailing list of the same name and is still generated by mail. Please reply via the "comment" links.

Always interested in offers/projects/new ideas. Eclectic experience in fields like: numerical computing; Python web; Java enterprise; functional languages; GPGPU; SQL databases; etc. Based in Santiago, Chile; telecommute worldwide. CV; email.

Personal Projects

Lepl parser for Python.

Colorless Green.

Photography around Santiago.

SVG experiment.

Professional Portfolio

Calibration of seismometers.

Data access via web services.

Cache rewrite.

Extending OpenSSH.

C-ORM: docs, API.

Last 100 entries

[Link] Neat Python Exceptions; [Link] Fix for Windows 10 to Avoid Ads; [Link] Attacks on ZRTP; [Link] UK Jazz Invasion; [Review] Cuba; [Link] Aricle on Gender Reversal of US Presidential Debate; {OpenSuse] Fix for Network Offline in Updater Applet; [Link] Parkinson's Related to Gut Flora; Farellones Bike Park; [Meta] Tags; Update: Second Ride; Schwalbe Thunder Burt 2.1 v Continental X-King 2.4; Mountain Biking in Santiago; Books on Ethics; Security Fail from Command Driven Interface; Everything Old is New Again; Interesting Take on Trump's Lies; Chutney v6; References on Entropy; Amusing "Alexa.." broadcast; The Shame of Chile's Education System; Playing mp4 gifs in Firefox on Opensuses Leap 42.2; Concurrency at Microsoft; Globalisation: Uk -> Chile; OpenSuse 42.2 and Synaptics Touch-Pads; Even; Cherry Jam; Lebanese Writer Amin Maalouf; C++ - it's the language of the future; Learning From Trump; Chinese Writer Hu Fayun; And; Apricot Jam; Also; Excellent Article on USA Politics; Oh Metafilter; Prejudice Against The Rurals; Also, Zizek; Trump; Why Trump Won; Doxygen + Latex on CentOS 6; SMASH - Solve 5 Biggest Problems in Physics; Good article on racism, brexit, and social divides; Grandaddy are back!; Consciousness From Max Entropy; Democrats; Harvard Will Fix Black Poverty; Modelling Bicycle Wheels; Amusing Polling Outlier; If Labour keeps telling working class people...; Populism and Choice; Books on Defeat; Enrique Ferrari - Argentine Author; Transcript of German Scientists on Learning of Hiroshima; Calvert Journal; Owen Jones on Twitter; Possible Japanese Authors; Complex American Literature; Chutney v5; Weird Componentized Virus; Interesting Argentinian Author - Antonio Di Benedetto; Useful Thread on MetaPhysics; RAND on fighting online anarchy (2001); NSA Hacked; Very Good LRB Article on Brexit; Nussbaum on Anger; Tasting; Apple + Kiwi Jam; Hit Me; Sudoku - CSP + Chaos; Recycling Electronics In Santiago; Vector Displays in OpenGL; And Anti-Aliased; OpenGL - Render via Intermediate Texture; And Garmin Connect; Using Garmin Forerunner 230 With Linux; (Beating Dead Horse) StackOverflow; Current State of Justice in China; Axiom of Determinacy; Ewww; Fee Chaos Book; Course on Differential Geometry; Okay, but...; Sparse Matrices, Deep Learning; Sounds Bad; Applebaum Rape; Tomato Chutney v4; Have to add...; Culturally Liberal and Nothing More; Weird Finite / Infinite Result; Your diamond is a beaten up mess; Maths Books; Good Bike Route from Providencia / Las Condes to Panul; Iain Pears (Author of Complex Plots); Plum Jam; Excellent; More Recently; For a moment I forgot StackOverflow sucked; A Few Weeks On...; Chilean Book Recommendations; How To Write Shared Libraries

© 2006-2017 Andrew Cooke (site) / post authors (content).

Using Constraint Programming to Identify Groups

From: andrew cooke <andrew@...>

Date: Mon, 29 Aug 2011 23:43:08 -0300

This is the text of my answer at
- it would be better to read it there, but I wanted a local copy in case it
was deleted at some point.


This is a little late, but this problem has been worrying me for some time.  I
was sure it could be solved with mixed integer / linear programming techniques
and asked for help in this question:

However, after getting a reply there, I had an insight that your problem, at
least as I understand it, is so simple (when framed as a constraint program)
that you can solve it trivially with a simple program (which you already
knew).  In other words, constraint programming would be a cool way to solve
this, but, at least with the approach I found, would give you the same answer
as something much simpler.

I'll explain below my reasoning, how I would implement it with a constraint
solving package, and then give the final, trivial, algorithm.

Mixed integer programming solution

The most important detail is the difference between horizontal and vertical
groups.  As far as i can see, anything that aligns vertically can be in the
same group.  But horizontal groups are different - components have to be close

The hardest part of solving a problem with constraints seems to be finding a
way to describe the limits in a way that the solver can understand.  I won't
go into the details here, but solvers are frustratingly limited.  Luckily I
think there is a way to do this here, and it is to consider horizontal
neighbours:  if there are N points in a row then we have `N-1` sets of
neighbours (for example, with 4 points A B C and D there are the three pairs
AB, BC, and CD).

For each pair, we can give a score, which is the number of spaces between them
(`S_i`) scaled by some factor `K`, and a flag (`F_i`) which is 0 or 1.  If the
pair are in the same horizontal group then we set the flag to 1, otherwise it
is zero.

It is critical to see that the set of flags for all the pairs *completely
defines a solution*.  For any row we can run along, placing pairs with a flag
of 1 in the same horizontal group, and starting a new horizontal group each
time the flag is 0.  Then, we can take all horizontal groups of size 1 and
convert them into vertical groups: any point that is not in a horizontal group
must be in a vertical group (even if it is a vertical group of just one).

So all we need now is a way to express an optimal solution in terms of the
flags.  I suggest that we want to minimise:

    sum(1 - F_i) + sum(K * S_i * F_i)

This has two terms.  The first is the sum of "one minus the flag" for each
pair.  The flag is 1 when the points are in the same horizontal group and 0
otherwise.  So minimising this value is the same as saying that we want as
*few* horizontal groups as possible.  If this was the only constraint then we
could set it to zero by making all the `F_i` 1 - by making all pairs on a row
members of the same group.

But the second term stops us from choosing such an extreme solution.  It
penalises groups with gaps.  If a pair are in the same group, but are
separated by `S_i` spaces, then we have a "penalty" of `K * S_i`.

So we have a trade-off.  We want horizontal groups, but we don't want gaps.
The final solution will depend on `K` - if it is large then we won't include
any spaces in horizontal groups.  But as it is decreased we will start to do
so, until when it is very small (tends to zero) we place everything in a row
in a single group.

Analytic solution

OK, cool.  At this point we have a way to express the problem that we can give
to a constraint engine.

But it's trivial to solve!  we don't need no stinkin' constraint engine to
solve this - we can just look at the expression:

    sum(1 - F_i) + K * sum(S_i * F_i)

The two sums are over the same pairs, so we can move everything into the sum:

    sum(1 - F_i + K * S_i * F_i)
    sum(1 - F_i * (K * S_i - 1))

And then extract the constant (`N` here is the total number of pairs):

    N - sum(F_i * (K * S_i - 1))

Now note that each term in the sum is independent (and additive).  so for each
term, we want the minimum value.  we have two options:

 - if `F_i` is 0 then the entire term is 0.  

 - otherwise, `F_i` is 1 and the term is `K * S_i - 1`.

So the best choice depends on whether `K * S_i` is greater than 1.  if `K *
S_i` is greater than 1 then the smallest value of the term is 0, and `F_i`
should be 0.  Otherwise the second choice above is negative, and `F_i` should
be one.

Trivial algorithm

What does this mean?  It means that for each pair we can simply look at the
number of spaces, `S_i`.  If that is greater than `1 / K` then the two points
should be in separate groups.  otherwise they should be in the same group.

So all this fancy maths and optimisation and constraints and bullshitting
comes down to: how far apart are two points in neighbouring pairs?  If they
are closer than some cut-off, put them in the same horizontal group.
Otherwise, put them in separate groups.

So here, finally, is your algorithm:

    choose some cut-off value, X
    place each point in its own, singleton, horizontal group
    for each row with more that one point:
        for each neighbouring pair in the row:
            if the space between the pair is less than X:
                joint into a single horizontal group
    for each column:
        join any single singleton groups into a single vertical group


 - You can use constraint programming techniques to solve this problem.

 - But such techniques are restricted to problems that can be described in
   "the right" (typically, linear) way.

 - The simplest such approach I can find is equivalent to a trivial, direct
   algorithm that divides points in a row into horizontal groups depending on
   the number of spaces between them.

 - But this all depends on a whole pile of assumptions which may, of course,
   be over-simplifications, or just plain wrong.

Comment on this post