Not All Optimization Models Need an Objective: A Midsummer Day Puzzle

Published on June 24, 2025 by Brian Schaefer

When building an optimization model, the first question is usually: “What are we trying to optimize?” Lower costs? Faster delivery? A more resilient network? But not all models need an objective. Sometimes, the goal is simply to answer: “Is any valid solution possible?” In business, these are known as feasibility-only models. They’re used in situations where all feasible solutions are considered equally good—or when there’s no time to find the best one. For example:

  • In live vehicle routing, the software might need to return any valid path immediately, without exploring for optimality.
  • In compliance modeling, a company might only need to verify that a staffing or scheduling plan meets all rules.
  • In scheduling, when the manager wants to override a part of the schedule for any reason, they can be alerted if there’s a problem with their manual adjustments.

In these cases, removing the objective can actually help the solver move faster. Without needing to search for the best solution, it’s free to stop as soon as it finds one that works. Outside of business, this concept is especially common in puzzle solving, where the only requirement is that the solution satisfies all constraints. There’s no need to optimize anything—just find what fits.

Here are a few classic examples:

Soduku

Fill a 9×9 grid so each digit 1–9 appears exactly once per row, column, and 3×3 block. There’s often only one valid solution—and any objective would be artificial.

Magic squares

Arrange numbers in an 𝑛 × 𝑛 grid so all rows, columns, and diagonals sum to the same value. The goal is to find even one such arrangement.

N-Queens Problem

Place 𝑛 queens on an 𝑛 × 𝑛 chessboard so that none attack each other. A classic feasibility challenge.

A Shakespearean Crossword for Midsummer Day

To celebrate Midsummer Day (June 24), we built a themed crossword using a mixed-integer programming (MIP) model—with no objective function at all. Inspired by A Midsummer Night’s Dream, we used a word list sourced entirely from the Project Gutenberg eBook of The Complete Works of William Shakespeare. No dictionaries. No modern words. Just pure Bard.

How the puzzle model is formulated

Inputs

  1. Puzzle layout
    The puzzle layout is encoded using the structure shown in the image. The across word references assigns each cell to one of the 16 across words (1-16) and the down word references data assigns each cell to one of the 16 down words (17-32). Zero means the cell is blacked out. The letter positions are also encoded for the input.
  2. List of words
    From the Shakespeare corpus, we extracted 8,834 unique words ranging from 3 to 6 letters. Each word was converted into numeric form (e.g., BACK → [2, 1, 3, 11]).

Decision variables

The model uses binary variables to represent whether a word is placed in a given position. Only valid placements are modeled—meaning the solver never needs to reject words that don’t fit.

            POSSIBLE   SLOTS IN       TOTAL
WORD LENGTH    WORDS     PUZZLE   VARIABLES
3 letters        512   x     12   =   6,144
4 letters      1,716   x      4   =   6,868
5 letters      2,777   x     12   =  33,324
6 letters      3,828   x      4   =  15,312
Total                                61,648

Constraints

The model only needs a few core rules:

  1. Each slot must be filled with exactly one word.
  2. Each crossing must have matching letters at the intersection.

Because the decision variables were prefiltered to only valid placements, we avoided the need for constraints to rule out “bad fits”—reducing model size and improving solve time.

We also added a few constraints to force some special words to go into the puzzle where we wanted them.

Objective Function

There is none. Formally, the model’s objective is to “minimize 0.” This tells the solver: return the first feasible solution you find. Since every valid puzzle is equally good, there’s no reason to search further. Want to generate another puzzle using the same structure and word list? Just shuffle the word list before solving. The solver will follow a different path and likely produce a different crossword. Or provide a different random seed to the solver.

Try the Puzzle

Below is the crossword grid and list of clues, each steeped in Shakespearean language. It’s a logic puzzle, a literary homage, and an example of how mathematical optimization doesn’t always need a goal—just structure and creativity.

Across

1. Used to be
4. Prize that might be won in a duel of wit
9. “Teaching the sheets a whiter __ than white”
10. Rosalind and Duke Senior’s woodland fate
11. A structured praise, like a sonnet to a summer’s day
12. Knightly posture, ready for joust or jest
13. A fool’s word, or a love unadorned
15. Greek mountain piled on Pelion in A Midsummer Night’s Dream reference
16. “A __ by any other name…”
20. Latin for holy, as in Sancta Maria from period prayers
22. “__, fair sun, and kill the envious moon,”
25. “Lend me your __”
26. A new arrival, or “late __ to the masquerade”
27. “Youth’s a stuff will not endure”
28. Being in a merry state
29. Common name, like Poins’ friend in Henry IV

Down

1. Archaic pronoun meaning “whoever” or “whosoever”
2. Latin 2nd-person verb for hearing
3. “__, madam! Nay, it is; I know not __.”
4. Time to feast
5. Not part of the court or castle
6. Latin gods invoked in Roman tragedies
7. “__ the world’s a stage…”
8. To allow to remain
14. “That old Time as he __ by takes with him.”
17. “Boundless as the sea, my love as deep”
18. Place where illusions become truths in Shakespeare
19. “I __ her language, lived in her eye, O coz,”
21. The nest of an eagle—or a spirit’s high perch in The Tempest
22. A unit of drama or fairy mischief
23. French word for king, often found in histories
24. Mischievous sprite like Puck

Solution

Link to view the solution

Happy Midsummer! May your solving be merry and your iambs pentametered.