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

C[omp]ute

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.

Last 100 entries

Flexible Muscle-Based Locomotion for Bipedal Creatures; SQL Performance Explained; The Little Manual of API Design; Multiple Word Sizes; CRC - Next Steps; FizzBuzz; Update on CRCs; Decent Links / Discussion Community; Automated Reasoning About LLVM Optimizations and Undefined Behavior; A Painless Guide To CRC Error Detection Algorithms; Tests in Julia; Dave Eggers: what's so funny about peace, love and Starship?; Cello - High Level C Programming; autoreconf needs tar; Will Self Goes To Heathrow; Top 5 BioInformatics Papers; Vasovagal Response; Good Food in Vina; Chilean Drug Criminals Use Subsitution Cipher; Adrenaline; Stiglitz on the Impact of Technology; Why Not; How I Am 5; Lenovo X240 OpenSuse 13.1; NSA and GCHQ - Psychological Trolls; Finite Fields in Julia (Defining Your Own Number Type); Julian Assange; Starting Qemu on OpenSuse; Noisy GAs/TMs; Venezuela; Reinstalling GRUB with EFI; Instructions For Disabling KDE Indexing; Evolving Speakers; Changing Salt Size in Simple Crypt 3.0.0; Logarithmic Map (Moved); More Info; Words Found in Voynich Manuscript; An Inventory Of 3D Space-Filling Curves; Foxes Using Magnetic Fields To Hunt; 5 Rounds RC5 No Rotation; JP Morgan and Madoff; Ori - Secure, Distributed File System; Physical Unclonable Functions (PUFs); Prejudice on Reddit; Recursion OK; Optimizing Julia Code; Cash Handouts in Brazil; Couple Nice Music Videos; It Also Works!; Adaptive Plaintext; It Works!; RC5 Without Rotation (2); 8 Years...; Attack Against Encrypted Linux Disks; Pushing Back On NSA At IETF; Summary of Experimental Ethics; Very Good Talk On Security, Snowden; Locusts are Grasshoppers!; Vagrant (OpenSuse and IDEs); Interesting Take On Mandela's Context; Haskell Cabal O(n^2) / O(n) Fix; How I Am 4; Chilean Charity Supporting Women; Doing SSH right; Festival of Urban Intervention; Neat Idea - Wormholes Provide Entanglement; And a Link....; Simple Encryption for Python 2.7; OpenSuse 13.1 Is Better!; Little Gain...; More Details on Technofull Damage; Palmrest Cracked Too....; Tecnofull (Lenovo Support) Is Fucking Useless; The Neuroscientist Who Discovered He Was a Psychopath; Interpolating Polynomials; Bottlehead Crack as Pre-amp; Ooops K702!; Bottlehead Crack, AKG K701; Breaking RC5 Without Rotation; Great post thank you; Big Balls of Mud; Phabricator - Tools for working together; Amazing Julia RC5 Code Parameterized By Word Size; Chi-Square Can Be Two-Sided; Why Do Brits Accept Surveillance?; Statistics Done Wrong; Mesas Trape from Bravo; European Report on Crypto Primitives and Protocols; Interesting Omissions; Oryx And Crake (Margaret Atwood); Music and Theory; My Arduino Programs; Elliptic Curve Crypto; Re: Licensing Interpreted Code; Licensing Interpreted Code; ASUS 1015E-DS03 OpenSuse 12.3 SSD; translating lettuce feature files into stub steps files; Re: translating lettuce feature files into stub steps files; A Tale of Two Psychiatrists; The Real Reason the Poor Go Without Bank Accounts; The Rational Choices of Crack Addicts

© 2006-2013 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
http://stackoverflow.com/questions/7076349/is-there-a-good-way-to-do-this-type-of-mining/7237972#7237972
- it would be better to read it there, but I wanted a local copy in case it
was deleted at some point.

Andrew


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: http://stackoverflow.com/q/7137334/181772

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
together.

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

Conclusion
----------

 - 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