Linear programming solver using SoPlex. More...

#include <SoplexLpSolver.h>

Inheritance diagram for delpi::SoplexLpSolver:

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<TypedIterable< std::pair< const Variable, mpq_class > > T>
soplex::DSVectorRational	ParseRowCoeff (const T &literal_monomials)
	Parse a sequence of literal_monomials and set the coefficient for each decisional variable appearing in it.
void	SetVarCoeff (soplex::DSVectorRational &coeffs, const Variable &var, const mpq_class &value) const
	Set the coefficients to apply to var on a specific row.
void	UpdateFeasible (const soplex::Rational &max_violation)
	Use the result from the lp solver to update the solution vector and objective value.

Private Attributes
bool	consolidated_
	Whether the LP problem has been consolidated.
soplex::SoPlex	spx_
	SoPlex LP solver.
soplex::LPColSetRational	spx_cols_
	Columns of the LP problem.
soplex::LPRowSetRational	spx_rows_
	Rows of the LP problem.
soplex::Rational	rninfinity_
	Rational negative infinity.
soplex::Rational	rinfinity_
	Rational positive infinity.

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 SoPlex.

Definition at line 29 of file SoplexLpSolver.h.

Member Function Documentation

◆ AddColumn()

LpSolver::ColumnIndex delpi::SoplexLpSolver::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 97 of file SoplexLpSolver.cpp.

◆ AddRow()

LpSolver::RowIndex delpi::SoplexLpSolver::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 121 of file SoplexLpSolver.cpp.

◆ column()

Column delpi::SoplexLpSolver::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 57 of file SoplexLpSolver.cpp.

◆ ParseRowCoeff()

template<TypedIterable< std::pair< const Variable, mpq_class > > T>

template soplex::DSVectorRational delpi::SoplexLpSolver::ParseRowCoeff ( const T & literal_monomials )

private

Parse a sequence of literal_monomials and set the coefficient for each decisional variable appearing in it.

Template Parameters

T	generic iterable containing pairs (Variable, coeff) (i.e. std::vector, std::set, std::span)

Parameters

literal_monomials symbolic formula representing the row

Definition at line 275 of file SoplexLpSolver.cpp.

◆ ReserveColumns()

void delpi::SoplexLpSolver::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 88 of file SoplexLpSolver.cpp.

◆ ReserveRows()

void delpi::SoplexLpSolver::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 92 of file SoplexLpSolver.cpp.

◆ row()

Row delpi::SoplexLpSolver::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 70 of file SoplexLpSolver.cpp.

◆ SetBound()

void delpi::SoplexLpSolver::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 133 of file SoplexLpSolver.cpp.

◆ SetCoefficient()

void delpi::SoplexLpSolver::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 141 of file SoplexLpSolver.cpp.

◆ SetObjective()

void delpi::SoplexLpSolver::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 159 of file SoplexLpSolver.cpp.

◆ SetVarCoeff()

void delpi::SoplexLpSolver::SetVarCoeff	(	soplex::DSVectorRational &	coeffs,
		const Variable &	var,
		const mpq_class &	value ) const

private

Set the coefficients to apply to var on a specific row.

The coefficient is set in coeff.

Parameters

[in,out]	coeffs	vector of coefficients to apply to the decisional variables
	var	variable to set the coefficients for
	value	value to set the coefficients to

Definition at line 281 of file SoplexLpSolver.cpp.

◆ SolveCore()

LpResult delpi::SoplexLpSolver::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 167 of file SoplexLpSolver.cpp.

◆ UpdateFeasible()

void delpi::SoplexLpSolver::UpdateFeasible ( const soplex::Rational & max_violation )

private

Use the result from the lp solver to update the solution vector and objective value.

The lp solver was able to find a feasible solution to the problem. The useful information will be stored in solution_ and dual_solution_.

Parameters

max_violation maximum distance of the solution from the optimal value

Definition at line 210 of file SoplexLpSolver.cpp.

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

delpi/solver/SoplexLpSolver.h
delpi/solver/SoplexLpSolver.cpp

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Function Documentation

◆ AddColumn()

◆ AddRow()

◆ column()

◆ ParseRowCoeff()

◆ ReserveColumns()

◆ ReserveRows()

◆ row()

◆ SetBound()

◆ SetCoefficient()

◆ SetObjective()

◆ SetVarCoeff()

◆ SolveCore()

◆ UpdateFeasible()