iconEuler Examples

Integer Linear Programming

by R. Grothmann

Euler has a two routines to solve integer linear programs: intsimplex
and lpsolve. intsimplex is implemented in the Euler language, and
uses the branch and bound method. lpsolve loads the LPSOLVE library,
which has been ported to Euler by Peter Notebeart.

This notebook demonstrates test cases.

Setup a test problem.
>A:=[10,8;9,11]; A:=1/A;
>b:=ones(rows(A),1);
>x:=0:0.1:15; y:=(b-A[:,1]*x)/A[:,2];
Plot the feasible restrictions.
>plot2d(x,y,a=0,b=20,c=0,d=20); insimg;

Integer Linear Programming

The function feasibleArea computes the corners of the feasible
set. This can be used to plot the area.
>xa:=feasibleArea(A,b); ...
>plot2d(xa[1],xa[2],filled=1,style="/",outline=1,add=1); insimg(antialiased=0);

Integer Linear Programming

And this is the target function.
>c:=[1,1]
[ 1  1 ]
We need <=.
>e:=-ones(size(b))
                 -1 
                 -1 
Solve this with the simplex method in Euler.
>{xs1,r,i}:=simplex(A,b,c,e,max=1); xs1,
      7.10526315789 
      2.31578947368 
The solution in fractional format.
>fracprint(xs1);
   135/19 
    44/19 
We find the optimal value with integer variables.
>intsimplex(A,b,c,max=1)
                  9 
                  0 
Or, if we require only y to be integer.
>intsimplex(A,b,c,i=[2],max=1)
      7.36363636364 
                  2 

A Combinatorial Problem

Here is another problem.

We take a square grid, and want to choose as many points as possible,
with the restriction that at each point at most one of the neighbors
(including the point itself) is chosen.

Euler has an incidence function, which can generate the incidence
matrix for a graph, or the incidence matrix of a rectangle.
>load incidence
Functions to create incidence matix for a graph, and
to solve resistance potential in a graph. For a demo
load the Resitance.en notebook.
For more information use "help incidence.e" or see the
user menu.
Set up the incidence matrix, where the points are connected to
themselves.
>n:=6; M:=id(n*n)+makeRectangleIncidence(n,n);
Add the restrictions that all points may be chosen only once.
>A:=M_id(n*n);
So we have (I+M).x<=1, and x<=1.
>b:=ones(rows(A),1);
The target function is the sum of x.
>c:=ones(1,cols(A));
All inequalities are <=.
>e:=-ones(rows(A),1);
The Euler Branch and Bound.
>xs1:=intsimplex(A,b,c,max=1);
Here is the layout of the chosen nodes.
>format(4,0); (redim(xs1',[n,n])), longformat;
  1   0   0   1   0   0 
  0   0   0   0   0   1 
  0   1   0   0   0   0 
  0   0   0   1   0   0 
  1   0   0   0   0   1 
  0   0   1   0   0   0 
>size(b)
[ 72  1 ]

LPSOLVE

Note that we have n^2=36 variables and 72 restrictions. So we can
solve only a 6x6 grid fast.

Using LPSOLVE, it is possible to solve much larger problems.
>load lpsolve
LPSOLVE package (ported by Peter Notebaert), and ilpsolve() routine.
The full documentation is available on 

http://lpsolve.sourceforge.net/5.5/Euler.htm
>n:=12; M:=id(n*n)+makeRectangleIncidence(n,n); ...
>A:=M_id(n*n); ...
>b:=ones(rows(A),1); ...
>c:=ones(1,cols(A)); ...
>e:=-ones(rows(A),1); ...
>xs1:=ilpsolve(A,b,c,e,max=1); ...
>format(4,0); (redim(xs1',[n,n])), longformat;
  1   0   0   1   0   0   1   0   0   1   0   0 
  0   0   0   0   0   0   0   0   0   0   0   1 
  0   1   0   0   1   0   0   1   0   0   0   0 
  0   0   0   0   0   0   0   0   0   1   0   0 
  1   0   0   1   0   0   1   0   0   0   0   1 
  0   0   0   0   0   0   0   0   1   0   0   0 
  0   1   0   0   1   0   0   0   0   0   1   0 
  0   0   0   0   0   0   1   0   0   0   0   0 
  1   0   0   1   0   0   0   0   1   0   0   1 
  0   0   0   0   0   1   0   0   0   0   0   0 
  0   0   1   0   0   0   0   0   0   1   0   0 
  1   0   0   0   1   0   0   1   0   0   0   1 

A Random Problem

Here is a random problem of the same kind.

We generate 100 points at random.
>x=random(100,1); y=random(100,1);
Then we generate a random incidence matrix with density 1/100.
>d=1/100; M=random(100,100)<d; M=max(M,M'); M=setdiag(M,0,1);
Compute the connected points and plot them.
>{xc,yc}=getGraph(x|y,M); ...
>plot2d(x,y,a=0,b=1,c=0,d=1,points=true); plot2d(xc,yc,add=true); ...
>insimg;

Integer Linear Programming

Now we do our combinatorial optimization.
>A:=M_id(100); ...
>b:=ones(rows(A),1); ...
>c:=ones(1,cols(A)); ...
>e:=-ones(rows(A),1); ...
>xs1:=ilpsolve(A,b,c,e,max=1);
And plot those points in red, which are chosen by the algorithm.
>i=nonzeros(xs1'); ...
>plot2d(x[i],y[i],a=0,b=1,c=0,d=1,points=true,color=red,style="[]#",add=true); ...
>insimg;

Integer Linear Programming

Examples Homepage