simplex_method.hpp File Reference

#include "config.hpp"
#include <cstddef>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include "factory.hpp"
#include "exception.hpp"
#include "cmp.hpp"
#include "vector.hpp"
#include "matrix.hpp"
#include "gauss.hpp"
#include "std_import.hpp"

Go to the source code of this file.

Namespaces

namespace  Arageli
namespace  Arageli::simplex_method
namespace  Arageli::ctrl
namespace  Arageli::ctrl::simplex_method

Classes

struct  Arageli::simplex_method::rule_s_primal_first
 Rule to choice the first appropriate column as pivot in the primal simplex method. More...
struct  Arageli::simplex_method::rule_r_primal_first
 Rule to choice the first appropriate row as pivot in the primal simplex method. More...
struct  Arageli::simplex_method::rule_r_primal_lex
 Rule to choice the lexmin appropriate row as pivot in the primal simplex method. More...
struct  Arageli::simplex_method::rule_r_dual_first
 Rule to choice the first appropriate row as pivot in the dual simplex method. More...
struct  Arageli::simplex_method::rule_s_dual_first
 Rule to choice the first appropriate column as pivot in the dual simplex method. More...
struct  Arageli::ctrl::simplex_method::primal_row_iters_idler
 Default controller for the primal_row_iters function. It's doing nothing. More...
class  Arageli::ctrl::simplex_method::primal_row_iters_idler::abort
struct  Arageli::ctrl::simplex_method::primal_col_iter_idler
 Default controller for the primal_col_iter function. It's doing nothing. More...
struct  Arageli::ctrl::simplex_method::primal_col_iter_slog< Stream >
 Simple controller for the primal_col_iter function. It outputs into a stream. More...
struct  Arageli::ctrl::simplex_method::primal_col_iters_idler
 Default controller for the primal_col_iters function. It's doing nothing. More...
struct  Arageli::ctrl::simplex_method::dual_col_iter_idler
 Default controller for the dual_col_iter function. It's doing nothing. More...
struct  Arageli::ctrl::simplex_method::dual_col_iter_slog< Stream >
 Simple controller for the primal_col_iter function. It outputs into a stream. More...
struct  Arageli::ctrl::simplex_method::dual_col_iters_idler
 Default controller for the dual_col_iters function. It's doing nothing. More...
struct  Arageli::ctrl::simplex_method::basis_create_by_artificial_idler
 Default controller for the basis_create_by_artificial function. It's doing nothing. More...
class  Arageli::ctrl::simplex_method::basis_create_by_artificial_idler::abort
struct  Arageli::ctrl::simplex_method::basis_artificial_idler
 Default controller for the primal_row_iters function. It's doing nothing. More...
class  Arageli::ctrl::simplex_method::basis_artificial_idler::abort
struct  Arageli::ctrl::simplex_method::primal_row_with_artificial_basis_idler
 Default controller for the primal_row_with_artificial_basis function. It's doing nothing. More...
struct  Arageli::ctrl::simplex_method::gomory1_iter_idler
 Default controller for the primal_row_iters function. It's doing nothing. More...
class  Arageli::ctrl::simplex_method::gomory1_iter_idler::abort
struct  Arageli::ctrl::simplex_method::gomory1_iters_idler
 Default controller for the primal_row_iters function. It's doing nothing. More...
class  Arageli::ctrl::simplex_method::gomory1_iters_idler::abort
struct  Arageli::simplex_method::linear_prog_task_base
class  Arageli::simplex_method::linear_prog_task< T, REFCNT >
 Model of the linear programming task with partial integer constraints. More...

Looking for parts of a simplex table that is not satisfied certain criterion.

template<typename T1, bool REFCNT1, typename T2, bool REFCNT2>
matrix< T1, REFCNT1 >::size_type Arageli::simplex_method::find_row_notallow (const matrix< T1, REFCNT1 > &a, const vector< T2, REFCNT2 > &basis)
 Finds the first not allowable basis column in a row simplex table.
template<typename T1, bool REFCNT1, typename T2, bool REFCNT2>
matrix< T1, REFCNT1 >::size_type Arageli::simplex_method::find_col_notallow (const matrix< T1, REFCNT1 > &a, const vector< T2, REFCNT2 > &nonbasis)
 Finds the first not allowable basis row in a column simplex table.
