How to use ortool's global constraints which are not integrated by CPMpy?

[hakank]

The ortools CP-SAT solver has quite a few constraints that's not (yet) integrated in CPMpy, for example; AddAutomaton, AddCumulative, AddForbiddenAssignments, AddInverse, AddNoOverlap, AddNoOverlap2D, AddReservoirConstraint.

It would be great to be able to use these constraints even if they are now defined in globalconstraints.py and/or ortools.py.

There are two methods in principles. Here I use AddAutomaton as an example (since I want to use it in my Nonogram solver :-)).

First, the approach that was suggested by Tias in a mail exchange a while ago. For a simple model it works by adding the constraint to the solver object, e.g.

import sys
import numpy as np
from cpmpy import *
from cpmpy.solvers import *

def get_different_solution(m, x):
  m += [any([t.value() != t for t in x])]

# Callback function for printing the solution
def print_solution(x):
    for a in x:
        print([val for val in a.value()])

def automaton_test(n=7,num_sols=0):
    # The DFA for AddAutomaton
    transitions = [
        (0,0,0), # 0*
        (0,1,1), # 1*
        (1,1,1), # 
        (1,0,2), # 0*
        (2,0,2)  #
        ]

    initial_state = 0 
    # all states are accepting states
    accepting_states = [0, 1, 2]

    # declare variables
    x = boolvar(shape=n,name="x")
    z = intvar(0,n,name="z")

    # constraints

    # Currently one have to include x in the model.
    model = Model(z == sum(x) )

    ss = CPM_ortools(model)
    # This (the next two lines) was suggested by Tias and it works:
    ort_vars = [ss.varmap[v] for v in x]
    ss.ort_model.AddAutomaton(ort_vars, initial_state,accepting_states,transitions)

    num_solutions = 0
    while ss.solve():
        num_solutions += 1
        print("x:",x.value(), "z:", z.value())
        get_different_solution(ss,x)
    print("num_solutions:",num_solutions)

n=7
automaton_test(n)

This works and is fast. Note that is use the CPM_ortools object and one have to translate the CPMpy variables to ORtools variables (the ss.varmap step).

However, for larger models this can be quite messy. It would be really nice if one could use the constraint as any other constraint, i.e. using via model += [AddAutomaton(...)] and without the step to translate the CPMpy variables.

