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

  • Thread starter Thread starter sheldor
  • Start date Start date
  • Tags Tags
    Integer Program
Click For Summary
SUMMARY

The discussion focuses on formulating an Integer Programming (IP) model to maximize scores from a word puzzle involving the selection of four three-letter words from a given list. Each word's score is determined by the position of its third letter in the alphabet, while a constraint requires that the sum of the positions of the first letters must be greater than or equal to the sum of the positions of the second letters. Participants seek guidance on defining variables, setting an objective function, and verifying the selection criteria for the words.

PREREQUISITES
  • Understanding of Integer Programming (IP) formulation
  • Familiarity with linear constraints and objective functions
  • Knowledge of alphabetic position scoring
  • Basic skills in mathematical optimization techniques
NEXT STEPS
  • Study Integer Programming formulations and examples
  • Learn about defining objective functions in optimization problems
  • Research methods for verifying constraints in mathematical models
  • Explore scoring systems based on character positions in the alphabet
USEFUL FOR

Students in operations research, mathematicians interested in optimization, and anyone involved in algorithm design for puzzle-solving or game theory.

sheldor
Messages
2
Reaction score
0

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.
 
Physics news on Phys.org
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
 
Thanks Ray. I will use your suggestions as a starting point.
 

Similar threads

Programs How good is this applied math program?
  • · Replies 13 ·
Replies
13
Views
4K
Challenge Math Challenge - December 2018
  • · Replies 67 ·
3
Replies
67
Views
16K