21
\$\begingroup\$

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 , 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.

\$\endgroup\$
  • \$\begingroup\$ Generalises codegolf.stackexchange.com/q/155460/194 \$\endgroup\$ – Peter Taylor Feb 21 '18 at 8:50
  • \$\begingroup\$ You 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. \$\endgroup\$ – Kirill L. Mar 1 '18 at 14:08
  • \$\begingroup\$ Yes I am looking for original implementations. \$\endgroup\$ – Weijun Zhou Mar 1 '18 at 14:13
  • \$\begingroup\$ @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. \$\endgroup\$ – Weijun Zhou Mar 1 '18 at 14:46
  • \$\begingroup\$ 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? \$\endgroup\$ – Kirill L. Mar 1 '18 at 16:03
2
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.