Linear programming solver using a custom implementation of the Simplex algorithm. More...

#include <DelpiLpSolver.h>

Inheritance diagram for delpi::DelpiLpSolver:

Public Member Functions
Column	column (ColumnIndex column_idx) const override
	Get the column at the given column_idx index.
Row	row (RowIndex row_idx) const override
	Get the row at the given row_idx index.
void	ReserveColumns (int num_columns) override
	Reserve space for the given number of columns and rows.
void	ReserveRows (int num_rows) override
	Reserve space for the given number of rows.
ColumnIndex	AddColumn (const Variable &var, const mpq_class &obj, const mpq_class &lb, const mpq_class &ub) override
	Add a new bounded column to the LP problem, ensuring that the variable var is in the range \( [lb, ub] \) and has the objective coefficient obj.
RowIndex	AddRow (const Expression::Addends &lhs, FormulaKind sense, const mpq_class &rhs) override
	Add a new row to the LP problem with the given lhs linear summation, sense and rhs.
void	SetBound (Variable var, const mpq_class &lb, const mpq_class &ub) override
	Set the bounds of a var in the LP problem to the given lb and ub.
void	SetCoefficient (RowIndex row, ColumnIndex column, const mpq_class &value) override
	Set the coefficient of the row constraint to apply at the column decisional variable.
void	SetObjective (int column, const mpq_class &value) override
	The the objective coefficient of the given column to the given value.
Public Member Functions inherited from delpi::LpSolver
	LpSolver (mpq_class ninfinity, mpq_class infinity, Config config={}, const std::string &class_name="LpSolver")
	Construct a new LpSolver object with the given config.
bool	Parse ()
	Parse the input file or stdin based on the Config parameters.
bool	ParseFile (const std::string &filename)
	Parse the file with the given filename.
bool	ParseString (const std::string &string)
	Parse the given string as input.
bool	ParseStream (std::istream &stream, const std::string &stream_name="(stdin)")
	Parse the given stream as input.
const std::unordered_map< std::string, std::string > &	info () const
	@getter{information stored in the LP solver}
std::unordered_map< Variable, mpq_class >	model (const std::vector< mpq_class > &x) const
	Get a mapping between the variables and their values in the solution vector x.
const mpq_class &	solution (const Variable var) const
	Get the value of var in the solution vector.
const Variable &	var (const int column) const
	Shorthand notation to get the real variable linked with column column.
const std::string &	GetInfo (const std::string &key) const
	Retrieve the information stored under the given key.
void	SetInfo (const std::string &key, const std::string &value)
	Set the information stored under the given key to the given value.
void	SetOption (const std::string &key, const std::string &value)
	Set the option identified by the given key to the given value.
virtual void	AddColumns (const std::span< Column > &columns)
	Add a vector of columns to the LP problem.
ColumnIndex	AddColumn (const Column &column)
	Add a new column to the LP problem.
ColumnIndex	AddColumn (const Variable &var)
	Add a new unbounded column corresponding to the variable var to the LP problem.
ColumnIndex	AddColumn (const Variable &var, const mpq_class &obj)
	Add a new column to the LP problem setting the objective coefficient of var to the given obj.
ColumnIndex	AddColumn (const Variable &var, const mpq_class &lb, const mpq_class &ub)
	Add a new bounded column to the LP problem, ensuring that the variable var is in the range \( [lb, ub] \).
virtual void	AddRows (const std::span< Row > &rows)
	Add a vector of rows to the LP problem.
RowIndex	AddRow (const Row &row)
	Add a new row to the LP problem with the given row.
virtual RowIndex	AddRow (const std::vector< std::pair< Variable, mpq_class > > &addends, const mpq_class &lb, const mpq_class &ub)=0
	Add a new row to the LP problem with the given addends bounded by lb and ub.
RowIndex	AddRow (const Formula &formula)
	Add a new row to the LP problem with the given formula.
RowIndex	AddRow (const Expression &lhs, FormulaKind sense, const mpq_class &rhs)
	Add a new row to the LP problem with the given lhs linear expression, sense and rhs.
void	SetObjective (const Expression &objective)
	Set the objective coefficients of the LP problem to the given objective.
