P is for Practical  
PerlMonks 
Re: Challenge: Letter Powerby sk (Curate) 
on Oct 12, 2005 at 07:23 UTC ( #499402=note: print w/ replies, xml )  Need Help?? 
Tanktalus, Just by looking at the structure of the problem, it appears to be NPComplete. It has some similarities to MDKP (multidimensional knapsacks) but here the capacity is not present but the profit values are multidimensional and they are related to other objects in the bag. An exact solution will be out of the picture when the data becomes large and i am sure your wife would appreciate some kind of approximation if it can be done in couple of mins rather than the best solution which might take days!!! Here is my Mathematical formulation and at this point I am not aware of any MINLP (mixedinteger non linear prog solvers).
Obviously as you can see the objective is Nonlinear and regular knapsack/LP approaches will not work. However the fuction appears to be quadartic and you might be able to get some good results by "relaxing" the binary assumption on the X[i,j]'s and use a nonlinear search designed for quadobjectives. Here a simple heuristic that i can think of and can be improved a lot  This is just written top of my head without thinking about convergence. If i ever get to implement this i shall post the code. Hope someone can build on what i had in mind very interesting problem! cheers SK
In Section
Seekers of Perl Wisdom

