как проверить, какие ограничения будут нарушены предполагаемым решением?

В некоторых случаях решатель не может найти решение для моей модели, которое, я думаю, есть. Поэтому я хотел бы заполнить решение, а затем проверить, какое ограничение нарушено. Как это сделать с помощью choco-solver?

Использование choco-solver 4.10.6.


choco
person brunesto    schedule 23.03.2021    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Принуждение к решению

В итоге я добавил ограничения, чтобы принудительно присвоить переменным значения моего предполагаемого решения: например.

    // constraints to force given solution 
    vehicle2FirstStop[0].eq(model.intVar(4)).post();
    vehicle2FirstStop[1].eq(model.intVar(3)).post();
    nextStop[1].eq(model.intVar(0)).post();
    nextStop[2].eq(model.intVar(1)).post();
    ...

а потом

 model.getSolver().showContradiction();
 if (model.getSolver().solve()) { ....

Показывает первое противоречие предполагаемого решения, например.

/!\ CONTRADICTION (PropXplusYeqZ(sum_exp_49, mul_exp_51, ...

Итак, следующий шаг — выяснить, откуда взялись такие термины, как sum_exp_49.

Сопоставление условий противоречия с кодом

Вот простое исправление для ограничений, которое, мы надеемся, предоставит достаточно информации. Мы можем переопределить методы модели post() и Associates(), чтобы она выдавала имя исходного файла Java и номер строки при отправке ограничения/создании переменной.

   Model model = new Model("Vrp1RpV") {
    /**
     * retrieve the filename and line number of first caller outside of choco-solver from stacktrace
     */
    String getSource() {
        String source = null;
        StackTraceElement[] stackTraceElements = Thread.currentThread().getStackTrace();            
        // starts from 3: thread.getStackTrace() + this.getSource() + caller (post() or associates())
        for (int i = 3; i < stackTraceElements.length; i++) {                
                // keep rewinding until we get out of choco-solver packages
                if (!stackTraceElements[i].getClassName().toString().startsWith("org.chocosolver")) {
                    source = stackTraceElements[i].getFileName() + ":" + stackTraceElements[i].getLineNumber();
                    break;
                }                
        }
        return source;
    }
    @Override
    public void post(Constraint... cs) throws SolverException {
        String source=getSource();
        // dump each constraint along source location
        for (Constraint c : cs) {
            System.err.println(source + " post: " + c);
        }
        super.post(cs);
    }
    
    @Override
    public void associates(Variable variable) {
        System.err.println(getSource() + " associates: " + variable.getName());
        super.associates(variable);
    }
};

Это сбросит такие вещи, как:

Vrp1RpV2.java:182 post: ARITHM ([prop(EQ_exp_47.EQ.mul_exp_48)])
Vrp1RpV2.java:182 associates: sum_exp_49
Vrp1RpV2.java:182 post: ARITHM ([prop(mul_exp_48.EQ.sum_exp_49)])
Vrp1RpV2.java:182 associates: EQ_exp_50
Vrp1RpV2.java:182 post: BASIC_REIF ([(stop2vehicle[2] = 1) <=> EQ_exp_50])
...

Отсюда можно увидеть, откуда берется sum_exp_49.

РЕДАКТИРОВАТЬ: добавлены Associates() благодаря предложению @cprudhom на https://gitter.im/chocoteam/choco-solver

person brunesto    schedule 23.03.2021