CODEWITHSUNDEEP
c#or-tools
T.Bob
T.Bob

Reputation: 120

Modeling complex constraints in OR-Tools

Let's assume this constraint with 2 variables (x % (26 ^ 13)) / (26 ^ 12) == (y % (26 ^ 5)) / (26 ^ 4).

The constraint solving model will have multiple of these constraints. How would one model such a constraint? Is this even possible?

        // Domains for w1/w2
        long[] wl1 = new long[]
        {
            17576,
            35152,
            52728,
            70304,
            87880
        };

        long[] wl2 = new long[]
        {
            8770424,
            8295872,
            3251560,
            949104,
            3673384
        };

        // Create model
        CpModel model = new CpModel();

        IntVar w1 = model.NewIntVarFromDomain(Domain.FromValues(wl1), "w1");
        IntVar w2 = model.NewIntVarFromDomain(Domain.FromValues(wl2), "w2");

        model.Add(((w1 % (26 ^ 13)) / (26 ^ 12)) == ((w2 % (26 ^ 5)) / (26 ^ 4))); // <-- Invalid syntax, as % operator cannot be used with Google.OrTools.Sat.IntVar

        // Create solver and solve ...
        CpSolver solver = new CpSolver();
        // ...

Edit: Update based on the answer below:

        IntVar w1 = model.NewIntVarFromDomain(Domain.FromValues(wl1), "w1");
        IntVar w2 = model.NewIntVarFromDomain(Domain.FromValues(wl2), "w2");

        long w1Modulo = 26 ^ 13;
        long w1ModuloMinusOne = 26 ^ 12;
        IntVar multiplicandw1= model.NewIntVarFromDomain(Domain.FromValues(new long[]{ w1Modulo }), "multiplicandw1");
        IntVar remainderw1 = model.NewIntVar(0, w1ModuloMinusOne, "remainderw1");
        model.Add(w1 == ((w1Modulo * multiplicandw1) + remainderw1));

        long w2Modulo = 26 ^ 5;
        long w2ModuloMinusOne = 26 ^ 4;
        IntVar multiplicandw2 = model.NewIntVarFromDomain(Domain.FromValues(new long[] { w2Modulo }), "multiplicandw2");
        IntVar remainderw2 = model.NewIntVar(0, w2ModuloMinusOne, "remainderw2");
        model.Add(w1 == ((w1Modulo * multiplicandw2) + remainderw2));

        model.Add(remainderw1 * w2Modulo == remainderw2 * w1Modulo);

Upvotes: 0

Views: 878

Answers (1)

Christopher Hamkins
Christopher Hamkins

Reputation: 1639

The arithmetic operations allowed for IntVars are determined by the overridden operators for them in their base class LinearExpr

        public static LinearExpr operator +(LinearExpr a, LinearExpr b);
        public static LinearExpr operator +(LinearExpr a, long v);
        public static LinearExpr operator +(long v, LinearExpr a);
        public static LinearExpr operator -(LinearExpr a);
        public static LinearExpr operator -(LinearExpr a, LinearExpr b);
        public static LinearExpr operator -(LinearExpr a, long v);
        public static LinearExpr operator -(long v, LinearExpr a);
        public static LinearExpr operator *(LinearExpr a, long v);
        public static LinearExpr operator *(long v, LinearExpr a);

Note that there is also no division.

However, the solver will infer implications in both directions, so by writing

IntVar A;
IntVar B;
long C;
... create the IntVar's with model.NewIntVar
modelAdd(A == B * C);

you effectively enforce B == A / C.

To implement a remainder operation, you can introduce another free variable like multiplicand and add the relationship like this:

IntVar multiplicand = model.NewIntVar(-5, 5, "multiplicand");
IntVar remainder = model.NewIntVar(0, 50, "remainder");
long modulo = (26 ^ 13)
model.Add(A == ((modulo * multiplicand) + remainder));

This will enforce (A % modulo) == remainder

multiplicand is a free variable for the solution which is only constrained to be an integer in its domain.

You'll have to create the variables with suitable domains for your solution, probably +/- 5 is too low when you're talking about 26 ^ 13...

Upvotes: 2

Related Questions