iconEuler Reference

Linear Programming

Simplex and integer Simplex routines.

This file contains an interface to the builtin Simplex method, a method for integer programs, and an interface to the LPSolve package. There is also a function, which can be used to plot feasible areas in the plane.

Simplex Algorithms

function simplex (A:real, b:real column, c:real vector, ..
    eq=-1, restrict=1, max:integer=0, min:integer=1, check:integer=0)

  Minimize c.x with respect to A.x<=b and x>=0 or other restrictions.
  
  Simplex method for maximization or minimization of a linear
  function with linear constrains, and restricted or unrestricted
  variables. The function calls the builtin Simplex algorithm.
  
  Minimizes or maximizes c.x with the conditions A.x <= b, or A.x >=
  b, or A.x == b, and optionally x>=0. The type of the condition is
  contained in a column vector eq. It is in each row -1 for <=, 1 for
  >=, 0 for equality. The column vector restrict determines, which
  variables should be restriced to be non-negative (1), or
  non-positive (-1), or unrestricted (0). If max=1, the function
  maximizes the target function.
  
  A : real matrix (nxm)
  b : real column vector (nx1)
  c : real row vector (1xm)
  eq : real column vector with entries -1, 0, or 1 (nx1)
  restrict : real row vector with entries 0, 1, or -1 (1xm)
  max,min : flags to maximize and minimize (set either of them)
  check: If true, an error will occur for unbounded or not feasible
  problems. If false, you need to check the r flag for the result.
  
  The return value is {x,r,i}, where x is the solution, and r has the
  following meaning:
  
  r=0 : success,
  r=-1 : no feasible point,
  r=1 : the problem is not bounded.
  
  i is a column vector, which is 1 for each active side condition.
  
  It must be remarked, that an equality condition generates two
  conditions. So i might be longer than the original number of
  conditions.
  
  >A=[1,1;4,5]; b=[1000;4500]; // x+y<=1000, 4x+5y<=4500
  >eq=[-1;-1]; // both equations <= (the default)
  >c=[5,6]; // 4x+5y -> Max.
  >restr=[1,1]; // x,y>=0 (the default)
  >simplex(A,b,c,eq,restr,>max,>check) // check for errors
  500
  500
  
  See: 
simplex (Euler Core),
intsimplex (Linear Programming)
function feasibleArea (A:real, b:real column, eq:=-1, restrict:=1)
function intsimplex (A:real, b:real column, c:real vector,
    eq=-1, restrict=1, max:integer=0, min:integer=1, i="all",
    check=false, ire:integer vector=none)

  Minimize c.x=b under the conditions A.x<=b, x integer, x>=0.
  
  This is the branch and bound algorithm for integer linear problems.
  It is implemented in the Euler language. There is a faster and more
  sophisticated algorithm ilpsolve.
  
  Minimizes or maximizes c.x with the conditions A.x <= b, or A.x >=
  b, or A.x == b, x integer. and optionally x>=0. The parameter i is a
  row vector of indices of variables, which should be positive. If
  i="all", all variables should be integer. This is the default.
  
  A : real matrix (nxm)
  b : real column vector (nx1)
  c : real row vector (1xm)
  eq : real column vector with entries -1, 0, or 1 (nx1)
  restrict : vector with non-negative restricted variables. Default
  is 1.
  max,min : flags to maximize and minimize
  i : real row vector with indices of integer variables ire :
  Alternative to i. Row vector with 0,1.
  
  Note that i and re work in different ways. This is due to the
  compatibility with ilpsolve. Use ire instead.
  
  check : If true, the function will throw an error, if the problem
  is unbounded, or has no feasible point.
  
  The function returns {x,r,a}, where x is the solution of the problem
  if r=0. a is the optimal value.
  
  >A=random(20,3)+1; b=ones(20,1)*1000; // random problem
  >c=ones(1,3);
  >intsimplex(A,b,c,>max,>check)
  193
  348
  41
  
  See: 
simplex (Euler Core),
ilpsolve (Linear Programming)

LPSolve Package

LPSOLVE package (ported by Peter Notebaert), and ilpsolve() routine. The full documentation is available on

This package provides contains much more effective routines than the intsimplex function.

defaultilpsolvedll:=0;
function startlpsolve ()

  Start the LPSOLVE DLL.
function ilpsolve (A, b, c, eq = -1,
    vlb = [], vub = [], i = "all",
    scalemode = 0, keep = 0, max = 0, ire = none)

  Minimize f.x subject a.x<=b, vlb<=x<=vub, and integer x.
  
  This routine is contained in the lpsolve DLL, which is loaded, if
  you load the lpsolve package with "load lpsolve". The routines have
  been ported to Euler by Peter Notebaert.
  
  The function solves the linear integer problem
  
  max v = f'*x
  a*x <> b
  vlb <= x <= vub
  x[i] are integer
  
  Arguments: The first four arguments are required.
  
  f: n vector of coefficients for a linear objective function.
  a: m by n matrix representing linear constraints.
  b: m vector of right sides for the inequality constraints.
  e: m vector that determines the sense of the inequalities:
  e(i) = -1  ==> Less Than
  e(i) =  0  ==> Equals
  e(i) =  1  ==> Greater Than
  vlb: n vector of lower bounds. If empty or omitted,
  then the lower bounds are set to zero.
  vub: n vector of upper bounds. May be omitted or empty.
  xint: vector of integer variables. May be omitted or empty.
  scalemode: scale flag. Off when 0 or omitted.
  keep: Flag for keeping the lp problem after it's been solved.
  If omitted, the lp will be deleted when solved.
  
  Output: The function returns {x,obj,duals}
  
  x: Optimal value of the decision variables.
  obj: Optimal value of the objective function.
  duals: solution of the dual problem.
  
  Loads the DLL once, when it is called.
  
  >A=random(50,5)+1; b=ones(50,1)*1000; // random problem
  >c=ones(1,5);
  >load lpsolve;
  >ilpsolve(A,b,c,i=[],>max,>check) // no integer problem
  61.7789496937
  156.76464272
  76.0735082666
  60.3330148438
  232.179101403
  >ilpsolve(A,b,c,>max,>check)
  62
  157
  76
  60
  
  See: 
intsimplex (Linear Programming),
lpsolve (LPSOLVE package)

Documentation Homepage