Class representing a linear program. More...

#include <agrum/CN/LpInterface.h>

Collaboration diagram for gum::credal::lp::LpInterface< GUM_SCALAR >:

Public Member Functions
LpCol	addCol ()
	Insert a new column, i.e.
std::vector< LpCol >	addCols (const unsigned int &cols)
	Insert new columns, i.e.
void	addRow (const LpExpr &expr)
	Add rows to the linear program according to a given expression ( which must be at least an inequality ).
void	addRow (LpExpr &&expr)
	Add rows to the linear program according to a given expression ( which must be at least an inequality ).
void	addPositivity ()
	Add positivity constraints for all variables.
void	addSumIsOne ()
	Add sum of variables is 1 constraints.
void	addProba ()
	Add positivity constraints and sum of variables is 1 ( probability constraints ).
std::vector< std::vector< GUM_SCALAR > >	solve ()
	Solve the linear program (H-representation of the polytope) by enumeration (of the polytope vertices) using lexicographic reverse search (lrs).
std::vector< LpCol >	getCols () const
	Get the variables of the LP.
std::string	toString () const
	Get the string representation of a calling linear program.
void	clear ()
	Reset the rows (inequalities) and columns (variables) of the LP as if it was created.
void	clearRows ()
	Reset the rows (inequalities) of the LP but not the columns (variables are kept).
Constructor / Destructor
	LpInterface ()
	Default constructor, empty problem.
	LpInterface (const LpInterface< GUM_SCALAR > &from)
	Copy constructor.
	LpInterface (LpInterface< GUM_SCALAR > &&from)
	Move copy constructor.
	~LpInterface ()
	Default destructor.
Compound assignment operator
LpInterface< GUM_SCALAR > &	operator= (const LpInterface< GUM_SCALAR > &from)
	Copy compound assignment.
LpInterface< GUM_SCALAR > &	operator= (LpInterface< GUM_SCALAR > &&from)
	Move coumpound assignment.

Private Attributes
std::vector< LpRow * >	_rows_
	Rows of the problem.
std::vector< LpCol >	_cols_
	Variables of the problem.
bool	_positivity_
	`true` if addPositivity() has been called, `false` otherwise.
bool	_sumIsOne_
	`true` if addSumIsOne() has been called, `false` otherwise.

Friends
template<typename T>
std::ostream &	operator<< (std::ostream &out, const LpInterface< T > &lpi)
	Overload of `<<` to use with output streams ( such as std::cout << ).

Detailed Description

template<GUM_Numeric GUM_SCALAR>
class gum::credal::lp::LpInterface< GUM_SCALAR >

Class representing a linear program.

Author: Matthieu HOURBRACQ and Pierre-Henri WUILLEMIN(_at_LIP6)

Definition at line 624 of file LpInterface.h.

Constructor & Destructor Documentation

◆ LpInterface() [1/3]

template<GUM_Numeric GUM_SCALAR>

gum::credal::lp::LpInterface< GUM_SCALAR >::LpInterface ( )

Default constructor, empty problem.

class LpInterface

Definition at line 110 of file LpInterface_tpl.h.

                                             {
        _positivity_ = false;
        _sumIsOne_   = false;
        GUM_CONSTRUCTOR(LpInterface);
      }

References LpInterface(), _positivity_, and _sumIsOne_.

Referenced by LpInterface(), LpInterface(), LpInterface(), ~LpInterface(), operator<<, operator=(), and operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ LpInterface() [2/3]

template<GUM_Numeric GUM_SCALAR>

gum::credal::lp::LpInterface< GUM_SCALAR >::LpInterface ( const LpInterface< GUM_SCALAR > & from )

Copy constructor.

Parameters

from	The LpInterface to be copied.

Definition at line 117 of file LpInterface_tpl.h.

                                                                                  :
          _cols_(from._cols_), _positivity_(from._positivity_), _sumIsOne_(from._sumIsOne_) {
        _rows_.resize(from._rows_.size());
 
        for (unsigned int i = 0, end = from._rows_.size(); i < end; i++)
          _rows_[i] = new LpRow(*from._rows_[i]);
 
        GUM_CONS_CPY(LpInterface);
      }

References LpInterface(), _cols_, _positivity_, _rows_, and _sumIsOne_.

