#include <initial_basis.h>

Public Member Functions
	InitialBasis (const CompactSparseMatrix &compact_matrix, const DenseRow &objective, const DenseRow &lower_bound, const DenseRow &upper_bound, const VariableTypeRow &variable_type)
	Takes references to the linear program data we need.

	InitialBasis (const InitialBasis &)=delete
	This type is neither copyable nor movable.

InitialBasis &	operator= (const InitialBasis &)=delete

void	CompleteBixbyBasis (ColIndex num_cols, RowToColMapping *basis)

void	CompleteTriangularPrimalBasis (ColIndex num_cols, RowToColMapping *basis)

void	CompleteTriangularDualBasis (ColIndex num_cols, RowToColMapping *basis)

void	GetPrimalMarosBasis (ColIndex num_cols, RowToColMapping *basis)

void	GetDualMarosBasis (ColIndex num_cols, RowToColMapping *basis)

void	ComputeCandidates (ColIndex num_cols, std::vector< ColIndex > *candidates)

Detailed Description

This class implements two initial basis algorithms. The idea is to replace as much as possible the columns of B that correspond to fixed slack variables with some column of A in order to have more freedom in the values the basic variables can take.

The first algorithm is Bixby's initial basis algorithm, described in the paper below. It considers the columns of A in a particular order (the ones with more freedom first) and adds the current column to the basis if it keeps B almost triangular and with coefficients close to 1.0 on the diagonal for good numerical stability.

Robert E. Bixby, "Implementing the Simplex Method: The Initial Basis" ORSA Jounal on Computing, Vol. 4, No. 3, Summer 1992. http://joc.journal.informs.org/content/4/3/267.abstract

The second algorithm is is similar to the "advanced initial basis" that GLPK uses by default. It adds columns one by one to the basis B while keeping it triangular (not almost triangular as in Bixby's algorithm). The next column to add is chosen amongst the set of possible candidates using a heuristic similar to the one used by Bixby.

Definition at line 46 of file initial_basis.h.

Constructor & Destructor Documentation

◆ InitialBasis() [1/2]

operations_research::glop::InitialBasis::InitialBasis	(	const CompactSparseMatrix &	compact_matrix,
		const DenseRow &	objective,
		const DenseRow &	lower_bound,
		const DenseRow &	upper_bound,
		const VariableTypeRow &	variable_type )

Takes references to the linear program data we need.

Definition at line 29 of file initial_basis.cc.

◆ InitialBasis() [2/2]

operations_research::glop::InitialBasis::InitialBasis ( const InitialBasis & )

delete

This type is neither copyable nor movable.

Member Function Documentation

◆ CompleteBixbyBasis()

void operations_research::glop::InitialBasis::CompleteBixbyBasis	(	ColIndex	num_cols,
		RowToColMapping *	basis )

Completes the entries of the given basis that are equal to kInvalidCol with one of the first num_cols columns of A using Bixby's algorithm.

Important: For this function, the matrix must be scaled such that the maximum absolute value in each column is 1.0.

Initialize can_be_replaced ('I' in Bixby's paper) and has_zero_coefficient ('r' in Bixby's paper).

This is 'v' in Bixby's paper.

Compute a list of candidate indices and sort them using the heuristic described in Bixby's paper.

Loop over the candidate columns, and add them to the basis if the heuristics are satisfied.

Bixby's heuristic only works with scaled columns. This should be the case by default since we only use this when the matrix is scaled, but it is not the case for our tests... The overhead for computing the infinity norm for each column should be minimal.

Definition at line 43 of file initial_basis.cc.

◆ CompleteTriangularDualBasis()

void operations_research::glop::InitialBasis::CompleteTriangularDualBasis	(	ColIndex	num_cols,
		RowToColMapping *	basis )

Definition at line 120 of file initial_basis.cc.

◆ CompleteTriangularPrimalBasis()

void operations_research::glop::InitialBasis::CompleteTriangularPrimalBasis	(	ColIndex	num_cols,
		RowToColMapping *	basis )

Similar to CompleteBixbyBasis() but completes the basis into a triangular one. This function usually produces better initial bases. The dual version just restricts the possible entering columns to the ones with a cost of 0.0 in order to always start with the all-zeros vector of dual values.

Returns false if an error occurred during the algorithm (numerically instable basis).

Definition at line 115 of file initial_basis.cc.

◆ ComputeCandidates()

void operations_research::glop::InitialBasis::ComputeCandidates	(	ColIndex	num_cols,
		std::vector< ColIndex > *	candidates )

Visible for testing. Computes a list of candidate column indices out of the fist num_candidate_columns of A and sorts them using the bixby_column_comparator_. This also fills max_scaled_abs_cost_.

Definition at line 358 of file initial_basis.cc.

◆ GetDualMarosBasis()

void operations_research::glop::InitialBasis::GetDualMarosBasis	(	ColIndex	num_cols,
		RowToColMapping *	basis )

Definition at line 110 of file initial_basis.cc.

◆ GetPrimalMarosBasis()

void operations_research::glop::InitialBasis::GetPrimalMarosBasis	(	ColIndex	num_cols,
		RowToColMapping *	basis )

Use Maros's LTSF crash from the book "Computational Techniques of the Simplex Method". Unlike the other crashes this does not use the initial content of the basis parameter.

Definition at line 105 of file initial_basis.cc.

◆ operator=()

InitialBasis & operations_research::glop::InitialBasis::operator= ( const InitialBasis & )