Perl-Sensitive Sunglasses PerlMonks

Re: Challenge: Letter Power

by sk (Curate)
 on Oct 12, 2005 at 07:23 UTC ( #499402=note: print w/replies, xml ) Need Help??

in reply to Challenge: Letter Power

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).

```
Let i represent the index (num in your example) and
j represent the actual word
c represent all the letters ('A'..'Z')

Let X[i,j] = { 1 if word (i,j) was chosen, 0 otherwise}

The value of each word can be broken into characters/letters

For all (i, j) -
# you get the value only if the word is chosen
V[i,j,c] = number of c's in the word (i,j) * X[i,j]

For all c
Let Value(c) = (sum {over all i,j} V[i,j,c])*((sum {over all i,j} V[
+i,j,c])+1)/2

Optimization problem
===================
Max sum {over c} Value(c)

# You can choose only one word from each index (num)
subject to: sum {over all j} X[i,j] = 1 for all i.
subject to: x[i,j] element of (0,1) for all i, j.

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 -

```1. For each index/word pair store the number of repeats of each charac
+ter.
2. INIT: Start with the index/word pair that has the highest value by
+itself (i.e. assuming the value of other index/words are zero).
3. Choose the next index/word pair that increases the value the most (
+let's say your init value for 1/alabama, then you move to index = 2 a
+nd look for the best next increase.)
4. Repeat step-3 until you exhaust all indices.
5. Now you have a local optimum based on your starting point.
6. EXCHANGE: Store the current objective, Go back to index = 1 and pic
+k the second best word in index = 1. Now check if you could improve t
+he previous solution by exchanging index = 2 with something new etc.
7. You can repeat this exercise for certain number of iterations and t
+hen you stop with the best solution found thus far.
NOTE that you can also use randomized approach to randomly pick an ele
+ment to exchange and try to improve the solution.

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

Create A New User
Node Status?
node history
Node Type: note [id://499402]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (6)
As of 2017-08-18 23:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (310 votes). Check out past polls.

Notices?