template<typename T1, bool REFCNT1>
matrix< T1, REFCNT1 >::size_type Arageli::simplex_method::find_primal_notallow (const matrix< T1, REFCNT1 > &a)
 Finds the first not allowable row in a primal simplex table.
template<typename T1, bool REFCNT1>
matrix< T1, REFCNT1 >::size_type Arageli::simplex_method::find_dual_notallow (const matrix< T1, REFCNT1 > &a)
 Finds the first not allowable column in a dual simplex table.

Determination type of a simplex table.

template<typename T1, bool REFCNT1, typename T2, bool REFCNT2>
bool Arageli::simplex_method::is_row_allow (const matrix< T1, REFCNT1 > &a, const vector< T2, REFCNT2 > &basis)
 Returns true if simplex table 'a' with basis 'basis' is row simplex table.
template<typename T1, bool REFCNT1, typename T2, bool REFCNT2>
bool Arageli::simplex_method::is_col_allow (const matrix< T1, REFCNT1 > &a, const vector< T2, REFCNT2 > &nonbasis)
 Returns true if simplex table 'a' with nonbasis 'nonbasis' is column simplex table.
template<typename T1, bool REFCNT1>
bool Arageli::simplex_method::is_primal_allow (const matrix< T1, REFCNT1 > &a)
 Returns true if simplex table 'a' is primal allowable.
template<typename T1, bool REFCNT1>
bool Arageli::simplex_method::is_dual_allow (const matrix< T1, REFCNT1 > &a)
 Returns true if simplex table 'a' is dual allowable.

The primal row iterations on a row simplex table.

template<typename T_q, bool REFCNT_q, typename T_basis, bool REFCNT_basis, typename T_pivot, typename Rule_s, typename Rule_r>
result_kind Arageli::simplex_method::primal_row_iter (matrix< T_q, REFCNT_q > &q, vector< T_basis, REFCNT_basis > &basis, T_pivot &prow, T_pivot &pcol, Rule_s rule_s, Rule_r rule_r)
 Performs one primal row iteration on a row simplex table.
template<typename T_q, bool REFCNT_q, typename T_basis, bool REFCNT_basis>
result_kind Arageli::simplex_method::primal_row_iter (matrix< T_q, REFCNT_q > &q, vector< T_basis, REFCNT_basis > &basis)
 Performs one primal row iteration on a row simplex table.
template<typename T_q, bool REFCNT_q, typename T_basis, bool REFCNT_basis, typename Rule_s, typename Rule_r>
result_kind Arageli::simplex_method::primal_row_iter (matrix< T_q, REFCNT_q > &q, vector< T_basis, REFCNT_basis > &basis, Rule_s rule_s, Rule_r rule_r)
 Performs one primal row iteration on a row simplex table.
template<typename T_q, bool REFCNT_q, typename T_basis, bool REFCNT_basis, typename T_pivot>
result_kind Arageli::simplex_method::primal_row_iter_pivotout (matrix< T_q, REFCNT_q > &q, vector< T_basis, REFCNT_basis > &basis, T_pivot &prow, T_pivot &pcol)
 Performs one primal row iteration on a row simplex table.

Artificial basis method.

template<typename T1, bool REFCNT1, typename T2, bool REFCNT2>
void Arageli::simplex_method::artificial_basis_create (matrix< T1, REFCNT1 > &a, vector< T2, REFCNT2 > &basis)
 Creates artificial task to find valid basis by the artifical basis method.

The Gomory's algorithms.

template<typename T, bool REFCNT, typename Prow>
result_kind Arageli::simplex_method::gomory1_clip (matrix< T, REFCNT > &t, Prow &prow)
 Creates Gomory's clip on optimal column simplex table.
template<typename T, bool REFCNT>
result_kind Arageli::simplex_method::gomory1_clip (matrix< T, REFCNT > &t)
 Creates Gomory's clip on optimal column simplex table.

Defines

#define ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE_SIMPLEX_METHOD

Enumerations

enum  Arageli::simplex_method::result_kind { Arageli::simplex_method::rk_found, Arageli::simplex_method::rk_empty, Arageli::simplex_method::rk_infinite, Arageli::simplex_method::rk_nonoptimal }
 General kind of result of one or more iterations of the simplex method. More...