void	SetObjective (const std::unordered_map< int, mpq_class > &objective)
	Set the objective coefficients of the LP problem to the given objective.
void	SetObjective (const std::vector< mpq_class > &objective)
	Set the objective coefficients of the LP problem to the given objective.
void	SetObjective (const Variable &var, const mpq_class &value)
	The the objective coefficient of the column corresponding to the give var to the given value.
LpResult	Solve ()
	Optimise the LP problem with the given delta.
void	Maximise (const Expression &objective_function)
	Set the objective_function to maximise while being subject to all the constraints.
template<TypedIterable< std::pair< const Variable, mpq_class > > T>
void	Maximise (const T &objective_function)
	Set the objective_function to maximise while being subject to all the constraints.
void	Minimise (const Expression &objective_function)
	Set the objective_function to minimise while being subject to all the constraints.
template<TypedIterable< std::pair< const Variable, mpq_class > > T>
void	Minimise (const T &objective_function)
	Set the objective_function to maximise while being subject to all the constraints.
void	ResetObjective ()
	Set all coefficients in the objective function to zero.
bool	CheckAgainstExpected (LpResult result) const
	Check whether the result obtained by the solver is compatible with the one collected from the file.
bool	Verify () const
	Verify that the current solution_ satisfies all the constraints in the LpSolver.

Protected Member Functions
void	EnsureSenseCore () override
	Make sure the LP solvers are aware of the sense of the LP problem (minimisation or maximisation).
Protected Member Functions inherited from delpi::LpSolver
void	EnsureSense (bool is_min)
	Make sure the LP solvers are aware of the sense of the LP problem (minimisation or maximisation).
bool	SetSimpleBoundInsteadOfAddRow (const std::vector< Expression::Addend > &addends, const mpq_class &lb, const mpq_class &ub)
	Check whether the row that is about to be added is a simple bound.

Private Member Functions
LpResult	SolveCore () override
	Internal method that optimises the LP problem with the given delta.
template<IsAnyOf< double, mpq_class > T>
LpResult	InternalSolve (const Matrix< T > &A, const Vector< T > &b, const Vector< T > &c, const T &tolerance, internal::Basis< T > &basis, Vector< T > x=nullptr, T obj=nullptr)
	Solve the LP problem using the Simplex algorithm.
void	RemoveAuxiliaryColumns (const internal::Basis< mpq_class > &feas_basis, const std::vector< Index > &aux_columns, Matrix< mpq_class > &slack_A, Vector< mpq_class > &slack_b, internal::Basis< mpq_class > &slack_basis) const
	Use aux_basis to update basis with a set of columns we know feasible.
void	SlackForm (Matrix< mpq_class > &slack_A, Vector< mpq_class > &slack_c) const
	Convert a generic LP problem into the standard form by adding slack variables where needed.
internal::Basis< mpq_class >	AuxForm (const Matrix< mpq_class > &slack_A, const Vector< mpq_class > &slack_b, Matrix< mpq_class > &aux_A, Vector< mpq_class > &aux_c, std::vector< Index > &aux_columns) const
	Convert a standard form LP problem into a feasible and bounded auxiliary problem.
void	ComputeSlackAndAuxVariables ()
	Compute the slack and auxiliary variables for the original LP problem stored in A_, b_ and c_ in order to convert it to the standard form and check its feasibility.

Private Attributes
Vector< mpq_class >	x_
	Solution vector.
internal::LpProblem	problem_
	Linear programming problem.
mpq_class	delta_
	Precision for the optimality check.

Additional Inherited Members
Public Types inherited from delpi::LpSolver
using	SolveCallback
	Callback invoked by the LP solver when a solution (or delta solution) is found.
using	PartialSolveCallback
	Callback invoked by the LP solver when a solution (or delta solution) is found.
Protected Attributes inherited from delpi::LpSolver
Config	config_
	Configuration to use.
LpStats	stats_
	Statistics of the solver.
std::unordered_map< std::string, std::string >	info_
	Generic information map. Generally collected from the file.
std::unordered_map< Variable, int >	var_to_col_
	Theory column ⇔ Variable.
