22
6
Introduction
Write a solver for integer linear programming.
Challenge
Your task is write a solver for integer linear programming (ILP). In ILP, linear inequalities of a set of unknowns (all of which are integers) are given, and the goal is to find the minimum or maximum of a linear function.
For example, for the inequalities (example taken from Mixed Integer Linear Programming)
4x+2y-15≤0
x+2y- 8≤0
x+ y- 5≤0
- x ≤0
- y ≤0
and the objective function 3x+2y
, the maximum of the objective function should be 12
(x=2,y=3
), while the minimum should be 0
(x=y=0
).
The input is given as an 2d array (or any equivalent following the standard specifications), each row corresponds to one inequality, with the exception of the final row. The numbers in the array are the coefficients, and the ≤0
part is always omitted. If there are n
elements in each row, it means there are n-1
unknowns.
The last row of the array correspond to the linear function. The coefficients are listed.
For example, the input array for the problem above is
[[4,2,-15],[1,2,-8],[1,1,-5],[-1,0,0],[0,-1,0],[3,2,0]].
The output should be the minimum and the maximum, given in any reasonable form.
For the following problem (two of the restrictions are taken away from the problem above):
[[4,2,-15],[1,2,-8],[1,1,-5],[3,2,0]].
The maximum is still 12
, but the minimum does not exist and the objective function can have arbitrarily large (in the sense of absolute value) negative values. In this case, the program should output 12
, following a falsy value that is decided by the answerer. Another case is that there are no solution at all, for example,
[[4,2,-15],[-1,-2,7],[-1,0,3],[0,1,0],[3,2,0]].
In this case, falsy values should be output as well. It would be nice to discern the case where the "optimal value" for the objective function is infinity and the case where there are no solutions at all, but this is not necessary.
The input only contains integer coefficients both for the inequalities and for the objective function. All the unknowns are also integers. The coefficient matrix of the inequalities is guaranteed to have full rank.
Test Cases
Credit to @KirillL. for finding a bug in the original test suite and deepening my understanding of ILP problems.
Input
Output
[[4,2,-15],[1,2,-8],[1,1,-5],[-1,0,0],[0,-1,0],[3,2,1]]
[1,13]
[[4,2,-15],[1,2,-8],[1,1,-5],[3,2,0]]
[-inf, 12]
[[4,2,-15],[-1,-2,7],[-1,0,3],[0,1,0],[3,2,0]]
[NaN, NaN]
[[-1,-1,-1,-1,-1,8],[1,1,1,1,0,0],[5,5,5,5,6,7]]
[55, inf]
[[-1,-1,-1,-1,-1,8],[1,1,1,1,0,0],[0,0,0,0,0,4]]
[4, 4]
[[4,2,-15],[-1,-2,7],[-1,0,3],[0,1,0],[0,0,4]]
[NaN, NaN]
Specs
No need to worry about exception handling.
This is code-golf, the lowest number of bytes wins.
Maximal number of unknowns:
9
. Maximal number of inequalities:12
.You can take input and provide output through any standard form, and you are free to choose the format.
As usual, default loopholes apply here.
Generalises https://codegolf.stackexchange.com/q/155460/194
– Peter Taylor – 2018-02-21T08:50:08.037You haven't explicitly mentioned it in the task description, but I suspect you are seeking original implementations of the algorithm, and not some boring code that makes use of existing libraries? Nevertheless, I played with your test cases in R and couldn't exactly reproduce the results.E.g., [55, inf] case only works when the variables are bounded to be non-negative. But then [-inf, 12] case also produces normal results [0, 12]. On the other hand, when the lower bound is -inf, the [55, inf] case fails to solve in both min and max scenarios. – Kirill L. – 2018-03-01T14:08:51.493
Yes I am looking for original implementations. – Weijun Zhou – 2018-03-01T14:13:34.903
@KirillL. Can you provide a vector where the function in test case [55, inf] gives a value smaller than 55? I just checked it against an online solver and the case seems to be fine. I have the following reasoning when making this test case: The first restriction requires the sum of all the free variables to be geq 8, but the second requires the sum of all except the last to be leq 0. If we ever try to decrease the goal by reducing any of the first 4 free var, it would require the final var to be increased by the same amount hence a larger value for the goal. – Weijun Zhou – 2018-03-01T14:46:18.387
Here is my snippet, although it won't work on TIO due to missing library. This gives 55, but exits with "model is unbounded" when I uncomment the set.bounds line. Quite possibly, the error is on my side, though. Could you also give a link to online solver?
– Kirill L. – 2018-03-01T16:03:38.633Here it is. I don't like the ads but at least it works. – Weijun Zhou – 2018-03-01T16:11:04.977
OK, that site specifically formulates the problem with x>=0. So, 55 test case is correct. But then I get 0 instead of -inf/error in [-inf, 12] case. I enter the constraints as 4 2 -1 15;1 2 -1 8;1 1 -1 5. Is that correct? – Kirill L. – 2018-03-01T19:03:16.977
Oh sorry I didn't notice the restriction. I don't mean the unknowns have to be nonnegative. So the issue is still with the 55. Can you give me a vector that gets a goal below 55 or point out what is wrong in my reasoning above? Thank you very much for your time and interest. Edit: I see what is faulty. Changed accordingly. – Weijun Zhou – 2018-03-02T08:07:20.660
@Sanchises In the challenge I stated that you can use any falsy value of your choice that is discernible from other cases as the output for cases without solutions. You can even use the same output for NaN and Inf and -Inf. – Weijun Zhou – 2018-03-02T09:22:45.250
@WeijunZhou Sorry, I misread that bit. Thanks. – Sanchises – 2018-03-02T09:29:45.270
The unknowns may be negative. Correct? – user202729 – 2018-03-03T17:17:34.120
Yes, the unknowns may be negative. – Weijun Zhou – 2018-03-03T18:00:12.570
@Scrooble You can use any set of value of your choice as the falsy value, as long as they are discernible from the cases where there are solutions, as stated in the question. – Weijun Zhou – 2018-03-04T00:10:55.440
@Scrooble Yes, you may output a space (or a letter, if you like). – Weijun Zhou – 2018-03-04T00:21:33.910
For test cases which function to optimize? still
3x+2y
? – l4m2 – 2018-04-15T10:15:52.3203x+2y
is specified by the last subarray[3,2,0]
– Weijun Zhou – 2018-04-16T03:16:35.133Can I output same value for both "all range" and "no range"? – l4m2 – 2018-04-20T04:18:07.017
You can take input and provide output through any standard form, and you are free to choose the format.
so can we split out the objective function? – l4m2 – 2018-04-20T04:19:59.323Yes, of course. – Weijun Zhou – 2018-04-20T05:29:47.893
Farewell, bounty. So tragic. – Khuldraeseth na'Barya – 2018-04-21T19:42:51.693