-1
$\begingroup$

Good morning ! I would like to implement this constraint using CP-SAT (see image below).

x_i,j is a boolean variable, a and b are given. The problem is that I don't know how to implement the indicator function in a constraint. I tried with int() function but it cannot be applied with a BoundedLinearExpression. Here is my code:

for i in range(20):
  for j in range(30):
    x[(i,j)] = model.NewBoolVar('variable%ii%ij' % (i,j))
model.Add(a <= sum( int( sum(x[(i,j)] for j in range(30)) >= 5 ) for i in range(20) ) <= b)

Any idea on how to solve it ?

$\endgroup$
4
  • 1
    $\begingroup$ This is a use-case for or-tools docs: Channeling constraints. As mentioned in the docs, this is highly linked to the concept of half/full reification in constraint-programming. (You might also want to decompose this into multiple expressions -> a new result-vector for all geq-expression results followed by two inequalities). $\endgroup$
    – sascha
    Mar 31, 2023 at 0:40
  • 1
    $\begingroup$ You can use AddLinearConstraint to have both LHS and RHS. $\endgroup$ Mar 31, 2023 at 5:53
  • $\begingroup$ Hello @sascha and @laurent-perron, thanks for your response. I think I made the result-vector : b = [model.NewBoolVar('b%i' % (i)) for i in range(20)] for i in range(20): model.Add( sum(x[(i,j)] for j in range(30) ) >= 5).OnlyEnforceIf(b[i]) So now I have all my indicator functions, but I struggle a bit for the second sum. Is it simply this following line that I need to add ? model.AddLinearConstraint(sum(b[i] for i in range(20)), a, b) $\endgroup$
    – Arthursbr
    Mar 31, 2023 at 10:16
  • 1
    $\begingroup$ Welcome to OR.SE Arthursbr. Please edit your question and rather than the image, use MathJax to make your question searchable. $\endgroup$
    – EhsanK
    Mar 31, 2023 at 13:04

1 Answer 1

0
$\begingroup$

If I understand you are trying this.
For each $i$, sum across $j$. Then if all the sums across $j \ge 5$ for all $i$ (basically the $\pi$, the AND logic), then whole sum will be between constants $a,b$.
I can linearize it as below (OR-Tools will do the same thing)
Introduce set of new binary variables $y_i$. Add linear constraints
$ \sum_j x_{i,j} \le 5+My_i$
$ 5- \sum_j x_{i,j} \le M(1-y_i)$
where could be appropriate big number, like upper bound of sum of $x$ values possible.

Then you'd need another binary variable $\delta$ and below constraints
$\delta \le y_i \quad \forall i$
$ \sum_iy_i -I+1 \le \delta$ where $I$ is total number of your $i$s

Then the below constraint
$ a-M(1-\delta) \le \sum_i \sum_j x_{i,j} \le b + M(1- \delta)$

$\endgroup$
2
  • $\begingroup$ I think it is supposed to be indicator $\mathbb{I}$, not product $\prod$. $\endgroup$
    – RobPratt
    Mar 31, 2023 at 13:31
  • 1
    $\begingroup$ This seems to assume, CP-SATs native mode of inference is based on LP/MILP technology which is questionable. CP-SAT contains most features of a MILP-solver and indeed does offer automatic linearization based on global/high-level constraints, but this is optional (can be turned off; defaults are conservative imho). It's hard to predict if cp-sat successfully progresses on a given problem better because of search/propagation or linearization, but the API alone is CP-based and reification/channeling-based approaches are imho the native approach (solver can decide how to exploit it internally). $\endgroup$
    – sascha
    Mar 31, 2023 at 15:26

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.