1
$\begingroup$

I have a simple constraint programming model which can be solved using the docplex library, however I am struggling to implement the same model using ortools (see the examples below).

Question: Is there a fundamental limitation of ortools which prevents implementing this solution, or is there a problem with my syntax?

Note: I am NOT interested in alternative problem formulations, e.g., reformulating this as an MIP. This is a toy problem and I know different formulations are possible. My goal is to understand the differences and limitations of different solvers when it comes to implementing a constraint like this.

Problem

Given a series with indices 0...n, find integer values of the series such that the value for each index i corresponds to the number of occurrences of i in the series.

For example, a solution for n = 4 is:

0 1 2 3 4
2 1 2 0 0

For index i=0, the value is 2, which corresponds to the series "2, 1, 2, 0, 0" containing two occurrences of the value 0. Index i=1 has a value of 1, corresponding to the single occurrence of 1 in the series. And so on.

Example input data

# Input: Series length
n = 5

# Define data
max_value = n - 1
NUMBERS = range(n)

docplex implementation works!

from docplex.cp.model import CpoModel

# Model instance
model = CpoModel(name='find series')

# Decision variables
s = model.integer_var_list(n, 0, max_value, "series")

# Constraint: Value should equal the # of occurrences of the index in the series
for i in NUMBERS:
    model.add(sum(s[j] == i for j in NUMBERS) == s[i])

# Solve
model.solve()

ortools implementation does NOT work!

When attempting to run the code below, I get an error when I try to define the constraints:

TypeError: unsupported operand type(s) for +: 'int' and 'BoundedLinearExpression'.

I've tried adjusting the syntax a few different ways, but it never reads the constraint as I intend it to.

from ortools.sat.python import cp_model

# Model instance
model = cp_model.CpModel()

# Decision variables
X = {}
for i in NUMBERS:
    X[i] = model.NewIntVar(0, max_value, f'X_{i}')

# Add constraints (CODE FAILS HERE)
for i in NUMBERS:
    model.Add(X[i] == sum([X[j]==i for j in NUMBERS]))

# Solve
solver = cp_model.CpSolver()
solver.Solve(model)

# Solution
print('Solve status: %s' % solver.StatusName())
if solver.StatusName() in ['FEASIBLE', 'OPTIMAL']:
    for i in NUMBERS:
        print(f'  X_{i}: {solver.Value(X[i])}')
```
$\endgroup$
2
  • $\begingroup$ You are trying to do sumif in ORtools. I am no expert in Google language but have you double checked if sum in a constraint under a condition is implemented in that way? Does ORtools give an lp file that shows the model? $\endgroup$ Nov 22, 2022 at 18:28
  • $\begingroup$ Per Laurent Perron's accepted answer, ORtools can implement a constraint like this using something called a "channeling constraint". It's not very intuitive to me, but it seems like the way to do a conditional sum $\endgroup$
    – SlowLoris
    Nov 22, 2022 at 20:47

1 Answer 1

3
$\begingroup$
  1. Please read this doc section

  2. cp-sat prefers Boolean variables. Here is a c++ version.

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