Balancing Latin Rectangles with LLM-Generated Streamliners

In this section, we define the general notation and background related to balanced Latin rectangles. A Latin rectangle is an $k\times n$ grid where $k\le n$ and each cell contains a symbol from 1 to $n$, such that no symbol appears more than once within a row or within a column. Latin squares (or Magic squares) are Latin rectangles where $n=k$. Latin squares are widely known and have been studied for centuries.

Díaz et al. [2] introduced the notion of balance in Latin rectangles, minimizing which helps preclude spatial-correlation artifacts and ensures statistical fairness while devising experiments. A spatially balanced Latin rectangle (or simply balanced Latin rectangle) is a Latin rectangle where the total distance between any pair of symbols is the same. Formally, ${\text{dist}}_i(r,s)$ denotes the distance between symbols $r$ and $s$ in the $i$th row. Note that . The distance between two symbols is defined as $\text{dist}(r,s)={\sum }_{1\le i\le k}{\text{dist}}_i(r,s)$. A Latin rectangle is balanced iff $\text{dist}(r,s)$ is the same for every pair $1\le r,s\le n$. Letting ${\text{Z}}_{n,k}$ be $k(n+1)/3$, it is easy to see that in a balanced Latin rectangle, $\text{dist}(r,s)={\text{Z}}_{n,k}$ for every pair.

However, balanced Latin rectangles only exist when $n=k$ and $n\not\equiv 1(mod3)$ [2], which rules out several combinations of $n$ and $k$. Consequently, Díaz et al. [2] defined the imbalance of a Latin rectangle as a measure of how far it is from being balanced. The imbalance between a pair of symbols $r,s$ is defined as $𝕀(r,s)=|\text{dist}(r,s)-{\text{Z}}_{n,k}|$ and the imbalance of a Latin rectangle $L$ is defined as . In the BLR problem, we are given two integers $k\le n$, and the goal is to find a $k\times n$ Latin rectangle $L$ such that $𝕀(L)$ is minimized. Note that ${\text{Z}}_{n,k}$ is always a rational number of the form $p/3$ and if either $k$ or $n+1$ are divisible by 3, then ${\text{Z}}_{n,k}$ is an integer. The same holds for $𝕀(L)$; hence, we always denote the imbalance values as $\mathrm{x}.0$, $\mathrm{x}.3$ or $\mathrm{x}.6$, respectively, to represent $\mathrm{x}$, $\mathrm{x}+\frac{1}{3}$ or $\mathrm{x}+\frac{2}{3}$ where $\mathrm{x}\in \mathbb{Z}$.

Streamlining constraints or streamliners are constraints added to a constraint programming model in order to speed up the solving process by pruning the search space and guiding the solver towards more promising subspaces of the solution space. Streamliners have provided significant speedups across numerous problem domains [1, 2, 3, 4, 5, 7, 8, 11, 14].

By definition, they are not required to be sound, i.e., they need not preserve the set of feasible solutions and are allowed to remove some or even all of the solutions. Streamliners are a generalization of the following well-known constraints:

• $\mathrm{■}$

  implied or redundant constraints which do not alter the solution space,

• $\mathrm{■}$

  symmetry-breaking constraints which eliminate all but one solution from symmetric equivalence classes

• $\mathrm{■}$

  dominance-breaking constraints which eliminate potentially suboptimal solutions such that at least one of the optimal solution remains.

In our work, we use the term “streamliner” in a broader sense to refer to any constraint that can speed up the solving of a constraint programming model. Consequently, the streamliners that we present include but are not limited to the three types listed above.

Formerly, streamliners were generated manually for each problem which was labor-intensive and hard to scale, which motivated research into automating streamliner generation [12, 13, 15, 20]. Typically, these methods involved crafting combinations of atomic constraints which restrict the variable domains and testing them on a large pool of benchmark instances. This process was extremely resource-intensive, taking several days to come up with promising streamliners for a given problem.

Looking for a more scalable and efficient way to come up with high-quality streamliners, we turn our attention to Large Language Models or LLMs. LLMs are transformer architectures with billions of parameters that have been trained on large datasets and can produce human-like text and code. In recent times, LLMs have seen significant growth in innovation and use. This widespread use is a testament to the versatility and broad applicability of LLMs, such as, chatbots, translators, and coding assistants. Recent advancements have endowed LLMs with the power of reasoning and problem-solving which further enables them to manipulate mathematical expressions and assist in devising proofs. However, LLMs are not infallible and can produce incorrect yet believable output. As a result, independent verification is crucial to harness the power of LLMs.