std::vector< Variable >	col_to_var_
	Literal ⇔ lp row.
std::vector< mpq_class >	solution_
	Solution vector.
std::vector< mpq_class >	dual_solution_
	Dual solution vector.
mpq_class	obj_lb_
	Lower bound on the objective value, if any.
mpq_class	obj_ub_
	Upper bound on the objective value, if any.
SolveCallback	solve_cb_
	Callback to call after solving the LP problem.
PartialSolveCallback	partial_solve_cb_
	Callback to call after solving the LP problem with a partial solution.
bool	is_min_
	Whether this is a minimization or maximization LP problem.
mpq_class	ninfinity_
	Negative infinity threshold value.
mpq_class	infinity_
	Infinity threshold value.

Detailed Description

Linear programming solver using a custom implementation of the Simplex algorithm.

It is based on the Bartels-Golub method.

Definition at line 27 of file DelpiLpSolver.h.

Member Function Documentation

◆ AddColumn()

LpSolver::ColumnIndex delpi::DelpiLpSolver::AddColumn	(	const Variable &	var,
		const mpq_class &	obj,
		const mpq_class &	lb,
		const mpq_class &	ub )

overridevirtual

Add a new bounded column to the LP problem, ensuring that the variable var is in the range \( [lb, ub] \) and has the objective coefficient obj.

Warning: The objective coefficient is set with respect to a minimisation problem.

Parameters

var	variable to add to the LP problem
obj	objective coefficient of the column
lb	lower bound of the column
ub	upper bound of the column

Returns: index of the last column added

Implements delpi::LpSolver.

Definition at line 60 of file DelpiLpSolver.cpp.

◆ AddRow()

LpSolver::RowIndex delpi::DelpiLpSolver::AddRow	(	const Expression::Addends &	lhs,
		FormulaKind	sense,
		const mpq_class &	rhs )

overridevirtual

Add a new row to the LP problem with the given lhs linear summation, sense and rhs.

The resulting row will be in the shape

\[lhs \text{ sense } rhs \]

where \( lhs \) is a linear expression, \( \text{ sense } \in \\{ \le, =, \ge \\} \) and \( rhs \) is a constant.

Parameters

lhs	linear summation on the left-hand side of the row
sense	sense of the row (i.e. <=, =, >=)
rhs	right-hand side of the row

Implements delpi::LpSolver.

Definition at line 81 of file DelpiLpSolver.cpp.

◆ AuxForm()

internal::Basis< mpq_class > delpi::DelpiLpSolver::AuxForm	(	const Matrix< mpq_class > &	slack_A,
		const Vector< mpq_class > &	slack_b,
		Matrix< mpq_class > &	aux_A,
		Vector< mpq_class > &	aux_c,
		std::vector< Index > &	aux_columns ) const

private

Convert a standard form LP problem into a feasible and bounded auxiliary problem.

It does so by introducing auxiliary variables for each row of the standard form problem where either no slack variable is present (i.e. the sense was originally equality) or the slack variable's coefficient and the right-hand side have different signs.

Precondition: ComputeSlackAndAuxVariables must have been called before this method.

Parameters

	slack_A	coefficient matrix of the problem in standard form
[out]	aux_A	coefficient matrix to be set in the auxiliary form with respect to std_A
[out]	aux_c	objective function coefficients to be set in the auxiliary form with respect to std_A

Returns: feasible and bounded basis for the auxiliary problem

Definition at line 420 of file DelpiLpSolver.cpp.

◆ column()

Column delpi::DelpiLpSolver::column ( ColumnIndex column_idx ) const

nodiscardoverridevirtual

Get the column at the given column_idx index.

Parameters

column_idx index of the column to get

Returns: column structure

Implements delpi::LpSolver.

Definition at line 37 of file DelpiLpSolver.cpp.

◆ ComputeSlackAndAuxVariables()

void delpi::DelpiLpSolver::ComputeSlackAndAuxVariables ( )

private

Compute the slack and auxiliary variables for the original LP problem stored in A_, b_ and c_ in order to convert it to the standard form and check its feasibility.

A generic LP problem is defined as:

