AddModuloEquality does not work with negative numbers

psarka commented 2 years ago

What version of OR-Tools and what language are you using? Version: 9.1.9490 Language: Python

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi) CP-SAT

What operating system (Linux, Windows, ...) and version? Linux, Ubuntu 20.04.3 LTS

What did you do? Steps to reproduce the behavior: Try to solve this (full script below):

m.AddLinearConstraint(a, -4, -4)
m.AddModuloEquality(0, a, 4)

What did you expect to see solution a = -4

What did you see instead? INFEASIBLE

Make sure you include information that can help us debug (full error message, model Proto). Full script for repro:

from ortools.sat.python.cp_model import CpModel
from ortools.sat.python.cp_model import CpSolver
from ortools.sat.python.cp_model import INFEASIBLE

m = CpModel()

a = m.NewIntVar(-100, 100, 'a')

m.AddLinearConstraint(a, -4, -4)
m.AddModuloEquality(0, a, 4)

solver = CpSolver()
print(solver.Solve(m) == INFEASIBLE)

(prints True)

lperron commented 2 years ago

0 % -4 == 0 ?

lperron commented 2 years ago

And abs(result) < abs(modulo)

psarka commented 2 years ago

@lperron Does this mean that I'm reading the function signature incorrectly? The docs say:

def AddModuloEquality(self, target, var, mod)

Adds target = var % mod.

So then m.AddModuloEquality(0, a, 4) would translate to the constraint 0 == a % 4 which should be satisfiied by a = -4.

kasperdokter commented 1 month ago

It seems that the docs should be changed to

if expr >= 0:
    target = expr % mod
else:
    target == -(-expr % mod)

or the implementation of add_modulo_equality should be updated.

lperron commented 1 month ago

it depends on your convention. I will check.

C and python differ. We use the C convention.

I have updated the doc. Laurent Perron | Operations Research | @.*** | (33) 1 42 68 53 00

Le mar. 23 juil. 2024 à 19:17, Kasper Dokter @.***> a écrit :

It seems that the docs should be changed to

if expr >= 0: target = expr % mod else: target == -(-expr % mod)

or the implementation of add_modulo_equality should be updated.

— Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/2864#issuecomment-2245805610, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3MJQN2HDWVFEG3E3DDZN2F2RAVCNFSM6AAAAABLK3PHWWVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDENBVHAYDKNRRGA . You are receiving this because you modified the open/close state.Message ID: <google/or-tools/issues/2864/2245805610 @.***>

google / or-tools

AddModuloEquality does not work with negative numbers #2864