aGrUM 2.3.2
a C++ library for (probabilistic) graphical models
LpInterface_tpl.h
Go to the documentation of this file.
1/****************************************************************************
2 * This file is part of the aGrUM/pyAgrum library. *
3 * *
4 * Copyright (c) 2005-2025 by *
5 * - Pierre-Henri WUILLEMIN(_at_LIP6) *
6 * - Christophe GONZALES(_at_AMU) *
7 * *
8 * The aGrUM/pyAgrum library is free software; you can redistribute it *
9 * and/or modify it under the terms of either : *
10 * *
11 * - the GNU Lesser General Public License as published by *
12 * the Free Software Foundation, either version 3 of the License, *
13 * or (at your option) any later version, *
14 * - the MIT license (MIT), *
15 * - or both in dual license, as here. *
16 * *
17 * (see https://agrum.gitlab.io/articles/dual-licenses-lgplv3mit.html) *
18 * *
19 * This aGrUM/pyAgrum library is distributed in the hope that it will be *
20 * useful, but WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, *
21 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES MERCHANTABILITY or FITNESS *
22 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE *
23 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER *
24 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, *
25 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR *
26 * OTHER DEALINGS IN THE SOFTWARE. *
27 * *
28 * See LICENCES for more details. *
29 * *
30 * SPDX-FileCopyrightText: Copyright 2005-2025 *
31 * - Pierre-Henri WUILLEMIN(_at_LIP6) *
32 * - Christophe GONZALES(_at_AMU) *
33 * SPDX-License-Identifier: LGPL-3.0-or-later OR MIT *
34 * *
35 * Contact : info_at_agrum_dot_org *
36 * homepage : http://agrum.gitlab.io *
37 * gitlab : https://gitlab.com/agrumery/agrum *
38 * *
39 ****************************************************************************/
40#pragma once
41
42
43#include "LpInterface.h"
44
45namespace gum {
46 namespace credal {
47 namespace lp {
48
52 template < typename SCALAR >
53 LpExpr& LpExpr::operator=(const SCALAR& rhs) {
54 clear();
55
56 _mValue_ = rhs;
57 _imiddle_ = true;
58
59 return *this;
60 }
61
62 template < typename T >
63 LpExpr& LpExpr::operator+=(const T& rhs) {
64 if (_ileft_ || _iright_)
65 GUM_ERROR(OperationNotAllowed, "expr::operator+= (expr) : <= present on one side of expr")
66
67 if (!_imiddle_) _imiddle_ = true;
68
69 _mValue_ += rhs;
70
71 return *this;
72 }
73
74 template < typename T >
75 LpExpr& LpExpr::operator-=(const T& rhs) {
76 if (_ileft_ || _iright_)
77 GUM_ERROR(OperationNotAllowed, "expr::operator-= (rhs) : <= present in one of expr")
78
79 if (!_imiddle_) _imiddle_ = true;
80
81 _mValue_ -= rhs;
82
83 return *this;
84 }
85
86 template < typename SCALAR >
87 void LpExpr::_addSide_(const SCALAR& from) {
88 if (!_ileft_) {
89 _lValue_ = from;
90 _ileft_ = true;
91 } else if (!_imiddle_) {
92 _mValue_ = from;
93 _imiddle_ = true;
94 } else if (!_iright_) {
95 _rValue_ = from;
96 _iright_ = true;
97 } else
99 "LpExpr::setSide ( const LpCol & from "
100 ") : too many <= ; no free side");
101 }
102
106 template < typename GUM_SCALAR >
108 _positivity_ = false;
109 _sumIsOne_ = false;
110 GUM_CONSTRUCTOR(LpInterface);
111 }
112
113 template < typename GUM_SCALAR >
116 _rows_.resize(from._rows_.size());
117
118 for (unsigned int i = 0, end = from._rows_.size(); i < end; i++)
119 _rows_[i] = new LpRow(*from._rows_[i]);
120
121 GUM_CONS_CPY(LpInterface);
122 }
123
124 template < typename GUM_SCALAR >
127 _rows_.swap(from._rows_);
128 _cols_.swap(from._cols_);
129 GUM_CONS_CPY(LpInterface);
130 }
131
132 template < typename GUM_SCALAR >
134 for (const auto row: _rows_)
135 delete row;
136
137 GUM_DESTRUCTOR(LpInterface);
138 }
139
140 template < typename GUM_SCALAR >
144 for (const auto& row: _rows_)
145 delete row;
146
147 _rows_.clear();
148 _rows_.shrink_to_fit();
149
150 _rows_.resize(from._rows_.size());
151
152 for (unsigned int i = 0, end = from._rows_.size(); i < end; i++)
153 _rows_[i] = new LpRow(*from._rows_[i]);
154
155 _cols_ = from._cols_;
157 _sumIsOne_ = from._sumIsOne_;
158
159 return *this;
160 }
161
162 template < typename GUM_SCALAR >
165 _rows_.swap(from._rows_);
166 _cols_.swap(from._cols_);
167
168 _positivity_ = from._positivity_;
169 _sumIsOne_ = from._sumIsOne_;
170
171 return *this;
172 }
173
174 template < typename T >
175 std::ostream& operator<<(std::ostream& out, const LpInterface< T >& lpi) {
176 out << lpi.toString();
177 return out;
178 }
179
180 template < typename GUM_SCALAR >
182 LpCol col((unsigned int)_cols_.size());
183
184 _cols_.push_back(col);
185
186 return col;
187 }
188
189 template < typename GUM_SCALAR >
190 std::vector< LpCol > LpInterface< GUM_SCALAR >::addCols(const unsigned int& cols) {
191 if (cols < 1)
193 "LpInterface::addCols ( cols ) : cols "
194 "needs must be equal or greater than 1 : "
195 << cols << " < 1");
196
197 for (unsigned int i = 0; i < cols; i++) {
198 _cols_.push_back(LpCol((unsigned int)_cols_.size()));
199 }
200
201 return _cols_;
202 }
203
204 template < typename GUM_SCALAR >
206 if (!expr._ileft_ && !expr._iright_)
208 "addRow ( const LpExpr & expr ) : expr : " << expr.toString()
209 << "is not an inequality.");
210
211 if ((expr._ileft_ && !expr._iright_) || (!expr._ileft_ && expr._iright_)) {
212 _rows_.push_back(new LpRow(expr, _cols_));
213 } else {
214 LpExpr lexpr(expr, true, true, false);
215 LpExpr rexpr(expr, false, true, true);
216
217 _rows_.push_back(new LpRow(std::move(lexpr),
218 _cols_));
219 _rows_.push_back(new LpRow(std::move(rexpr),
220 _cols_));
221 }
222 }
223
224 template < typename GUM_SCALAR >
226 if (!expr._ileft_ && !expr._iright_)
228 "addRow ( const LpExpr & expr ) : expr : " << expr.toString()
229 << "is not an inequality.");
230
231 if ((expr._ileft_ && !expr._iright_) || (!expr._ileft_ && expr._iright_)) {
232 _rows_.push_back(new LpRow(std::move(expr), _cols_));
233 } else {
234 LpExpr lexpr(std::move(expr), true, true, false);
235
237 LpExpr rexpr(std::move(expr), false, false, true);
238
240
241 *rexpr._mCoeffs_ = *lexpr._mCoeffs_;
242 rexpr._mValue_ = lexpr._mValue_;
243 rexpr._imiddle_ = true;
244
245 _rows_.push_back(new LpRow(std::move(lexpr),
246 _cols_));
247 _rows_.push_back(new LpRow(std::move(rexpr),
248 _cols_));
249 }
250 }
251
252 template < typename GUM_SCALAR >
254 if (_positivity_) return;
255
256 for (const auto& col: _cols_)
257 addRow(0 <= col);
258
259 _positivity_ = true;
260 }
261
262 template < typename GUM_SCALAR >
264 if (_sumIsOne_) return;
265
266 LpExpr expr;
267
268 for (const auto& col: _cols_)
269 expr += col;
270
271 addRow(1 <= std::move(expr) <= 1);
272
273 _sumIsOne_ = true;
274 }
275
276 template < typename GUM_SCALAR >
278 if (_positivity_ && _sumIsOne_) {
279 return;
280 } else if (_positivity_ && !_sumIsOne_) {
281 addSumIsOne();
282 return;
283 } else if (!_positivity_ && _sumIsOne_) {
285 return;
286 }
287
288 // we can do both with one loop, don't call the above functions.
289 // addPositivity();
290 // addSumIsOne();
291 LpExpr expr;
292
293 for (const auto& col: _cols_) {
294 addRow(0 <= col);
295 expr += col;
296 }
297
298 addRow(1 <= std::move(expr) <= 1);
299
300 _sumIsOne_ = true;
301 _positivity_ = true;
302 }
303
304 template < typename GUM_SCALAR >
305 std::vector< std::vector< GUM_SCALAR > > LpInterface< GUM_SCALAR >::solve() {
307
308 lrs.setUpH((unsigned int)_cols_.size());
309
310 std::vector< std::vector< GUM_SCALAR > > lrsMatrix;
311
312 for (const auto& row: _rows_) {
313 std::vector< GUM_SCALAR > expandedRow(_cols_.size() + 1, 0);
314
315 expandedRow[0] = row->_cste_;
316
317 for (const auto& elt: *row->_coeffs_)
318 expandedRow[elt.first.id() + 1] = elt.second;
319
320 lrsMatrix.push_back(expandedRow);
321 }
322
323 lrs.fillMatrix(lrsMatrix);
324
325 lrs.H2V();
326
327 return lrs.getOutput();
328 }
329
330 template < typename GUM_SCALAR >
331 std::vector< LpCol > LpInterface< GUM_SCALAR >::getCols() const {
332 return _cols_;
333 }
334
335 template < typename GUM_SCALAR >
337 std::ostringstream s;
338
339 s << std::endl << std::endl << "Variables : " << std::endl;
340
341 for (const auto& col: _cols_)
342 s << " " << col.toString();
343
344 s << std::endl;
345
346 for (const auto& row: _rows_)
347 s << std::endl << row->toString();
348
349 s << std::endl << std::endl;
350
351 return s.str();
352 }
353
354 template < typename GUM_SCALAR >
356 for (const auto& row: _rows_)
357 delete row;
358
359 _rows_.clear();
360 _rows_.shrink_to_fit();
364
365 _cols_.clear();
366 _cols_.shrink_to_fit();
367
368 _positivity_ = false;
369 _sumIsOne_ = false;
370 }
371
372 template < typename GUM_SCALAR >
374 for (const auto& row: _rows_)
375 delete row;
376
377 _rows_.clear();
378 _rows_.shrink_to_fit();
379
380 _positivity_ = false;
381 _sumIsOne_ = false;
382 }
383
385 template < typename T2 >
386 LpExpr operator+(LpExpr&& lhs, const T2& rhs) {
387 LpExpr expr = std::move(lhs);
388 expr += rhs;
389
390 return expr;
391 }
392
393 template < typename T2 >
394 LpExpr operator+(const LpExpr& lhs, const T2& rhs) {
395 LpExpr expr(lhs);
396 expr += rhs;
397
398 return expr;
399 }
400
401 template < typename T1, forbidden_type< T1, LpExpr > >
402 LpExpr operator+(const T1& lhs, LpExpr&& rhs) {
403 LpExpr expr = std::move(rhs);
404 ;
405 expr += lhs;
406
407 return expr;
408 }
409
410 template < typename T1, forbidden_type< T1, LpExpr > >
411 LpExpr operator+(const T1& lhs, LpExpr& rhs) {
412 LpExpr expr(rhs);
413 expr += lhs;
414
415 return expr;
416 }
417
418 template < typename T2, forbidden_type< T2, LpExpr > >
419 LpExpr operator+(const LpCol& lhs, const T2& rhs) {
420 LpExpr expr;
421 expr += lhs;
422 expr += rhs;
423
424 return expr;
425 }
426
427 template < typename T1, forbidden_type< T1, LpExpr >, forbidden_type< T1, LpCol > >
428 LpExpr operator+(const T1& lhs, const LpCol& rhs) {
429 LpExpr expr;
430 expr += rhs;
431 expr += lhs;
432
433 return expr;
434 }
435
437 template < typename T2 >
438 LpExpr operator-(LpExpr&& lhs, const T2& rhs) {
439 LpExpr expr = std::move(lhs);
440 expr -= rhs;
441
442 return expr;
443 }
444
445 template < typename T2 >
446 LpExpr operator-(const LpExpr& lhs, const T2& rhs) {
447 LpExpr expr(lhs);
448 expr -= rhs;
449
450 return expr;
451 }
452
453 template < typename T1, forbidden_type< T1, LpExpr > >
454 LpExpr operator-(const T1& lhs, LpExpr&& rhs) {
455 LpExpr expr;
456 expr += std::move(rhs);
457 ;
458 expr -= lhs;
459
460 return expr;
461 }
462
463 template < typename T1, forbidden_type< T1, LpExpr > >
464 LpExpr operator-(const T1& lhs, LpExpr& rhs) {
465 LpExpr expr;
466 expr += rhs;
467 expr -= lhs;
468
469 return expr;
470 }
471
472 template < typename T2, forbidden_type< T2, LpExpr > >
473 LpExpr operator-(const LpCol& lhs, const T2& rhs) {
474 LpExpr expr;
475 expr += lhs;
476 expr -= rhs;
477
478 return expr;
479 }
480
481 template < typename T1, forbidden_type< T1, LpExpr >, forbidden_type< T1, LpCol > >
482 LpExpr operator-(const T1& lhs, const LpCol& rhs) {
483 LpExpr expr;
484 expr += rhs;
485 expr -= lhs;
486
487 return expr;
488 }
489
491 template < typename SCALAR >
492 INLINE LpExpr LpExpr::multiply(const SCALAR& lhs, const LpCol& rhs) {
493 LpExpr expr;
494 expr._mCoeffs_->insert(rhs, lhs);
495 expr._imiddle_ = true;
496 return expr;
497 }
498
499 template < typename SCALAR >
500 LpExpr operator*(const SCALAR& lhs, const LpCol& rhs) {
501 return LpExpr::multiply(lhs, rhs);
502 }
503
504 template < typename SCALAR >
505 LpExpr operator*(const LpCol& lhs, const SCALAR& rhs) {
506 return LpExpr::multiply(rhs, lhs);
507 }
508
510 template < typename T1, typename T2 >
511 INLINE LpExpr LpExpr::lessThan(T1&& lhs, T2&& rhs) {
512 LpExpr expr;
513 expr._addSide_(std::forward< T1 >(lhs));
514 expr._addSide_(std::forward< T2 >(rhs));
515 return expr;
516 }
517
518 // const lvalue
519 template < typename T2 >
520 LpExpr operator<=(const LpExpr& lhs, T2&& rhs) {
521 return LpExpr::lessThan(lhs, std::forward< T2 >(rhs));
522 }
523
524 template < typename T2 >
525 LpExpr operator<=(const LpCol& lhs, T2&& rhs) {
526 return LpExpr::lessThan(lhs, std::forward< T2 >(rhs));
527 }
528
529 template < typename T1, forbidden_type< T1, LpExpr& >, forbidden_type< T1, LpCol& > >
530 LpExpr operator<=(T1&& lhs, const LpExpr& rhs) {
531 return LpExpr::lessThan(std::forward< T1 >(lhs), rhs);
532 }
533
534 template < typename T1, forbidden_type< T1, LpExpr& >, forbidden_type< T1, LpCol& > >
535 LpExpr operator<=(T1&& lhs, const LpCol& rhs) {
536 return LpExpr::lessThan(std::forward< T1 >(lhs), rhs);
537 }
538
539 // rvaue
540 template < typename T2 >
541 LpExpr operator<=(LpExpr&& lhs, T2&& rhs) {
542 return LpExpr::lessThan(std::move(lhs), std::forward< T2 >(rhs));
543 }
544
545 template < typename T2 >
546 LpExpr operator<=(LpCol&& lhs, T2&& rhs) {
547 return LpExpr::lessThan(std::move(lhs), std::forward< T2 >(rhs));
548 }
549
550 template < typename T1, forbidden_type< T1, LpExpr >, forbidden_type< T1, LpCol > >
551 LpExpr operator<=(T1&& lhs, LpExpr&& rhs) {
552 return LpExpr::lessThan(std::forward< T1 >(lhs), std::move(rhs));
553 }
554
555 template < typename T1, forbidden_type< T1, LpExpr >, forbidden_type< T1, LpCol > >
556 LpExpr operator<=(T1&& lhs, LpCol&& rhs) {
557 return LpExpr::lessThan(std::forward< T1 >(lhs), std::move(rhs));
558 }
559 } // namespace lp
560
561 } // namespace credal
562
563} // namespace gum
Class representing a polytope ( credal set ) by a set of linear constraints.
Exception : operation not allowed.
Class template acting as a wrapper for Lexicographic Reverse Search by David Avis.
Definition LrsWrapper.h:119
const matrix & getOutput() const
Get the output matrix solution of the problem.
void H2V()
H-representation to V-representation.
void fillMatrix(const std::vector< std::vector< GUM_SCALAR > > &matrix)
Fill the H-representation from the matrix given in argument.
void setUpH(const Size &card)
Sets up an H-representation.
Class representing a variable ( a column ) of a linear program, i.e.
Definition LpInterface.h:80
Class representing a linear expression.
LpExpr & operator+=(const LpCol &rhs)
Compound assignment operator += with a variable.
double _rValue_
The constant on the right side L : L <= M <= R.
bool _ileft_
True if this expression has a non-empty left side L : L <= M <= R .
bool _imiddle_
True if this expression has a non-empty middle side M ( the default ) : L <= M <= R .
LpExpr & operator-=(const LpCol &rhs)
Compound assignment operator -= with a variable.
LpExpr()
Default constructor.
std::string toString() const
Get the string representation of a calling expression.
void clear()
Clear all data of the calling expression as if it was constructed.
static LpExpr multiply(const SCALAR &lhs, const LpCol &rhs)
bool _iright_
True if this expression has a non-empty right side R : L <= M <= R .
static LpExpr lessThan(T1 &&lhs, T2 &&rhs)
HashTable< LpCol, double > * _mCoeffs_
The coefficients of each variable on the middle side L : L <= M <= R.
double _mValue_
The constant on the middle side L : L <= M <= R.
double _lValue_
The constant on the left side L : L <= M <= R.
LpExpr & operator=(const LpCol &rhs)
Assignment operator = with a variable.
void _addSide_(const LpCol &from)
Set the side of the calling expression, from LEFT TO RIGHT : L <= M <= R.
Class representing a linear program.
bool _sumIsOne_
true if addSumIsOne() has been called, false otherwise.
std::string toString() const
Get the string representation of a calling linear program.
void addSumIsOne()
Add sum of variables is 1 constraints.
void clear()
Reset the rows (inequalities) and columns (variables) of the LP as if it was created.
std::vector< LpCol > getCols() const
Get the variables of the LP.
void clearRows()
Reset the rows (inequalities) of the LP but not the columns (variables are kept).
std::vector< LpCol > _cols_
Variables of the problem.
std::vector< LpRow * > _rows_
Rows of the problem.
LpInterface< GUM_SCALAR > & operator=(const LpInterface< GUM_SCALAR > &from)
Copy compound assignment.
LpInterface()
Default constructor, empty problem.
void addPositivity()
Add positivity constraints for all variables.
std::vector< std::vector< GUM_SCALAR > > solve()
Solve the linear program (H-representation of the polytope) by enumeration (of the polytope vertices)...
std::vector< LpCol > addCols(const unsigned int &cols)
Insert new columns, i.e.
LpCol addCol()
Insert a new column, i.e.
void addProba()
Add positivity constraints and sum of variables is 1 ( probability constraints ).
void addRow(const LpExpr &expr)
Add rows to the linear program according to a given expression ( which must be at least an inequality...
~LpInterface()
Default destructor.
bool _positivity_
true if addPositivity() has been called, false otherwise.
Class representing a row of the linear program, i.e.
#define GUM_ERROR(type, msg)
Definition exceptions.h:72
namespace for constraint-based description of credal sets
Definition agrum.h:64
LpExpr operator+(LpExpr &&lhs, const T2 &rhs)
Overload of operator + between anything ( a scalar, a variable or an expression ) and anything except...
LpExpr operator<=(const LpExpr &lhs, T2 &&rhs)
Overload of operator <= between anything and anything.
LpExpr operator-(LpExpr &&lhs, const T2 &rhs)
Overload of operator - between anything ( a scalar, a variable or an expression ) and anything except...
std::ostream & operator<<(std::ostream &out, const LpRow &row)
namespace for all credal networks entities
Definition agrum.h:61
gum is the global namespace for all aGrUM entities
Definition agrum.h:46
value_type & operator*()
Returns the value pointed to by the iterator.