\[\begin{array}{rl} \min & c^T x \\ \text{s.t.} & l_r \le Ax \le u_r \\ & l_c \le x \le u_c \end{array} \]

whereas the standard form is:

\[\begin{array}{rl} \min & c^T x \\ \text{s.t.} & Ax = b \\ & x \ge 0 \end{array} \]

It does so by introducing slack variables for each row of the original problem where the sense is not equality. The slack variables are non-negative and have a positive coefficient if the sense is less than or equal, and a negative coefficient if the sense is greater than or equal. Since equality constraints are already in the standard form, no slack variable is needed. To know which slack variable corresponds to which row, the method stores the indices of the (slack columns + 1) in the slack_columns_ vector, with the index being positive if the coefficient of the slack variable is 1, negative otherwise. The method also stores the indices of the will-be auxiliary columns in the aux_columns_ vector in a similar fashion, with the sign of the index being the same as the sign of its coefficient Auxiliary variables are added to each row where either no slack variable has been added or the slack variable's coefficient and the right-hand side have different signs.

Note: the aux_columns_ vector is cleared before storing the new indices.; the slack_columns_ vector is cleared before storing the new indices.

Warning: in order to save space, the values stored in slack_columns_ and aux_columns_ are the indices + 1 and the sign of the index is the same as the sign of the coefficient.

◆ InternalSolve()

template<IsAnyOf< double, mpq_class > T>

template LpResult delpi::DelpiLpSolver::InternalSolve	(	const Matrix< T > &	A,
		const Vector< T > &	b,
		const Vector< T > &	c,
		const T &	tolerance,
		internal::Basis< T > &	basis,
		Vector< T > *	x = nullptr,
		T *	obj = nullptr )

private

Solve the LP problem using the Simplex algorithm.

The input is assumed to be in standard form, i.e.

\[\begin{array}{rl} \min & c^T x \\ \text{s.t.} & Ax = b \\ & x \ge 0 \end{array} \]

Precondition: The LP problem must be in standard form.; A must have the same number of rows as b and the same number of columns as c.; A must have the same number of rows as basis has columns (and rows, since basis is a square matrix).; basis must be a feasible basis for the problem.

Parameters

A	coefficient matrix
b	rhs vector
c	objective function
basis	starting feasible basis
x	pointer to the solution vector. If nullptr, the solution will not be stored
obj	pointer to the objective value. If nullptr, the objective value will not be stored
tolerance	tolerance for the optimality check. Must be 0 for exact arithmetic.

Returns: LpResult::OPTIMAL if the problem is feasible, bounded and an optimal solution has been found; LpResult::UNBOUNDED if the problem is unbounded

Definition at line 140 of file DelpiLpSolver.cpp.

◆ RemoveAuxiliaryColumns()

void delpi::DelpiLpSolver::RemoveAuxiliaryColumns	(	const internal::Basis< mpq_class > &	feas_basis,
		const std::vector< Index > &	aux_columns,
		Matrix< mpq_class > &	slack_A,
		Vector< mpq_class > &	slack_b,
		internal::Basis< mpq_class > &	slack_basis ) const

private

Use aux_basis to update basis with a set of columns we know feasible.

If aux_basis still contains any auxiliary columns, they will be removed from the basis and the corresponding row in A and b will be removed as well, thus reducing the size of the problem.

Precondition: the auxiliary columns must be the rightmost columns the aux_basis' coefficient matrix.

Parameters

	feas_basis	basis obtained from the auxiliary problem that produces an objective value of 0
[in,out]	slack_A	coefficient matrix of the standard form problem
[out]	slack_b	rhs vector of the standard form problem
[out]	slack_basis	basis associated with the standard form problem to be updated

Definition at line 391 of file DelpiLpSolver.cpp.

◆ ReserveColumns()

void delpi::DelpiLpSolver::ReserveColumns ( int size )

overridevirtual

Reserve space for the given number of columns and rows.

Can speed up the addition of columns if the guess is close to the actual number.

Parameters

size	number of columns to reserve

Reimplemented from delpi::LpSolver.

Definition at line 52 of file DelpiLpSolver.cpp.

◆ ReserveRows()