Here is the call graph for this function:

◆ LpInterface() [3/3]

template<GUM_Numeric GUM_SCALAR>

gum::credal::lp::LpInterface< GUM_SCALAR >::LpInterface ( LpInterface< GUM_SCALAR > && from )

Move copy constructor.

Parameters

from	The temporary LpInterface to be moved.

Definition at line 128 of file LpInterface_tpl.h.

                                                                             :
          _positivity_(from._positivity_), _sumIsOne_(from._sumIsOne_) {
        _rows_.swap(from._rows_);
        _cols_.swap(from._cols_);
        GUM_CONS_CPY(LpInterface);
      }

References LpInterface(), _cols_, _positivity_, _rows_, and _sumIsOne_.

Here is the call graph for this function:

◆ ~LpInterface()

template<GUM_Numeric GUM_SCALAR>

gum::credal::lp::LpInterface< GUM_SCALAR >::~LpInterface ( )

Default destructor.

Definition at line 136 of file LpInterface_tpl.h.

                                              {
        for (const auto row: _rows_)
          delete row;
 
        GUM_DESTRUCTOR(LpInterface);
      }

References LpInterface(), and _rows_.

Here is the call graph for this function:

Member Function Documentation

◆ addCol()

template<GUM_Numeric GUM_SCALAR>

LpCol gum::credal::lp::LpInterface< GUM_SCALAR >::addCol ( )

Insert a new column, i.e.

a new variable.

Returns: A copy of the variable.

Definition at line 184 of file LpInterface_tpl.h.

                                              {
        LpCol col((unsigned int)_cols_.size());
 
        _cols_.push_back(col);
 
        return col;
      }

References _cols_.

◆ addCols()

template<GUM_Numeric GUM_SCALAR>

std::vector< LpCol > gum::credal::lp::LpInterface< GUM_SCALAR >::addCols ( const unsigned int & cols )

Insert new columns, i.e.

new variables.

Parameters

cols	the constant reference to the number of variables we want.

Returns: The copy of the vector of all variables of the problem.

Definition at line 193 of file LpInterface_tpl.h.

                                                                                    {
        if (cols < 1)
          GUM_ERROR(OperationNotAllowed,
                    "LpInterface::addCols ( cols ) : cols "
                    "needs must be equal or greater than 1 : "
                        << cols << " < 1");
 
        for (unsigned int i = 0; i < cols; i++) {
          _cols_.push_back(LpCol((unsigned int)_cols_.size()));
        }
 
        return _cols_;
      }

References gum::credal::lp::LpCol::LpCol(), _cols_, and GUM_ERROR.

Here is the call graph for this function:

◆ addPositivity()

template<GUM_Numeric GUM_SCALAR>

void gum::credal::lp::LpInterface< GUM_SCALAR >::addPositivity ( )

Add positivity constraints for all variables.

Definition at line 256 of file LpInterface_tpl.h.

                                                    {
        if (_positivity_) return;
 
        for (const auto& col: _cols_)
          addRow(0 <= col);
 
        _positivity_ = true;
      }

References _cols_, _positivity_, and addRow().

Referenced by addProba().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ addProba()

template<GUM_Numeric GUM_SCALAR>

void gum::credal::lp::LpInterface< GUM_SCALAR >::addProba ( )

Add positivity constraints and sum of variables is 1 ( probability constraints ).

Definition at line 280 of file LpInterface_tpl.h.

                                               {
        if (_positivity_ && _sumIsOne_) {
          return;
        } else if (_positivity_ && !_sumIsOne_) {
          addSumIsOne();
          return;
        } else if (!_positivity_ && _sumIsOne_) {
          addPositivity();
          return;
        }
 
        // we can do both with one loop, don't call the above functions.
        // addPositivity();
        // addSumIsOne();
        LpExpr expr;
 
        for (const auto& col: _cols_) {
          addRow(0 <= col);
          expr += col;
        }
 
        addRow(1 <= std::move(expr) <= 1);
 
        _sumIsOne_   = true;
        _positivity_ = true;
      }

References _cols_, _positivity_, _sumIsOne_, addPositivity(), addRow(), and addSumIsOne().

Here is the call graph for this function:

◆ addRow() [1/2]

