[SciPy-User] Non-science BPP problem (John Obelenus)

Thu Feb 6 15:34:37 EST 2014

Ah, OK, what you have is a Constrained, Integer Linear 'Programming'
problem (Programming is in quotes because, in this context, due to
historical misfortune, it means something quite different from what it now
typically means).  Unfortunately, this is a rather advanced area of
mathematics (often not taught until the graduate level), at the
intersection of combinatorics and optimization, but at least now you have
the terms you can use to conduct searches.  However, there may be people on
this list who have already "solved" (i.e., written code to solve) this
problem, and they may be willing to share and/or provide guidance.

One concrete suggestion: one method that I often find useful when
approaching combinatorics problems is to study the simplest non-trivial
case--e.g., say two boys, two girls, with the types of rankings you
indicate--and figure out the solution by hand.  Then complicate the problem
incrementally until, hopefully, the pattern inherent in the solution (or
method of solution) becomes evident.  In other words, work inductively,
rather than deductively.  (FWIW: integer programming problems often require
iterative, rather than formulaic, solutions, so figuring out how to solve
the problem by hand may be no different than what you would have to
implement in code anyway.)

Good luck!

DG

Date: Thu, 6 Feb 2014 14:33:02 -0500
> From: John Obelenus <jobelenus at gmail.com>
> Subject: Re: [SciPy-User] Non-science BPP problem
> To: SciPy Users List <scipy-user at scipy.org>
> Message-ID:
>         <
> CALV8KbdBxB0Ux0+FoH+udbYKGT88OD3eo3eL3Gc26zY-yY9u_Q at mail.gmail.com>
> Content-Type: text/plain; charset="utf-8"
>
> Certainly! Thank you David for showing some interest. This is specifically
> for a player ranking/team creation system, but its certainly a BPP, with
> some wrinkles.
>
> I have N teams (the bins). And I have M players. Each player has a ranking.
> I have both a ranking # (e.g. 1,2,3,...) and a relative ranking (e.g. 35
> points = #1 rank, and 29 points = #2 rank, etc). Assigning teams according
> to decreasing absolute rank so that teams are even split by absolute
> ranking is pretty trivial (and thus "balanced" to an acceptable definition
> of "balanced").
>
> What I am trying to solve now is pairing, e.g. players sign up to play with
> their friends. So player at Rank A is packed into a group with player Rank
> J. And the aggregate ranking of all the teams/groups ought to accommodate
> these pairings such that the packages are "balanced" as evenly as they can
> be.
>
> So the "Volume" parameter is what I don't know how to specify for the BPP
> problem here.
>
> And a further wrinkle is that males and females are assigned to teams
> differently (e.g. so each team has an approximately equal# of males and
> females), but ranked together (e.g. a female may have a higher rank than a
> male, and that matters) and will certainly be paired together to be on the
> same team/group. And I am very sure that complicates things :)
>
>
> On Thu, Feb 6, 2014 at 2:24 PM, David Goldsmith <d.l.goldsmith at gmail.com
> >wrote:
>
> > Hi, John.  Please describe your specific problem in somewhat greater
> > detail: "Bin Packing Problem" could mean different things to different
> > scientists, depending on their area of expertise.  Thanks!
> >
> > DG
> >
> > Date: Thu, 6 Feb 2014 11:57:59 -0500
> >
> >> From: John Obelenus <jobelenus at gmail.com>
> >> Subject: [SciPy-User] Non-science BPP problem
> >> To: scipy-user at scipy.org
> >> Message-ID:
> >>         <CALV8Kbc-WpYX=
> >> X-Csv3vdiSvR44dEFN-2KEEOy1Gy9ucfdPAcw at mail.gmail.com>
> >> Content-Type: text/plain; charset="utf-8"
> >>
> >> [Noob Trigger Warning]
> >>
> >> Hey everyone, I'm your standard python programmer that realizes I have a
> >> variation of a Bin Packing Problem on my hands. I turn to you for your
> >> help
> >> in understanding how to use the wonders of your math packages to solve
> the
> >> BPP. I saw that `openopt` has a simple and extended BPP solver, but I am
> >> open for whatever python package is going to get the job done.
> >>
> >> I realize this isn't your standard scipy user mailing, as I'm looking
> for
> >> help just getting started on how to address/specify my problem so that
> the
> >> package can solve it. I took a shot at the archives here but it seems
> >> everyone else here is far past my level. If anyone has good introductory
> >> resources that can get me from where I am now (understanding that I
> have a
> >> Bin Packing Problem and generally how that works) to solving it
> >> (specifically, how to use the packages and implement my data to the
> solver
> >> to get a coherent answer) that would be greatly appreciated.
> >>
> >> Thanks for your time
> >> -A Humble Non-Science Programmer
> >> -------------- next part --------------
> >> An HTML attachment was scrubbed...
> >> URL:
> >>
> http://mail.scipy.org/pipermail/scipy-user/attachments/20140206/5fe4f918/attachment-0001.html
> >>
> >>
> >
> > _______________________________________________
> > SciPy-User mailing list
> > SciPy-User at scipy.org
> > http://mail.scipy.org/mailman/listinfo/scipy-user
> >
> >
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL:
> http://mail.scipy.org/pipermail/scipy-user/attachments/20140206/29ddda95/attachment.html
>
> ------------------------------
>
> _______________________________________________
> SciPy-User mailing list
> SciPy-User at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>
>
> End of SciPy-User Digest, Vol 126, Issue 10
> *******************************************
>

-- 
>From "A Letter From The Future" in "Peak Everything" by Richard Heinberg:

"By the time I was an older teenager, a certain...attitude was developing
among the young people...a feeling of utter contempt for anyone over a
certain age--maybe 30 or 40.  The adults had consumed so many resources,
and now there were none left for their own children...when those adults
were younger, they [were] just doing what everybody else was doing...they
figured it was normal to cut down ancient forests for...phone books, pump
every last gallon of oil to power their SUV's...[but] for...my generation
all that was just a dim memory...We [grew up] living in darkness, with
shortages of food and water, with riots in the streets, with people begging
on street corners...for us, the adults were the enemy."

Want to *really* understand what's *really* going on?  Read "Peak
Everything."
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.scipy.org/pipermail/scipy-user/attachments/20140206/64b0b940/attachment.html>