Are there python tools for addressing problems like assignment? At this point,
I don't fully understand my problem, but I believe it is a mixture of discrete assignment together with some continuous variables. My son suggests coding it by hand using some kind of simple hill climbing, but maybe I could leverage existing code for this? _______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user |
On Sun, Mar 31, 2013 at 12:59 PM, Neal Becker <[hidden email]> wrote:
> Are there python tools for addressing problems like assignment? At this point, > I don't fully understand my problem, but I believe it is a mixture of discrete > assignment together with some continuous variables. My son suggests coding it > by hand using some kind of simple hill climbing, but maybe I could leverage > existing code for this? There are some tools for simple linear assignment. https://pypi.python.org/pypi/munkres/ https://pypi.python.org/pypi/hungarian/ https://pypi.python.org/pypi/pyLAPJV/ None of them will help if you need to do continuous optimization as well. You may be able to get a satisficing answer by alternating linear assignment and continuous optimization, but I'm pretty sure there are no algorithmic guarantees with that approach. You may be able to cast your problem as a mixed integer programming problem. Check out the tools provided by Coopr and COIN-OR: https://software.sandia.gov/trac/coopr http://www.coin-or.org/ -- Robert Kern _______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user |
In reply to this post by Neal Becker
Hi,
On Sun, Mar 31, 2013 at 2:59 PM, Neal Becker <[hidden email]> wrote: Are there python tools for addressing problems like assignment? At this point, FWIW, Ihave implemented a pure python assignment solver few years back, based on quite comprehensive book "Assignment Problems" by Rainer Burkard, Mauro Dell'Amico, and Silvano Martello (ISBN: 978-0-898716-63-4), http://www.assignmentproblems.com/
I can mail the code (less than 100 lines) to you, but the code is slightly awkward, since it follows very closely the algorithm described in the book (so you might need to have access for it).
BTW, what is typical size of your cost matrix you are aiming to handle? Regards, -eat
_______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user |
In reply to this post by Neal Becker
Neal Becker <ndbecker2 <at> gmail.com> writes:
> Are there python tools for addressing problems like assignment? At this point, > I don't fully understand my problem, but I believe it is a mixture of discrete > assignment together with some continuous variables. My son suggests coding it > by hand using some kind of simple hill climbing, but maybe I could leverage > existing code for this? Neal, http://code.google.com/p/python-zibopt does mixed integer programming, i.e. linear prog + some integer constraints -- could that help ? (I like its little language for separating a readable problem description from solvers, number-crunching. Is there a general-purpose framework for such, "general-purpose" meaning > 1 user ? Cf. wikipedia AMPL and APMonitor.) cheers -- denis _______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user |
On Tue, Apr 2, 2013 at 11:22 AM, denis <[hidden email]> wrote:
> Neal Becker <ndbecker2 <at> gmail.com> writes: > >> Are there python tools for addressing problems like assignment? At this point, >> I don't fully understand my problem, but I believe it is a mixture of discrete >> assignment together with some continuous variables. My son suggests coding it >> by hand using some kind of simple hill climbing, but maybe I could leverage >> existing code for this? > > Neal, > http://code.google.com/p/python-zibopt does mixed integer programming, > i.e. linear prog + some integer constraints -- > could that help ? Off-topic, but what a license mess that package (python-zibopt) has -- it's a GPLed wrapper for non-free code, which I guess means that it's simply not legal to redistribute it at all? -n _______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user |
On Tue, Apr 2, 2013 at 11:42 AM, Nathaniel Smith <[hidden email]> wrote:
> On Tue, Apr 2, 2013 at 11:22 AM, denis <[hidden email]> wrote: >> Neal Becker <ndbecker2 <at> gmail.com> writes: >> >>> Are there python tools for addressing problems like assignment? At this point, >>> I don't fully understand my problem, but I believe it is a mixture of discrete >>> assignment together with some continuous variables. My son suggests coding it >>> by hand using some kind of simple hill climbing, but maybe I could leverage >>> existing code for this? >> >> Neal, >> http://code.google.com/p/python-zibopt does mixed integer programming, >> i.e. linear prog + some integer constraints -- >> could that help ? > > Off-topic, but what a license mess that package (python-zibopt) has -- > it's a GPLed wrapper for non-free code, which I guess means that it's > simply not legal to redistribute it at all? Pretty much. -- Robert Kern _______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user |
Free forum by Nabble | Edit this page |