template<GUM_Numeric GUM_SCALAR>

void gum::credal::lp::LpInterface< GUM_SCALAR >::addRow ( const LpExpr & expr )

Add rows to the linear program according to a given expression ( which must be at least an inequality ).

Parameters

expr	the constant reference to the expression to convert to rows.

Definition at line 208 of file LpInterface_tpl.h.

                                                               {
        if (!expr._ileft_ && !expr._iright_)
          GUM_ERROR(OperationNotAllowed,
                    "addRow ( const LpExpr & expr ) : expr : " << expr.toString()
                                                               << "is not an inequality.");
 
        if ((expr._ileft_ && !expr._iright_) || (!expr._ileft_ && expr._iright_)) {
          _rows_.push_back(new LpRow(expr, _cols_));
        } else {
          LpExpr lexpr(expr, true, true, false);
          LpExpr rexpr(expr, false, true, true);
 
          _rows_.push_back(new LpRow(std::move(lexpr),
                                     _cols_));   
          _rows_.push_back(new LpRow(std::move(rexpr),
                                     _cols_));   
        }
      }

References gum::credal::lp::LpRow::LpRow(), _cols_, gum::credal::lp::LpExpr::_ileft_, gum::credal::lp::LpExpr::_iright_, _rows_, GUM_ERROR, and gum::credal::lp::LpExpr::toString().

Referenced by addPositivity(), addProba(), and addSumIsOne().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ addRow() [2/2]

template<GUM_Numeric GUM_SCALAR>

void gum::credal::lp::LpInterface< GUM_SCALAR >::addRow ( LpExpr && expr )

Add rows to the linear program according to a given expression ( which must be at least an inequality ).

Parameters

expr	the temporary expression to move to rows.

Definition at line 228 of file LpInterface_tpl.h.

                                                          {
        if (!expr._ileft_ && !expr._iright_)
          GUM_ERROR(OperationNotAllowed,
                    "addRow ( const LpExpr & expr ) : expr : " << expr.toString()
                                                               << "is not an inequality.");
 
        if ((expr._ileft_ && !expr._iright_) || (!expr._ileft_ && expr._iright_)) {
          _rows_.push_back(new LpRow(std::move(expr), _cols_));
        } else {
          LpExpr lexpr(std::move(expr), true, true, false);
          LpExpr rexpr(std::move(expr), false, false, true);
 
          *rexpr._mCoeffs_ = *lexpr._mCoeffs_;
          rexpr._mValue_   = lexpr._mValue_;
          rexpr._imiddle_  = true;
 
          _rows_.push_back(new LpRow(std::move(lexpr),
                                     _cols_));   
          _rows_.push_back(new LpRow(std::move(rexpr),
                                     _cols_));   
        }
      }

References gum::credal::lp::LpRow::LpRow(), _cols_, gum::credal::lp::LpExpr::_imiddle_, gum::credal::lp::LpExpr::_mCoeffs_, gum::credal::lp::LpExpr::_mValue_, _rows_, and GUM_ERROR.

Here is the call graph for this function:

◆ addSumIsOne()

template<GUM_Numeric GUM_SCALAR>

void gum::credal::lp::LpInterface< GUM_SCALAR >::addSumIsOne ( )

Add sum of variables is 1 constraints.

Definition at line 266 of file LpInterface_tpl.h.

                                                  {
        if (_sumIsOne_) return;
 
        LpExpr expr;
 
        for (const auto& col: _cols_)
          expr += col;
 
        addRow(1 <= std::move(expr) <= 1);
 
        _sumIsOne_ = true;
      }

References _cols_, _sumIsOne_, and addRow().

Referenced by addProba().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ clear()

template<GUM_Numeric GUM_SCALAR>

void gum::credal::lp::LpInterface< GUM_SCALAR >::clear ( )

Reset the rows (inequalities) and columns (variables) of the LP as if it was created.

Definition at line 358 of file LpInterface_tpl.h.

                                            {
        for (const auto& row: _rows_)
          delete row;
 
        _rows_.clear();
        _rows_.shrink_to_fit();   
 
        _cols_.clear();
        _cols_.shrink_to_fit();
 
        _positivity_ = false;
        _sumIsOne_   = false;
      }