Functions

template<typename T_q, bool REFCNT_q, typename T_basis, bool REFCNT_basis, typename Rule_s, typename Rule_r, typename Ctrler>
result_kind Arageli::simplex_method::primal_row_iters (matrix< T_q, REFCNT_q > &q, vector< T_basis, REFCNT_basis > &basis, Rule_s rule_s, Rule_r rule_r, Ctrler ctrler)
 Performs numerous primal row iterations on a row simplex table.
template<typename T_q, bool REFCNT_q, typename T_basis, bool REFCNT_basis>
result_kind Arageli::simplex_method::primal_row_iters (matrix< T_q, REFCNT_q > &q, vector< T_basis, REFCNT_basis > &basis)
 Performs numerous primal row iterations on a row simplex table.
template<typename T_q, bool REFCNT_q, typename T_basis, bool REFCNT_basis, typename Ctrler>
result_kind Arageli::simplex_method::primal_row_iters (matrix< T_q, REFCNT_q > &q, vector< T_basis, REFCNT_basis > &basis, Ctrler ctrler)
 Performs numerous primal row iterations on a row simplex table.
template<typename T_Q, bool REFCNT_Q, typename T_nonbasis, bool REFCNT_nonbasis, typename Rule_s, typename Rule_r, typename Ctrler>
result_kind Arageli::simplex_method::primal_col_iters (matrix< T_Q, REFCNT_Q > &Q, vector< T_nonbasis, REFCNT_nonbasis > &nonbasis, Rule_s rule_s, Rule_r rule_r, Ctrler ctrler)
 Performs numerous primal colunt iterations on a column simplex table.
template<typename T_Q, bool REFCNT_Q, typename T_nonbasis, bool REFCNT_nonbasis>
result_kind Arageli::simplex_method::primal_col_iters (matrix< T_Q, REFCNT_Q > &Q, vector< T_nonbasis, REFCNT_nonbasis > &nonbasis)
 Performs numerous primal column iterations on a column simplex table.
template<typename T_Q, bool REFCNT_Q, typename T_nonbasis, bool REFCNT_nonbasis, typename Rule_s, typename Rule_r, typename Ctrler>
result_kind Arageli::simplex_method::dual_col_iter (matrix< T_Q, REFCNT_Q > &Q, vector< T_nonbasis, REFCNT_nonbasis > &nonbasis, Rule_s rule_s, Rule_r rule_r, Ctrler ctrler)
 Performs one dual column iteration on a column simplex table.
template<typename T_Q, bool REFCNT_Q, typename T_nonbasis, bool REFCNT_nonbasis>
result_kind Arageli::simplex_method::dual_col_iter (matrix< T_Q, REFCNT_Q > &Q, vector< T_nonbasis, REFCNT_nonbasis > &nonbasis)
 Performs one dual column iteration on a column simplex table.
template<typename T_Q, bool REFCNT_Q, typename T_nonbasis, bool REFCNT_nonbasis, typename Rule_s, typename Rule_r>
result_kind Arageli::simplex_method::dual_col_iter (matrix< T_Q, REFCNT_Q > &Q, vector< T_nonbasis, REFCNT_nonbasis > &nonbasis, Rule_s rule_s, Rule_r rule_r)
 Performs one dual column iteration on a column simplex table.
template<typename T_Q, bool REFCNT_Q, typename T_nonbasis, bool REFCNT_nonbasis, typename Rule_s, typename Rule_r, typename Ctrler>
result_kind Arageli::simplex_method::dual_col_iters (matrix< T_Q, REFCNT_Q > &Q, vector< T_nonbasis, REFCNT_nonbasis > &nonbasis, Rule_s rule_s, Rule_r rule_r, Ctrler ctrler)
 Performs numerous dual colunt iterations on a column simplex table.
template<typename T_q, bool REFCNT_q, typename T_nonbasis, bool REFCNT_nonbasis, typename Ctrler>
result_kind Arageli::simplex_method::dual_col_iters (matrix< T_q, REFCNT_q > &q, vector< T_nonbasis, REFCNT_nonbasis > &nonbasis, Ctrler ctrler)
 Performs numerous dual colunt iterations on a column simplex table.