void delpi::DelpiLpSolver::ReserveRows ( int size )

overridevirtual

Reserve space for the given number of rows.

Can speed up the addition of rows if the guess is close to the actual number.

Parameters

size	number of rows to reserve

Reimplemented from delpi::LpSolver.

Definition at line 56 of file DelpiLpSolver.cpp.

◆ row()

Row delpi::DelpiLpSolver::row ( RowIndex row_idx ) const

nodiscardoverridevirtual

Get the row at the given row_idx index.

Parameters

row_idx index of the row to get

Returns: row structure

Implements delpi::LpSolver.

Definition at line 42 of file DelpiLpSolver.cpp.

◆ SetBound()

void delpi::DelpiLpSolver::SetBound	(	Variable	var,
		const mpq_class &	lb,
		const mpq_class &	ub )

overridevirtual

Set the bounds of a var in the LP problem to the given lb and ub.

Parameters

var	variable to be bounded
lb	lower bound
ub	upper bound

Implements delpi::LpSolver.

Definition at line 91 of file DelpiLpSolver.cpp.

◆ SetCoefficient()

void delpi::DelpiLpSolver::SetCoefficient	(	RowIndex	row,
		ColumnIndex	column,
		const mpq_class &	value )

overridevirtual

Set the coefficient of the row constraint to apply at the column decisional variable.

Parameters

row	row of the constraint
column	column containing the decisional variable to set the coefficient for
value	new value of the coefficient

Implements delpi::LpSolver.

Definition at line 98 of file DelpiLpSolver.cpp.

◆ SetObjective()

void delpi::DelpiLpSolver::SetObjective	(	int	column,
		const mpq_class &	value )

overridevirtual

The the objective coefficient of the given column to the given value.

Parameters

column	column to set the objective for
value	new objective coefficient for the column

Implements delpi::LpSolver.

Definition at line 105 of file DelpiLpSolver.cpp.

◆ SlackForm()

void delpi::DelpiLpSolver::SlackForm	(	Matrix< mpq_class > &	slack_A,
		Vector< mpq_class > &	slack_c ) const

private

Convert a generic LP problem into the standard form by adding slack variables where needed.

A generic LP problem is defined as:

\[\begin{array}{rl} \min & c^T x \\ \text{s.t.} & l_r \le Ax \le u_r \\ & l_c \le x \le u_c \end{array} \]

whereas the standard form is:

\[\begin{array}{rl} \min & c^T x \\ \text{s.t.} & Ax = b \\ & x \ge 0 \end{array} \]

It does so by introducing slack variables for each row of the original problem where the sense is not equality. The slack variables are non-negative and have a positive coefficient if the sense is less than or equal, and a negative coefficient if the sense is greater than or equal. Since equality constraints are already in the standard form, no slack variable is needed.

Precondition: ComputeSlackAndAuxVariables must have been called before this method.

Parameters

[out]	slack_A	coefficient matrix to be set in the standard form with respect to A_
[out]	slack_c	objective function coefficients to be set in the standard form with respect to c_

◆ SolveCore()

LpResult delpi::DelpiLpSolver::SolveCore ( )

overrideprivatevirtual

Internal method that optimises the LP problem with the given delta.

Returns: OPTIMAL if an optimal solution has been found and the return value of delta is \( = 0 \); DELTA_OPTIMAL if a delta-optimal solution has been found and the return value of delta \(\ge 0 \); UNBOUNDED if the problem is unbounded; INFEASIBLE if the problem is infeasible; ERROR if an error occurred

Implements delpi::LpSolver.

Definition at line 117 of file DelpiLpSolver.cpp.

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

delpi/solver/DelpiLpSolver.h
delpi/solver/DelpiLpSolver.cpp

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Function Documentation

◆ AddColumn()

◆ AddRow()

◆ AuxForm()

◆ column()

◆ ComputeSlackAndAuxVariables()

◆ InternalSolve()

◆ RemoveAuxiliaryColumns()

◆ ReserveColumns()

◆ ReserveRows()

◆ row()

◆ SetBound()

◆ SetCoefficient()

◆ SetObjective()

◆ SlackForm()

◆ SolveCore()