1.1 --- a/src/work/marci/lp/lp_solver_base.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1118 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#ifndef LEMON_LP_SOLVER_BASE_H
1.6 -#define LEMON_LP_SOLVER_BASE_H
1.7 -
1.8 -///\ingroup misc
1.9 -///\file
1.10 -
1.11 -// #include <stdio.h>
1.12 -#include <stdlib.h>
1.13 -#include <iostream>
1.14 -#include <map>
1.15 -#include <limits>
1.16 -// #include <stdio>
1.17 -//#include <stdlib>
1.18 -extern "C" {
1.19 -#include "glpk.h"
1.20 -}
1.21 -
1.22 -#include <iostream>
1.23 -#include <vector>
1.24 -#include <string>
1.25 -#include <list>
1.26 -#include <memory>
1.27 -#include <utility>
1.28 -
1.29 -#include <lemon/invalid.h>
1.30 -#include <expression.h>
1.31 -//#include <stp.h>
1.32 -//#include <lemon/max_flow.h>
1.33 -//#include <augmenting_flow.h>
1.34 -//#include <iter_map.h>
1.35 -
1.36 -using std::cout;
1.37 -using std::cin;
1.38 -using std::endl;
1.39 -
1.40 -namespace lemon {
1.41 -
1.42 - /// \addtogroup misc
1.43 - /// @{
1.44 -
1.45 - /// \brief A partitioned vector with iterable classes.
1.46 - ///
1.47 - /// This class implements a container in which the data is stored in an
1.48 - /// stl vector, the range is partitioned into sets and each set is
1.49 - /// doubly linked in a list.
1.50 - /// That is, each class is iterable by lemon iterators, and any member of
1.51 - /// the vector can bo moved to an other class.
1.52 - template <typename T>
1.53 - class IterablePartition {
1.54 - protected:
1.55 - struct Node {
1.56 - T data;
1.57 - int prev; //invalid az -1
1.58 - int next;
1.59 - };
1.60 - std::vector<Node> nodes;
1.61 - struct Tip {
1.62 - int first;
1.63 - int last;
1.64 - };
1.65 - std::vector<Tip> tips;
1.66 - public:
1.67 - /// The classes are indexed by integers from \c 0 to \c classNum()-1.
1.68 - int classNum() const { return tips.size(); }
1.69 - /// This lemon style iterator iterates through a class.
1.70 - class Class;
1.71 - /// Constructor. The number of classes is to be given which is fixed
1.72 - /// over the life of the container.
1.73 - /// The partition classes are indexed from 0 to class_num-1.
1.74 - IterablePartition(int class_num) {
1.75 - for (int i=0; i<class_num; ++i) {
1.76 - Tip t;
1.77 - t.first=t.last=-1;
1.78 - tips.push_back(t);
1.79 - }
1.80 - }
1.81 - protected:
1.82 - void befuz(Class it, int class_id) {
1.83 - if (tips[class_id].first==-1) {
1.84 - if (tips[class_id].last==-1) {
1.85 - nodes[it.i].prev=nodes[it.i].next=-1;
1.86 - tips[class_id].first=tips[class_id].last=it.i;
1.87 - }
1.88 - } else {
1.89 - nodes[it.i].prev=tips[class_id].last;
1.90 - nodes[it.i].next=-1;
1.91 - nodes[tips[class_id].last].next=it.i;
1.92 - tips[class_id].last=it.i;
1.93 - }
1.94 - }
1.95 - void kifuz(Class it, int class_id) {
1.96 - if (tips[class_id].first==it.i) {
1.97 - if (tips[class_id].last==it.i) {
1.98 - tips[class_id].first=tips[class_id].last=-1;
1.99 - } else {
1.100 - tips[class_id].first=nodes[it.i].next;
1.101 - nodes[nodes[it.i].next].prev=-1;
1.102 - }
1.103 - } else {
1.104 - if (tips[class_id].last==it.i) {
1.105 - tips[class_id].last=nodes[it.i].prev;
1.106 - nodes[nodes[it.i].prev].next=-1;
1.107 - } else {
1.108 - nodes[nodes[it.i].next].prev=nodes[it.i].prev;
1.109 - nodes[nodes[it.i].prev].next=nodes[it.i].next;
1.110 - }
1.111 - }
1.112 - }
1.113 - public:
1.114 - /// A new element with data \c t is pushed into the vector and into class
1.115 - /// \c class_id.
1.116 - Class push_back(const T& t, int class_id) {
1.117 - Node n;
1.118 - n.data=t;
1.119 - nodes.push_back(n);
1.120 - int i=nodes.size()-1;
1.121 - befuz(i, class_id);
1.122 - return i;
1.123 - }
1.124 - /// A member is moved to an other class.
1.125 - void set(Class it, int old_class_id, int new_class_id) {
1.126 - kifuz(it.i, old_class_id);
1.127 - befuz(it.i, new_class_id);
1.128 - }
1.129 - /// Returns the data pointed by \c it.
1.130 - T& operator[](Class it) { return nodes[it.i].data; }
1.131 - /// Returns the data pointed by \c it.
1.132 - const T& operator[](Class it) const { return nodes[it.i].data; }
1.133 - ///.
1.134 - class Class {
1.135 - friend class IterablePartition;
1.136 - protected:
1.137 - int i;
1.138 - public:
1.139 - /// Default constructor.
1.140 - Class() { }
1.141 - /// This constructor constructs an iterator which points
1.142 - /// to the member of th container indexed by the integer _i.
1.143 - Class(const int& _i) : i(_i) { }
1.144 - /// Invalid constructor.
1.145 - Class(const Invalid&) : i(-1) { }
1.146 - friend bool operator<(const Class& x, const Class& y);
1.147 - friend std::ostream& operator<<(std::ostream& os,
1.148 - const Class& it);
1.149 - bool operator==(const Class& node) const {return i == node.i;}
1.150 - bool operator!=(const Class& node) const {return i != node.i;}
1.151 - };
1.152 - friend bool operator<(const Class& x, const Class& y) {
1.153 - return (x.i < y.i);
1.154 - }
1.155 - friend std::ostream& operator<<(std::ostream& os,
1.156 - const Class& it) {
1.157 - os << it.i;
1.158 - return os;
1.159 - }
1.160 - /// First member of class \c class_id.
1.161 - Class& first(Class& it, int class_id) const {
1.162 - it.i=tips[class_id].first;
1.163 - return it;
1.164 - }
1.165 - /// Next member.
1.166 - Class& next(Class& it) const {
1.167 - it.i=nodes[it.i].next;
1.168 - return it;
1.169 - }
1.170 - /// True iff the iterator is valid.
1.171 - bool valid(const Class& it) const { return it.i!=-1; }
1.172 -
1.173 - class ClassIt : public Class {
1.174 - const IterablePartition* iterable_partition;
1.175 - public:
1.176 - ClassIt() { }
1.177 - ClassIt(Invalid i) : Class(i) { }
1.178 - ClassIt(const IterablePartition& _iterable_partition,
1.179 - const int& i) : iterable_partition(&_iterable_partition) {
1.180 - _iterable_partition.first(*this, i);
1.181 - }
1.182 - ClassIt(const IterablePartition& _iterable_partition,
1.183 - const Class& _class) :
1.184 - Class(_class), iterable_partition(&_iterable_partition) { }
1.185 - ClassIt& operator++() {
1.186 - iterable_partition->next(*this);
1.187 - return *this;
1.188 - }
1.189 - };
1.190 -
1.191 - };
1.192 -
1.193 -
1.194 - /*! \e
1.195 - \todo kellenene uj iterable structure bele, mert ez nem az igazi
1.196 - \todo A[x,y]-t cserel. Jobboldal, baloldal csere.
1.197 - \todo LEKERDEZESEK!!!
1.198 - \todo DOKSI!!!! Doxygen group!!!
1.199 - The aim of this class is to give a general surface to different
1.200 - solvers, i.e. it makes possible to write algorithms using LP's,
1.201 - in which the solver can be changed to an other one easily.
1.202 - \nosubgrouping
1.203 - */
1.204 - template <typename _Value>
1.205 - class LPSolverBase {
1.206 -
1.207 - /*! @name Uncategorized functions and types (public members)
1.208 - */
1.209 - //@{
1.210 - public:
1.211 -
1.212 - //UNCATEGORIZED
1.213 -
1.214 - /// \e
1.215 - typedef IterablePartition<int> Rows;
1.216 - /// \e
1.217 - typedef IterablePartition<int> Cols;
1.218 - /// \e
1.219 - typedef _Value Value;
1.220 - /// \e
1.221 - typedef Rows::Class Row;
1.222 - /// \e
1.223 - typedef Cols::Class Col;
1.224 - public:
1.225 - /// \e
1.226 - IterablePartition<int> row_iter_map;
1.227 - /// \e
1.228 - IterablePartition<int> col_iter_map;
1.229 - /// \e
1.230 - std::vector<Row> int_row_map;
1.231 - /// \e
1.232 - std::vector<Col> int_col_map;
1.233 - /// \e
1.234 - const int VALID_CLASS;
1.235 - /// \e
1.236 - const int INVALID_CLASS;
1.237 - /// \e
1.238 - static const _Value INF;
1.239 - public:
1.240 - /// \e
1.241 - LPSolverBase() : row_iter_map(2),
1.242 - col_iter_map(2),
1.243 - VALID_CLASS(0), INVALID_CLASS(1) { }
1.244 - /// \e
1.245 - virtual ~LPSolverBase() { }
1.246 - //@}
1.247 -
1.248 - /*! @name Medium level interface (public members)
1.249 - These functions appear in the low level and also in the high level
1.250 - interfaces thus these each of these functions have to be implemented
1.251 - only once in the different interfaces.
1.252 - This means that these functions have to be reimplemented for all of the
1.253 - different lp solvers. These are basic functions, and have the same
1.254 - parameter lists in the low and high level interfaces.
1.255 - */
1.256 - //@{
1.257 - public:
1.258 -
1.259 - //UNCATEGORIZED FUNCTIONS
1.260 -
1.261 - /// \e
1.262 - virtual void setMinimize() = 0;
1.263 - /// \e
1.264 - virtual void setMaximize() = 0;
1.265 -
1.266 - //SOLVER FUNCTIONS
1.267 -
1.268 - /// \e
1.269 - virtual void solveSimplex() = 0;
1.270 - /// \e
1.271 - virtual void solvePrimalSimplex() = 0;
1.272 - /// \e
1.273 - virtual void solveDualSimplex() = 0;
1.274 -
1.275 - //SOLUTION RETRIEVING
1.276 -
1.277 - /// \e
1.278 - virtual _Value getObjVal() = 0;
1.279 -
1.280 - //OTHER FUNCTIONS
1.281 -
1.282 - /// \e
1.283 - virtual int rowNum() const = 0;
1.284 - /// \e
1.285 - virtual int colNum() const = 0;
1.286 - /// \e
1.287 - virtual int warmUp() = 0;
1.288 - /// \e
1.289 - virtual void printWarmUpStatus(int i) = 0;
1.290 - /// \e
1.291 - virtual int getPrimalStatus() = 0;
1.292 - /// \e
1.293 - virtual void printPrimalStatus(int i) = 0;
1.294 - /// \e
1.295 - virtual int getDualStatus() = 0;
1.296 - /// \e
1.297 - virtual void printDualStatus(int i) = 0;
1.298 - /// Returns the status of the slack variable assigned to row \c row.
1.299 - virtual int getRowStat(const Row& row) = 0;
1.300 - /// \e
1.301 - virtual void printRowStatus(int i) = 0;
1.302 - /// Returns the status of the variable assigned to column \c col.
1.303 - virtual int getColStat(const Col& col) = 0;
1.304 - /// \e
1.305 - virtual void printColStatus(int i) = 0;
1.306 -
1.307 - //@}
1.308 -
1.309 - /*! @name Low level interface (protected members)
1.310 - Problem manipulating functions in the low level interface
1.311 - */
1.312 - //@{
1.313 - protected:
1.314 -
1.315 - //MATRIX MANIPULATING FUNCTIONS
1.316 -
1.317 - /// \e
1.318 - virtual int _addCol() = 0;
1.319 - /// \e
1.320 - virtual int _addRow() = 0;
1.321 - /// \e
1.322 - virtual void _eraseCol(int i) = 0;
1.323 - /// \e
1.324 - virtual void _eraseRow(int i) = 0;
1.325 - /// \e
1.326 - virtual void _setRowCoeffs(int i,
1.327 - const std::vector<std::pair<int, _Value> >& coeffs) = 0;
1.328 - /// \e
1.329 - /// This routine modifies \c coeffs only by the \c push_back method.
1.330 - virtual void _getRowCoeffs(int i,
1.331 - std::vector<std::pair<int, _Value> >& coeffs) = 0;
1.332 - /// \e
1.333 - virtual void _setColCoeffs(int i,
1.334 - const std::vector<std::pair<int, _Value> >& coeffs) = 0;
1.335 - /// \e
1.336 - /// This routine modifies \c coeffs only by the \c push_back method.
1.337 - virtual void _getColCoeffs(int i,
1.338 - std::vector<std::pair<int, _Value> >& coeffs) = 0;
1.339 - /// \e
1.340 - virtual void _setCoeff(int col, int row, _Value value) = 0;
1.341 - /// \e
1.342 - virtual _Value _getCoeff(int col, int row) = 0;
1.343 - // public:
1.344 - // /// \e
1.345 - // enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
1.346 - protected:
1.347 - /// \e
1.348 - /// The lower bound of a variable (column) have to be given by an
1.349 - /// extended number of type _Value, i.e. a finite number of type
1.350 - /// _Value or -INF.
1.351 - virtual void _setColLowerBound(int i, _Value value) = 0;
1.352 - /// \e
1.353 - /// The lower bound of a variable (column) is an
1.354 - /// extended number of type _Value, i.e. a finite number of type
1.355 - /// _Value or -INF.
1.356 - virtual _Value _getColLowerBound(int i) = 0;
1.357 - /// \e
1.358 - /// The upper bound of a variable (column) have to be given by an
1.359 - /// extended number of type _Value, i.e. a finite number of type
1.360 - /// _Value or INF.
1.361 - virtual void _setColUpperBound(int i, _Value value) = 0;
1.362 - /// \e
1.363 - /// The upper bound of a variable (column) is an
1.364 - /// extended number of type _Value, i.e. a finite number of type
1.365 - /// _Value or INF.
1.366 - virtual _Value _getColUpperBound(int i) = 0;
1.367 - /// \e
1.368 - /// The lower bound of a linear expression (row) have to be given by an
1.369 - /// extended number of type _Value, i.e. a finite number of type
1.370 - /// _Value or -INF.
1.371 - virtual void _setRowLowerBound(int i, _Value value) = 0;
1.372 - /// \e
1.373 - /// The lower bound of a linear expression (row) is an
1.374 - /// extended number of type _Value, i.e. a finite number of type
1.375 - /// _Value or -INF.
1.376 - virtual _Value _getRowLowerBound(int i) = 0;
1.377 - /// \e
1.378 - /// The upper bound of a linear expression (row) have to be given by an
1.379 - /// extended number of type _Value, i.e. a finite number of type
1.380 - /// _Value or INF.
1.381 - virtual void _setRowUpperBound(int i, _Value value) = 0;
1.382 - /// \e
1.383 - /// The upper bound of a linear expression (row) is an
1.384 - /// extended number of type _Value, i.e. a finite number of type
1.385 - /// _Value or INF.
1.386 - virtual _Value _getRowUpperBound(int i) = 0;
1.387 - /// \e
1.388 - virtual void _setObjCoeff(int i, _Value obj_coef) = 0;
1.389 - /// \e
1.390 - virtual _Value _getObjCoeff(int i) = 0;
1.391 -
1.392 - //SOLUTION RETRIEVING
1.393 -
1.394 - /// \e
1.395 - virtual _Value _getPrimal(int i) = 0;
1.396 - //@}
1.397 -
1.398 - /*! @name High level interface (public members)
1.399 - Problem manipulating functions in the high level interface
1.400 - */
1.401 - //@{
1.402 - public:
1.403 -
1.404 - //MATRIX MANIPULATING FUNCTIONS
1.405 -
1.406 - /// \e
1.407 - Col addCol() {
1.408 - int i=_addCol();
1.409 - Col col;
1.410 - col_iter_map.first(col, INVALID_CLASS);
1.411 - if (col_iter_map.valid(col)) { //van hasznalhato hely
1.412 - col_iter_map.set(col, INVALID_CLASS, VALID_CLASS);
1.413 - col_iter_map[col]=i;
1.414 - } else { //a cucc vegere kell inzertalni mert nincs szabad hely
1.415 - col=col_iter_map.push_back(i, VALID_CLASS);
1.416 - }
1.417 - int_col_map.push_back(col);
1.418 - return col;
1.419 - }
1.420 - /// \e
1.421 - Row addRow() {
1.422 - int i=_addRow();
1.423 - Row row;
1.424 - row_iter_map.first(row, INVALID_CLASS);
1.425 - if (row_iter_map.valid(row)) { //van hasznalhato hely
1.426 - row_iter_map.set(row, INVALID_CLASS, VALID_CLASS);
1.427 - row_iter_map[row]=i;
1.428 - } else { //a cucc vegere kell inzertalni mert nincs szabad hely
1.429 - row=row_iter_map.push_back(i, VALID_CLASS);
1.430 - }
1.431 - int_row_map.push_back(row);
1.432 - return row;
1.433 - }
1.434 - /// \e
1.435 - void eraseCol(const Col& col) {
1.436 - col_iter_map.set(col, VALID_CLASS, INVALID_CLASS);
1.437 - int cols[2];
1.438 - cols[1]=col_iter_map[col];
1.439 - _eraseCol(cols[1]);
1.440 - col_iter_map[col]=0; //glpk specifikus, de kell ez??
1.441 - Col it;
1.442 - for (col_iter_map.first(it, VALID_CLASS);
1.443 - col_iter_map.valid(it); col_iter_map.next(it)) {
1.444 - if (col_iter_map[it]>cols[1]) --col_iter_map[it];
1.445 - }
1.446 - int_col_map.erase(int_col_map.begin()+cols[1]);
1.447 - }
1.448 - /// \e
1.449 - void eraseRow(const Row& row) {
1.450 - row_iter_map.set(row, VALID_CLASS, INVALID_CLASS);
1.451 - int rows[2];
1.452 - rows[1]=row_iter_map[row];
1.453 - _eraseRow(rows[1]);
1.454 - row_iter_map[row]=0; //glpk specifikus, de kell ez??
1.455 - Row it;
1.456 - for (row_iter_map.first(it, VALID_CLASS);
1.457 - row_iter_map.valid(it); row_iter_map.next(it)) {
1.458 - if (row_iter_map[it]>rows[1]) --row_iter_map[it];
1.459 - }
1.460 - int_row_map.erase(int_row_map.begin()+rows[1]);
1.461 - }
1.462 - /// \e
1.463 - void setCoeff(Col col, Row row, _Value value) {
1.464 - _setCoeff(col_iter_map[col], row_iter_map[row], value);
1.465 - }
1.466 - /// \e
1.467 - _Value getCoeff(Col col, Row row) {
1.468 - return _getCoeff(col_iter_map[col], row_iter_map[row], value);
1.469 - }
1.470 - /// \e
1.471 - void setColLowerBound(Col col, _Value lo) {
1.472 - _setColLowerBound(col_iter_map[col], lo);
1.473 - }
1.474 - /// \e
1.475 - _Value getColLowerBound(Col col) {
1.476 - return _getColLowerBound(col_iter_map[col]);
1.477 - }
1.478 - /// \e
1.479 - void setColUpperBound(Col col, _Value up) {
1.480 - _setColUpperBound(col_iter_map[col], up);
1.481 - }
1.482 - /// \e
1.483 - _Value getColUpperBound(Col col) {
1.484 - return _getColUpperBound(col_iter_map[col]);
1.485 - }
1.486 - /// \e
1.487 - void setRowLowerBound(Row row, _Value lo) {
1.488 - _setRowLowerBound(row_iter_map[row], lo);
1.489 - }
1.490 - /// \e
1.491 - _Value getRowLowerBound(Row row) {
1.492 - return _getRowLowerBound(row_iter_map[row]);
1.493 - }
1.494 - /// \e
1.495 - void setRowUpperBound(Row row, _Value up) {
1.496 - _setRowUpperBound(row_iter_map[row], up);
1.497 - }
1.498 - /// \e
1.499 - _Value getRowUpperBound(Row row) {
1.500 - return _getRowUpperBound(row_iter_map[row]);
1.501 - }
1.502 - /// \e
1.503 - void setObjCoeff(const Col& col, _Value obj_coef) {
1.504 - _setObjCoeff(col_iter_map[col], obj_coef);
1.505 - }
1.506 - /// \e
1.507 - _Value getObjCoeff(const Col& col) {
1.508 - return _getObjCoeff(col_iter_map[col]);
1.509 - }
1.510 -
1.511 - //SOLUTION RETRIEVING FUNCTIONS
1.512 -
1.513 - /// \e
1.514 - _Value getPrimal(const Col& col) {
1.515 - return _getPrimal(col_iter_map[col]);
1.516 - }
1.517 -
1.518 - //@}
1.519 -
1.520 - /*! @name User friend interface
1.521 - Problem manipulating functions in the user friend interface
1.522 - */
1.523 - //@{
1.524 -
1.525 - //EXPRESSION TYPES
1.526 -
1.527 - /// \e
1.528 - typedef Expr<Col, _Value> Expression;
1.529 - /// \e
1.530 - typedef Expr<Row, _Value> DualExpression;
1.531 - /// \e
1.532 - typedef Constr<Col, _Value> Constraint;
1.533 -
1.534 - //MATRIX MANIPULATING FUNCTIONS
1.535 -
1.536 - /// \e
1.537 - void setRowCoeffs(Row row, const Expression& expr) {
1.538 - std::vector<std::pair<int, _Value> > row_coeffs;
1.539 - for(typename Expression::Data::const_iterator i=expr.data.begin();
1.540 - i!=expr.data.end(); ++i) {
1.541 - row_coeffs.push_back(std::make_pair
1.542 - (col_iter_map[(*i).first], (*i).second));
1.543 - }
1.544 - _setRowCoeffs(row_iter_map[row], row_coeffs);
1.545 - }
1.546 - /// \e
1.547 - void setRow(Row row, const Constraint& constr) {
1.548 - setRowCoeffs(row, constr.expr);
1.549 - setRowLowerBound(row, constr.lo);
1.550 - setRowUpperBound(row, constr.up);
1.551 - }
1.552 - /// \e
1.553 - Row addRow(const Constraint& constr) {
1.554 - Row row=addRow();
1.555 - setRowCoeffs(row, constr.expr);
1.556 - setRowLowerBound(row, constr.lo);
1.557 - setRowUpperBound(row, constr.up);
1.558 - return row;
1.559 - }
1.560 - /// \e
1.561 - /// This routine modifies \c expr by only adding to it.
1.562 - void getRowCoeffs(Row row, Expression& expr) {
1.563 - std::vector<std::pair<int, _Value> > row_coeffs;
1.564 - _getRowCoeffs(row_iter_map[row], row_coeffs);
1.565 - for(typename std::vector<std::pair<int, _Value> >::const_iterator
1.566 - i=row_coeffs.begin(); i!=row_coeffs.end(); ++i) {
1.567 - expr+= (*i).second*int_col_map[(*i).first];
1.568 - }
1.569 - }
1.570 - /// \e
1.571 - void setColCoeffs(Col col, const DualExpression& expr) {
1.572 - std::vector<std::pair<int, _Value> > col_coeffs;
1.573 - for(typename DualExpression::Data::const_iterator i=expr.data.begin();
1.574 - i!=expr.data.end(); ++i) {
1.575 - col_coeffs.push_back(std::make_pair
1.576 - (row_iter_map[(*i).first], (*i).second));
1.577 - }
1.578 - _setColCoeffs(col_iter_map[col], col_coeffs);
1.579 - }
1.580 - /// \e
1.581 - /// This routine modifies \c expr by only adding to it.
1.582 - void getColCoeffs(Col col, DualExpression& expr) {
1.583 - std::vector<std::pair<int, _Value> > col_coeffs;
1.584 - _getColCoeffs(col_iter_map[col], col_coeffs);
1.585 - for(typename std::vector<std::pair<int, _Value> >::const_iterator
1.586 - i=col_coeffs.begin(); i!=col_coeffs.end(); ++i) {
1.587 - expr+= (*i).second*int_row_map[(*i).first];
1.588 - }
1.589 - }
1.590 - /// \e
1.591 - void setObjCoeffs(const Expression& expr) {
1.592 - // writing zero everywhere
1.593 - for(Cols::ClassIt it(col_iter_map, VALID_CLASS); it!=INVALID; ++it)
1.594 - setObjCoeff(it, 0.0);
1.595 - // writing the data needed
1.596 - for(typename Expression::Data::const_iterator i=expr.data.begin();
1.597 - i!=expr.data.end(); ++i) {
1.598 - setObjCoeff((*i).first, (*i).second);
1.599 - }
1.600 - }
1.601 - /// \e
1.602 - /// This routine modifies \c expr by only adding to it.
1.603 - void getObjCoeffs(Expression& expr) {
1.604 - for(Cols::ClassIt it(col_iter_map, VALID_CLASS); it!=INVALID; ++it)
1.605 - expr+=getObjCoeff(it)*it;
1.606 - }
1.607 - //@}
1.608 -
1.609 -
1.610 - /*! @name MIP functions and types (public members)
1.611 - */
1.612 - //@{
1.613 - public:
1.614 - /// \e
1.615 - virtual void solveBandB() = 0;
1.616 - /// \e
1.617 - virtual void setLP() = 0;
1.618 - /// \e
1.619 - virtual void setMIP() = 0;
1.620 - protected:
1.621 - /// \e
1.622 - virtual void _setColCont(int i) = 0;
1.623 - /// \e
1.624 - virtual void _setColInt(int i) = 0;
1.625 - /// \e
1.626 - virtual _Value _getMIPPrimal(int i) = 0;
1.627 - public:
1.628 - /// \e
1.629 - void setColCont(Col col) {
1.630 - _setColCont(col_iter_map[col]);
1.631 - }
1.632 - /// \e
1.633 - void setColInt(Col col) {
1.634 - _setColInt(col_iter_map[col]);
1.635 - }
1.636 - /// \e
1.637 - _Value getMIPPrimal(Col col) {
1.638 - return _getMIPPrimal(col_iter_map[col]);
1.639 - }
1.640 - //@}
1.641 - };
1.642 -
1.643 - template <typename _Value>
1.644 - const _Value LPSolverBase<_Value>::INF=std::numeric_limits<_Value>::infinity();
1.645 -
1.646 -
1.647 - /// \brief Wrapper for GLPK solver
1.648 - ///
1.649 - /// This class implements a lemon wrapper for GLPK.
1.650 - class LPGLPK : public LPSolverBase<double> {
1.651 - public:
1.652 - typedef LPSolverBase<double> Parent;
1.653 -
1.654 - public:
1.655 - /// \e
1.656 - LPX* lp;
1.657 -
1.658 - public:
1.659 - /// \e
1.660 - LPGLPK() : Parent(),
1.661 - lp(lpx_create_prob()) {
1.662 - int_row_map.push_back(Row());
1.663 - int_col_map.push_back(Col());
1.664 - lpx_set_int_parm(lp, LPX_K_DUAL, 1);
1.665 - }
1.666 - /// \e
1.667 - ~LPGLPK() {
1.668 - lpx_delete_prob(lp);
1.669 - }
1.670 -
1.671 - //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
1.672 -
1.673 - /// \e
1.674 - void setMinimize() {
1.675 - lpx_set_obj_dir(lp, LPX_MIN);
1.676 - }
1.677 - /// \e
1.678 - void setMaximize() {
1.679 - lpx_set_obj_dir(lp, LPX_MAX);
1.680 - }
1.681 -
1.682 - //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
1.683 -
1.684 - protected:
1.685 - /// \e
1.686 - int _addCol() {
1.687 - int i=lpx_add_cols(lp, 1);
1.688 - _setColLowerBound(i, -INF);
1.689 - _setColUpperBound(i, INF);
1.690 - return i;
1.691 - }
1.692 - /// \e
1.693 - int _addRow() {
1.694 - int i=lpx_add_rows(lp, 1);
1.695 - return i;
1.696 - }
1.697 - /// \e
1.698 - virtual void _setRowCoeffs(int i,
1.699 - const std::vector<std::pair<int, double> >& coeffs) {
1.700 - int mem_length=1+colNum();
1.701 - int* indices = new int[mem_length];
1.702 - double* doubles = new double[mem_length];
1.703 - int length=0;
1.704 - for (std::vector<std::pair<int, double> >::
1.705 - const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
1.706 - ++length;
1.707 - indices[length]=it->first;
1.708 - doubles[length]=it->second;
1.709 - }
1.710 - lpx_set_mat_row(lp, i, length, indices, doubles);
1.711 - delete [] indices;
1.712 - delete [] doubles;
1.713 - }
1.714 - /// \e
1.715 - virtual void _getRowCoeffs(int i,
1.716 - std::vector<std::pair<int, double> >& coeffs) {
1.717 - int mem_length=1+colNum();
1.718 - int* indices = new int[mem_length];
1.719 - double* doubles = new double[mem_length];
1.720 - int length=lpx_get_mat_row(lp, i, indices, doubles);
1.721 - for (int i=1; i<=length; ++i) {
1.722 - coeffs.push_back(std::make_pair(indices[i], doubles[i]));
1.723 - }
1.724 - delete [] indices;
1.725 - delete [] doubles;
1.726 - }
1.727 - /// \e
1.728 - virtual void _setColCoeffs(int i,
1.729 - const std::vector<std::pair<int, double> >& coeffs) {
1.730 - int mem_length=1+rowNum();
1.731 - int* indices = new int[mem_length];
1.732 - double* doubles = new double[mem_length];
1.733 - int length=0;
1.734 - for (std::vector<std::pair<int, double> >::
1.735 - const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
1.736 - ++length;
1.737 - indices[length]=it->first;
1.738 - doubles[length]=it->second;
1.739 - }
1.740 - lpx_set_mat_col(lp, i, length, indices, doubles);
1.741 - delete [] indices;
1.742 - delete [] doubles;
1.743 - }
1.744 - /// \e
1.745 - virtual void _getColCoeffs(int i,
1.746 - std::vector<std::pair<int, double> >& coeffs) {
1.747 - int mem_length=1+rowNum();
1.748 - int* indices = new int[mem_length];
1.749 - double* doubles = new double[mem_length];
1.750 - int length=lpx_get_mat_col(lp, i, indices, doubles);
1.751 - for (int i=1; i<=length; ++i) {
1.752 - coeffs.push_back(std::make_pair(indices[i], doubles[i]));
1.753 - }
1.754 - delete [] indices;
1.755 - delete [] doubles;
1.756 - }
1.757 - /// \e
1.758 - virtual void _eraseCol(int i) {
1.759 - int cols[2];
1.760 - cols[1]=i;
1.761 - lpx_del_cols(lp, 1, cols);
1.762 - }
1.763 - virtual void _eraseRow(int i) {
1.764 - int rows[2];
1.765 - rows[1]=i;
1.766 - lpx_del_rows(lp, 1, rows);
1.767 - }
1.768 - void _setCoeff(int col, int row, double value) {
1.769 - /// FIXME not yet implemented
1.770 - }
1.771 - double _getCoeff(int col, int row) {
1.772 - /// FIXME not yet implemented
1.773 - return 0.0;
1.774 - }
1.775 - virtual void _setColLowerBound(int i, double lo) {
1.776 - if (lo==INF) {
1.777 - //FIXME error
1.778 - }
1.779 - int b=lpx_get_col_type(lp, i);
1.780 - double up=lpx_get_col_ub(lp, i);
1.781 - if (lo==-INF) {
1.782 - switch (b) {
1.783 - case LPX_FR:
1.784 - case LPX_LO:
1.785 - lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
1.786 - break;
1.787 - case LPX_UP:
1.788 - break;
1.789 - case LPX_DB:
1.790 - case LPX_FX:
1.791 - lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
1.792 - break;
1.793 - default: ;
1.794 - //FIXME error
1.795 - }
1.796 - } else {
1.797 - switch (b) {
1.798 - case LPX_FR:
1.799 - case LPX_LO:
1.800 - lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
1.801 - break;
1.802 - case LPX_UP:
1.803 - case LPX_DB:
1.804 - case LPX_FX:
1.805 - if (lo==up)
1.806 - lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
1.807 - else
1.808 - lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
1.809 - break;
1.810 - default: ;
1.811 - //FIXME error
1.812 - }
1.813 - }
1.814 - }
1.815 - virtual double _getColLowerBound(int i) {
1.816 - int b=lpx_get_col_type(lp, i);
1.817 - switch (b) {
1.818 - case LPX_FR:
1.819 - return -INF;
1.820 - case LPX_LO:
1.821 - return lpx_get_col_lb(lp, i);
1.822 - case LPX_UP:
1.823 - return -INF;
1.824 - case LPX_DB:
1.825 - case LPX_FX:
1.826 - return lpx_get_col_lb(lp, i);
1.827 - default: ;
1.828 - //FIXME error
1.829 - return 0.0;
1.830 - }
1.831 - }
1.832 - virtual void _setColUpperBound(int i, double up) {
1.833 - if (up==-INF) {
1.834 - //FIXME error
1.835 - }
1.836 - int b=lpx_get_col_type(lp, i);
1.837 - double lo=lpx_get_col_lb(lp, i);
1.838 - if (up==INF) {
1.839 - switch (b) {
1.840 - case LPX_FR:
1.841 - case LPX_LO:
1.842 - break;
1.843 - case LPX_UP:
1.844 - lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
1.845 - break;
1.846 - case LPX_DB:
1.847 - case LPX_FX:
1.848 - lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
1.849 - break;
1.850 - default: ;
1.851 - //FIXME error
1.852 - }
1.853 - } else {
1.854 - switch (b) {
1.855 - case LPX_FR:
1.856 - lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
1.857 - break;
1.858 - case LPX_LO:
1.859 - if (lo==up)
1.860 - lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
1.861 - else
1.862 - lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
1.863 - break;
1.864 - case LPX_UP:
1.865 - lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
1.866 - break;
1.867 - case LPX_DB:
1.868 - case LPX_FX:
1.869 - if (lo==up)
1.870 - lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
1.871 - else
1.872 - lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
1.873 - break;
1.874 - default: ;
1.875 - //FIXME error
1.876 - }
1.877 - }
1.878 - }
1.879 - virtual double _getColUpperBound(int i) {
1.880 - int b=lpx_get_col_type(lp, i);
1.881 - switch (b) {
1.882 - case LPX_FR:
1.883 - case LPX_LO:
1.884 - return INF;
1.885 - case LPX_UP:
1.886 - case LPX_DB:
1.887 - case LPX_FX:
1.888 - return lpx_get_col_ub(lp, i);
1.889 - default: ;
1.890 - //FIXME error
1.891 - return 0.0;
1.892 - }
1.893 - }
1.894 - virtual void _setRowLowerBound(int i, double lo) {
1.895 - if (lo==INF) {
1.896 - //FIXME error
1.897 - }
1.898 - int b=lpx_get_row_type(lp, i);
1.899 - double up=lpx_get_row_ub(lp, i);
1.900 - if (lo==-INF) {
1.901 - switch (b) {
1.902 - case LPX_FR:
1.903 - case LPX_LO:
1.904 - lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
1.905 - break;
1.906 - case LPX_UP:
1.907 - break;
1.908 - case LPX_DB:
1.909 - case LPX_FX:
1.910 - lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
1.911 - break;
1.912 - default: ;
1.913 - //FIXME error
1.914 - }
1.915 - } else {
1.916 - switch (b) {
1.917 - case LPX_FR:
1.918 - case LPX_LO:
1.919 - lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
1.920 - break;
1.921 - case LPX_UP:
1.922 - case LPX_DB:
1.923 - case LPX_FX:
1.924 - if (lo==up)
1.925 - lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
1.926 - else
1.927 - lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
1.928 - break;
1.929 - default: ;
1.930 - //FIXME error
1.931 - }
1.932 - }
1.933 - }
1.934 - virtual double _getRowLowerBound(int i) {
1.935 - int b=lpx_get_row_type(lp, i);
1.936 - switch (b) {
1.937 - case LPX_FR:
1.938 - return -INF;
1.939 - case LPX_LO:
1.940 - return lpx_get_row_lb(lp, i);
1.941 - case LPX_UP:
1.942 - return -INF;
1.943 - case LPX_DB:
1.944 - case LPX_FX:
1.945 - return lpx_get_row_lb(lp, i);
1.946 - default: ;
1.947 - //FIXME error
1.948 - return 0.0;
1.949 - }
1.950 - }
1.951 - virtual void _setRowUpperBound(int i, double up) {
1.952 - if (up==-INF) {
1.953 - //FIXME error
1.954 - }
1.955 - int b=lpx_get_row_type(lp, i);
1.956 - double lo=lpx_get_row_lb(lp, i);
1.957 - if (up==INF) {
1.958 - switch (b) {
1.959 - case LPX_FR:
1.960 - case LPX_LO:
1.961 - break;
1.962 - case LPX_UP:
1.963 - lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
1.964 - break;
1.965 - case LPX_DB:
1.966 - case LPX_FX:
1.967 - lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
1.968 - break;
1.969 - default: ;
1.970 - //FIXME error
1.971 - }
1.972 - } else {
1.973 - switch (b) {
1.974 - case LPX_FR:
1.975 - lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
1.976 - break;
1.977 - case LPX_LO:
1.978 - if (lo==up)
1.979 - lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
1.980 - else
1.981 - lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
1.982 - break;
1.983 - case LPX_UP:
1.984 - lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
1.985 - break;
1.986 - case LPX_DB:
1.987 - case LPX_FX:
1.988 - if (lo==up)
1.989 - lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
1.990 - else
1.991 - lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
1.992 - break;
1.993 - default: ;
1.994 - //FIXME error
1.995 - }
1.996 - }
1.997 - }
1.998 - virtual double _getRowUpperBound(int i) {
1.999 - int b=lpx_get_row_type(lp, i);
1.1000 - switch (b) {
1.1001 - case LPX_FR:
1.1002 - case LPX_LO:
1.1003 - return INF;
1.1004 - case LPX_UP:
1.1005 - case LPX_DB:
1.1006 - case LPX_FX:
1.1007 - return lpx_get_row_ub(lp, i);
1.1008 - default: ;
1.1009 - //FIXME error
1.1010 - return 0.0;
1.1011 - }
1.1012 - }
1.1013 - /// \e
1.1014 - virtual double _getObjCoeff(int i) {
1.1015 - return lpx_get_obj_coef(lp, i);
1.1016 - }
1.1017 - /// \e
1.1018 - virtual void _setObjCoeff(int i, double obj_coef) {
1.1019 - lpx_set_obj_coef(lp, i, obj_coef);
1.1020 - }
1.1021 - public:
1.1022 - /// \e
1.1023 - void solveSimplex() { lpx_simplex(lp); }
1.1024 - /// \e
1.1025 - void solvePrimalSimplex() { lpx_simplex(lp); }
1.1026 - /// \e
1.1027 - void solveDualSimplex() { lpx_simplex(lp); }
1.1028 - protected:
1.1029 - virtual double _getPrimal(int i) {
1.1030 - return lpx_get_col_prim(lp, i);
1.1031 - }
1.1032 - public:
1.1033 - /// \e
1.1034 - double getObjVal() { return lpx_get_obj_val(lp); }
1.1035 - /// \e
1.1036 - int rowNum() const { return lpx_get_num_rows(lp); }
1.1037 - /// \e
1.1038 - int colNum() const { return lpx_get_num_cols(lp); }
1.1039 - /// \e
1.1040 - int warmUp() { return lpx_warm_up(lp); }
1.1041 - /// \e
1.1042 - void printWarmUpStatus(int i) {
1.1043 - switch (i) {
1.1044 - case LPX_E_OK: cout << "LPX_E_OK" << endl; break;
1.1045 - case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;
1.1046 - case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;
1.1047 - case LPX_E_SING: cout << "LPX_E_SING" << endl; break;
1.1048 - }
1.1049 - }
1.1050 - /// \e
1.1051 - int getPrimalStatus() { return lpx_get_prim_stat(lp); }
1.1052 - /// \e
1.1053 - void printPrimalStatus(int i) {
1.1054 - switch (i) {
1.1055 - case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;
1.1056 - case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;
1.1057 - case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;
1.1058 - case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;
1.1059 - }
1.1060 - }
1.1061 - /// \e
1.1062 - int getDualStatus() { return lpx_get_dual_stat(lp); }
1.1063 - /// \e
1.1064 - void printDualStatus(int i) {
1.1065 - switch (i) {
1.1066 - case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;
1.1067 - case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;
1.1068 - case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;
1.1069 - case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
1.1070 - }
1.1071 - }
1.1072 - /// Returns the status of the slack variable assigned to row \c row.
1.1073 - int getRowStat(const Row& row) {
1.1074 - return lpx_get_row_stat(lp, row_iter_map[row]);
1.1075 - }
1.1076 - /// \e
1.1077 - void printRowStatus(int i) {
1.1078 - switch (i) {
1.1079 - case LPX_BS: cout << "LPX_BS" << endl; break;
1.1080 - case LPX_NL: cout << "LPX_NL" << endl; break;
1.1081 - case LPX_NU: cout << "LPX_NU" << endl; break;
1.1082 - case LPX_NF: cout << "LPX_NF" << endl; break;
1.1083 - case LPX_NS: cout << "LPX_NS" << endl; break;
1.1084 - }
1.1085 - }
1.1086 - /// Returns the status of the variable assigned to column \c col.
1.1087 - int getColStat(const Col& col) {
1.1088 - return lpx_get_col_stat(lp, col_iter_map[col]);
1.1089 - }
1.1090 - /// \e
1.1091 - void printColStatus(int i) {
1.1092 - switch (i) {
1.1093 - case LPX_BS: cout << "LPX_BS" << endl; break;
1.1094 - case LPX_NL: cout << "LPX_NL" << endl; break;
1.1095 - case LPX_NU: cout << "LPX_NU" << endl; break;
1.1096 - case LPX_NF: cout << "LPX_NF" << endl; break;
1.1097 - case LPX_NS: cout << "LPX_NS" << endl; break;
1.1098 - }
1.1099 - }
1.1100 -
1.1101 - // MIP
1.1102 - /// \e
1.1103 - void solveBandB() { lpx_integer(lp); }
1.1104 - /// \e
1.1105 - void setLP() { lpx_set_class(lp, LPX_LP); }
1.1106 - /// \e
1.1107 - void setMIP() { lpx_set_class(lp, LPX_MIP); }
1.1108 - protected:
1.1109 - /// \e
1.1110 - void _setColCont(int i) { lpx_set_col_kind(lp, i, LPX_CV); }
1.1111 - /// \e
1.1112 - void _setColInt(int i) { lpx_set_col_kind(lp, i, LPX_IV); }
1.1113 - /// \e
1.1114 - double _getMIPPrimal(int i) { return lpx_mip_col_val(lp, i); }
1.1115 - };
1.1116 -
1.1117 - /// @}
1.1118 -
1.1119 -} //namespace lemon
1.1120 -
1.1121 -#endif //LEMON_LP_SOLVER_BASE_H