In this work, we extend the StreamLLM approach developed by Voboril et al. [18]. In contrast to their work, we target optimization problems instead of decision problems, and we use more sophisticated procedures to traverse the space of solutions using the objective values as guidance. Please refer to Listing 1 for the MiniZinc model of the BLR problem that we use to test the performance of the different approaches and also provide to the LLM as context for generating streamlining constraints. Note that in the MiniZinc model: pos[row,symbol] denotes the position of a symbol in a row, rect[row,col] denotes the symbol at a specific cell of the Latin rectangle, dist[r,s] denotes $\text{dist}(r,s)$, and imbalances[r,s] denotes $𝕀(r,s)$.

We introduce a novel approach to improve the performance of optimization problems in constraint programming. Our approach is based on the automatic generation of streamliners by using LLMs. We use BLR as the target problem to test and demonstrate the performance of our approach. Our completely autonomous procedure prompts the LLM to suggest streamlining constraints for the supplied (unstreamlined) MiniZinc model of the BLR problem. The generated streamliners are tested on the input instance for a short time to evaluate their performance relatively quickly.

In each iteration, one of several LLMs and one of three possible prompts is randomly chosen. This capitalizes on the strengths of different LLMs and different prompts. The first prompt prompt_basic (shown in Figure 2) asks the LLM to analyze the MiniZinc code and generate five new, creative, and syntactically correct streamliners. The formulation of the prompt is very similar to the prompt used by Voboril et al. [18]. The second prompt prompt_combinations asks for five combinations of streamliners (each consisting of multiple constraints) instead of five individual streamliners. The third prompt prompt_description is an extension of the first prompt with a detailed description of the BLR problem. In the following sections, we present two different approaches to use the produced streamliners. In both approaches, syntactically incorrect streamliners are simply discarded. All hyperparameter values used in these approaches were fixed on the basis of some preliminary experiments.

Our incremental warmstart approach utilizes the warmstart annotation in MiniZinc. Warmstarting is a feature of certain solvers for optimization problems, where we can seed the solver’s search with an initial feasible solution. This can be useful to guide the solver to find better solutions quicker. In the context of the BLR problem, we warmstart the solver with the best solution obtained so far.

Our approach, as shown in Figure 3, starts with an initial training time $t=1$ minute, running the original encoding for that time and storing the solution $s$. Then, one of the LLMs is randomly chosen and asked to produce five new streamliners for the given problem. These streamliners are evaluated in parallel for $t$ minutes. For the evaluation, the currently best solution $s$ is used as warmstart. If a new solution $s^{\prime }$ is better than $s$, it replaces $s$ as the current best solution. If there is no new improved solution after 5 iterations, the training time $t$ is increased by 2 minutes. With a longer training time, there is a higher potential for future streamliners to find better solutions. The process ends after a total of 4 hours have passed. At the end of the process, we can directly read off the final solution $s$. One variation of our incremental warmstart approach is to give it an already known solution (potentially from literature) right at the start. This makes the solving process even more efficient and enhances the chances to improve upon previously known bounds.

Evolutionary algorithms are optimization techniques inspired by the biological process of evolution. A set of possible solutions is stored as a population. In every generation, good solutions are selected, combined, and mutated to create potentially better solutions to add to the population.

Our evolutionary approach is shown in Figure 4. At the beginning, we run the original, unstreamlined encoding for three minutes to figure out its performance. Further, we create the set $S$ for potential streamliners. At the beginning, $S$ is empty. So we ask the randomly picked LLM to produce five new streamliners for the given problem. They are evaluated in parallel for 3 minutes. All streamliners that perform better than the original model after three minutes are added to the population, along with their corresponding imbalance values $𝕀$. This phase is called exploration. The first 20 streamliners added to the population are called the original population. Then, the evolutionary phase starts. In every iteration step, we sample 10 streamliners from our population according to probabilities proportional to ${𝕀}^{-4}$, favoring those with lower imbalance values. Then, these 10 streamliners are given to the LLM as reference to derive five new streamliners. This would be the combination and mutation part in terms of evolution. Again, all streamliners that produce better results than the original model are added to the population. We run this process for 5 hours. At the end of the process, we read off the three best-performing streamliners from the final population. These streamliners can potentially also be used for other instances of the same problem. Finally, we run these three streamliners in parallel for a further 4 hours and then report the best result. In our experiments, we also run a variant of this process called exploration-only, where we omit the evolutionary phase and only run the exploration phase for 5 hours. This is again followed by running the three best streamliners in parallel for a further 4 hours. The goal of the exploration-only variant is to assess whether the evolution indeed works well or whether the improvements are only due to the relatively long running time.

