jade::basic_lemke< TValue > Class Template Reference

A template for a class that implements Lemke's algorithm. More...

#include <jade.lemke.hpp>

Collaboration diagram for jade::basic_lemke< TValue >:

Data Structures
struct	state
	Possible states of the algorithm. More...

Public Types
typedef TValue	value_type
	The value type. More...
typedef basic_matrix< value_type >	matrix_type
	The matrix type. More...
typedef std::vector< size_t >	labels_type
	The labels type. More...
typedef state::type	state_type
	The state type. More...

Public Member Functions
	basic_lemke (const matrix_type &tableau)
	Initializes a new instance of the class based on the specified tableau. More...
	basic_lemke (const matrix_type &m, const matrix_type &q)
	Initializes a new instance of the class based on the specified M and Q matrices. More...
	basic_lemke (const matrix_type &q, const matrix_type &a, const matrix_type &c, const matrix_type &b)
	Initializes a new instance of the class based on the specified Q and A matrices and c and b vectors. More...
std::string	format_label (const size_t label) const
const labels_type &	get_labels () const
matrix_type	get_output () const
size_t	get_pivot_col () const
size_t	get_pivot_row () const
state_type	get_state () const
const matrix_type &	get_tableau () const
bool	is_executing () const
bool	iterate ()
	Performs one step of the algorithm. More...
bool	solve ()
	Executes the algorithm until it has completed or has aborted. More...
std::string	str () const

Static Public Member Functions
static bool	solve (matrix_type &out, const matrix_type &tableau)
	Attempts to solve the linear complementarity problem using Lemke's Algorithm. If successful, this method stores the z vector into the output parameter. More...
static bool	solve (matrix_type &out, const matrix_type &m, const matrix_type &q)
	Attempts to solve the linear complementarity problem using Lemke's Algorithm. If successful, this method stores the z vector into the output parameter. More...
static bool	solve (matrix_type &out, const matrix_type &q, const matrix_type &a, const matrix_type &c, const matrix_type &b)
	Attempts to solve the linear complementarity problem using Lemke's Algorithm. If successful, this method stores the z vector into the output parameter. More...

Static Public Attributes
static constexpr auto	invalid_index
	The value associated with an invalid or unassigned index. More...

Detailed Description

template<typename TValue>
class jade::basic_lemke< TValue >

A template for a class that implements Lemke's algorithm.

Definition at line 18 of file jade.lemke.hpp.

Member Typedef Documentation

labels_type

template<typename TValue >

typedef std::vector<size_t> jade::basic_lemke< TValue >::labels_type

The labels type.

Definition at line 72 of file jade.lemke.hpp.

matrix_type

template<typename TValue >

typedef basic_matrix<value_type> jade::basic_lemke< TValue >::matrix_type

The matrix type.

Definition at line 69 of file jade.lemke.hpp.

state_type

template<typename TValue >

typedef state::type jade::basic_lemke< TValue >::state_type

The state type.

Definition at line 75 of file jade.lemke.hpp.

value_type

template<typename TValue >

typedef TValue jade::basic_lemke< TValue >::value_type

The value type.

Definition at line 66 of file jade.lemke.hpp.

Constructor & Destructor Documentation

basic_lemke() [1/3]

template<typename TValue >

jade::basic_lemke< TValue >::basic_lemke ( const matrix_type &  tableau )

inlineexplicit

Initializes a new instance of the class based on the specified tableau.

Parameters

tableau

The tableau.

Definition at line 81 of file jade.lemke.hpp.

            : _labels    ()
            , _pivot_col (invalid_index)
            , _pivot_row (invalid_index)
            , _state     (state::executing)
            , _tableau   (tableau)
        {
            assert(tableau.get_height() > 0);
            assert(tableau.get_width() == tableau.get_height() * 2 + 2);
 
            const auto & t  = _tableau;
            const auto   n  = t.get_height();
            const auto   z0 = n + n;
 
            //
            // Initially add the labels.
            //
            _labels.reserve(n);
            for (size_t i = 0; i < n; i++)
                _labels.push_back(i);
 
            //
            // The first pivot column is z_0; attempt to find the first pivot
            // row, but abort if necessary.
            //
            _pivot_col = z0;
            if (!_find_initial_pivot_row())
                _terminate(state::aborted_initialization);
        }

