A similar problem is addressed in Higher order Perl. (Chapter 1, page 35)

This does indeed sound like an optimization problem on the order of NP-Complete.

The standard NP-Complete routine I use (when lacking a problem or domain specific optimization) is a recursive solution that tries to cover all combinatorial possibilities, but will short circuit (prune the tree) in the case where the fitness function would never succeed from that point on.

The key functions I define are apply_move() (applies the move to a current state), fitness() (tests the current state) and next_moves() (gets the set of valid moves). The first time I generalized this function was in a game theory course. An assumption is that you want to have your fitness function give an ordered rating from 0..MAXVAL (0 means total failure, MAXVAL means the best you can get). And yes, the tool I use for this has been heavily tainted by lisp (scheme, actually).

sub find_solution {
  my ($state,
      $fitness_fcn,
      $nextmoves_fcn,
      $applymove_fcn,
     ) = @_;
  return () unless $fitness_fcn->($state);
  my @next_moves = $nextmoves_fcn->($state);
  return $state unless @next_moves;
  return map {
    find_solution($applymove_fcn->($state, $_),
                  $fitness_fcn,
                  $nextmoves_fcn,
                  $applymove_fcn,
                 );
  } grep {
    $fitness_fcn->($applymove_fcn->($state, $_);
  } @next_moves;
}
[download]

* Code is provided with no warranty, is written from memory, and has not been tested.

Depending on the complexity of $applymove_fcn, it may make sense to apply a ST to this as well, but for understanding the code, it is not necessary.

If you have a time constraint, you could even sort the results of each level to that you try the most fit (to that point) solutions first.

For your specific problem, the fitness test could rank the solutions as the inverse total deviation from the average or something similar (making a perfect solution 1/0 :-). The larger the fitness test result, the better the solution (for some definition of better). If you want to limit the overage or underage of any specific customer, you would rank the fitness of those solutions exceeding these limits as 0. Most of the tweaking for a faster method is then done in the fitness function. The faster you can prune a branch of the result tree, the faster you will find your solution.

But this is just one solution. If there is a domain or problem specific solution, that will, more than likely, give a faster solution or solutions.

The standard NP-Complete routine I use (when lacking a problem or domain specific optimization) is a recursive solution that tries to cover all combinatorial possibilities, but will short circuit (prune the tree) in the case where the fitness function would never succeed from that point on.

I have something similar with a variation of fitness() except that the function does all the heavy-lifting of driving the moves:

Re: How can I calculate the right combination of postage stamps? (combinatoric n Choose k with conditions)

Thanks for all the suggestions so far - I'm investigating them all.


I'm looking for an error of less than 0.001 from the actual average for all buckets (unless the bucket has < 3 or 4 allocations) and the timeframe is less than 3 seconds on a new linux blade.