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?
On Sun, Mar 31, 2013 at 12:59 PM, Neal Becker <ndbecker2@gmail.com> 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
Hi, On Sun, Mar 31, 2013 at 2:59 PM, Neal Becker <ndbecker2@gmail.com> 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?
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 SciPy-User@scipy.org http://mail.scipy.org/mailman/listinfo/scipy-user
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
On Tue, Apr 2, 2013 at 11:22 AM, denis <denis-bz-py@t-online.de> 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
On Tue, Apr 2, 2013 at 11:42 AM, Nathaniel Smith <njs@pobox.com> wrote:
On Tue, Apr 2, 2013 at 11:22 AM, denis <denis-bz-py@t-online.de> 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
participants (5)
-
denis -
eat -
Nathaniel Smith -
Neal Becker -
Robert Kern