template<typename T_q, bool REFCNT_q, typename T_nonbasis, bool REFCNT_nonbasis>
result_kind Arageli::simplex_method::dual_col_iters (matrix< T_q, REFCNT_q > &q, vector< T_nonbasis, REFCNT_nonbasis > &nonbasis)
 Performs numerous dual column iterations on a column simplex table.
template<typename T1, bool REFCNT1, typename T2, bool REFCNT2, typename Ctrler>
void Arageli::simplex_method::basis_create_by_artificial (matrix< T1, REFCNT1 > &q, vector< T2, REFCNT2 > &basis, Ctrler ctrler)
 Produces a valid basis from artifical optimal simplex table due the artifical basis method.
template<typename T1, bool REFCNT1, typename T2, bool REFCNT2>
void Arageli::simplex_method::basis_create_by_artificial (matrix< T1, REFCNT1 > &a, vector< T2, REFCNT2 > &basis)
 Produces a valid basis from artifical optimal simplex table due the artifical basis method.
template<typename T1, bool REFCNT1, typename T3, bool REFCNT3, typename Rule_s, typename Rule_r, typename Ctrler>
result_kind Arageli::simplex_method::basis_artificial (matrix< T1, REFCNT1 > &q, vector< T3, REFCNT3 > &basis, Rule_s rule_s, Rule_r rule_r, Ctrler ctrler)
 Builds primal allowable basis from simplex table q by artificial basis method.
template<typename T1, bool REFCNT1, typename T3, bool REFCNT3, typename Ctrler>
result_kind Arageli::simplex_method::basis_artificial (matrix< T1, REFCNT1 > &q, vector< T3, REFCNT3 > &basis, Ctrler ctrler)
 Builds primal allowable basis from simplex table q by artificial basis method.
template<typename T1, bool REFCNT1, typename T3, bool REFCNT3>
result_kind Arageli::simplex_method::basis_artificial (matrix< T1, REFCNT1 > &q, vector< T3, REFCNT3 > &basis)
 Builds primal allowable basis from simplex table q by artificial basis method.
template<typename T1, bool REFCNT1, typename T2, bool REFCNT2, typename T3, bool REFCNT3>
void Arageli::simplex_method::row_table_create (const matrix< T1, REFCNT1 > &a, const vector< T2, REFCNT2 > &b, matrix< T3, REFCNT3 > &q)
 Creating of a row table from matrix A and vector b, with zeros in the first row.
template<typename T1, bool REFCNT1, typename T2, bool REFCNT2>
void Arageli::simplex_method::row_table_place_c (const vector< T1, REFCNT1 > &c, matrix< T2, REFCNT2 > &q)
template<typename T1, bool REFCNT1, typename T2, bool REFCNT2>
void Arageli::simplex_method::row_table_extract_c (vector< T1, REFCNT1 > &c, const matrix< T2, REFCNT2 > &q)
template<typename T1, bool REFCNT1, typename T2, bool REFCNT2>
void Arageli::simplex_method::row_table_pivot_basis_c (matrix< T1, REFCNT1 > &q, const vector< T2, REFCNT2 > &basis)
template<typename T1, bool REFCNT1, typename T2, bool REFCNT2, typename T3, bool REFCNT3>
void Arageli::simplex_method::row_table_extract_solution (const matrix< T1, REFCNT1 > &q, const vector< T2, REFCNT2 > &basis, vector< T3, REFCNT3 > &x)
template<typename T1, bool REFCNT1, typename N, typename T2, bool REFCNT2>
void Arageli::simplex_method::col_table_extract_solution (const matrix< T1, REFCNT1 > &t, const N &n, vector< T2, REFCNT2 > &x)
template<typename T1, bool REFCNT1, typename T2, bool REFCNT2, typename T3, bool REFCNT3, typename T4, bool REFCNT4>
void Arageli::simplex_method::row_table_create (const matrix< T1, REFCNT1 > &a, const vector< T2, REFCNT2 > &b, const vector< T3, REFCNT3 > &c, matrix< T4, REFCNT4 > &q)
 Creating of a row table from matrix A and vectors b, c.
template<typename T1, bool REFCNT1, typename T2, bool REFCNT2, typename T4, bool REFCNT4>
void Arageli::simplex_method::row_table_split (matrix< T1, REFCNT1 > &a, vector< T2, REFCNT2 > &b, const matrix< T4, REFCNT4 > &q)
 Creating of matrix A and vectors b, c from a row table q.
