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

注意这里也没有除法。

但是，求解器会在两个方向上推断出含义，所以写成

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 可能太低了...

在 OR-Tools 中对复杂约束进行建模

Modeling complex constraints in OR-Tools

c#

or-tools