I am using the glpk.js library in an Angular application to solve an ILP problem. I have been using the library for some time now and it usually works well. I have encountered similar issues in the past, but I was able to sidestep them without finding out why they occurred. It might very well be the case, that I am not using the library correctly as their documentation is quite lacking.
I construct a "base" ILP problem and then I iterate over some array, construct additional constraints depending on each element of my array and try to solve the base ILP with the new constrains for each element.
I know there is a solution for each of the ILPs, but the solver returns PROBLEM HAS NO PRIMAL FEASIBLE SOLUTION for all but one of the ILPs.
My base ILP (in human readable format):
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
where the objective function is to minimise the sum of the p-variables.
when I apply the following additional constraints, the solver returns a solution (p10 = 1, all other p = 0):
rise0 = 0
rise1 = 0
rise2 = 0
rise3 = 0
rise4 = 1
rise5 = 0
p0 = 0
when I apply the following additional constraints, the solver returns no solution, even if p0 = 1, all other p = 0, solves the ILP:
rise0 = -1
rise1 = 0
rise2 = 0
rise3 = 0
rise4 = 0
rise5 = 0
p0 = 1
all the other sets of constrains also contain some rise with a negative value, which seems to cause the issue.
I am using the following configuration as input to the solver (JSON for the second example ILP):
{
"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"]
}
I assumed all integers (including negative) are allowed as solutions. But the only logical explanation to my problem seems to be that this is not the case. How can I enable negative integers as possible solutions?
I should have just researched the library more. There is an issue in the repository of the library that answers my question.
It really is the case that variables are bound to non-negative integers.
Variables with negative values can be expressed by splitting them into a positive and a negative part.
In my case it means I have to create a rise0plus and a rise0minus variable and modify my constrains as follows (for each rise variable):
p1 - p0 -rise0plus +rise0minus = 0
...
rise0plus -rise0minus = -1