Here is the call graph for this function:

basic_lemke() [2/3]

template<typename TValue >

jade::basic_lemke< TValue >::basic_lemke ( const matrix_type &  m, const matrix_type &  q  )

inline

Initializes a new instance of the class based on the specified M and Q matrices.

Parameters

m	The M matrix.
q	The Q matrix.

Definition at line 116 of file jade.lemke.hpp.

            : basic_lemke(_create_tableau(m, q))
        {
        }

basic_lemke() [3/3]

template<typename TValue >

jade::basic_lemke< TValue >::basic_lemke ( const matrix_type &  q, const matrix_type &  a, const matrix_type &  c, const matrix_type &  b  )

inline

Initializes a new instance of the class based on the specified Q and A matrices and c and b vectors.

Parameters

q	The Q matrix.
a	The A matrix.
c	The c vector.
b	The b vector.

Definition at line 127 of file jade.lemke.hpp.

            : basic_lemke(_create_tableau(q, a, c, b))
        {
        }

Member Function Documentation

format_label()

template<typename TValue >

std::string jade::basic_lemke< TValue >::format_label ( const size_t  label ) const

inline

Returns

The specified label index as a string; labels are formatted as w_1, w_2, ..., w_n; z_0, z_1, ..., z_n; or q.

Parameters

label

The label to format.

Definition at line 140 of file jade.lemke.hpp.

        {
            const auto & t  = _tableau;
            const auto   n  = t.get_height();
            const auto   z1 = n;
            const auto   z0 = n + n;
            const auto   q  = n + n + 1;
 
            std::ostringstream out;
            if      (label  < z1) out << "w_" << label + 1;
            else if (label  < z0) out << "z_" << label + 1 - n;
            else if (label == z0) out << "z_0";
            else if (label ==  q) out << "q";
            else                  out << label;
            return out.str();
        }

Here is the call graph for this function:

Here is the caller graph for this function:

get_labels()

template<typename TValue >

const labels_type& jade::basic_lemke< TValue >::get_labels ( ) const

inline

Returns

The vector of labels.

Definition at line 162 of file jade.lemke.hpp.

        {
            return _labels;
        }

get_output()

template<typename TValue >

matrix_type jade::basic_lemke< TValue >::get_output ( ) const

inline

Returns

The output.

Definition at line 170 of file jade.lemke.hpp.

        {
            const auto & t  = _tableau;
            const auto   n  = t.get_height();
            const auto   z1 = n;
            const auto   q  = n + n + 1;
 
            matrix_type out (n, 1);
 
            for (size_t i = 0; i < n; i++)
            {
                const auto label = _labels[i];
                if (label >= z1)
                    out[label - z1] = t(i, q);
            }
 
            return out;
        }

Here is the call graph for this function:

Here is the caller graph for this function:

get_pivot_col()

template<typename TValue >

size_t jade::basic_lemke< TValue >::get_pivot_col ( ) const

inline

Returns

The pivot column, or invalid_index if the algorithm has terminated.

Definition at line 193 of file jade.lemke.hpp.

        {
            return _pivot_col;
        }

get_pivot_row()

template<typename TValue >

size_t jade::basic_lemke< TValue >::get_pivot_row ( ) const

inline

Returns

The pivot row, or invalid_index if the algorithm has terminated.

Definition at line 202 of file jade.lemke.hpp.

        {
            return _pivot_row;
        }

get_state()

template<typename TValue >

state_type jade::basic_lemke< TValue >::get_state ( ) const

inline

Returns

The state.

Definition at line 210 of file jade.lemke.hpp.

        {
            return _state;
        }

get_tableau()

template<typename TValue >

const matrix_type& jade::basic_lemke< TValue >::get_tableau ( ) const

inline

Returns

The tableau.

Definition at line 218 of file jade.lemke.hpp.

        {
            return _tableau;
        }

is_executing()

template<typename TValue >

bool jade::basic_lemke< TValue >::is_executing ( ) const

inline

Returns

True if the algorithm is still executing; otherwise, false.

Definition at line 226 of file jade.lemke.hpp.

        {
            return _state == state::executing;
        }

iterate()

template<typename TValue >

bool jade::basic_lemke< TValue >::iterate ( )

inline

Performs one step of the algorithm.

Returns

True if the still executing; otherwise, false.

