Linear programming solver using QSopt_ex. More...

#include <QsoptexLpSolver.h>

Inheritance diagram for delpi::QsoptexLpSolver:

Public Member Functions
Column	column (int column_idx) const override
	Get the column at the given column_idx index.
Row	row (int row_idx) const override
	Get the row at the given row_idx index.
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.
void	UpdateStats (unsigned int precision)
	Update the lp stats from the QSopt_ex solver.
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.
virtual void	ReserveColumns (int size)
	Reserve space for the given number of columns and rows.
virtual void	ReserveRows (int size)
	Reserve space for the given number of rows.
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>
void	SetRowCoeff (int row, const T &literal_monomials)
	Parse a sequence of literal_monomials and set the coefficient for each decisional variable appearing in it.
void	SetVarCoeff (int row, const Variable &var, const mpq_class &value) const
	Set the coefficients to apply to var on a specific row.
void	UpdateFeasible ()
	Use the result from the lp solver to update the solution vector and objective value.

Private Attributes
mpq_QSprob	qsx_
	QSopt_ex LP solver.
QSbasis	basis_
	Last basis.
qsopt_ex::MpqArray	ray_
	Ray of the last infeasible solution.
qsopt_ex::MpqArray	x_
	Solution vector.

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

Definition at line 29 of file QsoptexLpSolver.h.

Member Function Documentation

◆ AddColumn()

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

◆ AddRow()

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

◆ column()

Column delpi::QsoptexLpSolver::column ( int 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 65 of file QsoptexLpSolver.cpp.

◆ row()

Row delpi::QsoptexLpSolver::row ( int 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 82 of file QsoptexLpSolver.cpp.

◆ SetBound()

void delpi::QsoptexLpSolver::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 162 of file QsoptexLpSolver.cpp.

◆ SetCoefficient()

void delpi::QsoptexLpSolver::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 322 of file QsoptexLpSolver.cpp.

◆ SetObjective()

void delpi::QsoptexLpSolver::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 174 of file QsoptexLpSolver.cpp.

◆ SetRowCoeff()

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

template void delpi::QsoptexLpSolver::SetRowCoeff	(	int	row,
		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

row	row to set the coefficients for
literal_monomials	symbolic formula representing the row

Definition at line 276 of file QsoptexLpSolver.cpp.

◆ SetVarCoeff()

void delpi::QsoptexLpSolver::SetVarCoeff	(	int	row,
		const Variable &	var,
		const mpq_class &	value ) const

private

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

Parameters

row	row to set the coefficients for
var	variable to set the coefficients for
value	value to set the coefficients to

Definition at line 304 of file QsoptexLpSolver.cpp.

◆ SolveCore()

LpResult delpi::QsoptexLpSolver::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 180 of file QsoptexLpSolver.cpp.

◆ UpdateFeasible()

void delpi::QsoptexLpSolver::UpdateFeasible ( )

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

Definition at line 224 of file QsoptexLpSolver.cpp.

◆ UpdateStats()

void delpi::QsoptexLpSolver::UpdateStats ( unsigned int precision )

Update the lp stats from the QSopt_ex solver.

The precision must be captured before calling this method.

Parameters

precision precision used to obtain the solution

Definition at line 238 of file QsoptexLpSolver.cpp.

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

delpi/solver/QsoptexLpSolver.h
delpi/solver/QsoptexLpSolver.cpp

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Function Documentation

◆ AddColumn()

◆ AddRow()

◆ column()

◆ row()

◆ SetBound()

◆ SetCoefficient()

◆ SetObjective()

◆ SetRowCoeff()

◆ SetVarCoeff()

◆ SolveCore()

◆ UpdateFeasible()

◆ UpdateStats()