References _cols_, _positivity_, _rows_, and _sumIsOne_.

Referenced by operator=().

Here is the caller graph for this function:

◆ clearRows()

template<GUM_Numeric GUM_SCALAR>

void gum::credal::lp::LpInterface< GUM_SCALAR >::clearRows ( )

Reset the rows (inequalities) of the LP but not the columns (variables are kept).

Definition at line 376 of file LpInterface_tpl.h.

                                                {
        for (const auto& row: _rows_)
          delete row;
 
        _rows_.clear();
        _rows_.shrink_to_fit();
 
        _positivity_ = false;
        _sumIsOne_   = false;
      }

References _positivity_, _rows_, and _sumIsOne_.

◆ getCols()

template<GUM_Numeric GUM_SCALAR>

std::vector< LpCol > gum::credal::lp::LpInterface< GUM_SCALAR >::getCols ( ) const

Get the variables of the LP.

Returns: A copy of the variables as a vector of variables.

Definition at line 334 of file LpInterface_tpl.h.

                                                                  {
        return _cols_;
      }

References _cols_.

◆ operator=() [1/2]

template<GUM_Numeric GUM_SCALAR>

LpInterface< GUM_SCALAR > & gum::credal::lp::LpInterface< GUM_SCALAR >::operator= ( const LpInterface< GUM_SCALAR > & from )

Copy compound assignment.

Parameters

from	The LpInterface to be copied.

Definition at line 145 of file LpInterface_tpl.h.

                                                                                  {
        for (const auto& row: _rows_)
          delete row;
 
        _rows_.clear();
        _rows_.shrink_to_fit();
 
        _rows_.resize(from._rows_.size());
 
        for (unsigned int i = 0, end = from._rows_.size(); i < end; i++)
          _rows_[i] = new LpRow(*from._rows_[i]);
 
        _cols_       = from._cols_;
        _positivity_ = from._positivity_;
        _sumIsOne_   = from._sumIsOne_;
 
        return *this;
      }

References LpInterface(), gum::credal::lp::LpRow::LpRow(), _cols_, _positivity_, _rows_, _sumIsOne_, and clear().

Here is the call graph for this function:

◆ operator=() [2/2]

template<GUM_Numeric GUM_SCALAR>

LpInterface< GUM_SCALAR > & gum::credal::lp::LpInterface< GUM_SCALAR >::operator= ( LpInterface< GUM_SCALAR > && from )

Move coumpound assignment.

Parameters

from	The temporary LpInterface to be moved.

Definition at line 167 of file LpInterface_tpl.h.

                                                                             {
        _rows_.swap(from._rows_);
        _cols_.swap(from._cols_);
 
        _positivity_ = from._positivity_;
        _sumIsOne_   = from._sumIsOne_;
 
        return *this;
      }

References LpInterface(), _cols_, _positivity_, _rows_, and _sumIsOne_.

Here is the call graph for this function:

◆ solve()

template<GUM_Numeric GUM_SCALAR>

std::vector< std::vector< GUM_SCALAR > > gum::credal::lp::LpInterface< GUM_SCALAR >::solve ( )

Solve the linear program (H-representation of the polytope) by enumeration (of the polytope vertices) using lexicographic reverse search (lrs).

Only works with bounded polyhedron (polytopes) and not unbounded ones (i.e. defined by vertices and rays).

Returns: The V-representation (vertices) of the polytope as a vector of vectors (vector of vertices).

Definition at line 308 of file LpInterface_tpl.h.

                                                                            {
        LRSWrapper< GUM_SCALAR > lrs;
 
        lrs.setUpH((unsigned int)_cols_.size());
 
        std::vector< std::vector< GUM_SCALAR > > lrsMatrix;
 
        for (const auto& row: _rows_) {
          std::vector< GUM_SCALAR > expandedRow(_cols_.size() + 1, 0);
 
          expandedRow[0] = row->_cste_;
 
          for (const auto& elt: *row->_coeffs_)
            expandedRow[elt.first.id() + 1] = elt.second;
 
          lrsMatrix.push_back(expandedRow);
        }
 
        lrs.fillMatrix(lrsMatrix);
 
        lrs.H2V();
 
        return lrs.getOutput();
      }

