How to Set Up an Optimization Problem Like the 0/1 Knapsack

Question

I'd like some help in understanding and setting up (what may be) an optimization problem that has some similarities to the 0/1 knapsack problem. In this problem the items are a given number of words (analogous to knapsack items) that can go into the given fields of a crossword puzzle (analogous to a knapsack). A word can fit into a field if their lengths match. The constraints are, as usual, that the letters where any two fields intersect must be the same letter. The goal is to fill the fields with as many words as possible from the given set of words. In general, some fields may ultimately be left unfilled--eg, if there are no words remaining that meet all intersecting field constraints.

At first I thought this could be approached as an optimization problem like the 0/1 knapsack. The initial fields might be filled longest first (analogous to an efficient knapsack solution). But the progressive selection of words is not filling an undifferentiated space like a knapsack. Rather each next selected word must exactly fit into one of the remaining fields. I can't tell if this lends itself to an optimization algorithm, or requires falling back to brute search through all possibilities. What could be a good objective function to maximize? Maximizing the number of filled fields or the number of selected words is a possibility, but can this kind of optimization be used to kill a lot of nodes in the search tree like it does for the knapsack problem?

I can solve the standard knapsack problem with a branch & bound algorithm that relaxes the item weights when progressively filling, but not sure if something like this would work for this crossword problem.

PS: For those who haven't studied the 0/1 knapsack, here is a short video that (purports) to explain some of the key considerations https://www.youtube.com/watch?v=yV1d-b_NeK8

Edit: Here's an example problem, with the best solution (as suggested by A.Omidi):

Wordset = (squid sound swiss pique roses best suns weds psst nod ssw)

Fieldset = (1across 5across 6across 7across 8across 1down 2down 3down 4down 6down)

@PSST
@IOW
SQUID
SUNS@
WEDS@

Best solution found by brute force search through all possibe field/word pairs:

<FILL (6DOWN SSW) NIL 6.0 8 0.0
  ((FILLED 1ACROSS) (FILLED 1DOWN) (FILLED 2DOWN) (FILLED 3DOWN) (FILLED 6ACROSS) (FILLED 6DOWN) (FILLED 7ACROSS) (FILLED 8ACROSS)
   (REMAINING-FIELDS&WORDS-HT #<HASH-TABLE :TEST EQUAL :COUNT 2 {258ED8D1}>) (TEXT 1ACROSS "PSST") (TEXT 1DOWN "PIQUE")
   (TEXT 2DOWN "SOUND") (TEXT 3DOWN "SWISS") (TEXT 4DOWN "T?D") (TEXT 5ACROSS "IOW?") (TEXT 6ACROSS "SQUID") (TEXT 6DOWN "SSW")
   (TEXT 7ACROSS "SUNS") (TEXT 8ACROSS "WEDS") (USED-FIELD-IDS-HT #<HASH-TABLE :TEST EQ :COUNT 8 {258ED3E9}>))
  NIL>

My main question is whether choosing an appropriate objective function (eg, maximizing the number of words filled in) will actually prune the search tree. My intuition is that, contrary to knapsack pruning, it will not significantly prune the tree. (But I haven't programmed it; fair amount of work just to test.)

Answer 1

You can certainly model this as a binary integer program. The constraints are very straightforward, and either filling the maximum number of fields or (equivalently) maximizing the number of words used makes sense to me. Whether it would solve efficiently is an empirical question.

It could also be modeled as a constraint programming problem. The number of variables would be smaller. Where an IP model would use a binary variable $x_{i,j}$ to indicate whether word $i$ gets stuffed into field $j,$ a CP model might use an integer variable $y_j$ with domain $0,\dots,W$ (where $W$ is the number of words) to select the word that goes into field $j$ (with $y_j=0$ indicating the field is left empty). Alternatively, you might use a variable $z_i$ with domain $0,\dots,F$ ($F$ the number of fields) to indicate the field into which word $i$ gets stuffed (again using $z_i=0$ to indicate the word is unused). In fact, you might very well include both sets of variables, together with compatibility constraints (word $i$ going into field $j$ implies word $k$ cannot go into field $\ell$ because the fields intersect in what would be different letters for the two words). A CP approach avoids a bunch of matrix arithmetic and does domain reductions more directly (if I put word $i$ in field $j,$ then it cannot be used anywhere else and these other words no longer can be used in these intersecting fields).

In my very limited experience with CP, one drawback relative to IP models tends to be weaker objective bounding with CP. I'm not sure that would be a big issue with this particular problem.