ORTools SAT альтернатива CS IntVar []. Элемент (индекс IntExpr), чтобы оценить взаимные назначения - PullRequest
Новая
       21

ORTools SAT альтернатива CS IntVar []. Элемент (индекс IntExpr), чтобы оценить взаимные назначения

4 голосов
/ 23 мая 2019

Я пытаюсь назначить затраты, если в IntVar есть «взаимное» назначение []. Вот как я это сделал в старом ConstraintSolver ... 

IntVar[] assignments = solver.MakeIntVarArray(size, 0, size-1, "assignments");
var cost = Enumerable.Range(0, size)
    .Select(i => 999 * (assignments.Element(assignments[i]) == i))
    .ToArray()
    .ToSum()
    .Var();
var objective = cost.Minimize(1);

Теперь я пытаюсь использовать более новую CpSolver в Google.OrTools.Sat, где расширение .Element отсутствует (я полагаю, на это есть веские причины). Мне удалось заставить его "работать", используя четыре IntVars [], но я подозреваю, что это просто большая ошибка моделирования с моей стороны. 

foreach (var i in Enumerable.Range(0, size))
{
    model.AddElement(assignments[i], assignments, reciprocals[i]);
    model.Add(reciprocals[i] == i).OnlyEnforceIf(reciprocalBools[i]);
    model.Add(reciprocals[i] != i).OnlyEnforceIf(reciprocalBools[i].Not());
    model.Add(costs[i] == 999).OnlyEnforceIf(reciprocalBools[i]);
    model.Add(costs[i] == 0).OnlyEnforceIf(reciprocalBools[i].Not());
}
model.Minimize(costs.Sum());

Исходя из моего тестирования, вышеприведенное представляется функционально правильным, однако по мере увеличения size SAT-версия моего тестового приложения работает на порядок хуже, чем CS-версия. Любые предложения будут с благодарностью.

1 Ответ

1 голос
/ 24 мая 2019

вот лучшая версия 

foreach (var i in Enumerable.Range(0, size))
{
    model.AddElement(assignments[i], assignments, reciprocals[i]);
    model.Add(reciprocals[i] == i).OnlyEnforceIf(reciprocalBools[i]);
    model.Add(reciprocals[i] != i).OnlyEnforceIf(reciprocalBools[i].Not());
}
model.Minimize(999 * LinearExpr.Sum(reciprocalBools));

У нас также есть обратное ограничение (model.AddInverseConstraint(x_array, y_array)) что обеспечивает 

x_array[i] == j <=> y_array[j] == i

Тем не менее, мне интересно, если вам все это нужно.

Если xi = {xi_1, .., xi_n} (отображение в массив логических переменных) reciprocalBools[i] is true если exists j, such that (xi_j && xj_i) is true

Так что вам просто нужно сосчитать пары (xi_j && xj_i) обе верные.

Это не просто.

учитывая i и j, i! = J 

Literal implied = model.newBoolVar("");
model.addBoolOr(new Literal[] {xi_j.not(), xj_i.not(), implied});
model.addImplication(implied, xi_j);
model.addImplication(implied, xj_i);

Теперь у вас есть implied <=> xi_j && xj_i. И вы можете сосчитать эти implied переменные.

если i == j, не создавайте переменную implied, не добавляйте логическое ограничение 3 и используйте xi_i напрямую.

...