References _cols_, _rows_, gum::credal::LRSWrapper< GUM_SCALAR >::fillMatrix(), gum::credal::LRSWrapper< GUM_SCALAR >::getOutput(), gum::credal::LRSWrapper< GUM_SCALAR >::H2V(), and gum::credal::LRSWrapper< GUM_SCALAR >::setUpH().

Here is the call graph for this function:

◆ toString()

template<GUM_Numeric GUM_SCALAR>

std::string gum::credal::lp::LpInterface< GUM_SCALAR >::toString ( ) const

Get the string representation of a calling linear program.

Returns: The string representation of the calling linear program.

Definition at line 339 of file LpInterface_tpl.h.

                                                          {
        std::ostringstream s;
 
        s << std::endl << std::endl << "Variables : " << std::endl;
 
        for (const auto& col: _cols_)
          s << " " << col.toString();
 
        s << std::endl;
 
        for (const auto& row: _rows_)
          s << std::endl << row->toString();
 
        s << std::endl << std::endl;
 
        return s.str();
      }

References _cols_, and _rows_.

Referenced by operator<<.

Here is the caller graph for this function:

◆ operator<<

template<GUM_Numeric GUM_SCALAR>

template<typename T>

std::ostream & operator<<	(	std::ostream &	out,
		const LpInterface< T > &	lpi )

friend

Overload of << to use with output streams ( such as std::cout << ).

Parameters

out	the reference to the caller, i.e. left side of `<<`.
lpi	the constant reference to the linear program whose representation we want.

Returns: The address of the caller.

Definition at line 178 of file LpInterface_tpl.h.

                                                                           {
        out << lpi.toString();
        return out;
      }

References LpInterface(), operator<<, and toString().

Referenced by operator<<.

Member Data Documentation

◆ _cols_

template<GUM_Numeric GUM_SCALAR>

std::vector< LpCol > gum::credal::lp::LpInterface< GUM_SCALAR >::_cols_

private

Variables of the problem.

Definition at line 774 of file LpInterface.h.

Referenced by LpInterface(), LpInterface(), addCol(), addCols(), addPositivity(), addProba(), addRow(), addRow(), addSumIsOne(), clear(), getCols(), operator=(), operator=(), solve(), and toString().

◆ _positivity_

template<GUM_Numeric GUM_SCALAR>

bool gum::credal::lp::LpInterface< GUM_SCALAR >::_positivity_

private

true if addPositivity() has been called, false otherwise.

Definition at line 778 of file LpInterface.h.

Referenced by LpInterface(), LpInterface(), LpInterface(), addPositivity(), addProba(), clear(), clearRows(), operator=(), and operator=().

◆ _rows_

template<GUM_Numeric GUM_SCALAR>

std::vector< LpRow* > gum::credal::lp::LpInterface< GUM_SCALAR >::_rows_

private

Rows of the problem.

Definition at line 772 of file LpInterface.h.

Referenced by LpInterface(), LpInterface(), ~LpInterface(), addRow(), addRow(), clear(), clearRows(), operator=(), operator=(), solve(), and toString().

◆ _sumIsOne_

template<GUM_Numeric GUM_SCALAR>

bool gum::credal::lp::LpInterface< GUM_SCALAR >::_sumIsOne_

private

true if addSumIsOne() has been called, false otherwise.

Definition at line 781 of file LpInterface.h.

Referenced by LpInterface(), LpInterface(), LpInterface(), addProba(), addSumIsOne(), clear(), clearRows(), operator=(), and operator=().

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

agrum/CN/polytope/LpInterface.h
agrum/CN/polytope/LpInterface_tpl.h

Public Member Functions

Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ LpInterface() [1/3]

◆ LpInterface() [2/3]

◆ LpInterface() [3/3]

◆ ~LpInterface()

Member Function Documentation

◆ addCol()

◆ addCols()

◆ addPositivity()

◆ addProba()

◆ addRow() [1/2]

◆ addRow() [2/2]

◆ addSumIsOne()

◆ clear()

◆ clearRows()

◆ getCols()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ solve()

◆ toString()

Friends And Related Symbol Documentation

◆ operator<<

Member Data Documentation

◆ _cols_

◆ _positivity_

◆ _rows_

◆ _sumIsOne_