We run all our experiments on compute nodes with 2.40GHz, 10-core 2×Intel Xeon E5-2640 v4 processors. We use MiniZinc version 2.9.2 for the incremental warmstart approach¹¹1MiniZinc version 2.9.2 offers more robust support for the warmstart feature and MiniZinc version 2.8.3 for the other experiments. We use Gurobi version 11.0.2 as the backend solver for MiniZinc, since previous work mainly used Gurobi and our preliminary experiments showed it to outperform Chuffed. We use five LLMs, namely GPT-4o (openai/gpt-4o-2024-11-20), GPT-o3 (openai/o3-mini-high), Claude 3.7 Sonnet (anthropic/claude-3.7-sonnet), Deepseek R1 (deepseek/deepseek-r1), and Gemini 2.0 Flash (google/gemini-2.0-flash-001). We access all these LLMs via the unified OpenRouter API in Python 3.11.5.

As a baseline for our experiments, we use the currently best-known results for BLRs from literature [2, 9, 10]. Since several best-known results were computed more than a decade ago, we augment the baseline with results obtained by running Gurobi for 4 hours. We run Gurobi on two variants of the model, one with the symmetry-breaking constraints used by Díaz et al. [2] and one without. These symmetry-breaking constraints enforce: $\text{pos}(s,1)=s$ for $1\le s\le n$ and for . Listing 2 shows the MiniZinc code for these constraints. We use the results from Gurobi for instances where it can improve the previous best result or where no results are found in the literature (this includes most of the instances with $n=13$). The baseline imbalance values are shown in Table 2. In our experiments, we only consider the instances that are yet to be solved optimally, which includes most with $k>2$ and $n>7$.

We run the incremental warmstart approach described in Section 3.2 twice to see how much the randomness of LLMs influences the experiment’s outcome. Overall, the results are fairly similar between the two runs. For about three-quarters of the instances, the results differ by less than 10%. Three outliers differ by more than 20%, with the highest difference being 34%. Of all the LLM responses, around 14% had syntax errors in the produced json or minizinc code and were simply discarded. For each instance, the result of the better run is shown in Table 3. Overall, 24 out of 44 instances show an improvement compared to the baseline.

Analyzing the different prompts shows that prompt_basic, prompt_description, and prompt_combinations are respectively responsible for generating 37.8%, 36.9%, and 25.3% of all streamliners that lead to an improvement. This shows that providing a detailed problem description does not influence the outcome of the LLM a lot. Further, it shows that asking for combinations of streamliners also does not lead to significantly better results. This might be because there is a higher likelihood that streamliners hinder each other instead of combining their strengths, and the LLM is not fully capable of finding the mutually compatible combinations. When comparing the five different LLMs, the fraction of improvements they contribute are as follows: GPT-o3: 22.6%, GPT-4o: 22.3%, Gemini: 20.7%, Claude: 20.2%, Deepseek R1: 14.2%.

Figure 5 shows the change of imbalance over time for seven curated, representative instances. The initial result that is found after 1 minute is about 25% to 60% worse than the baseline. In the beginning, new improvements are found quite quickly; later, however, it flattens out. After about 2 hours of incremental warmstart, many of the instances can already outperform the baseline. Interestingly, if we ignore the previously known results for the BLR problem and only compare against the results from the 4-hour Gurobi runs, our incremental warmstart approach performs better on 40 of 44 instances.

We run the evolutionary approach and the exploration-only approach for 5 hours each. At the end, we evaluate the three best-performing streamliners from each by running them for 4 hours and then report the best result in Table 4. The evolutionary approach could improve 24 out of 44 instances with respect to the baseline, while the exploration-only approach improved 21 instances. For 6 instances, the evolutionary approach failed to assemble the original population of 20 streamliners and thus terminated before starting the evolution phase. In those cases, the result is the same as the result for the exploration-only approach. Overall, the evolutionary approach performs slightly better than the exploration-only approach.

