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.
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 (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)