in reply to Efficient Assignment of Many People To Many Locations?

This method does not guarantee that you will get the optimal solution. You may get a good solution but it can be at a local minimum.

Also I think that if the set of salesmen and locations is sufficiently large, there is such a large number of solutions to try that your "swap, test and keep if better" method will do no better than picking a truly random combination, unless you can prove that once you have a better result after a swap all following solutions in the tree underneath this swap are always better than all other possibilities without this swap (in other words you avoid the "local minimum" trap).

CountZero

"If you have four groups working on a compiler, you'll get a 4-pass compiler." - Conway's Law

  • Comment on Re: Efficient Assignment of Many People To Many Locations?

Replies are listed 'Best First'.
Re^2: Efficient Assignment of Many People To Many Locations?
by ff (Hermit) on Feb 25, 2005 at 16:02 UTC
    To paraphrase my comment in a recent node, Re: Student Class Section Lottery, if you generate about 30 random solutions and score them with some kind of criteria, the top scorer has a high likelihood of being close to the optimal solution.

    (I'm happy to share this as one of the most useful/interesting things I learned in all my college days, from an Operations Research class some 20+ years ago. :-)

[reply]
      That is a very interesting comment. If you can live with "good enough" rather than "maximum" it is indeed worth trying.

      Is the number "30" somehow related to the number of elements in the set of all possibilities or is it a value which is valid over a large spread of sets?

      Perhaps someone more versed in statistics than me can look into the following: given a problem which has 1,000,000 solutions, generate 30 random numbers between 1 and 1,000,000. If the score of the solution is equal to the value chosen, what are the chances that one of these random values is within 10% of the maximum value (1,000,000)?

      CountZero

      "If you have four groups working on a compiler, you'll get a 4-pass compiler." - Conway's Law

[reply]
        The cool part is that 30 is valid over an arbitrarily large spread of sets. Yes, we need a statistician to show this (or I have to hunt down some 20-year-old notebooks), and of course you could generate more than 30 solutions, but there's a knee-of-a-curve thing about "30": basically it's hard to draw 30 "solutions" from a pot full of randomly arranged solutions and not have "one" come from each of the extreme edges of possible solutions, i.e. from better than 90th percentile and worse than 10th. That's what makes this the Law of Large Numbers--it is irrelevant how many possible solutions there really are.
[reply]

        There is a 10% chance at any iteration of choosing a value in the top 10% (duh) when you are just selecting linearly numbers on a number line. So, the probability of choosing a number in the top 10% over 30 iterations is simply:

        printf("%.0f%%",100*(1-.9**30));

        [download]

        I don't see the magic of the number 30 here-- the cost/benefit of iterations to improved results appears to be linear to me. You get results that are twice as good by doing twice as many iterations.

        It's easy to conceive of a non-linear results set where you are likely to come nowhere near the maximum value by picking some smallish number of random iterations.

        Try, for instance, finding the maximum value of 1/10**N where N is an integer between 0 and 1,000,000. What is the percent error between your randomly selected max over thirty iterations and the actual max value? My money says it is 100%. Of course, evaluating the linear variance of an exponential function may be a bit of a stretch...

[reply]
[d/l]

In Section Seekers of Perl Wisdom