Integer Linear Programming

Question

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.

Answer 1

Python 3, 534 bytes

import itertools as t
import operator as o
I=float("inf")
e=lambda p,A:sum([i[0]*i[1]for i in zip(p,A[:-1])])+A[-1]
def w(x,j):
	d=len(x[0])-1;C=[0]*d;v,w=I,I
	while 1:
		L={(*n,):(sum([0 if e(n,A)<=0 else e(n,A)for A in x[:-1]]),j*e(n,x[-1]))for n in [[sum(a) for a in zip(C,c)]for c in t.product(*[[-1,0,1]]*d)]};C,P=min(L.items(),key=o.itemgetter(1))[0],C;v,w,p,q=L[C][0],L[C][1],v,w
		if(all([e(C,A)<=e(P,A)for A in x[:-1]]))*(j*(e(C,x[-1])-e(P,x[-1]))<0)+(p==v>0):return I
		if(p==v)*(q<=w):return j*q
f=lambda x:(w(x,1),w(x,-1))

Try it online!

Overview

It is an iterative algorithm, starting from the origo. It collects the neighbour positions and assigns a potential function: x:(a,b) where x is the position, a is the sum of the position's distances from the half-spaces of each linear inequality, b is the value of the objective at that position.

x:(a,b) < y:(c,d) iff a<c or a=c and b<d

The iteration stops, when:

• the first coordinate of the potential hasn't decreased and positive: the system is infeasible
• the distance from every half-space has decreased just like the objective: the system is unbounded.
• none of previous and the potential hasn't decreased: it is the optimal value.

Answer 2

Matlab, 226 bytes

DISCLAIMER: Not an "original" implementation, only for fun.

Simple solution taking advantage of the intlinprog function:

function r=f(a);b=-1*a(1:end-1,end);p=a(end,1:end-1);c=a(1:end-1,1:end-1);[~,f,h]=intlinprog(p,1:size(a,2)-1,c,b);[~,g,i]=intlinprog(-p,1:size(a,2)-1,c,b);s=[inf,nan,f];t=[inf,nan,g];r=a(end,end)+[s(4-abs(h)) -t(4-abs(i))];end

It returns the optimal values, or inf (-inf) if the problem is unbounded or nan if it is infeasible.

a = [4 2 -15; 1 2 -8; 1 1 -5; -1 0 0; 0 -1 0; 3 2 1]
b = [4 2 -15; 1 2 -8; 1 1 -5; 3 2 0]
c = [4 2 -15; -1 -2 7; -1 0 3; 0 1 0; 3 2 0]
d = [-1 -1 -1 -1 -1 8;  1 1 1 1 0 0; 0 0 0 0 0 4]
e = [4 2 -15; -1 -2 7; -1 0 3; 0 1 0; 0 0 4]

>> f(a)
ans =

     1    13

>> f(b)
ans =

   Inf    12

>> f(c)
ans =

   NaN   NaN

>> f(d)
ans =

     4     4

>> f(e)
ans =

   NaN   NaN