Another striking observation is that some of the streamliners found by our approach perform so well that running the streamlined model for 3 minutes yielded better results than running the unstreamlined model for 4 hours. Running the streamliners found in the evolutionary process for 4 further hours improved the imbalance by 10% on average compared to the result from initial 3-minute run.

Comparing the five different LLM models shows that GPT-o3, GPT-4o, Deepseek R1, Claude, and Gemini respectively found 26.0%, 25.2%, 17.9%, 17.5%, and 13.4% of the three best streamliners across all instances and variants. It is also worth noting that there are only two streamliners that appear in the list of top three streamliners for more than two instances. This demonstrates the great diversity of LLM-generated streamliners.

We showcase some interesting streamliners that were generated by our evolutionary approach in Listing 3 and provide a brief explanation of each of them below:

A

This streamliner is generated for the instances $8\times 10$, $8\times 11$, and $3\times 9$. It enforces each row to be strictly lexicographically smaller than the next row. However, since every entry within a row must be different, this constraint amounts to enforcing lexicographically ascending entries in the first cell of each row. Thus, the LLM rediscovered the already known symmetry-breaking constraint from literature. Interestingly, the formulation found by the LLM performed a bit better on the corresponding instances than the original formulation by Díaz et al. [2].

B

This symmetry-breaking constraint works similarly to the one above. It fixes the order of the rows according to the position of the symbol 1 in each row. Instead of the values of the variable rect, the values of the variable pos are increasing with every row. This constraint is generated for the instances $5\times 8$, $8\times 10$. Further, this constraint was also part of a combination of constraints for three instances, namely, $5\times 11$, $5\times 8$, and $6\times 11$.

C

This streamliner is decisive to achieve the improved imbalance result for the $4\times 12$ instance. It enforces that for every row, cells that are horizontally mirrored about the center column, add up to $n+1$. The resulting Latin rectangle can be found in Figure 6(c).

D

This constraint enforces that for every pair of symbols, the distance must not be $0$. Since all elements in a row are anyway defined to be different, this is an implied constraint. Nonetheless, it helped the solver find a $4\times 11$ Latin rectangle with better imbalance.

E

This combination of constraints ensures that each value $i\in [1,n]$ appears at least $k-1$ times in each column of pos and that each pairwise imbalance is less than or equal to half of the maximum possible imbalance. It showcases one of the most complex combinations of constraints we obtained from the LLMs. It is not only able to combine multiple constraints but also add an include statement and introduce a new array of decision variables. This code is generated for the $6\times 8$ instance. It outperforms the results from the 4-hour Gurobi runs but does not manage to beat the previously known best result.

Our incremental warmstart approach can not only be started from scratch but also from an already known solution. Hence, with an aim of finding the best Latin rectangles without concern for fair comparison, we run the incremental warmstart approach using the results from the evolutionary approach and with some previously published results from literature.

Table 1 summarizes the final best results we found from all approaches considered. Overall, we can improve 32 out of 44 instances. The list below shows which improving result is found by which approach. If two approaches arrive at the same result for a particular instance, then it is included in both approaches.

• $\mathrm{■}$

  incremental warmstart: $5\times 9$, $9\times 10$, $3\times 11$, $5\times 11$, $7\times 12$, $8\times 12$, $3\times 13$, $5\times 13$, $8\times 13$

• $\mathrm{■}$

  exploration-only: $3\times 10$, $4\times 11$, $4\times 12$, $6\times 13$

• $\mathrm{■}$

  evolution: $3\times 10$, $4\times 11$, $5\times 11$, $4\times 12$, $5\times 12$, $11\times 13$

• $\mathrm{■}$

  combination of approaches: $7\times 9$, $8\times 9$, $4\times 10$, $6\times 10$, $7\times 10$, $8\times 10$, $6\times 11$, $7\times 11$, $8\times 11$, $9\times 11$, $3\times 12$, $9\times 12$, $4\times 13$, $7\times 13$, $9\times 13$, $10\times 13$, $12\times 13$

In Figure 6 we present some of the Latin rectangles generated by our approach which significantly improved upon previously known results (by at least 14%) as well the $4\times 12$ Latin rectangle for illustration purposes.