[SciPy-User] "Order of items" optimization

[Andrea Gavana]

Hi,

On Tuesday, 10 November 2015, Andrew Nelson <andyfaff at 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 at gmail.com
> <javascript:_e(%7B%7D,'cvml','davidmenhur at gmail.com');>> wrote:
>
>>
>> On 9 Nov 2015 08:23, "Andrea Gavana" <andrea.gavana at gmail.com
>> <javascript:_e(%7B%7D,'cvml','andrea.gavana at 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 at scipy.org
>> <javascript:_e(%7B%7D,'cvml','SciPy-User at scipy.org');>
>> https://mail.scipy.org/mailman/listinfo/scipy-user
>>
>>
>
>
> --
> _____________________________________
> Dr. Andrew Nelson
>
>
> _____________________________________
>


--
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.scipy.org/pipermail/scipy-user/attachments/20151110/c0ea17c7/attachment.html>