OR-Tools中的复杂约束建模

Question

让我们假设这个约束具有2个变量(x % (26 ^ 13)) / (26 ^ 12) == (y % (26 ^ 5)) / (26 ^ 4)。

约束求解模型将具有多个这些约束。如何对这样的约束进行建模？这有可能吗？

        // 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();
        // ...

编辑:根据以下答案进行更新：

        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);

Answer 1

IntVar允许的算术运算由它们的基类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);

请注意，也没有除法。

但是，求解器将在两个方向上推断含义，因此通过编写

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

您可以有效地执行B == A / C。

要实现余数操作，您可以引入另一个自由变量，如multiplicand，并像这样添加关系：

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

这将强制执行(A % modulo) == remainder

multiplicand是解的自由变量，它只被约束为其域中的整数。

你必须为你的解决方案创建具有合适域的变量，当你谈论26^13时，+/- 5可能太低了……