Revised Simplex algorithm for linear programming. More...

#include <Simplex.H>

Collaboration diagram for Aleph::RevisedSimplex< T >:

Classes
struct	EtaMatrix

Public Types
enum	State { Not_Solved , Solving , Unbounded , Solved , Unfeasible }
	Solution states for the linear program. More...

Public Member Functions
	RevisedSimplex (size_t num_vars, size_t num_constraints)
	Constructs a Revised Simplex solver.

void	set_objective (size_t j, T coef)
	Sets objective coefficient.

void	set_objective (const T *coefs)
	Sets all objective coefficients.

void	set_constraint (size_t i, size_t j, T coef)
	Sets constraint coefficient.

void	set_rhs (size_t i, T rhs)
	Sets RHS value for a constraint.

void	set_constraint_row (size_t i, const T *coefs, T rhs)
	Adds a complete constraint.

void	set_refactorization_frequency (size_t freq)
	Sets refactorization frequency.

State	solve ()
	Solves the linear program.

T	get_solution (size_t j) const
	Gets solution value for variable j.

T	objective_value () const
	Computes objective function value.

State	get_state () const noexcept
	Gets current state.

const SimplexStats &	get_stats () const noexcept
	Gets execution statistics.

size_t	get_num_vars () const noexcept
	Gets number of variables.

size_t	get_num_constraints () const noexcept
	Gets number of constraints.

bool	verify_solution () const
	Verifies solution satisfies all constraints.

void	print_stats () const
	Prints statistics to stdout.

Private Member Functions
void	ftran (const std::vector< T > &a, std::vector< T > &y) const

void	btran (const std::vector< T > &c_B, std::vector< T > &pi_out) const

T	compute_reduced_cost (size_t j) const

void	get_column (size_t j, std::vector< T > &col) const

int	select_entering_variable ()

int	select_leaving_variable (int entering, T &theta)

void	update_basis_inverse (int leaving_row, const std::vector< T > &d_col)

void	refactorize ()

Private Attributes
size_t	m

size_t	n

std::vector< T >	c

std::vector< std::vector< T > >	A

std::vector< T >	b

std::vector< int >	basic

std::vector< int >	nonbasic

std::vector< bool >	is_basic

std::vector< EtaMatrix >	eta_file

std::vector< std::vector< T > >	B_inv_explicit

std::vector< T >	x_B

std::vector< T >	solution

std::vector< T >	pi

std::vector< T >	d

std::vector< T >	work

T	eps

size_t	refactor_frequency

bool	use_steepest_edge

State	state

SimplexStats	stats

Detailed Description

template<typename T>
class Aleph::RevisedSimplex< T >

Revised Simplex algorithm for linear programming.

The Revised Simplex method is an efficient variant of the standard Simplex algorithm that maintains only the basis inverse B⁻¹ instead of the full tableau. This provides significant memory and computational savings for larger problems.

Key Differences from Standard Simplex

Aspect	Standard Simplex	Revised Simplex
Storage	Full tableau O((m+1)×(n+m+1))	B⁻¹ + original data O(m² + mn)
Pivot	Update entire tableau	Update only B⁻¹
Pricing	Read from tableau	Compute π = c_B·B⁻¹, then c̄_j = c_j - π·a_j
Best for	Small/dense problems	Large/sparse problems

Algorithm Overview

Initialize: Set up initial basis (slack variables)
Pricing: Compute dual prices π = c_B · B⁻¹
Select entering: Find j with most negative c̄_j = c_j - π · a_j
FTRAN: Compute d = B⁻¹ · a_j (tableau column)
Ratio test: Find leaving variable using d
BTRAN/Update: Update B⁻¹ using eta-matrix product form
Repeat until optimal or unbounded

Eta-Matrix Updates

Instead of computing B⁻¹ directly, we maintain it as a product of elementary matrices (eta-matrices): B⁻¹ = E_k · E_{k-1} · ... · E_1 · B_0⁻¹

