#StackBounty: #code-golf #math #optimization Integer Linear Programming

Bounty: 50

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

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],[2,3,4,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.


Get this bounty!!!

Leave a Reply