Можно ли определить ограничение несовместимости?

Question

Я использую jsLPSolver для решения задачи целочисленного программирования.

У меня проблемы с настройкой модели с учетом ограничений несовместимости.У меня есть следующая модель:

{
    "optimize": "cost",
    "opType": "min",
    "constraints": {
        "c1": { "min": 36000.0, "max": 36800.0 },
        "c2": { "min": 12000.0, "max": 12800.0 },
        "c3": { "equal": 1000.0 }
    },
    "variables": {
        "p1": { "c1": 0, "c2": 0, "c3": 1, "cost": 437.47, },
        "p2": { "c1": 0, "c2": 60.0, "c3": 1, "cost": 1964.49, },
        "p3": { "c1": 34.0, "c2": 0, "c3": 1, "cost": 1428.98, },
        "p4": { "c1": 46.0, "c2": 0, "c3": 1, "cost": 1973.11, }
    },
    "ints": { "p1": 1, "p2": 1, "p3": 1, "p4": 1 }
}

и выполнимый результат

{ bounded: true, feasible: true, p2: 200, p3: 66, p4: 734, result: 1935473.42 }

Однако существует ограничение, что p3 и p4 не может быть вместе в решении, поскольку они несовместимы.

Можно ли определить ограничение несовместимости, чтобы определить, что p3 и p4 являются несовместимыми переменными?

РЕДАКТИРОВАТЬ

Я подумываю об использовании ограничения типа p3 + p4 = 0:

{
    "optimize": "cost",
    "opType": "min",
    "constraints": {
        "c1": { "min": 36000.0, "max": 36800.0 },
        "c2": { "min": 12000.0, "max": 12800.0 },
        "c3": { "equal": 1000.0 },
        "incompatible": { "equal": 0.0 }
    },
    "variables": {
        "p1": { "c1": 0, "c2": 0, "c3": 1, "cost": 437.47, "incompatible": 0.0 },
        "p2": { "c1": 0, "c2": 60.0, "c3": 1, "cost": 1964.49, "incompatible": 0.0 },
        "p3": { "c1": 34.0, "c2": 0, "c3": 1, "cost": 1428.98, "incompatible": 1.0 },
        "p4": { "c1": 46.0, "c2": 0, "c3": 1, "cost": 1973.11, "incompatible": 1.0 }
    },
    "ints": { "p1": 1, "p2": 1, "p3": 1, "p4": 1 }
}

, но посмотрите, что происходит с решением в этом случае:

{ bounded: true, feasible: false, p2: 200, p3: -3000, p4: 3000, result: 0 }

как видно по https://runkit.com/tetrimesquita/incompatible-contraint,, что правильно , но невозможно .

Answer 1

Теперь я вижу, что p3 и p4 непрерывны. (Если они на самом деле являются двоичными, см. этот ответ .) В этом случае добавьте две новые двоичные переменные, скажем z3 и z4, которые равны 1, если p3 и p4 (соответственно ) больше нуля:

p3 <= Mz3
p4 <= Mz4

, где M - большое число. Затем добавьте ограничение

z3 + z4 <= 1

Первые два ограничения говорят, что если p3 > 0, то z3 должно равняться 1 (и аналогично для p4 и z4). Третье ограничение говорит, что самое большее из z3 и z4 может равняться 1, то есть самое большее одно из p3 и p4 может быть положительным.

Если p3 и p4 не ограничены (допускается быть положительным или отрицательным) и вы хотите, чтобы не более одного из них было ненулевым , то также добавьте:

-p3 <= Mz3
-p4 <= Mz4

Answer 2

Если p3 и p4 являются двоичными, вы можете просто использовать

p3 + p4 <= 1

Или, если вы хотите, чтобы точно один из них равнялся 1, тогда используйте

p3 + p4 = 1

Я не знаком с синтаксисом для jsLPSolver, но приведенные выше ограничения обеспечивают логику.

Answer 3

Вероятно, не самая элегантная версия, но это должно сделать это:

var solver = require("javascript-lp-solver");

var model = {
    "optimize": "cost",
    "opType": "min",
    "constraints": {
        "c1": { "min": 36000.0, "max": 36800.0 },
        "c2": { "min": 12000.0, "max": 12800.0 },
        "c3": { "equal": 1000.0 }
    },
    "variables": {
        "p1": { "c1": 0, "c2": 0, "c3": 1, "cost": 437.47, },
        "p2": { "c1": 0, "c2": 60.0, "c3": 1, "cost": 1964.49, },
        "p3": { "c1": 34.0, "c2": 0, "c3": 1, "cost": 1428.98, },
    },
    "ints": { "p1": 1, "p2": 1, "p3": 1}
}

var results_p3 = solver.Solve(model);

var model = {
    "optimize": "cost",
    "opType": "min",
    "constraints": {
        "c1": { "min": 36000.0, "max": 36800.0 },
        "c2": { "min": 12000.0, "max": 12800.0 },
        "c3": { "equal": 1000.0 }
    },
    "variables": {
        "p1": { "c1": 0, "c2": 0, "c3": 1, "cost": 437.47, },
        "p2": { "c1": 0, "c2": 60.0, "c3": 1, "cost": 1964.49, },
        "p4": { "c1": 46.0, "c2": 0, "c3": 1, "cost": 1973.11, }
    },
    "ints": { "p1": 1, "p2": 1, "p4": 1 }
}

var results_p4 = solver.Solve(model);

var finalResults = (results_p3.feasible && (results_p3.result < results_p4.result)) ? results_p3 : results_p4;

console.log(results_p3);
console.log(results_p4);
console.log(finalResults);

Идея состоит в том, что вы запускаете модель дважды - один раз, когда p3 фиксируется, и один раз, когда p4 фиксируется. Затем вы берете решение, которое подчиняется ограничениям и дает лучший результат [1].

Смотрите вывод здесь:

https://runkit.com/dionhaefner/so-incompatible-constraint

[1] Возможно, вам следует немного отполировать эту последнюю проверку. Например, что должно произойти, если оба результата невозможны? Что если у обоих результат 0? Возможно, вам также придется проверить свойство bounded.