Periodic refactorization is performed to maintain numerical stability and reduce accumulated errors.

Performance

Memory: O(m² + mn) vs O(mn + m²) for standard
Time per iteration: O(m²) for dense, O(nnz) for sparse
Best for: n >> m (many variables, few constraints)

Template Parameters

T	Numeric type for coefficients (typically double).

See also: Simplex

Definition at line 1743 of file Simplex.H.

Member Enumeration Documentation

◆ State

template<typename T >

enum Aleph::RevisedSimplex::State

Solution states for the linear program.

Enumerator
Not_Solved
Solving
Unbounded
Solved
Unfeasible

Definition at line 1747 of file Simplex.H.

Constructor & Destructor Documentation

◆ RevisedSimplex()

template<typename T >

Aleph::RevisedSimplex< T >::RevisedSimplex	(	size_t	num_vars,
		size_t	num_constraints
	)

inline

Constructs a Revised Simplex solver.

Parameters

[in]	num_vars	Number of decision variables.
[in]	num_constraints	Number of constraints.

Definition at line 2047 of file Simplex.H.

References ah_invalid_argument_if, and Aleph::maps().

Member Function Documentation

◆ btran()

template<typename T >

void Aleph::RevisedSimplex< T >::btran	(	const std::vector< T > &	c_B,
		std::vector< T > &	pi_out
	)		const

inlineprivate

Definition at line 1809 of file Simplex.H.

References Aleph::RevisedSimplex< T >::B_inv_explicit, Aleph::RevisedSimplex< T >::m, Aleph::maps(), and Aleph::sum().

Referenced by Aleph::RevisedSimplex< T >::select_entering_variable().

◆ compute_reduced_cost()

template<typename T >

T Aleph::RevisedSimplex< T >::compute_reduced_cost ( size_t j ) const

inlineprivate

Definition at line 1823 of file Simplex.H.

References Aleph::RevisedSimplex< T >::A, Aleph::RevisedSimplex< T >::c, Aleph::RevisedSimplex< T >::m, Aleph::maps(), Aleph::RevisedSimplex< T >::n, and Aleph::RevisedSimplex< T >::pi.

Referenced by Aleph::RevisedSimplex< T >::select_entering_variable().

◆ ftran()

template<typename T >

void Aleph::RevisedSimplex< T >::ftran	(	const std::vector< T > &	a,
		std::vector< T > &	y
	)		const

inlineprivate

Definition at line 1793 of file Simplex.H.

References Aleph::RevisedSimplex< T >::B_inv_explicit, Aleph::RevisedSimplex< T >::m, Aleph::sum(), and y.

Referenced by Aleph::RevisedSimplex< T >::select_leaving_variable().

◆ get_column()

template<typename T >

void Aleph::RevisedSimplex< T >::get_column	(	size_t	j,
		std::vector< T > &	col
	)		const

inlineprivate

Definition at line 1839 of file Simplex.H.

References Aleph::RevisedSimplex< T >::A, Aleph::RevisedSimplex< T >::m, Aleph::maps(), and Aleph::RevisedSimplex< T >::n.

Referenced by Aleph::RevisedSimplex< T >::select_leaving_variable().

◆ get_num_constraints()

template<typename T >

size_t Aleph::RevisedSimplex< T >::get_num_constraints ( ) const

inlinenoexcept

Gets number of constraints.

Definition at line 2264 of file Simplex.H.

References Aleph::RevisedSimplex< T >::m.

◆ get_num_vars()

template<typename T >

size_t Aleph::RevisedSimplex< T >::get_num_vars ( ) const

inlinenoexcept

Gets number of variables.

Definition at line 2261 of file Simplex.H.

References Aleph::RevisedSimplex< T >::n.

◆ get_solution()

template<typename T >

T Aleph::RevisedSimplex< T >::get_solution ( size_t j ) const

inline

