Write a solver for integer linear programming.
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
x=2,y=3), while the minimum should be
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
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
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):
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,
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.
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]
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:
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.