Prev Next

@(@\newcommand{\W}[1]{ \; #1 \; } \newcommand{\R}[1]{ {\rm #1} } \newcommand{\B}[1]{ {\bf #1} } \newcommand{\D}[2]{ \frac{\partial #1}{\partial #2} } \newcommand{\DD}[3]{ \frac{\partial^2 #1}{\partial #2 \partial #3} } \newcommand{\Dpow}[2]{ \frac{\partial^{#1}}{\partial {#2}^{#1}} } \newcommand{\dpow}[2]{ \frac{ {\rm d}^{#1}}{{\rm d}\, {#2}^{#1}} }@)@
abs_normal: Solve a Linear Program Using Simplex Method

Syntax
ok = simplex_method(level, b, A, c, maxitr, xout)
Prototype 

template <class Vector>
bool simplex_method(
     size_t        level   ,
     const Vector& A       ,
     const Vector& b       ,
     const Vector& c       ,
     size_t        maxitr  ,
     Vector&       xout    )

Source
This following is a link to the source code for this example: simplex_method.hpp .

Problem
We are given @(@ A \in \B{R}^{m \times n} @)@, @(@ b \in \B{R}^m @)@, @(@ c \in \B{R}^n @)@. This routine solves the problem @[@ \begin{array}{rl} \R{minimize} & g^T x \; \R{w.r.t} \; x \in \B{R}_+^n \\ \R{subject \; to} & A x + b \leq 0 \end{array} @]@

Vector
The type Vector is a simple vector with elements of type double.

level
This value is less than or equal two. If level == 0 , no tracing is printed. If level >= 1 , a trace @(@ x @)@ and the corresponding objective @(@ z @)@ is printed at each iteration. If level == 2 , a trace of the simplex Tableau is printed at each iteration.

A
This is a row-major representation of the matrix @(@ A @)@ in the problem.

b
This is the vector @(@ b @)@ in the problem.

c
This is the vector @(@ c @)@ in the problem.

maxitr
This is the maximum number of simplex iterations to try before giving up on convergence.

xout
This argument has size is n and the input value of its elements does no matter. Upon return it is the primal variables corresponding to the problem solution.

ok
If the return value ok is true, a solution has been found.

Example
The file simplex_method.cpp contains an example and test of simplex_method. It returns true if the test passes and false otherwise.
Input File: example/abs_normal/simplex_method.hpp