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

C-ORM: docs, API.

Last 100 entries

FBI Claimed Vandalism; Architectural Tessellation; Also: Go, Blake's 7; Delusions of Gender (book); Crypto AG DID work with NSA / GCHQ; UNUMS (Universal Number Format); MOOCs (Massive Open Online Courses); Interesting Looking Game; Euler's Theorem for Polynomials; Weeks 3-6; Reddit Comment; Differential Cryptanalysis For Dummies; Japanese Graphic Design; Books To Be Re-Read; And Today I Learned Bugs Need Clear Examples; Factoring a 67 bit prime in your head; Islamic Geometric Art; Useful Julia Backtraces from Tasks; Nothing, however, is lost with less discomfort than that which, when lost, cannot be missed; Article on Didion; Cost of Living by City; British Slavery; Derrida on Metaphor; African SciFi; Traits in Julia; Alternative Japanese Lit; Pulic Key as Address (Snow); Why Information Grows; The Blindness Of The Chilean Elite; Some Victoriagate Links; This Is Why I Left StackOverflow; New TLS Implementation; Maths for Physicists; How I Am 8; 1000 Word Philosophy; Cyberpunk Reading List; Detailed Discussion of Message Dispatch in ParserCombinator Library for Julia; FizzBuzz in Julia w Dependent Types; kokko - Design Shop in Osaka; Summary of Greece, Currently; LLVM and GPUs; See Also; Schoolgirl Groyps (Maths); Japanese Lit; Another Example - Modular Arithmetic; Music from United; Python 2 and 3 compatible alternative.; Read Agatha Christie for the Plot; A Constructive Look at TempleOS; Music Thread w Many Recommendations; Fixed Version; A Useful Julia Macro To Define Equality And Hash; k3b cdrom access, OpenSuse 13.1; Week 2; From outside, the UK looks less than stellar; Huge Fonts in VirtualBox; Keen - Complex Emergencies; The Fallen of World War II; Some Spanish Fiction; Calling C From Fortran 95; Bjork DJ Set; Z3 Example With Python; Week 1; Useful Guide To Starting With IJulia; UK Election + Media; Review: Reinventing Organizations; Inline Assembly With Julia / LLVM; Against the definition of types; Dumb Crypto Paper; The Search For Quasi-Periodicity...; Is There An Alternative To Processing?; CARDIAC (CARDboard Illustrative Aid to Computation); The Bolivian Case Against Chile At The Hague; Clear, Cogent Economic Arguments For Immigration; A Program To Say If I Am Working; Decent Cards For Ill People; New Photo; Luksic And Barrick Gold; President Bachelet's Speech; Baltimore Primer; libxml2 Parsing Stream; configure.ac Recipe For Library Path; The Davalos Affair For Idiots; Not The Onion: Google Fireside Chat w Kissinger; Bicycle Wheels, Inertia, and Energy; Another Tax Fraud; Google's Borg; A Verion That Redirects To Local HTTP Server; Spanish Accents For Idiots; Aluminium Cans; Advice on Spray Painting; Female View of Online Chat From a Male; UX Reading List; S4 Subgroups - Geometric Interpretation; Fucking Email; The SQM Affair For Idiots; Using Kolmogorov Complexity; Oblique Strategies in bash; Curses Tools; Markov Chain Monte Carlo Without all the Bullshit; Email Para Matias Godoy Mercado

© 2006-2015 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