[SciPy-User] assignment optimization problem

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

[SciPy-User] assignment optimization problem

Neal Becker
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
Reply | Threaded
Open this post in threaded view
|

Re: assignment optimization problem

Robert Kern-2
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
Reply | Threaded
Open this post in threaded view
|

Re: assignment optimization problem

eat-3
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,
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
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user


_______________________________________________
SciPy-User mailing list
[hidden email]
http://mail.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|

Re: assignment optimization problem

Denis-B
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
Reply | Threaded
Open this post in threaded view
|

Re: assignment optimization problem

Nathaniel Smith
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
Reply | Threaded
Open this post in threaded view
|

Re: assignment optimization problem

Robert Kern-2
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