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])}')
```