CODEWITHSUNDEEP
or-toolscp-sat
Andrea Reina
Andrea Reina

Reputation: 1240

Possible to set a Cp_Model constraint in terms of the sum of maxima of different variables/linear expressions?

I need to express a constraint in terms of a sum of maxima. I'm aware it's no longer a linear problem but I'm hoping that there's a way to fake or approximate it somehow:

model = cp_model.CpModel()

foo = {x: model.NewBoolVar(f"var{x}") for x in range(1, 6)}
bar = {x: model.NewBoolVar(f"var{x}") for x in range(6, 11)}

model.Add(
    sum(max(k * v for k, v in variables.items()) for variables in [foo, bar]) <= 20
)
# NotImplementedError: Evaluating a BoundedLinearExpr as a Boolean value is not supported.

The error is that you can't call max():

max(k * v for k, v in foo.items())
# NotImplementedError: Evaluating a BoundedLinearExpr as a Boolean value is not supported.

Faking max() with log(sum(exp(...), ...)) doesn't work because log() fails:

log(sum(int(exp(k)) * v for k, v in foo.items()))
# TypeError: must be real number, not _SumArray

As does converting log(sum(...) into sum(prod(...)):

prod(sum(int(exp(k)) * v for k, v in variables.items()) for variables in [foo, bar])
# TypeError: Not an integer linear expression: ((((((403 * var6)) + (1096 * var7)) + (2980 * var8)) + (8103 * var9)) + (22026 * var10))

Full code listing:

from functools import reduce
from math import log, exp
import operator as op
from ortools.sat.python import cp_model

def prod(args):
    return reduce(op.mul, args)

model = cp_model.CpModel()

foo = {x: model.NewBoolVar(f"var{x}") for x in range(1, 6)}
bar = {x: model.NewBoolVar(f"var{x}") for x in range(6, 11)}

model.Add(
    sum(max(k * v for k, v in variables.items()) for variables in [foo, bar]) <= 20
)
# NotImplementedError: Evaluating a BoundedLinearExpr as a Boolean value is not supported.

max(k * v for k, v in foo.items())
# NotImplementedError: Evaluating a BoundedLinearExpr as a Boolean value is not supported.

log(sum(int(exp(k)) * v for k, v in foo.items()))
# TypeError: must be real number, not _SumArray

prod(sum(int(exp(k)) * v for k, v in variables.items()) for variables in [foo, bar])
# TypeError: Not an integer linear expression: ((((((403 * var6)) + (1096 * var7)) + (2980 * var8)) + (8103 * var9)) + (22026 * var10))

Upvotes: 1

Views: 1153

Answers (1)

Laurent Perron
Laurent Perron

Reputation: 11014

  1. max() from python is interpreted before the Add() method is called. The result is unpredictable, and just wrong.

  2. The solver is integral only, so any trick using math double functions will just not work.

just use the model.AddMaxEquality() method documented here.

In is used in many examples of the distribution, including this one.

Note that MaxArray takes an array of variables. So you will need to create intermediate variables for all terms in max equation.

Upvotes: 3

Related Questions