template<typename T1, bool REFCNT1, typename T2, bool REFCNT2, typename T3, bool REFCNT3, typename T4, bool REFCNT4>
void Arageli::simplex_method::row_table_split (matrix< T1, REFCNT1 > &a, vector< T2, REFCNT2 > &b, const vector< T3, REFCNT3 > &c, const matrix< T4, REFCNT4 > &q)
 Creating of matrix A and vectors b, c from a row table q.
template<typename T1, bool REFCNT1, typename T2, bool REFCNT2, typename T3, bool REFCNT3, typename T4, bool REFCNT4, typename T5, bool REFCNT5>
void Arageli::simplex_method::col_table_create_by_standard (const matrix< T1, REFCNT1 > &a, const vector< T2, REFCNT2 > &b, const vector< T3, REFCNT3 > &c, matrix< T4, REFCNT4 > &t, vector< T5, REFCNT5 > &nonbasis)
 Makes primal column table by given task in standard shape.
template<typename Ta, bool REFCNTa, typename Tb, bool REFCNTb, typename Tc, bool REFCNTc, typename Tx, bool REFCNTx, typename Tbasis, bool REFCNTbasis, typename Tres, typename Rule_s, typename Rule_r, typename Ctrler>
result_kind Arageli::simplex_method::primal_row_with_artificial_basis (const matrix< Ta, REFCNTa > &a, const vector< Tb, REFCNTb > &b, const vector< Tc, REFCNTc > &c, vector< Tx, REFCNTx > &basis_x, vector< Tbasis, REFCNTbasis > &basis, Tres &res, Rule_s rule_s, Rule_r rule_r, Ctrler ctrler)
 Solves the linear programming problem with artificial basis method as zeroth step.
template<typename Ta, bool REFCNTa, typename Tb, bool REFCNTb, typename Tc, bool REFCNTc, typename Tx, bool REFCNTx, typename Tbasis, bool REFCNTbasis, typename Tres>
result_kind Arageli::simplex_method::primal_row_with_artificial_basis (const matrix< Ta, REFCNTa > &a, const vector< Tb, REFCNTb > &b, const vector< Tc, REFCNTc > &c, vector< Tx, REFCNTx > &basis_x, vector< Tbasis, REFCNTbasis > &basis, Tres &res)
 Solves the linear programming problem with artificial basis method as zeroth step.
template<typename T1, bool REFCNT1, typename T2, bool REFCNT2>
void Arageli::simplex_method::basis_to_nonbasis (const vector< T1, REFCNT1 > &basis, vector< T2, REFCNT2 > &nonbasis, std::size_t first_number, std::size_t n)
 Makes nonbasis by basis.
template<typename T1, bool REFCNT1, typename T2, bool REFCNT2>
void Arageli::simplex_method::basis_to_nonbasis (const vector< T1, REFCNT1 > &basis, vector< T2, REFCNT2 > &nonbasis, std::size_t n)
 Makes nonbasis by basis.
template<typename T_Q, bool REFCNT_Q, typename T_basis, bool REFCNT_basis, typename T_T, bool REFCNT_T, typename T_nonbasis, bool REFCNT_nonbasis>
void Arageli::simplex_method::row_to_col_table (const matrix< T_Q, REFCNT_Q > &q, const vector< T_basis, REFCNT_basis > &basis, matrix< T_T, REFCNT_T > &t, vector< T_nonbasis, REFCNT_nonbasis > &nonbasis)
 Converts a valid simplex table from a row form to a column form.
template<typename T_QT, bool REFCNT_QT, typename T_basis_nonbasis, bool REFCNT_basis_nonbasis>
void Arageli::simplex_method::row_to_col_table (matrix< T_QT, REFCNT_QT > &qt, vector< T_basis_nonbasis, REFCNT_basis_nonbasis > &basis_nonbasis)
 Converts a valid simplex table from a row form to a column form.
