The stupid question is the question not asked | |
PerlMonks |
Re: Challenge: Letter Powerby sk (Curate) |
on Oct 12, 2005 at 07:23 UTC ( [id://499402]=note: print w/replies, xml ) | Need Help?? |
Tanktalus, Just by looking at the structure of the problem, it appears to be NP-Complete. It has some similarities to MDKP (multi-dimensional 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 (mixed-integer non linear prog solvers).
Obviously as you can see the objective is Non-linear 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 non-linear search designed for quad-objectives. 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
|
|