3
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ When you say $i$ must appear in a span, do you mean that (a) it must appear in at least one span in the row (and may appear in other columns as a singleton), (b) it must appear in exactly one span (and nowhere else in the row), (c) it must appear in at least one span but possibly more than one span (but never in less than $s_i$ consecutive slots) or (d) something else? $\endgroup$
    – prubin
    May 26, 2023 at 20:33
  • 1
    $\begingroup$ Once the constraints are satisfied, are there any optimization objectives? $\endgroup$
    – Reinderien
    May 26, 2023 at 23:33
  • $\begingroup$ @prubin By "span" I mean a repeated sequence of digits. Each time $i$ appears in a row, it appears as part of a span of $i$s of constrained length. For example, if $s_2= 2$ and $S_2 = 3$, then $1 1 2 2 2 3 1 1 2 2 8$ could be feasible but $1 1 2 2 2 2 1 1 2 2 8$ would not be, because there is a span of 2's of length four. $\endgroup$ May 27, 2023 at 0:00
  • 1
    $\begingroup$ Difficulty of solution will depend fairly heavily on data for C c R r S s. Where do these actually come from? Do you have samples? $\endgroup$
    – Reinderien
    May 27, 2023 at 2:44

3 Answers 3

2
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Thank you for taking the time to formulate this - I really appreciate it. Would you recommend trying this using the ortools MPSolver? $\endgroup$ May 29, 2023 at 0:12
  • $\begingroup$ I have never used that solver, but it is worth a try. If you share your input parameters, members of the community might try other solvers. $\endgroup$
    – RobPratt
    May 29, 2023 at 2:15
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.