Gets solution value for variable j.

Parameters

[in] j Variable index.

Returns: Optimal value of variable x_j.

Definition at line 2236 of file Simplex.H.

References ah_out_of_range_error_if, Aleph::RevisedSimplex< T >::n, and Aleph::RevisedSimplex< T >::solution.

◆ get_state()

template<typename T >

State Aleph::RevisedSimplex< T >::get_state ( ) const

inlinenoexcept

Gets current state.

Definition at line 2255 of file Simplex.H.

References Aleph::RevisedSimplex< T >::state.

◆ get_stats()

template<typename T >

const SimplexStats & Aleph::RevisedSimplex< T >::get_stats ( ) const

inlinenoexcept

Gets execution statistics.

Definition at line 2258 of file Simplex.H.

References Aleph::RevisedSimplex< T >::stats.

◆ objective_value()

template<typename T >

T Aleph::RevisedSimplex< T >::objective_value ( ) const

inline

Computes objective function value.

Returns: Optimal objective value.

Definition at line 2246 of file Simplex.H.

References Aleph::RevisedSimplex< T >::c, Aleph::RevisedSimplex< T >::n, Aleph::RevisedSimplex< T >::solution, and Aleph::sum().

◆ print_stats()

template<typename T >

void Aleph::RevisedSimplex< T >::print_stats ( ) const

inline

Prints statistics to stdout.

Definition at line 2284 of file Simplex.H.

References Aleph::SimplexStats::elapsed_ms, Aleph::RevisedSimplex< T >::eta_file, Aleph::SimplexStats::iterations, Aleph::RevisedSimplex< T >::m, Aleph::RevisedSimplex< T >::n, Aleph::SimplexStats::pivots, Aleph::RevisedSimplex< T >::refactor_frequency, and Aleph::RevisedSimplex< T >::stats.

◆ refactorize()

template<typename T >

void Aleph::RevisedSimplex< T >::refactorize ( )

inlineprivate

Definition at line 1967 of file Simplex.H.

References Aleph::RevisedSimplex< T >::A, Aleph::RevisedSimplex< T >::B_inv_explicit, Aleph::RevisedSimplex< T >::basic, Aleph::RevisedSimplex< T >::eta_file, Aleph::RevisedSimplex< T >::m, Aleph::maps(), and Aleph::RevisedSimplex< T >::n.

◆ select_entering_variable()

template<typename T >

int Aleph::RevisedSimplex< T >::select_entering_variable ( )

inlineprivate

Definition at line 1858 of file Simplex.H.

References Aleph::RevisedSimplex< T >::basic, Aleph::RevisedSimplex< T >::btran(), Aleph::RevisedSimplex< T >::c, Aleph::RevisedSimplex< T >::compute_reduced_cost(), Aleph::RevisedSimplex< T >::eps, Aleph::RevisedSimplex< T >::m, Aleph::maps(), Aleph::RevisedSimplex< T >::n, Aleph::RevisedSimplex< T >::nonbasic, and Aleph::RevisedSimplex< T >::pi.

Referenced by Aleph::RevisedSimplex< T >::solve().

◆ select_leaving_variable()

template<typename T >

int Aleph::RevisedSimplex< T >::select_leaving_variable	(	int	entering,
		T &	theta
	)

inlineprivate

Definition at line 1890 of file Simplex.H.

References Aleph::RevisedSimplex< T >::d, Aleph::RevisedSimplex< T >::eps, Aleph::RevisedSimplex< T >::ftran(), Aleph::RevisedSimplex< T >::get_column(), Aleph::RevisedSimplex< T >::m, Aleph::maps(), and Aleph::RevisedSimplex< T >::x_B.

Referenced by Aleph::RevisedSimplex< T >::solve().

◆ set_constraint()

template<typename T >

void Aleph::RevisedSimplex< T >::set_constraint	(	size_t	i,
		size_t	j,
		T	coef
	)

inline