For a "real" - or at least more complex example - see my Nonogram solver (http://hakank.org/cpmpy/nonogram_regular.py ) where I call regular several times in a loop over the hints:

def check_rule(rules, y):
    # ...
    return [regular(y, n_states, input_max, transition_fn, initial_state,
                    accepting_states)]

def nonogram_regular(rows, row_rule_len, row_rules, cols, col_rule_len, col_rules,num_sols=2,minizinc_solver=None):

    board = intvar(1,2,shape=(rows,cols),name="board")

    model = Model()

    # constraints
    for i in range(rows):
        model += [check_rule([row_rules[i][j] for j in range(row_rule_len)],
                             [board[i, j] for j in range(cols)])]

    for j in range(cols):
        model += [check_rule([col_rules[j][k] for k in range(col_rule_len)],
                             [board[i, j] for i in range(rows)])]

     # ...

One way would be that a user could defined this via some interface, e.g.

def automaton(x, initial_state,accepting_states,transitions):
     return GlobalConstraint("AddAutomaton", [x, initial_state,accepting_states,transitions])

def check_rule(rules, y):
    # ...
    return [automaton(y, initial_state,accepting_states, transitions)]

Or, perhaps simply use the ortools constraint directly, which would be neater:

def check_rule(rules, y):
    # ....
    return AddAutomaton(y, initial_state, accepting_states, transitions)

def nonogram(...):
    # .... 
    for i in range(rows):
        model += [check_rule([row_rules[i][j] for j in range(row_rule_len)],
                             [board[i, j] for j in range(cols)])]

I don't expect that CPMpy should have to do any check specific checks in these cases. Instead it's the user's responsibility to ensure that all variables are properly used (and be prepared to get strange error messages if not).

[tias]

Hi Hakan,

I would like to support

def check_rule(rules, y):
    # ...
    return GlobalConstraint("AddAutomaton", [y, initial_state,accepting_states, transitions])

which should then automatically be translated in CPM_ortools into

ort_vars = [ss.varmap[v] for v in y]
ss.ort_model.AddAutomaton(ort_vars, initial_state,accepting_states,transitions)

This is TODO.

On a side-note, it is possible to do it more directly interleaved with a slight change of style:

def nonogram_regular(rows, row_rule_len, row_rules, cols, col_rule_len, col_rules,num_sols=2,minizinc_solver=None):

    board = intvar(1,2,shape=(rows,cols),name="board")

    omodel = CPM_ortools(Model())

    omodel += [... some constriants ...]

    # constraints
    for i in range(rows):
        check_rule(omodel, [row_rules[i][j] for j in range(row_rule_len)],
                             [board[i, j] for j in range(cols)])

    for j in range(cols):
        check_rule(omodel, [col_rules[j][k] for k in range(col_rule_len)],
                             [board[i, j] for i in range(rows)])

with

def check_rule(omodel, rules, y):
    # ....
    # the above should include the y = [omodel.varmap[v] for v in y] dance
    omodel.ort_model.AddAutomaton(y, initial_state, accepting_states, transitions)

[hakank]

Thanks for the suggestion about the rewriting of the model.

[tias]

OK, so we reworked the solver interfaces a few months back, and the above approach (s.ort_model.Add...) is now documented, with 's.solver_var(x)' the generic way for all solvers to translate CPMpy variables to solver-specific variables. https://cpmpy.readthedocs.io/en/latest/solvers.html#native-solver-access-and-constraints

But our discussion here actually went quite further. I've implemented a prototype of it in #121 I'll copy paste the example here

from cpmpy import *
from cpmpy.expressions.globalconstraints import NativeConstraint
x = intvar(0,10, shape=3)

# CPMpy standard
s = SolverLookup.get("ortools")
s += Table(x, [[0,1,2],[2,1,0]])
print(s.solveAll())

# CPMpy with current 'direct solver access' use
s = SolverLookup.get("ortools")
s.ort_model.AddAllowedAssignments(s.solver_vars(x), [[0,1,2],[2,1,0]])
print(s.solveAll())

# Proposal in branch
s = SolverLookup.get("ortools")
s += NativeConstraint("AddAllowedAssignments", (x, [[0,1,2],[2,1,0]]))
print(s.solveAll())

# Proposal also allows to indicate some args are const/novar/should be passed as is
# the top two variants (now) also do not scan the data part
s = SolverLookup.get("ortools")
s += NativeConstraint("AddAllowedAssignments", (x, [[0,1,2],[2,1,0]]), arg_novar=[1])
print(s.solveAll())

(the reason for a new NativeConstraint class instead of reusing GlobalConstraint is that the latter requires a decompose function to be generic, while the former clearly does not; also allows us to add the arg_novar property.)

What do you think? Feedback welcome...

[tias]

Hi @hakank,

I'm happy to report that we recently merged and released a new CPMpy version with 'DirectConstraint', which started in this discussion! (it is just a rename of NativeConstraint, but then fully implemented, documented and tested for all solvers).

See the documentation and links to ortools examples (automaton, circuit, multicircuit) here: https://cpmpy.readthedocs.io/en/latest/solvers.html#direct-solver-access

and the nonogram example implemented in a notebook here: https://github.com/CPMpy/cpmpy/blob/master/examples/nonogram_ortools.ipynb

We'd be happy for you to experiment with it and give feedback!

(we are also working on a DirectVariable for a similar generic access to custom solver variables like OrTools' IntervalVars, that is very much WIP, discussion and code in #121 )