По крайней мере один Var равен X в массиве Var с использованием Choco Solver

Я использую Choco Solver и, учитывая массив переменных типа int, мне нужно ограничение, которое проверяет, что хотя бы одна переменная в массиве равна статическому значению...

Что-то похожее на IntConstraintFactory#count, но со следующим документом:

/**
 * Let N be the number of variables of the VARIABLES collection assigned to value VALUE;
 * Enforce condition N >= LIMIT to hold.
 * <p>
 *
 * @param VALUE an int
 * @param VARS  a vector of variables
 * @param LIMIT a variable
 */
public static Constraint at_least(int VALUE, IntVar[] VARS, IntVar LIMIT) {
    return new Constraint("At least", /* help here ? */);
}

Кто-нибудь знает, существует ли он или как я могу эффективно его реализовать?


person avianey    schedule 12.08.2016    source источник
comment
Один общий подход, работающий для большинства примитивов оптимизации (SAT, MIP, CP): ввести ограничения-индикаторы, которые отмечают, если переменная hits является целевым значением. Затем добавьте один из возможных подходов кардинальности (или просто OR в вашем случае).   -  person sascha    schedule 12.08.2016
comment
Распространенное название этого ограничения в сообществе CP — GCC (глобальное кардинальное ограничение), возможно, это поможет вам найти ответ (в частности, я не знаком с choco)   -  person tobyodavies    schedule 21.08.2016


Ответы (1)


Если вы хотите опубликовать ограничение atLeast(VALUE,VARS, LIMIT) в Choco Solver, вы можете просто опубликовать count(VALUE,VARS,X) с X IntVar исходного домена. [0,VARS.length] и опубликовать arithm(X,">=",LIMIT). Это сделает работу. Для этого нет необходимости реализовывать конкретное ограничение.

Если вы хотите проверить, что хотя бы одна переменная в VARS равна VALUE, это еще проще, просто опубликуйте count(VALUE, VARS, X) с [1,VARS.length] в качестве начального домена для X. Таким образом, минимальное количество вхождений VALUE будет не менее 1. Нет необходимости создавать вторую переменную и арифметическое ограничение.

person Jean-Guillaume Fages    schedule 21.08.2016