# [OR-Tools][CP-SAT] Implement an indicator function in a constraint

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 ?

• 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). Mar 31 at 0:40
• You can use AddLinearConstraint to have both LHS and RHS. Mar 31 at 5:53
• 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) Mar 31 at 10:16
• Welcome to OR.SE Arthursbr. Please edit your question and rather than the image, use MathJax to make your question searchable.
– EhsanK
Mar 31 at 13:04

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

• I think it is supposed to be indicator $\mathbb{I}$, not product $\prod$. Mar 31 at 13:31
• 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). Mar 31 at 15:26