Sets constraint coefficient.

Parameters

[in]	i	Constraint index.
[in]	j	Variable index.
[in]	coef	Coefficient value.

Definition at line 2093 of file Simplex.H.

References Aleph::RevisedSimplex< T >::A, ah_out_of_range_error_if, Aleph::RevisedSimplex< T >::m, and Aleph::RevisedSimplex< T >::n.

◆ set_constraint_row()

template<typename T >

void Aleph::RevisedSimplex< T >::set_constraint_row	(	size_t	i,
		const T *	coefs,
		T	rhs
	)

inline

Adds a complete constraint.

Parameters

[in]	i	Constraint index.
[in]	coefs	Array of n coefficients.
[in]	rhs	Right-hand side value.

Definition at line 2117 of file Simplex.H.

References Aleph::RevisedSimplex< T >::A, ah_out_of_range_error_if, Aleph::RevisedSimplex< T >::b, Aleph::RevisedSimplex< T >::m, Aleph::maps(), and Aleph::RevisedSimplex< T >::n.

◆ set_objective() [1/2]

template<typename T >

void Aleph::RevisedSimplex< T >::set_objective ( const T * coefs )

inline

Sets all objective coefficients.

Parameters

[in] coefs Array of n coefficients.

Definition at line 2081 of file Simplex.H.

References Aleph::RevisedSimplex< T >::c, Aleph::maps(), and Aleph::RevisedSimplex< T >::n.

◆ set_objective() [2/2]

template<typename T >

void Aleph::RevisedSimplex< T >::set_objective	(	size_t	j,
		T	coef
	)

inline

Sets objective coefficient.

Parameters

[in]	j	Variable index.
[in]	coef	Coefficient value.

Definition at line 2071 of file Simplex.H.

References ah_out_of_range_error_if, Aleph::RevisedSimplex< T >::c, and Aleph::RevisedSimplex< T >::n.

◆ set_refactorization_frequency()

template<typename T >

void Aleph::RevisedSimplex< T >::set_refactorization_frequency ( size_t freq )

inline

Sets refactorization frequency.

B⁻¹ is recomputed explicitly every N iterations to maintain numerical stability.

Parameters

[in] freq Refactorization frequency (default: max(50, m)).

Definition at line 2132 of file Simplex.H.

References Aleph::maps(), and Aleph::RevisedSimplex< T >::refactor_frequency.

◆ set_rhs()

template<typename T >

void Aleph::RevisedSimplex< T >::set_rhs	(	size_t	i,
		T	rhs
	)

inline

Sets RHS value for a constraint.

Parameters

[in]	i	Constraint index.
[in]	rhs	Right-hand side value.

Definition at line 2105 of file Simplex.H.

References ah_out_of_range_error_if, Aleph::RevisedSimplex< T >::b, Aleph::RevisedSimplex< T >::m, and Aleph::maps().

◆ solve()

template<typename T >

State Aleph::RevisedSimplex< T >::solve ( )

inline

Solves the linear program.

Returns: Solution state (Solved, Unbounded, or Unfeasible).

Definition at line 2141 of file Simplex.H.

◆ update_basis_inverse()

template<typename T >

void Aleph::RevisedSimplex< T >::update_basis_inverse	(	int	leaving_row,
		const std::vector< T > &	d_col
	)

inlineprivate

Definition at line 1923 of file Simplex.H.

References Aleph::RevisedSimplex< T >::B_inv_explicit, Aleph::RevisedSimplex< T >::eps, Aleph::RevisedSimplex< T >::m, and Aleph::maps().

Referenced by Aleph::RevisedSimplex< T >::solve().

◆ verify_solution()

template<typename T >

bool Aleph::RevisedSimplex< T >::verify_solution ( ) const

inline

Verifies solution satisfies all constraints.

Returns: true if feasible, false otherwise.

Definition at line 2270 of file Simplex.H.

