What is the Integer Program Formulation for Maximizing Scores in a Word Puzzle?

[sheldor]

Homework Statement

Consider the following puzzle. You are to choose 4 three-letter "words" from the following list:

ECB EFH BEJ GGE HIJ CDE GEG CBJ

For each word, you earn a score equal to the position that the word's third letter appears in the alphabet. For example, ECB earns a score of "2", EFH earns a score of "8", and so on. Your goal is to choose the four words that maximize your total score, subject to the following constraint. The sum of the positions in the alphabet for the first letter of each word chosen must be at least as large as the sum of the positions in the alphabet for the second letter of each word chosen

Formulate an IP only for this problem.

Homework Equations

The Attempt at a Solution

No solution needed. Any help with choosing variables and setting an objective function would be appreciated.

 

[Ray Vickson]

You have 8 words, Wi, i=1,2,...,8. For each Wi you need do decide whether or not to choose it. How can you write this in terms of variables of some type? If somebody hands you values for all your variables, how can you determine whether their suggestion picks 4 words exactly? How can you calculate the objective value corresponding to their suggestion? How can you determine whether or not their suggestion satisfies the first-second letter requirement?

RGV

 

[sheldor]

Thanks Ray. I will use your suggestions as a starting point.