LpSimplex

Purpose

Solve general linear programming problems.

lpSimplex solves problems of the form

${\begin{array}{cccccl}\min \limits _{x}&f(x)&=&c^{T}x&&\\s/t&x_{L}&\leq &x&\leq &x_{U}\\&b_{L}&\leq &Ax&\leq &b_{U}\\\end{array}}$

where $x,x_{L},x_{U}\in \mathbb {R} ^{n}$ , $c\in \mathbb {R} ^{n}$, $A\in \mathbb {R} ^{m\times n}$ and $b_{L},b_{U}\in \mathbb {R} ^{m}$.

Calling Syntax

Result = lpSimplex(Prob) or
Result = tomRun('lpSimplex', Prob, 1);

Inputs

Prob	Problem description structure. The following fields are used:
	QP.c	Constant vector.
	A	Constraint matrix for linear constraints.
	b_L	Lower bounds on the linear constraints.
	b_U	Upper bounds on the linear constraints.
	x_L	Lower bounds on the variables.
	x_U	Upper bounds on the variables.
	x_0	Starting point.
	Solver.Alg	Variable selection rule to be used: 0: Minimum reduced cost. 1: Bland's rule (default). 2: Minimum reduced cost. Dantzig's rule.
	QP.B	Active set B 0 at start: B(i) = 1: Include variable x(i) is in basic set. B(i) = 0: Variable x(i) is set on its lower bound. B(i) = -1: Variable x(i) is set on its upper bound.
	optParam	Structure with special fields for optimization parameters, see TOMLAB Appendix A. Fields used are: MaxIter, PriLev, wait, eps_f, eps_Rank, xTol and bTol.

Outputs

Result	Structure with result from optimization. The following fields are changed:
	x_k	Optimal point.
	f_k	Function value at optimum.
	g_k	Gradient value at optimum, c.
	v_k	Lagrange multipliers.
	x_0	Starting point.
	f_0	Function value at start.
	xState	State of each variable, described in Table 150.
	ExitFlag	0: Optimal solution found. 1: Maximal number of iterations reached. 2: Unbounded feasible region. 5: Too many active variables in given initial point. 6: No feasible point found with Phase 1. 10: Errors in input parameters. 11: Illegal initial x as input.
	Inform	If ExitF lag > 0, Inform = ExitF lag.
	QP.B	Optimal active set. See input variable QP.B.
	Solver	Solver used.
	SolverAlgorithm	Solver algorithm used.
	Iter	Number of iterations.
	FuncEv	Number of function evaluations. Equal to Iter.
	ConstrEv	Number of constraint evaluations. Equal to Iter.
	Prob	Problem structure used.

Description

The routine lpSimplex implements an active set strategy (Simplex method) for Linear Programming using an additional set of slack variables for the linear constraints. If the given starting point is not feasible then a Phase I objective is used until a feasible point is found.

M-files Used

ResultDef.m

See Also

qpSolve