References Aleph::RevisedSimplex< T >::A, Aleph::RevisedSimplex< T >::b, Aleph::RevisedSimplex< T >::eps, Aleph::RevisedSimplex< T >::m, Aleph::maps(), Aleph::RevisedSimplex< T >::n, and Aleph::RevisedSimplex< T >::solution.

Member Data Documentation

◆ A

template<typename T >

std::vector<std::vector<T> > Aleph::RevisedSimplex< T >::A

private

Definition at line 1754 of file Simplex.H.

Referenced by Aleph::RevisedSimplex< T >::compute_reduced_cost(), Aleph::RevisedSimplex< T >::get_column(), Aleph::RevisedSimplex< T >::refactorize(), Aleph::RevisedSimplex< T >::set_constraint(), Aleph::RevisedSimplex< T >::set_constraint_row(), and Aleph::RevisedSimplex< T >::verify_solution().

◆ b

template<typename T >

std::vector<T> Aleph::RevisedSimplex< T >::b

private

Definition at line 1755 of file Simplex.H.

Referenced by Aleph::RevisedSimplex< T >::set_constraint_row(), Aleph::RevisedSimplex< T >::set_rhs(), Aleph::RevisedSimplex< T >::solve(), and Aleph::RevisedSimplex< T >::verify_solution().

◆ B_inv_explicit

template<typename T >

std::vector<std::vector<T> > Aleph::RevisedSimplex< T >::B_inv_explicit

private

Definition at line 1769 of file Simplex.H.

Referenced by Aleph::RevisedSimplex< T >::btran(), Aleph::RevisedSimplex< T >::ftran(), Aleph::RevisedSimplex< T >::refactorize(), Aleph::RevisedSimplex< T >::solve(), and Aleph::RevisedSimplex< T >::update_basis_inverse().

◆ basic

template<typename T >

std::vector<int> Aleph::RevisedSimplex< T >::basic

private

Definition at line 1758 of file Simplex.H.

Referenced by Aleph::RevisedSimplex< T >::refactorize(), Aleph::RevisedSimplex< T >::select_entering_variable(), and Aleph::RevisedSimplex< T >::solve().

◆ c

template<typename T >

std::vector<T> Aleph::RevisedSimplex< T >::c

private

Definition at line 1753 of file Simplex.H.

Referenced by Aleph::RevisedSimplex< T >::compute_reduced_cost(), Aleph::RevisedSimplex< T >::objective_value(), Aleph::RevisedSimplex< T >::select_entering_variable(), Aleph::RevisedSimplex< T >::set_objective(), and Aleph::RevisedSimplex< T >::set_objective().

◆ d

template<typename T >

std::vector<T> Aleph::RevisedSimplex< T >::d

mutableprivate

Definition at line 1777 of file Simplex.H.

Referenced by Aleph::RevisedSimplex< T >::select_leaving_variable(), and Aleph::RevisedSimplex< T >::solve().

◆ eps

template<typename T >

T Aleph::RevisedSimplex< T >::eps

private

Definition at line 1781 of file Simplex.H.

Referenced by Aleph::RevisedSimplex< T >::select_entering_variable(), Aleph::RevisedSimplex< T >::select_leaving_variable(), Aleph::RevisedSimplex< T >::update_basis_inverse(), and Aleph::RevisedSimplex< T >::verify_solution().

◆ eta_file

template<typename T >

std::vector<EtaMatrix> Aleph::RevisedSimplex< T >::eta_file

private

Definition at line 1768 of file Simplex.H.

Referenced by Aleph::RevisedSimplex< T >::print_stats(), and Aleph::RevisedSimplex< T >::refactorize().

◆ is_basic

template<typename T >

std::vector<bool> Aleph::RevisedSimplex< T >::is_basic

private

Definition at line 1760 of file Simplex.H.

Referenced by Aleph::RevisedSimplex< T >::solve().

◆ m

template<typename T >

