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.
On 9 Nov 2015 08:23, "Andrea Gavana" <andrea.gavana@gmail.com> 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.
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 <davidmenhur@gmail.com> wrote:
On 9 Nov 2015 08:23, "Andrea Gavana" <andrea.gavana@gmail.com> 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 SciPy-User@scipy.org https://mail.scipy.org/mailman/listinfo/scipy-user
-- _____________________________________ Dr. Andrew Nelson _____________________________________
Hi, On Tuesday, 10 November 2015, Andrew Nelson <andyfaff@gmail.com> 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 <davidmenhur@gmail.com <javascript:_e(%7B%7D,'cvml','davidmenhur@gmail.com');>> wrote:
On 9 Nov 2015 08:23, "Andrea Gavana" <andrea.gavana@gmail.com <javascript:_e(%7B%7D,'cvml','andrea.gavana@gmail.com');>> 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 SciPy-User@scipy.org <javascript:_e(%7B%7D,'cvml','SciPy-User@scipy.org');> https://mail.scipy.org/mailman/listinfo/scipy-user
-- _____________________________________ Dr. Andrew Nelson
_____________________________________
--
On 10 November 2015 at 07:07, Andrea Gavana <andrea.gavana@gmail.com> 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.
On Tue, Nov 10, 2015 at 7:09 AM Daπid <davidmenhur@gmail.com> wrote:
On 10 November 2015 at 07:07, Andrea Gavana <andrea.gavana@gmail.com> 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
participants (4)
-
Andrea Gavana -
Andrew Nelson -
Daπid -
Thiago Franco Moraes