[SciPy-User] "Order of items" optimization

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

[SciPy-User] "Order of items" optimization

Andrea Gavana
Hello List,

    I am sure the problem I am trying to solve is fairly known but my English/Google skills are failing me today. 

The issue I am facing is to find the "best" (or "optimal") ordering of some items (and the order is important). These items can only be taken at most once - no repetition, although an item can also be deemed unimportant and not taken at all. So basically it would be a 0-1 coefficient for each item, but the order in which these items are taken is fundamental.

I don't have big issues in writing the objective function for this kind of problem, but I am unclear about the solution method: I have looked at the Knapsack problem and bin packing problem, but I am not sure they completely apply to my situation.

Any pointer, suggestion (and maybe if you have a link with some Python code somewhere) would be very appreciated :-) .

Thank you in advance for your help :-) .

Andrea.

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

Re: "Order of items" optimization

Daπid


On 9 Nov 2015 08:23, "Andrea Gavana" <[hidden email]> wrote:
> The issue I am facing is to find the "best" (or "optimal") ordering of some items (and the order is important). These items can only be taken at most once - no repetition, although an item can also be deemed unimportant and not taken at all. So basically it would be a 0-1 coefficient for each item, but the order in which these items are taken is fundamental.

What you are doing is some variation of the travelling salesman problem. It is a very standard problem in computer science.


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

Re: "Order of items" optimization

Andrew Nelson
You can create all the permutations by using the itertools.permutations generator. You could visit all the permutations in turn and calculate the objective function, selecting the best one. However, this is a brute force approach and its run time would depend on how many items you needed to look at.

On 9 November 2015 at 22:12, Daπid <[hidden email]> wrote:


On 9 Nov 2015 08:23, "Andrea Gavana" <[hidden email]> wrote:
> The issue I am facing is to find the "best" (or "optimal") ordering of some items (and the order is important). These items can only be taken at most once - no repetition, although an item can also be deemed unimportant and not taken at all. So basically it would be a 0-1 coefficient for each item, but the order in which these items are taken is fundamental.

What you are doing is some variation of the travelling salesman problem. It is a very standard problem in computer science.


_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.scipy.org/mailman/listinfo/scipy-user




--
_____________________________________
Dr. Andrew Nelson


_____________________________________

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

Re: "Order of items" optimization

Andrea Gavana
Hi,

On Tuesday, 10 November 2015, Andrew Nelson <[hidden email]> wrote:
You can create all the permutations by using the itertools.permutations generator. You could visit all the permutations in turn and calculate the objective function, selecting the best one. However, this is a brute force approach and its run time would depend on how many items you needed to look at.

On 9 November 2015 at 22:12, Daπid <<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;davidmenhur@gmail.com&#39;);" target="_blank">davidmenhur@...> wrote:


On 9 Nov 2015 08:23, "Andrea Gavana" <<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;andrea.gavana@gmail.com&#39;);" target="_blank">andrea.gavana@...> wrote:
> The issue I am facing is to find the "best" (or "optimal") ordering of some items (and the order is important). These items can only be taken at most once - no repetition, although an item can also be deemed unimportant and not taken at all. So basically it would be a 0-1 coefficient for each item, but the order in which these items are taken is fundamental.

What you are doing is some variation of the travelling salesman problem. It is a very standard problem in computer science.


I thought about that, the only problem is that I don't have an initial "city", i.e., all the events can be the first point. That would mean solving a TSP problem for each event as starting point - a few optimizations...

Generating all the permutations is not feasible either - I have 118 events to permute, and that gives an enormous number of possible permutations...

Thank you again for providing your suggestions!

Andrea.

 

_______________________________________________
SciPy-User mailing list
<a href="javascript:_e(%7B%7D,&#39;cvml&#39;,&#39;SciPy-User@scipy.org&#39;);" target="_blank">SciPy-User@...
https://mail.scipy.org/mailman/listinfo/scipy-user




--
_____________________________________
Dr. Andrew Nelson


_____________________________________


--


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

Re: "Order of items" optimization

Daπid
On 10 November 2015 at 07:07, Andrea Gavana <[hidden email]> wrote:

I thought about that, the only problem is that I don't have an initial "city", i.e., all the events can be the first point. That would mean solving a TSP problem for each event as starting point - a few optimizations...

Your starting point can be a "virtual" city that is equidistant to all the others. This distance just has to be large enough so you don't take that path back.



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

Re: "Order of items" optimization

Thiago Franco de Moraes

On Tue, Nov 10, 2015 at 7:09 AM Daπid <[hidden email]> wrote:
On 10 November 2015 at 07:07, Andrea Gavana <[hidden email]> wrote:

I thought about that, the only problem is that I don't have an initial "city", i.e., all the events can be the first point. That would mean solving a TSP problem for each event as starting point - a few optimizations...

Your starting point can be a "virtual" city that is equidistant to all the others. This distance just has to be large enough so you don't take that path back.



You could try to generate a minimun spanning tree since MST is an aproximation to the traveling salesman problem [1]

[1] - https://www.ics.uci.edu/~eppstein/161/960206.html
 

_______________________________________________
SciPy-User mailing list
[hidden email]
https://mail.scipy.org/mailman/listinfo/scipy-user