size_t Aleph::RevisedSimplex< T >::m

private

Definition at line 1751 of file Simplex.H.

◆ n

◆ nonbasic

template<typename T >

std::vector<int> Aleph::RevisedSimplex< T >::nonbasic

private

Definition at line 1759 of file Simplex.H.

Referenced by Aleph::RevisedSimplex< T >::select_entering_variable(), and Aleph::RevisedSimplex< T >::solve().

◆ pi

template<typename T >

std::vector<T> Aleph::RevisedSimplex< T >::pi

mutableprivate

Definition at line 1776 of file Simplex.H.

Referenced by Aleph::RevisedSimplex< T >::compute_reduced_cost(), and Aleph::RevisedSimplex< T >::select_entering_variable().

◆ refactor_frequency

template<typename T >

size_t Aleph::RevisedSimplex< T >::refactor_frequency

private

Definition at line 1782 of file Simplex.H.

Referenced by Aleph::RevisedSimplex< T >::print_stats(), and Aleph::RevisedSimplex< T >::set_refactorization_frequency().

◆ solution

template<typename T >

std::vector<T> Aleph::RevisedSimplex< T >::solution

private

Definition at line 1773 of file Simplex.H.

Referenced by Aleph::RevisedSimplex< T >::get_solution(), Aleph::RevisedSimplex< T >::objective_value(), Aleph::RevisedSimplex< T >::solve(), and Aleph::RevisedSimplex< T >::verify_solution().

◆ state

template<typename T >

State Aleph::RevisedSimplex< T >::state

private

Definition at line 1786 of file Simplex.H.

Referenced by Aleph::RevisedSimplex< T >::get_state(), and Aleph::RevisedSimplex< T >::solve().

◆ stats

template<typename T >

SimplexStats Aleph::RevisedSimplex< T >::stats

mutableprivate

Definition at line 1787 of file Simplex.H.

Referenced by Aleph::RevisedSimplex< T >::get_stats(), Aleph::RevisedSimplex< T >::print_stats(), and Aleph::RevisedSimplex< T >::solve().

◆ use_steepest_edge

template<typename T >

bool Aleph::RevisedSimplex< T >::use_steepest_edge

private

Definition at line 1783 of file Simplex.H.

◆ work

template<typename T >

std::vector<T> Aleph::RevisedSimplex< T >::work

mutableprivate

Definition at line 1778 of file Simplex.H.

◆ x_B

template<typename T >

std::vector<T> Aleph::RevisedSimplex< T >::x_B

private

Definition at line 1772 of file Simplex.H.

Referenced by Aleph::RevisedSimplex< T >::select_leaving_variable(), and Aleph::RevisedSimplex< T >::solve().

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

Simplex.H

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Key Differences from Standard Simplex

Algorithm Overview

Eta-Matrix Updates

Performance

Member Enumeration Documentation

◆ State

Constructor & Destructor Documentation

◆ RevisedSimplex()

Member Function Documentation

◆ btran()

◆ compute_reduced_cost()

◆ ftran()

◆ get_column()

◆ get_num_constraints()

◆ get_num_vars()

◆ get_solution()

◆ get_state()

◆ get_stats()

◆ objective_value()

◆ print_stats()

◆ refactorize()

◆ select_entering_variable()

◆ select_leaving_variable()

◆ set_constraint()

◆ set_constraint_row()

◆ set_objective() [1/2]

◆ set_objective() [2/2]

◆ set_refactorization_frequency()

◆ set_rhs()

◆ solve()

◆ update_basis_inverse()

◆ verify_solution()

Member Data Documentation

◆ A

◆ b

◆ B_inv_explicit

◆ basic

◆ c

◆ d

◆ eps

◆ eta_file

◆ is_basic

◆ m

◆ n

◆ nonbasic

◆ pi

◆ refactor_frequency

◆ solution

◆ state

◆ stats

◆ use_steepest_edge

◆ work

◆ x_B