Definition at line 235 of file jade.lemke.hpp.

        {
            if (_state != state::executing)
                return false;
 
            if (!_eliminate())
                return _terminate(state::aborted_elimination);
 
            if (!_relabel())
                return _terminate(state::completed);
 
            if (!_find_pivot_row())
                return _terminate(state::aborted_pivot);
 
            return true;
        }

Here is the caller graph for this function:

solve() [1/4]

template<typename TValue >

bool jade::basic_lemke< TValue >::solve ( )

inline

Executes the algorithm until it has completed or has aborted.

Returns

True if completed; otherwise, false.

Definition at line 256 of file jade.lemke.hpp.

        {
            while (_state == state::executing)
                iterate();
 
            return _state == state::completed;
        }

Here is the call graph for this function:

Here is the caller graph for this function:

solve() [2/4]

template<typename TValue >

static bool jade::basic_lemke< TValue >::solve ( matrix_type &  out, const matrix_type &  m, const matrix_type &  q  )

inlinestatic

Attempts to solve the linear complementarity problem using Lemke's Algorithm. If successful, this method stores the z vector into the output parameter.

Returns

True if successful; otherwise, false.

Parameters

out	The output vector.
m	The M matrix.
q	The q vector.

Definition at line 290 of file jade.lemke.hpp.

        {
            return solve(out, _create_tableau(m, q));
        }

Here is the call graph for this function:

solve() [3/4]

template<typename TValue >

static bool jade::basic_lemke< TValue >::solve ( matrix_type &  out, const matrix_type &  q, const matrix_type &  a, const matrix_type &  c, const matrix_type &  b  )

inlinestatic

Attempts to solve the linear complementarity problem using Lemke's Algorithm. If successful, this method stores the z vector into the output parameter.

Returns

True if successful; otherwise, false.

Parameters

out	The output vector.
q	The Q matrix.
a	The A matrix.
c	The c vector.
b	The b vector.

Definition at line 305 of file jade.lemke.hpp.

        {
            return solve(out, _create_tableau(q, a, c, b));
        }

Here is the call graph for this function:

solve() [4/4]

template<typename TValue >

static bool jade::basic_lemke< TValue >::solve ( matrix_type &  out, const matrix_type &  tableau  )

inlinestatic

Attempts to solve the linear complementarity problem using Lemke's Algorithm. If successful, this method stores the z vector into the output parameter.

Returns

True if successful; otherwise, false.

Parameters

out	The output vector.
tableau	The tableau.

Definition at line 271 of file jade.lemke.hpp.

        {
            basic_lemke lemke (tableau);
            if (!lemke.solve())
                return false;
 
            out = lemke.get_output();
            return true;
        }

Here is the call graph for this function:

str()

template<typename TValue >

std::string jade::basic_lemke< TValue >::str ( ) const

inline

Returns

A string representation of the class.

Definition at line 318 of file jade.lemke.hpp.

        {
            const auto & t = _tableau;
            const auto   n = t.get_height();
            const auto   q = n + n + 1;
 
            static const size_t cx = 8;
            std::ostringstream out;
            out << std::setprecision(3)
                << std::setw(cx) << "BV";
 
            for (size_t j = 0; j <= q; j++)
                out << std::setw(cx) << format_label(j);
            out << std::endl;
 
            for (size_t i = 0; i < n; i++)
            {
                out << std::setw(cx) << format_label(_labels[i]);
                for (size_t j = 0; j <= q; j++)
                    out << std::setw(cx) << t(i, j);
                out << std::endl;
            }
 
            out << std::endl
                << "state: " << state::str(_state) << std::endl
                << "pivot: ";
 
            if (_pivot_row == invalid_index)
                out << "<none>";
            else
                out << "{ " << format_label(_pivot_row)
                    << ", " << format_label(_pivot_col) << " }";
 
            out << std::endl << std::endl;
            return out.str();
        }

Here is the call graph for this function:

Field Documentation

invalid_index

template<typename TValue >

constexpr auto jade::basic_lemke< TValue >::invalid_index

staticconstexpr

Initial value:

=
            std::numeric_limits<size_t>::max()

The value associated with an invalid or unassigned index.

Definition at line 24 of file jade.lemke.hpp.

---

The documentation for this class was generated from the following file:

• jade.lemke.hpp