Constraint programming problem with matrix of integers

Question

I am trying to solve the following problem. Suppose $A$ is an $m \times n$ matrix of integers with entries in $\{1, \dots, k\}$. There are two kinds of constraints on the entries of this matrix:

• For each integer, there are constraints on the number of times that integer can appear in each row and column. The integer $i$ must appear in each column no fewer than $c_i$ and no more than $C_i$ times, and in each row no fewer than $r_i$ and no more than $R_i$ times.
• For each integer $i$, it must appear in each row as part of a span - where that integer repeats for some length $l$. The length of the span must be between $s_i$ and $S_i$.

In my application, I have $m \approx 30$, $n \approx 50$, and $k \approx 10$. I tried modeling this using Google's ortools, and can generate a matrix that satisfies the constraints on the rows and columns (first bullet point), but am having trouble with the constraints on the span lengths. I came up with a solution but it runs for hours and does not find a feasible solution.

Is there a kind of problem in the literature which is similar to this? Could anyone give some pointers about how I can try to solve this?

Answer 1

You might try integer programming instead of constraint programming. Let binary decision variable $x_{uvi}$ indicate whether entry $(u,v)$ takes value $i$, and let binary decision variable $y_{uvi}$ indicate whether entry $(u,v)$ starts a span with value $i$. The constraints are \begin{align} \sum_i x_{uvi} &= 1 &&\text{for all $u,v$} \tag1\label1\\ r_i \le \sum_v x_{uvi} &\le R_i &&\text{for all $u,i$} \tag2\label2\\ c_i \le \sum_u x_{uvi} &\le C_i &&\text{for all $v,i$} \tag3\label3\\ x_{uvi} - x_{u,v-1,i} &\le y_{uvi} &&\text{for all $u,v,i$} \tag4\label4\\ y_{uvi} &\le x_{uwi} &&\text{for all $u,v,i$ and all $w\in\{v,\dots,v+s_i-1\}$} \tag5\label5\\ \sum_{w=v}^{v+S_i} x_{uwi} &\le S_i &&\text{for all $u,v,i$} \tag6\label6 \end{align} Constraint \eqref{1} assigns exactly one value to each entry. Constraints \eqref{2} and \eqref{3} enforce the counts of value $i$ in the rows and columns, respectively. Constraint \eqref{4} enforces $(x_{uvi} \land \lnot x_{u,v-1,i}) \implies y_{uvi}$. Constraint \eqref{5} enforces $y_{uvi} \implies \bigwedge_{w=v}^{v+s_i-1} x_{uwi}$ so that each span has length at least $s_i$. Constraint \eqref{6} prevents spans of length $>S_i$.

Answer 2

There is a bit of tangential similarity to cutting stock problems. One possible approach would be to define, for each integer $i$, the set of legal spans. So if $s_2=2$ and $S_2=3,$ the legal spans for 2 are $22$ and $222.$

Next, build the set of legal patterns for each row, where a pattern is a combination of spans that contains $n$ integers and contains $i$ between $r_i$ and $R_i$ times for each $i.$ You can start by finding all span combinations for each integer that meet the $r_i$ to $R_i$ constraints, then find all combinations of those combinations that get all the integers and fit in a row, then look at all arrangements (permutations) of those spans.

Once you have enumerated all possible row patterns, the remaining problem is to select one pattern for each row such that every column contains between $c_i$ and $C_i$ instances of $i$ for each $i.$ Since any permutation of the rows of a feasible answer remains feasible, you might want to specify some sort of antisymmetry constraint, such as row 1, column 1 containing the integer 1.

This can become computationally infeasible pretty quickly, as the number of patterns can be enormous.

Answer 3

You can reuse RobPratt@ ideas with CP-SAT.

First, for each cell, you have a Boolean var array, 1 for each integer. You then use and AddExactlyOne(bool_variables_for_each_color) to constrain it.

For the number of occurrence of a given color, just use sum(bool_variables_for_one_color) == target.

Now the complex constraint is a min/max sequence of one color. Luckily, it is already implemented in the shift_scheduling_sat.py example to limit the sequence of one type of shift.

The code for add_soft_sequence_constraint is a bit more general as it also accept soft lower and upper bounds for sequences.