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

In summary, the conversation discusses a puzzle where 4 three-letter words need to be chosen from a list of 8 words to maximize a score based on the position of the third letter in the alphabet. The first and second letters of the chosen words must also meet a certain requirement. The conversation suggests using variables to represent each word and determining the objective value and if the requirement is met based on those variables.
  • #1
sheldor
2
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
  • #2
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
 
  • #3
Thanks Ray. I will use your suggestions as a starting point.
 

1. What is Integer Program Formulation?

Integer Program Formulation is a mathematical optimization technique used to solve problems with integer variables. It involves formulating a mathematical model with constraints and an objective function, and then using algorithms to find the best possible solution within a set of integer values.

2. What types of problems can be solved using Integer Program Formulation?

Integer Program Formulation is used to solve problems in various fields such as engineering, economics, and logistics. Some common problems include resource allocation, production planning, and scheduling.

3. How is Integer Program Formulation different from Linear Programming?

Integer Program Formulation is a more general form of Linear Programming, where the decision variables are restricted to integer values. This makes it more suitable for solving real-world problems that involve discrete decision-making.

4. What are the main steps involved in Integer Program Formulation?

The main steps in Integer Program Formulation include formulating the problem, identifying the decision variables and their constraints, defining the objective function, and then solving the problem using algorithms such as branch and bound or cutting plane methods.

5. What are the limitations of Integer Program Formulation?

Integer Program Formulation can become computationally expensive for large problems, as the number of possible integer combinations increases exponentially. Additionally, it may not always guarantee finding the optimal solution, and may require multiple iterations to reach a feasible solution.

Similar threads

Programs How good is this applied math program?
    • STEM Academic Advising
Replies
13
Views
2K
Challenge Math Challenge - December 2018
    • Math Proof Training and Practice
2
Replies
67
Views
10K

Hot Threads

Recent Insights

Back
Top