template<typename T_Q, bool REFCNT_Q, typename T_basis, bool REFCNT_basis, typename T_DQ, bool REFCNT_DQ, typename T_Dbasis, bool REFCNT_Dbasis>
void Arageli::simplex_method::primal_row_to_dual_row_table (const matrix< T_Q, REFCNT_Q > &q, const vector< T_basis, REFCNT_basis > &basis, matrix< T_DQ, REFCNT_DQ > &dq, vector< T_Dbasis, REFCNT_Dbasis > &dbasis)
 Creates a dual row simplex table by primal row simplex table with selected basis.
template<typename T1, bool REFCNT1, typename T2, bool REFCNT2, typename Ctrler>
result_kind Arageli::simplex_method::gomory1_iter (matrix< T1, REFCNT1 > &t, vector< T2, REFCNT2 > &nonbasis, Ctrler ctrler)
 One iteration of The First Gomory's Algorithm on an optimal column simplex table.
template<typename T1, bool REFCNT1, typename T2, bool REFCNT2, typename Ctrler>
result_kind Arageli::simplex_method::gomory1_iters (matrix< T1, REFCNT1 > &t, vector< T2, REFCNT2 > &nonbasis, Ctrler ctrler)
template<typename T1, bool REFCNT1, typename T2, bool REFCNT2>
result_kind Arageli::simplex_method::gomory1_iters (matrix< T1, REFCNT1 > &t, vector< T2, REFCNT2 > &nonbasis)
template<typename T_a, bool REFCNT_a, typename T_b, bool REFCNT_b, typename T_c, bool REFCNT_c, typename T_da, bool REFCNT_da, typename T_db, bool REFCNT_db, typename T_dc, bool REFCNT_dc, typename T_basis, bool REFCNT_basis>
void Arageli::simplex_method::primal_to_dual_canonical (const matrix< T_a, REFCNT_a > &a, const vector< T_b, REFCNT_b > &b, const vector< T_c, REFCNT_c > &c, matrix< T_da, REFCNT_da > &da, vector< T_db, REFCNT_db > &db, vector< T_dc, REFCNT_dc > &dc, vector< T_basis, REFCNT_basis > &basis)
 Makes the dual task in canonical shape by primal task.
template<typename T_a, bool REFCNT_a, typename T_b, bool REFCNT_b, typename T_c, bool REFCNT_c, typename T_basis, bool REFCNT_basis, typename T_da, bool REFCNT_da, typename T_db, bool REFCNT_db, typename T_dc, bool REFCNT_dc, typename T_res, typename T_ab, bool REFCNT_ab, typename T_cb, bool REFCNT_cb>
void Arageli::simplex_method::primal_to_dual_standard_discr (const matrix< T_a, REFCNT_a > &a, const vector< T_b, REFCNT_b > &b, const vector< T_c, REFCNT_c > &c, const vector< T_basis, REFCNT_basis > basis, matrix< T_da, REFCNT_da > &da, vector< T_db, REFCNT_db > &db, vector< T_dc, REFCNT_dc > &dc, T_res &res_offset, matrix< T_ab, REFCNT_ab > &bsuba, vector< T_cb, REFCNT_cb > &bsubc)
 Makes the dual task in standard shape by primal task via introducing discrepancy variables.
template<typename T, bool REFCNT, typename Ch, typename ChT>
std::basic_ostream< Ch, ChT > & Arageli::simplex_method::output_list (std::basic_ostream< Ch, ChT > &out, const linear_prog_task< T, REFCNT > &lpt)
template<typename T, bool REFCNT, typename Ch, typename ChT>
std::basic_istream< Ch, ChT > & Arageli::simplex_method::input_list (std::basic_istream< Ch, ChT > &in, linear_prog_task< T, REFCNT > &lpt)
template<typename T, bool REFCNT, typename Ch, typename ChT>
std::basic_ostream< Ch, ChT > & Arageli::simplex_method::output_aligned (std::basic_ostream< Ch, ChT > &out, const linear_prog_task< T, REFCNT > &lpt, const char *var="x")


Detailed Description

Direct and dual simplex methods with different ways of choosing of pivot elements. Set of controller objects. There are as row as columnt methods, as noninteger as integer ones.

Definition in file simplex_method.hpp.


Define Documentation

#define ARAGELI_INCLUDE_CPP_WITH_EXPORT_TEMPLATE_SIMPLEX_METHOD

Definition at line 2682 of file simplex_method.hpp.


Generated on Thu Aug 31 17:38:18 2006 for Arageli by  doxygen 1.4.7