Integer Linear Programming
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.