Re: combinatorial optimization problem (six-pick wager grouping)

bullockbefriending bard wrote:

(I'm aware that there are other ways to attack this problem, e.g. some
kind of brute force backtracking, or possibly treating it as a set
packing problem and welcome further thoughts and ideas along these and
other lines. however, i would be very appreciative if anybody deeply
versed in graph theoretic approaches could comment on my ideas below -
i think think it is a nice formulation of the problem and produces
interesting solutions patterns in graphviz when i view the results -
but i am not knowledgeable enough to know if it's even remotely
feasible to extract solutions algorithmically.. essentially what my
approach would require is finding fairly maximal cliques in a large
graph and then matching those cliques with other disjoint cliques.)

I'n not a graph theorist, nor a graph algorithm buff, so I can't really
comment on your approach. It seems clever, and is quite elegant, but I
don't have any kind of a feel for how effective it would be.


But I wanted to ask you if you'd tried an experiment with simple brute
force ? Not only to discover whether you really have a performance
problem, but also to give you some idea of how much "compression" you
could expect to get (and therefore what the tradeoffs would be between
speed and effectiveness).

I hacked together a simple test. It's really /grossly/ inefficient.
The algorithm is somewhere over O(N^2), and hasn't even been
micro-optimised (like not running it in an interpreted language, for a
start). Using bets of 6 legs, uniformly distributed between 14 horses
in each race, it was able to "compress" 10,000 bets in a few seconds,
and (N^2 remember!) 100,000 bets in several minutes.

The algorithm is simple. Two bets can be safely merged iff the sum of
their ranks is >= to the rank of ther "sum". By "rank" I mean the
number of bets the record represents. E.g
8/1/1+2/1/1/1 (rank = 2)
1/1/1+3/1/1/8 (rank = 2)
"sum": 1+8/1/1+2+3/1/1/1+8 (rank = 12)
so these two bets cannot be merged (since you'd end up paying for bets
you didn't want to make).

Use that criterion in a nested loop. Start with an empty collection of
bets, plus a candidate pool of bets to be added. For each candidate
attempt to merge it with each bet already in the pool. If you find any
legal mergee then replace that bet in the pool with the merged value,
otherwise add the candiate to the pool as a new entry. If you didn't
find any merges (or only a few) then you're done. Otherwise exchange
pool and candidate list and have another go.

In my experiment starting with 100,000 original records, that
removed/merged successively
90525 , 4863, 149, 41, 4, 1, 0
bet records on each pass. Leaving only 3,767. (My code ignores
duplicate records, so a few "just vanish")

I'm pretty sure that the code could be speeded up a lot. Perhaps by
using some fancy (and rather tedious) indexing to speed up locating
potential mergees in the inner loop. Or, since the first pass gets rid
of such a high percentage of records, it would probably be effective to
splitt the first group up into bunches of 1,000 or even 10,000, reduce
each bunch independently, then feed the whole lot back into the main
algorithm.


Another point is that I'm that this pairwise-only merging can't catch
all possible merges, but since we get approximately 96% compression
anyway, that might not matter.


Anyway, I have no idea what kind of hardware you'll be running on, nor
of what your performance goals are, but I wanted to illustrate that
cheap-n-chearful wasn't /necessarily/ going to be impractical.


Finally, to give some notion of the size of networks I am looking at,
one fairly maximal (I hope) edge case had 143,000 vertices and 2.5
million edges when I ignored wager size. In practice, I would
probably
only create edges between two (modified Hamming distance = 1)
vertices
when their wager sizes were within an acceptable (say +/- 10%) range
of each other. Adding this constraint results in a graph containing
multiple networks, each unconnected with the others. This would tend
to reduce the aggregate number of edges quite significantly.
Presumably I would then attack each of these self-contained networks
and attempt to extract fairly optimal bet groupings from them -
issues
of wager size having been dealt with at one fell swoop by virtue of
fact that each network only contains wagers of acceptably similar
size.

Definitely. Let the stake size split the problem up for you as much as
possible (I wouldn't even use a +/-10% range). If you are playing
with much-worse-than-linear algorithms, grab any chance you can to
divide the problem up (/especially/ when, as here, it's free).

-- chris
.

Relevant Pages

  • Re: Standard graph API?
    ... isomorphism graph library. ... It's pretty uniformly agreed that there is no standard graph ... the algorithm can't be specialized for the graph at ... My thought is to use some sort of templating system. ...
    (comp.lang.python)
  • Difference between two systems of DAGs
    ... I am looking for a graph algorithm, ... carry no label or other information except direction. ... edit operations are to change the label of a vertex or the ...
    (comp.theory)
  • Re: Vertex Cover implementation
    ... i code this simple greedy algorithm for the vertex cover: ... As you are constructing your graph you can update the vertex ... each edge appears on two adjacency lists. ... reason to use a priority queue for your algorithm. ...
    (comp.theory)
  • Re: Pathfinding in community
    ... > Each member is able to add his own contacts at the community. ... Dijkstra's algorithm is simply a refined breadth first search. ... In your case all the edges on the graph have the same weight, ... I would suggest loading this data into an array of arrays. ...
    (comp.lang.php)
  • Re: Total Common Numbers
    ... These are the exact same results that I have for 16 numbers. ... So, I am suggesting, that until we get the algorithm right, that ... verify that the algorithm is correct, ... lets assume that the POOL is 9 numbers from which 6 ...
    (microsoft.public.vb.general.discussion)