我在Angular应用程序中使用glpk.js库来解决ILP问题。我已经使用图书馆一段时间了，它通常工作得很好。我过去也遇到过类似的问题，但我能够避开它们，而不去找出它们发生的原因。很可能是我没有正确使用这个库，因为它们的文档非常缺乏。
构造一个"base"ILP问题，然后我迭代一些数组，根据数组的每个元素构造额外的约束，并尝试用每个元素的新约束来解决基本ILP。
我知道每个ilp都有一个解，但是求解器对除了一个ilp之外的所有ilp都返回PROBLEM HAS NO PRIMAL FEASIBLE SOLUTION。
我的基本ILP(人类可读格式):
p0 >= 0
p1 >= 0
p2 >= 0
p3 >= 0
p4 >= 0
p5 >= 0
p6 >= 0
p7 >= 0
p0 +p1 +p2 +p3 +p4 +p5 +p6 +p7 >= 1
p1 -p0 -rise0 = 0
p2 +p3 -p1 -rise1 = 0
p4 -p2 -rise2 = 0
p6 -p4 -rise3 = 0
p10 -p6 -p5 -rise4 = 0
p5 -p3 -rise5 = 0
，其中目标函数是最小化p变量的和。
当我应用以下附加约束时，求解器返回一个解(p10 = 1，所有其他p = 0):
rise0 = 0
rise1 = 0
rise2 = 0
rise3 = 0
rise4 = 1
rise5 = 0
p0 = 0
当我应用以下附加约束时，求解器不返回任何解，即使p0 = 1，所有其他p = 0，也解决了ILP:
rise0 = -1
rise1 = 0
rise2 = 0
rise3 = 0
rise4 = 0
rise5 = 0
p0 = 1
所有其他的约束集合也包含一些带有负值的上升，这似乎是导致问题的原因。
我使用以下配置作为求解器的输入(第二个示例ILP的JSON):
{
"name":"p0",
"objective": {
"direction":1,
"name":"region",
"vars": [
{"name":"p0","coef":1},
{"name":"p1","coef":1},
{"name":"p2","coef":1},
{"name":"p3","coef":1},
{"name":"p4","coef":1},
{"name":"p5","coef":1},
{"name":"p6","coef":1},
{"name":"p7","coef":1}
]
},
"subjectTo": [
{"name":"c0","vars":[{"name":"p0","coef":1}],"bnds":{"type":2,"ub":0,"lb":0}},
{"name":"c1","vars":[{"name":"p1","coef":1}],"bnds":{"type":2,"ub":0,"lb":0}},
{"name":"c2","vars":[{"name":"p2","coef":1}],"bnds":{"type":2,"ub":0,"lb":0}},
{"name":"c3","vars":[{"name":"p3","coef":1}],"bnds":{"type":2,"ub":0,"lb":0}},
{"name":"c4","vars":[{"name":"p4","coef":1}],"bnds":{"type":2,"ub":0,"lb":0}},
{"name":"c5","vars":[{"name":"p5","coef":1}],"bnds":{"type":2,"ub":0,"lb":0}},
{"name":"c6","vars":[{"name":"p6","coef":1}],"bnds":{"type":2,"ub":0,"lb":0}},
{"name":"c7","vars":[{"name":"p7","coef":1}],"bnds":{"type":2,"ub":0,"lb":0}},
{"name":"c8","vars":[{"name":"p0","coef":1},{"name":"p1","coef":1},{"name":"p2","coef":1},{"name":"p3","coef":1},{"name":"p4","coef":1},{"name":"p5","coef":1},{"name":"p6","coef":1},{"name":"p7","coef":1}],"bnds":{"type":2,"ub":0,"lb":1}},
{"name":"c9","vars":[{"name":"p1","coef":1},{"name":"p0","coef":-1},{"name":"rise0","coef":-1}],"bnds":{"type":5,"ub":0,"lb":0}},
{"name":"c10","vars":[{"name":"p2","coef":1},{"name":"p3","coef":1},{"name":"p1","coef":-1},{"name":"rise1","coef":-1}],"bnds":{"type":5,"ub":0,"lb":0}},
{"name":"c11","vars":[{"name":"p4","coef":1},{"name":"p2","coef":-1},{"name":"rise2","coef":-1}],"bnds":{"type":5,"ub":0,"lb":0}},
{"name":"c12","vars":[{"name":"p6","coef":1},{"name":"p4","coef":-1},{"name":"rise3","coef":-1}],"bnds":{"type":5,"ub":0,"lb":0}},
{"name":"c13","vars":[{"name":"p7","coef":1},{"name":"p6","coef":-1},{"name":"p5","coef":-1},{"name":"rise4","coef":-1}],"bnds":{"type":5,"ub":0,"lb":0}},
{"name":"c14","vars":[{"name":"p5","coef":1},{"name":"p3","coef":-1},{"name":"rise5","coef":-1}],"bnds":{"type":5,"ub":0,"lb":0}},
{"name":"c15","vars":[{"name":"rise0","coef":1}],"bnds":{"type":5,"ub":-1,"lb":-1}},
{"name":"c16","vars":[{"name":"rise1","coef":1}],"bnds":{"type":5,"ub":0,"lb":0}},
{"name":"c17","vars":[{"name":"rise5","coef":1}],"bnds":{"type":5,"ub":0,"lb":0}},
{"name":"c18","vars":[{"name":"rise2","coef":1}],"bnds":{"type":5,"ub":0,"lb":0}},
{"name":"c19","vars":[{"name":"rise3","coef":1}],"bnds":{"type":5,"ub":0,"lb":0}},
{"name":"c20","vars":[{"name":"rise4","coef":1}],"bnds":{"type":5,"ub":0,"lb":0}},
{"name":"c21","vars":[{"name":"p0","coef":1}],"bnds":{"type":5,"ub":1,"lb":1}}
],
"binaries":[],
"generals": ["p0","p1","p2","p3","p4","p5","p6","p7","rise0","rise1","rise2","rise3","rise4","rise5"]
}
我假设所有整数(包括负数)都可以作为解。但对我的问题唯一合乎逻辑的解释似乎是事实并非如此。如何使负整数成为可能的解决方案?
我应该多研究一下图书馆。在库的存储库中有一个问题，它回答了我的问题。
确实是这样，变量被绑定到非负整数。
带有负值的变量可以分为正负两部分来表示。
在我的情况下，这意味着我必须创建一个rise0plus和rise0minus变量，并修改我的约束如下(为每个上升变量):
p1 - p0 -rise0plus +rise0minus = 0
...
rise0plus -rise0minus = -1