4

我正在使用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所示，这是正确但不可行的。

4

3 回答 3

1

我现在看到了，p3并且p4是连续的。（如果它们实际上是二进制的，请参阅此答案。）在这种情况下，添加两个新的二进制变量，例如z3和z4，如果p3和p4（分别）大于零，则等于 1：

p3 <= Mz3
p4 <= Mz4

哪里M是大数。然后添加一个约束

z3 + z4 <= 1

前两个约束表示 if p3 > 0, thenz3必须相等1（对于 and 也类似p4）z4。第三个约束条件至多有一个z3和z4可以等于1，即至多有一个p3和p4可以是正数。

如果p3andp4不受限制（允许为正或负）并且您希望最多要求其中一个为非零，则还添加：

-p3 <= Mz3
-p4 <= Mz4
于 2019-05-13T13:26:58.050 回答
0

如果p3和p4是二进制的，你可以使用

p3 + p4 <= 1

或者，如果您希望其中一个恰好等于 1，则使用

p3 + p4 = 1

我不熟悉 jsLPSolver 的语法，但上面的约束提供了逻辑。

于 2019-05-13T13:18:00.330 回答
0

可能不是最优雅的版本，但应该这样做：

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属性。

于 2019-05-13T12:24:24.013 回答