1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/lp/lp_solver_base.h Tue Feb 01 12:53:30 2005 +0000
1.3 @@ -0,0 +1,918 @@
1.4 +// -*- c++ -*-
1.5 +#ifndef LEMON_LP_SOLVER_WRAPPER_H
1.6 +#define LEMON_LP_SOLVER_WRAPPER_H
1.7 +
1.8 +///\ingroup misc
1.9 +///\file
1.10 +///\brief Dijkstra algorithm.
1.11 +
1.12 +// #include <stdio.h>
1.13 +#include <stdlib.h>
1.14 +#include <iostream>
1.15 +#include <map>
1.16 +#include <limits>
1.17 +// #include <stdio>
1.18 +//#include <stdlib>
1.19 +extern "C" {
1.20 +#include "glpk.h"
1.21 +}
1.22 +
1.23 +#include <iostream>
1.24 +#include <vector>
1.25 +#include <string>
1.26 +#include <list>
1.27 +#include <memory>
1.28 +#include <utility>
1.29 +
1.30 +//#include <lemon/list_graph.h>
1.31 +#include <lemon/invalid.h>
1.32 +#include <expression.h>
1.33 +//#include <bfs_dfs.h>
1.34 +//#include <stp.h>
1.35 +//#include <lemon/max_flow.h>
1.36 +//#include <augmenting_flow.h>
1.37 +//#include <iter_map.h>
1.38 +
1.39 +using std::cout;
1.40 +using std::cin;
1.41 +using std::endl;
1.42 +
1.43 +namespace lemon {
1.44 +
1.45 + /// \addtogroup misc
1.46 + /// @{
1.47 +
1.48 + /// \brief A partitioned vector with iterable classes.
1.49 + ///
1.50 + /// This class implements a container in which the data is stored in an
1.51 + /// stl vector, the range is partitioned into sets and each set is
1.52 + /// doubly linked in a list.
1.53 + /// That is, each class is iterable by lemon iterators, and any member of
1.54 + /// the vector can bo moved to an other class.
1.55 + template <typename T>
1.56 + class IterablePartition {
1.57 + protected:
1.58 + struct Node {
1.59 + T data;
1.60 + int prev; //invalid az -1
1.61 + int next;
1.62 + };
1.63 + std::vector<Node> nodes;
1.64 + struct Tip {
1.65 + int first;
1.66 + int last;
1.67 + };
1.68 + std::vector<Tip> tips;
1.69 + public:
1.70 + /// The classes are indexed by integers from \c 0 to \c classNum()-1.
1.71 + int classNum() const { return tips.size(); }
1.72 + /// This lemon style iterator iterates through a class.
1.73 + class ClassIt;
1.74 + /// Constructor. The number of classes is to be given which is fixed
1.75 + /// over the life of the container.
1.76 + /// The partition classes are indexed from 0 to class_num-1.
1.77 + IterablePartition(int class_num) {
1.78 + for (int i=0; i<class_num; ++i) {
1.79 + Tip t;
1.80 + t.first=t.last=-1;
1.81 + tips.push_back(t);
1.82 + }
1.83 + }
1.84 + protected:
1.85 + void befuz(ClassIt it, int class_id) {
1.86 + if (tips[class_id].first==-1) {
1.87 + if (tips[class_id].last==-1) {
1.88 + nodes[it.i].prev=nodes[it.i].next=-1;
1.89 + tips[class_id].first=tips[class_id].last=it.i;
1.90 + }
1.91 + } else {
1.92 + nodes[it.i].prev=tips[class_id].last;
1.93 + nodes[it.i].next=-1;
1.94 + nodes[tips[class_id].last].next=it.i;
1.95 + tips[class_id].last=it.i;
1.96 + }
1.97 + }
1.98 + void kifuz(ClassIt it, int class_id) {
1.99 + if (tips[class_id].first==it.i) {
1.100 + if (tips[class_id].last==it.i) {
1.101 + tips[class_id].first=tips[class_id].last=-1;
1.102 + } else {
1.103 + tips[class_id].first=nodes[it.i].next;
1.104 + nodes[nodes[it.i].next].prev=-1;
1.105 + }
1.106 + } else {
1.107 + if (tips[class_id].last==it.i) {
1.108 + tips[class_id].last=nodes[it.i].prev;
1.109 + nodes[nodes[it.i].prev].next=-1;
1.110 + } else {
1.111 + nodes[nodes[it.i].next].prev=nodes[it.i].prev;
1.112 + nodes[nodes[it.i].prev].next=nodes[it.i].next;
1.113 + }
1.114 + }
1.115 + }
1.116 + public:
1.117 + /// A new element with data \c t is pushed into the vector and into class
1.118 + /// \c class_id.
1.119 + ClassIt push_back(const T& t, int class_id) {
1.120 + Node n;
1.121 + n.data=t;
1.122 + nodes.push_back(n);
1.123 + int i=nodes.size()-1;
1.124 + befuz(i, class_id);
1.125 + return i;
1.126 + }
1.127 + /// A member is moved to an other class.
1.128 + void set(ClassIt it, int old_class_id, int new_class_id) {
1.129 + kifuz(it.i, old_class_id);
1.130 + befuz(it.i, new_class_id);
1.131 + }
1.132 + /// Returns the data pointed by \c it.
1.133 + T& operator[](ClassIt it) { return nodes[it.i].data; }
1.134 + /// Returns the data pointed by \c it.
1.135 + const T& operator[](ClassIt it) const { return nodes[it.i].data; }
1.136 + ///.
1.137 + class ClassIt {
1.138 + friend class IterablePartition;
1.139 + protected:
1.140 + int i;
1.141 + public:
1.142 + /// Default constructor.
1.143 + ClassIt() { }
1.144 + /// This constructor constructs an iterator which points
1.145 + /// to the member of th container indexed by the integer _i.
1.146 + ClassIt(const int& _i) : i(_i) { }
1.147 + /// Invalid constructor.
1.148 + ClassIt(const Invalid&) : i(-1) { }
1.149 + friend bool operator<(const ClassIt& x, const ClassIt& y);
1.150 + friend std::ostream& operator<<(std::ostream& os,
1.151 + const ClassIt& it);
1.152 + };
1.153 + friend bool operator<(const ClassIt& x, const ClassIt& y) {
1.154 + return (x.i < y.i);
1.155 + }
1.156 + friend std::ostream& operator<<(std::ostream& os,
1.157 + const ClassIt& it) {
1.158 + os << it.i;
1.159 + return os;
1.160 + }
1.161 + /// First member of class \c class_id.
1.162 + ClassIt& first(ClassIt& it, int class_id) const {
1.163 + it.i=tips[class_id].first;
1.164 + return it;
1.165 + }
1.166 + /// Next member.
1.167 + ClassIt& next(ClassIt& it) const {
1.168 + it.i=nodes[it.i].next;
1.169 + return it;
1.170 + }
1.171 + /// True iff the iterator is valid.
1.172 + bool valid(const ClassIt& it) const { return it.i!=-1; }
1.173 + };
1.174 +
1.175 +
1.176 + /*! \e
1.177 + \todo A[x,y]-t cserel. Jobboldal, baloldal csere.
1.178 + \todo LEKERDEZESEK!!!
1.179 + \todo DOKSI!!!! Doxygen group!!!
1.180 + The aim of this class is to give a general surface to different
1.181 + solvers, i.e. it makes possible to write algorithms using LP's,
1.182 + in which the solver can be changed to an other one easily.
1.183 + */
1.184 + template <typename _Value>
1.185 + class LPSolverBase {
1.186 + public:
1.187 + /// \e
1.188 + typedef _Value Value;
1.189 + /// \e
1.190 + typedef IterablePartition<int>::ClassIt RowIt;
1.191 + /// \e
1.192 + typedef IterablePartition<int>::ClassIt ColIt;
1.193 + public:
1.194 + /// \e
1.195 + IterablePartition<int> row_iter_map;
1.196 + /// \e
1.197 + IterablePartition<int> col_iter_map;
1.198 + /// \e
1.199 + const int VALID_CLASS;
1.200 + /// \e
1.201 + const int INVALID_CLASS;
1.202 + /// \e
1.203 + static const _Value INF;
1.204 + public:
1.205 + /// \e
1.206 + LPSolverBase() : row_iter_map(2),
1.207 + col_iter_map(2),
1.208 + VALID_CLASS(0), INVALID_CLASS(1) { }
1.209 + /// \e
1.210 + virtual ~LPSolverBase() { }
1.211 +
1.212 + //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
1.213 +
1.214 + public:
1.215 + /// \e
1.216 + virtual void setMinimize() = 0;
1.217 + /// \e
1.218 + virtual void setMaximize() = 0;
1.219 +
1.220 + //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
1.221 +
1.222 + protected:
1.223 + /// \e
1.224 + virtual int _addCol() = 0;
1.225 + /// \e
1.226 + virtual int _addRow() = 0;
1.227 + /// \e
1.228 + virtual void _eraseCol(int i) = 0;
1.229 + /// \e
1.230 + virtual void _eraseRow(int i) = 0;
1.231 + /// \e
1.232 + virtual void _setRowCoeffs(int i,
1.233 + const std::vector<std::pair<int, _Value> >& coeffs) = 0;
1.234 + /// \e
1.235 + virtual void _setColCoeffs(int i,
1.236 + const std::vector<std::pair<int, _Value> >& coeffs) = 0;
1.237 + public:
1.238 + /// \e
1.239 + enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
1.240 + protected:
1.241 + /// \e
1.242 + /// The lower bound of a variable (column) have to be given by an
1.243 + /// extended number of type _Value, i.e. a finite number of type
1.244 + /// _Value or -INF.
1.245 + virtual void _setColLowerBound(int i, _Value value) = 0;
1.246 + /// \e
1.247 + /// The lower bound of a variable (column) is an
1.248 + /// extended number of type _Value, i.e. a finite number of type
1.249 + /// _Value or -INF.
1.250 + virtual _Value _getColLowerBound(int i) = 0;
1.251 + /// \e
1.252 + /// The upper bound of a variable (column) have to be given by an
1.253 + /// extended number of type _Value, i.e. a finite number of type
1.254 + /// _Value or INF.
1.255 + virtual void _setColUpperBound(int i, _Value value) = 0;
1.256 + /// \e
1.257 + /// The upper bound of a variable (column) is an
1.258 + /// extended number of type _Value, i.e. a finite number of type
1.259 + /// _Value or INF.
1.260 + virtual _Value _getColUpperBound(int i) = 0;
1.261 + /// \e
1.262 + /// The lower bound of a linear expression (row) have to be given by an
1.263 + /// extended number of type _Value, i.e. a finite number of type
1.264 + /// _Value or -INF.
1.265 + virtual void _setRowLowerBound(int i, _Value value) = 0;
1.266 + /// \e
1.267 + /// The lower bound of a linear expression (row) is an
1.268 + /// extended number of type _Value, i.e. a finite number of type
1.269 + /// _Value or -INF.
1.270 + virtual _Value _getRowLowerBound(int i) = 0;
1.271 + /// \e
1.272 + /// The upper bound of a linear expression (row) have to be given by an
1.273 + /// extended number of type _Value, i.e. a finite number of type
1.274 + /// _Value or INF.
1.275 + virtual void _setRowUpperBound(int i, _Value value) = 0;
1.276 + /// \e
1.277 + /// The upper bound of a linear expression (row) is an
1.278 + /// extended number of type _Value, i.e. a finite number of type
1.279 + /// _Value or INF.
1.280 + virtual _Value _getRowUpperBound(int i) = 0;
1.281 + /// \e
1.282 + virtual void _setObjCoef(int i, _Value obj_coef) = 0;
1.283 + /// \e
1.284 + virtual _Value _getObjCoef(int i) = 0;
1.285 +
1.286 + //LOW LEVEL, SOLUTION RETRIEVING FUNCTIONS
1.287 +
1.288 + protected:
1.289 + /// \e
1.290 + virtual _Value _getPrimal(int i) = 0;
1.291 +
1.292 + //HIGH LEVEL INTERFACE, MATRIX MANIPULATING FUNTIONS
1.293 +
1.294 + public:
1.295 + /// \e
1.296 + ColIt addCol() {
1.297 + int i=_addCol();
1.298 + ColIt col_it;
1.299 + col_iter_map.first(col_it, INVALID_CLASS);
1.300 + if (col_iter_map.valid(col_it)) { //van hasznalhato hely
1.301 + col_iter_map.set(col_it, INVALID_CLASS, VALID_CLASS);
1.302 + col_iter_map[col_it]=i;
1.303 + } else { //a cucc vegere kell inzertalni mert nincs szabad hely
1.304 + col_it=col_iter_map.push_back(i, VALID_CLASS);
1.305 + }
1.306 + return col_it;
1.307 + }
1.308 + /// \e
1.309 + RowIt addRow() {
1.310 + int i=_addRow();
1.311 + RowIt row_it;
1.312 + row_iter_map.first(row_it, INVALID_CLASS);
1.313 + if (row_iter_map.valid(row_it)) { //van hasznalhato hely
1.314 + row_iter_map.set(row_it, INVALID_CLASS, VALID_CLASS);
1.315 + row_iter_map[row_it]=i;
1.316 + } else { //a cucc vegere kell inzertalni mert nincs szabad hely
1.317 + row_it=row_iter_map.push_back(i, VALID_CLASS);
1.318 + }
1.319 + return row_it;
1.320 + }
1.321 + /// \e
1.322 + void eraseCol(const ColIt& col_it) {
1.323 + col_iter_map.set(col_it, VALID_CLASS, INVALID_CLASS);
1.324 + int cols[2];
1.325 + cols[1]=col_iter_map[col_it];
1.326 + _eraseCol(cols[1]);
1.327 + col_iter_map[col_it]=0; //glpk specifikus, de kell ez??
1.328 + ColIt it;
1.329 + for (col_iter_map.first(it, VALID_CLASS);
1.330 + col_iter_map.valid(it); col_iter_map.next(it)) {
1.331 + if (col_iter_map[it]>cols[1]) --col_iter_map[it];
1.332 + }
1.333 + }
1.334 + /// \e
1.335 + void eraseRow(const RowIt& row_it) {
1.336 + row_iter_map.set(row_it, VALID_CLASS, INVALID_CLASS);
1.337 + int rows[2];
1.338 + rows[1]=row_iter_map[row_it];
1.339 + _eraseRow(rows[1]);
1.340 + row_iter_map[row_it]=0; //glpk specifikus, de kell ez??
1.341 + RowIt it;
1.342 + for (row_iter_map.first(it, VALID_CLASS);
1.343 + row_iter_map.valid(it); row_iter_map.next(it)) {
1.344 + if (row_iter_map[it]>rows[1]) --row_iter_map[it];
1.345 + }
1.346 + }
1.347 + /// \e
1.348 + template <typename Begin, typename End>
1.349 + void setRowCoeffs(RowIt row_it, Begin begin, End end) {
1.350 + std::vector<std::pair<int, double> > coeffs;
1.351 + for ( ; begin!=end; ++begin) {
1.352 + coeffs.push_back(std::
1.353 + make_pair(col_iter_map[begin->first], begin->second));
1.354 + }
1.355 + _setRowCoeffs(row_iter_map[row_it], coeffs);
1.356 + }
1.357 + /// \e
1.358 + template <typename Begin, typename End>
1.359 + void setColCoeffs(ColIt col_it, Begin begin, End end) {
1.360 + std::vector<std::pair<int, double> > coeffs;
1.361 + for ( ; begin!=end; ++begin) {
1.362 + coeffs.push_back(std::
1.363 + make_pair(row_iter_map[begin->first], begin->second));
1.364 + }
1.365 + _setColCoeffs(col_iter_map[col_it], coeffs);
1.366 + }
1.367 + /// \e
1.368 + void setColLowerBound(ColIt col_it, _Value lo) {
1.369 + _setColLowerBound(col_iter_map[col_it], lo);
1.370 + }
1.371 + /// \e
1.372 + _Value getColLowerBound(ColIt col_it) {
1.373 + return _getColLowerBound(col_iter_map[col_it]);
1.374 + }
1.375 + /// \e
1.376 + void setColUpperBound(ColIt col_it, _Value up) {
1.377 + _setColUpperBound(col_iter_map[col_it], up);
1.378 + }
1.379 + /// \e
1.380 + _Value getColUpperBound(ColIt col_it) {
1.381 + return _getColUpperBound(col_iter_map[col_it]);
1.382 + }
1.383 + /// \e
1.384 + void setRowLowerBound(RowIt row_it, _Value lo) {
1.385 + _setRowLowerBound(row_iter_map[row_it], lo);
1.386 + }
1.387 + /// \e
1.388 + _Value getRowLowerBound(RowIt row_it) {
1.389 + return _getRowLowerBound(row_iter_map[row_it]);
1.390 + }
1.391 + /// \e
1.392 + void setRowUpperBound(RowIt row_it, _Value up) {
1.393 + _setRowUpperBound(row_iter_map[row_it], up);
1.394 + }
1.395 + /// \e
1.396 + _Value getRowUpperBound(RowIt row_it) {
1.397 + return _getRowUpperBound(row_iter_map[row_it]);
1.398 + }
1.399 + /// \e
1.400 + void setObjCoef(const ColIt& col_it, _Value obj_coef) {
1.401 + _setObjCoef(col_iter_map[col_it], obj_coef);
1.402 + }
1.403 + /// \e
1.404 + _Value getObjCoef(const ColIt& col_it) {
1.405 + return _getObjCoef(col_iter_map[col_it]);
1.406 + }
1.407 +
1.408 + //MOST HIGH LEVEL, USER FRIEND FUNCTIONS
1.409 +
1.410 + /// \e
1.411 + typedef Expr<ColIt, _Value> Expression;
1.412 + /// \e
1.413 + typedef Expr<RowIt, _Value> DualExpression;
1.414 + /// \e
1.415 + void setRowCoeffs(RowIt row_it, const Expression& expr) {
1.416 + std::vector<std::pair<int, _Value> > row_coeffs;
1.417 + for(typename Expression::Data::const_iterator i=expr.data.begin();
1.418 + i!=expr.data.end(); ++i) {
1.419 + row_coeffs.push_back(std::make_pair
1.420 + (col_iter_map[(*i).first], (*i).second));
1.421 + }
1.422 + _setRowCoeffs(row_iter_map[row_it], row_coeffs);
1.423 + }
1.424 + /// \e
1.425 + void setColCoeffs(ColIt col_it, const DualExpression& expr) {
1.426 + std::vector<std::pair<int, _Value> > col_coeffs;
1.427 + for(typename DualExpression::Data::const_iterator i=expr.data.begin();
1.428 + i!=expr.data.end(); ++i) {
1.429 + col_coeffs.push_back(std::make_pair
1.430 + (row_iter_map[(*i).first], (*i).second));
1.431 + }
1.432 + _setColCoeffs(col_iter_map[col_it], col_coeffs);
1.433 + }
1.434 + /// \e
1.435 + void setObjCoeffs(const Expression& expr) {
1.436 + for(typename Expression::Data::const_iterator i=expr.data.begin();
1.437 + i!=expr.data.end(); ++i) {
1.438 + setObjCoef((*i).first, (*i).second);
1.439 + }
1.440 + }
1.441 +
1.442 + //SOLVER FUNCTIONS
1.443 +
1.444 + /// \e
1.445 + virtual void solveSimplex() = 0;
1.446 + /// \e
1.447 + virtual void solvePrimalSimplex() = 0;
1.448 + /// \e
1.449 + virtual void solveDualSimplex() = 0;
1.450 + /// \e
1.451 +
1.452 + //HIGH LEVEL, SOLUTION RETRIEVING FUNCTIONS
1.453 +
1.454 + public:
1.455 +
1.456 + /// \e
1.457 + _Value getPrimal(const ColIt& col_it) {
1.458 + return _getPrimal(col_iter_map[col_it]);
1.459 + }
1.460 + /// \e
1.461 + virtual _Value getObjVal() = 0;
1.462 +
1.463 + //OTHER FUNCTIONS
1.464 +
1.465 + /// \e
1.466 + virtual int rowNum() const = 0;
1.467 + /// \e
1.468 + virtual int colNum() const = 0;
1.469 + /// \e
1.470 + virtual int warmUp() = 0;
1.471 + /// \e
1.472 + virtual void printWarmUpStatus(int i) = 0;
1.473 + /// \e
1.474 + virtual int getPrimalStatus() = 0;
1.475 + /// \e
1.476 + virtual void printPrimalStatus(int i) = 0;
1.477 + /// \e
1.478 + virtual int getDualStatus() = 0;
1.479 + /// \e
1.480 + virtual void printDualStatus(int i) = 0;
1.481 + /// Returns the status of the slack variable assigned to row \c row_it.
1.482 + virtual int getRowStat(const RowIt& row_it) = 0;
1.483 + /// \e
1.484 + virtual void printRowStatus(int i) = 0;
1.485 + /// Returns the status of the variable assigned to column \c col_it.
1.486 + virtual int getColStat(const ColIt& col_it) = 0;
1.487 + /// \e
1.488 + virtual void printColStatus(int i) = 0;
1.489 + };
1.490 +
1.491 + template <typename _Value>
1.492 + const _Value LPSolverBase<_Value>::INF=std::numeric_limits<_Value>::infinity();
1.493 +
1.494 +
1.495 + /// \brief Wrapper for GLPK solver
1.496 + ///
1.497 + /// This class implements a lemon wrapper for GLPK.
1.498 + class LPGLPK : public LPSolverBase<double> {
1.499 + public:
1.500 + typedef LPSolverBase<double> Parent;
1.501 +
1.502 + public:
1.503 + /// \e
1.504 + LPX* lp;
1.505 +
1.506 + public:
1.507 + /// \e
1.508 + LPGLPK() : Parent(),
1.509 + lp(lpx_create_prob()) {
1.510 + lpx_set_int_parm(lp, LPX_K_DUAL, 1);
1.511 + }
1.512 + /// \e
1.513 + ~LPGLPK() {
1.514 + lpx_delete_prob(lp);
1.515 + }
1.516 +
1.517 + //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
1.518 +
1.519 + /// \e
1.520 + void setMinimize() {
1.521 + lpx_set_obj_dir(lp, LPX_MIN);
1.522 + }
1.523 + /// \e
1.524 + void setMaximize() {
1.525 + lpx_set_obj_dir(lp, LPX_MAX);
1.526 + }
1.527 +
1.528 + //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
1.529 +
1.530 + protected:
1.531 + /// \e
1.532 + int _addCol() {
1.533 + int i=lpx_add_cols(lp, 1);
1.534 + _setColLowerBound(i, -INF);
1.535 + _setColUpperBound(i, INF);
1.536 + return i;
1.537 + }
1.538 + /// \e
1.539 + int _addRow() {
1.540 + int i=lpx_add_rows(lp, 1);
1.541 + return i;
1.542 + }
1.543 + /// \e
1.544 + virtual void _setRowCoeffs(int i,
1.545 + const std::vector<std::pair<int, double> >& coeffs) {
1.546 + int mem_length=1+colNum();
1.547 + int* indices = new int[mem_length];
1.548 + double* doubles = new double[mem_length];
1.549 + int length=0;
1.550 + for (std::vector<std::pair<int, double> >::
1.551 + const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
1.552 + ++length;
1.553 + indices[length]=it->first;
1.554 + doubles[length]=it->second;
1.555 +// std::cout << " " << indices[length] << " "
1.556 +// << doubles[length] << std::endl;
1.557 + }
1.558 +// std::cout << i << " " << length << std::endl;
1.559 + lpx_set_mat_row(lp, i, length, indices, doubles);
1.560 + delete [] indices;
1.561 + delete [] doubles;
1.562 + }
1.563 + /// \e
1.564 + virtual void _setColCoeffs(int i,
1.565 + const std::vector<std::pair<int, double> >& coeffs) {
1.566 + int mem_length=1+rowNum();
1.567 + int* indices = new int[mem_length];
1.568 + double* doubles = new double[mem_length];
1.569 + int length=0;
1.570 + for (std::vector<std::pair<int, double> >::
1.571 + const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
1.572 + ++length;
1.573 + indices[length]=it->first;
1.574 + doubles[length]=it->second;
1.575 + }
1.576 + lpx_set_mat_col(lp, i, length, indices, doubles);
1.577 + delete [] indices;
1.578 + delete [] doubles;
1.579 + }
1.580 + /// \e
1.581 + virtual void _eraseCol(int i) {
1.582 + int cols[2];
1.583 + cols[1]=i;
1.584 + lpx_del_cols(lp, 1, cols);
1.585 + }
1.586 + virtual void _eraseRow(int i) {
1.587 + int rows[2];
1.588 + rows[1]=i;
1.589 + lpx_del_rows(lp, 1, rows);
1.590 + }
1.591 + virtual void _setColLowerBound(int i, double lo) {
1.592 + if (lo==INF) {
1.593 + //FIXME error
1.594 + }
1.595 + int b=lpx_get_col_type(lp, i);
1.596 + double up=lpx_get_col_ub(lp, i);
1.597 + if (lo==-INF) {
1.598 + switch (b) {
1.599 + case LPX_FR:
1.600 + case LPX_LO:
1.601 + lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
1.602 + break;
1.603 + case LPX_UP:
1.604 + break;
1.605 + case LPX_DB:
1.606 + case LPX_FX:
1.607 + lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
1.608 + break;
1.609 + default: ;
1.610 + //FIXME error
1.611 + }
1.612 + } else {
1.613 + switch (b) {
1.614 + case LPX_FR:
1.615 + case LPX_LO:
1.616 + lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
1.617 + break;
1.618 + case LPX_UP:
1.619 + case LPX_DB:
1.620 + case LPX_FX:
1.621 + if (lo==up)
1.622 + lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
1.623 + else
1.624 + lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
1.625 + break;
1.626 + default: ;
1.627 + //FIXME error
1.628 + }
1.629 + }
1.630 + }
1.631 + virtual double _getColLowerBound(int i) {
1.632 + int b=lpx_get_col_type(lp, i);
1.633 + switch (b) {
1.634 + case LPX_FR:
1.635 + return -INF;
1.636 + case LPX_LO:
1.637 + return lpx_get_col_lb(lp, i);
1.638 + case LPX_UP:
1.639 + return -INF;
1.640 + case LPX_DB:
1.641 + case LPX_FX:
1.642 + return lpx_get_col_lb(lp, i);
1.643 + default: ;
1.644 + //FIXME error
1.645 + return 0.0;
1.646 + }
1.647 + }
1.648 + virtual void _setColUpperBound(int i, double up) {
1.649 + if (up==-INF) {
1.650 + //FIXME error
1.651 + }
1.652 + int b=lpx_get_col_type(lp, i);
1.653 + double lo=lpx_get_col_lb(lp, i);
1.654 + if (up==INF) {
1.655 + switch (b) {
1.656 + case LPX_FR:
1.657 + case LPX_LO:
1.658 + break;
1.659 + case LPX_UP:
1.660 + lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
1.661 + break;
1.662 + case LPX_DB:
1.663 + case LPX_FX:
1.664 + lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
1.665 + break;
1.666 + default: ;
1.667 + //FIXME error
1.668 + }
1.669 + } else {
1.670 + switch (b) {
1.671 + case LPX_FR:
1.672 + lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
1.673 + case LPX_LO:
1.674 + if (lo==up)
1.675 + lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
1.676 + else
1.677 + lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
1.678 + break;
1.679 + case LPX_UP:
1.680 + lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
1.681 + break;
1.682 + case LPX_DB:
1.683 + case LPX_FX:
1.684 + if (lo==up)
1.685 + lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
1.686 + else
1.687 + lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
1.688 + break;
1.689 + default: ;
1.690 + //FIXME error
1.691 + }
1.692 + }
1.693 + }
1.694 + virtual double _getColUpperBound(int i) {
1.695 + int b=lpx_get_col_type(lp, i);
1.696 + switch (b) {
1.697 + case LPX_FR:
1.698 + case LPX_LO:
1.699 + return INF;
1.700 + case LPX_UP:
1.701 + case LPX_DB:
1.702 + case LPX_FX:
1.703 + return lpx_get_col_ub(lp, i);
1.704 + default: ;
1.705 + //FIXME error
1.706 + return 0.0;
1.707 + }
1.708 + }
1.709 + virtual void _setRowLowerBound(int i, double lo) {
1.710 + if (lo==INF) {
1.711 + //FIXME error
1.712 + }
1.713 + int b=lpx_get_row_type(lp, i);
1.714 + double up=lpx_get_row_ub(lp, i);
1.715 + if (lo==-INF) {
1.716 + switch (b) {
1.717 + case LPX_FR:
1.718 + case LPX_LO:
1.719 + lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
1.720 + break;
1.721 + case LPX_UP:
1.722 + break;
1.723 + case LPX_DB:
1.724 + case LPX_FX:
1.725 + lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
1.726 + break;
1.727 + default: ;
1.728 + //FIXME error
1.729 + }
1.730 + } else {
1.731 + switch (b) {
1.732 + case LPX_FR:
1.733 + case LPX_LO:
1.734 + lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
1.735 + break;
1.736 + case LPX_UP:
1.737 + case LPX_DB:
1.738 + case LPX_FX:
1.739 + if (lo==up)
1.740 + lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
1.741 + else
1.742 + lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
1.743 + break;
1.744 + default: ;
1.745 + //FIXME error
1.746 + }
1.747 + }
1.748 + }
1.749 + virtual double _getRowLowerBound(int i) {
1.750 + int b=lpx_get_row_type(lp, i);
1.751 + switch (b) {
1.752 + case LPX_FR:
1.753 + return -INF;
1.754 + case LPX_LO:
1.755 + return lpx_get_row_lb(lp, i);
1.756 + case LPX_UP:
1.757 + return -INF;
1.758 + case LPX_DB:
1.759 + case LPX_FX:
1.760 + return lpx_get_row_lb(lp, i);
1.761 + default: ;
1.762 + //FIXME error
1.763 + return 0.0;
1.764 + }
1.765 + }
1.766 + virtual void _setRowUpperBound(int i, double up) {
1.767 + if (up==-INF) {
1.768 + //FIXME error
1.769 + }
1.770 + int b=lpx_get_row_type(lp, i);
1.771 + double lo=lpx_get_row_lb(lp, i);
1.772 + if (up==INF) {
1.773 + switch (b) {
1.774 + case LPX_FR:
1.775 + case LPX_LO:
1.776 + break;
1.777 + case LPX_UP:
1.778 + lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
1.779 + break;
1.780 + case LPX_DB:
1.781 + case LPX_FX:
1.782 + lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
1.783 + break;
1.784 + default: ;
1.785 + //FIXME error
1.786 + }
1.787 + } else {
1.788 + switch (b) {
1.789 + case LPX_FR:
1.790 + lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
1.791 + case LPX_LO:
1.792 + if (lo==up)
1.793 + lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
1.794 + else
1.795 + lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
1.796 + break;
1.797 + case LPX_UP:
1.798 + lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
1.799 + break;
1.800 + case LPX_DB:
1.801 + case LPX_FX:
1.802 + if (lo==up)
1.803 + lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
1.804 + else
1.805 + lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
1.806 + break;
1.807 + default: ;
1.808 + //FIXME error
1.809 + }
1.810 + }
1.811 + }
1.812 + virtual double _getRowUpperBound(int i) {
1.813 + int b=lpx_get_row_type(lp, i);
1.814 + switch (b) {
1.815 + case LPX_FR:
1.816 + case LPX_LO:
1.817 + return INF;
1.818 + case LPX_UP:
1.819 + case LPX_DB:
1.820 + case LPX_FX:
1.821 + return lpx_get_row_ub(lp, i);
1.822 + default: ;
1.823 + //FIXME error
1.824 + return 0.0;
1.825 + }
1.826 + }
1.827 + /// \e
1.828 + virtual double _getObjCoef(int i) {
1.829 + return lpx_get_obj_coef(lp, i);
1.830 + }
1.831 + /// \e
1.832 + virtual void _setObjCoef(int i, double obj_coef) {
1.833 + lpx_set_obj_coef(lp, i, obj_coef);
1.834 + }
1.835 + public:
1.836 + /// \e
1.837 + void solveSimplex() { lpx_simplex(lp); }
1.838 + /// \e
1.839 + void solvePrimalSimplex() { lpx_simplex(lp); }
1.840 + /// \e
1.841 + void solveDualSimplex() { lpx_simplex(lp); }
1.842 + /// \e
1.843 + protected:
1.844 + virtual double _getPrimal(int i) {
1.845 + return lpx_get_col_prim(lp, i);
1.846 + }
1.847 + public:
1.848 + /// \e
1.849 + double getObjVal() { return lpx_get_obj_val(lp); }
1.850 + /// \e
1.851 + int rowNum() const { return lpx_get_num_rows(lp); }
1.852 + /// \e
1.853 + int colNum() const { return lpx_get_num_cols(lp); }
1.854 + /// \e
1.855 + int warmUp() { return lpx_warm_up(lp); }
1.856 + /// \e
1.857 + void printWarmUpStatus(int i) {
1.858 + switch (i) {
1.859 + case LPX_E_OK: cout << "LPX_E_OK" << endl; break;
1.860 + case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;
1.861 + case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;
1.862 + case LPX_E_SING: cout << "LPX_E_SING" << endl; break;
1.863 + }
1.864 + }
1.865 + /// \e
1.866 + int getPrimalStatus() { return lpx_get_prim_stat(lp); }
1.867 + /// \e
1.868 + void printPrimalStatus(int i) {
1.869 + switch (i) {
1.870 + case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;
1.871 + case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;
1.872 + case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;
1.873 + case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;
1.874 + }
1.875 + }
1.876 + /// \e
1.877 + int getDualStatus() { return lpx_get_dual_stat(lp); }
1.878 + /// \e
1.879 + void printDualStatus(int i) {
1.880 + switch (i) {
1.881 + case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;
1.882 + case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;
1.883 + case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;
1.884 + case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
1.885 + }
1.886 + }
1.887 + /// Returns the status of the slack variable assigned to row \c row_it.
1.888 + int getRowStat(const RowIt& row_it) {
1.889 + return lpx_get_row_stat(lp, row_iter_map[row_it]);
1.890 + }
1.891 + /// \e
1.892 + void printRowStatus(int i) {
1.893 + switch (i) {
1.894 + case LPX_BS: cout << "LPX_BS" << endl; break;
1.895 + case LPX_NL: cout << "LPX_NL" << endl; break;
1.896 + case LPX_NU: cout << "LPX_NU" << endl; break;
1.897 + case LPX_NF: cout << "LPX_NF" << endl; break;
1.898 + case LPX_NS: cout << "LPX_NS" << endl; break;
1.899 + }
1.900 + }
1.901 + /// Returns the status of the variable assigned to column \c col_it.
1.902 + int getColStat(const ColIt& col_it) {
1.903 + return lpx_get_col_stat(lp, col_iter_map[col_it]);
1.904 + }
1.905 + /// \e
1.906 + void printColStatus(int i) {
1.907 + switch (i) {
1.908 + case LPX_BS: cout << "LPX_BS" << endl; break;
1.909 + case LPX_NL: cout << "LPX_NL" << endl; break;
1.910 + case LPX_NU: cout << "LPX_NU" << endl; break;
1.911 + case LPX_NF: cout << "LPX_NF" << endl; break;
1.912 + case LPX_NS: cout << "LPX_NS" << endl; break;
1.913 + }
1.914 + }
1.915 + };
1.916 +
1.917 + /// @}
1.918 +
1.919 +} //namespace lemon
1.920 +
1.921 +#endif //LEMON_LP_SOLVER_WRAPPER_H
2.1 --- a/src/work/marci/lp/lp_solver_wrapper_2.h Mon Jan 31 17:00:12 2005 +0000
2.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
2.3 @@ -1,551 +0,0 @@
2.4 -// -*- c++ -*-
2.5 -#ifndef LEMON_LP_SOLVER_WRAPPER_H
2.6 -#define LEMON_LP_SOLVER_WRAPPER_H
2.7 -
2.8 -///\ingroup misc
2.9 -///\file
2.10 -///\brief Dijkstra algorithm.
2.11 -
2.12 -// #include <stdio.h>
2.13 -#include <stdlib.h>
2.14 -// #include <stdio>
2.15 -//#include <stdlib>
2.16 -extern "C" {
2.17 -#include "glpk.h"
2.18 -}
2.19 -
2.20 -#include <iostream>
2.21 -#include <vector>
2.22 -#include <string>
2.23 -#include <list>
2.24 -#include <memory>
2.25 -#include <utility>
2.26 -
2.27 -//#include <sage_graph.h>
2.28 -//#include <lemon/list_graph.h>
2.29 -//#include <lemon/graph_wrapper.h>
2.30 -#include <lemon/invalid.h>
2.31 -//#include <bfs_dfs.h>
2.32 -//#include <stp.h>
2.33 -//#include <lemon/max_flow.h>
2.34 -//#include <augmenting_flow.h>
2.35 -//#include <iter_map.h>
2.36 -
2.37 -using std::cout;
2.38 -using std::cin;
2.39 -using std::endl;
2.40 -
2.41 -namespace lemon {
2.42 -
2.43 -
2.44 - /// \addtogroup misc
2.45 - /// @{
2.46 -
2.47 - /// \brief A partitioned vector with iterable classes.
2.48 - ///
2.49 - /// This class implements a container in which the data is stored in an
2.50 - /// stl vector, the range is partitioned into sets and each set is
2.51 - /// doubly linked in a list.
2.52 - /// That is, each class is iterable by lemon iterators, and any member of
2.53 - /// the vector can bo moved to an other class.
2.54 - template <typename T>
2.55 - class IterablePartition {
2.56 - protected:
2.57 - struct Node {
2.58 - T data;
2.59 - int prev; //invalid az -1
2.60 - int next;
2.61 - };
2.62 - std::vector<Node> nodes;
2.63 - struct Tip {
2.64 - int first;
2.65 - int last;
2.66 - };
2.67 - std::vector<Tip> tips;
2.68 - public:
2.69 - /// The classes are indexed by integers from \c 0 to \c classNum()-1.
2.70 - int classNum() const { return tips.size(); }
2.71 - /// This lemon style iterator iterates through a class.
2.72 - class ClassIt;
2.73 - /// Constructor. The number of classes is to be given which is fixed
2.74 - /// over the life of the container.
2.75 - /// The partition classes are indexed from 0 to class_num-1.
2.76 - IterablePartition(int class_num) {
2.77 - for (int i=0; i<class_num; ++i) {
2.78 - Tip t;
2.79 - t.first=t.last=-1;
2.80 - tips.push_back(t);
2.81 - }
2.82 - }
2.83 - protected:
2.84 - void befuz(ClassIt it, int class_id) {
2.85 - if (tips[class_id].first==-1) {
2.86 - if (tips[class_id].last==-1) {
2.87 - nodes[it.i].prev=nodes[it.i].next=-1;
2.88 - tips[class_id].first=tips[class_id].last=it.i;
2.89 - }
2.90 - } else {
2.91 - nodes[it.i].prev=tips[class_id].last;
2.92 - nodes[it.i].next=-1;
2.93 - nodes[tips[class_id].last].next=it.i;
2.94 - tips[class_id].last=it.i;
2.95 - }
2.96 - }
2.97 - void kifuz(ClassIt it, int class_id) {
2.98 - if (tips[class_id].first==it.i) {
2.99 - if (tips[class_id].last==it.i) {
2.100 - tips[class_id].first=tips[class_id].last=-1;
2.101 - } else {
2.102 - tips[class_id].first=nodes[it.i].next;
2.103 - nodes[nodes[it.i].next].prev=-1;
2.104 - }
2.105 - } else {
2.106 - if (tips[class_id].last==it.i) {
2.107 - tips[class_id].last=nodes[it.i].prev;
2.108 - nodes[nodes[it.i].prev].next=-1;
2.109 - } else {
2.110 - nodes[nodes[it.i].next].prev=nodes[it.i].prev;
2.111 - nodes[nodes[it.i].prev].next=nodes[it.i].next;
2.112 - }
2.113 - }
2.114 - }
2.115 - public:
2.116 - /// A new element with data \c t is pushed into the vector and into class
2.117 - /// \c class_id.
2.118 - ClassIt push_back(const T& t, int class_id) {
2.119 - Node n;
2.120 - n.data=t;
2.121 - nodes.push_back(n);
2.122 - int i=nodes.size()-1;
2.123 - befuz(i, class_id);
2.124 - return i;
2.125 - }
2.126 - /// A member is moved to an other class.
2.127 - void set(ClassIt it, int old_class_id, int new_class_id) {
2.128 - kifuz(it.i, old_class_id);
2.129 - befuz(it.i, new_class_id);
2.130 - }
2.131 - /// Returns the data pointed by \c it.
2.132 - T& operator[](ClassIt it) { return nodes[it.i].data; }
2.133 - /// Returns the data pointed by \c it.
2.134 - const T& operator[](ClassIt it) const { return nodes[it.i].data; }
2.135 - ///.
2.136 - class ClassIt {
2.137 - friend class IterablePartition;
2.138 - protected:
2.139 - int i;
2.140 - public:
2.141 - /// Default constructor.
2.142 - ClassIt() { }
2.143 - /// This constructor constructs an iterator which points
2.144 - /// to the member of th container indexed by the integer _i.
2.145 - ClassIt(const int& _i) : i(_i) { }
2.146 - /// Invalid constructor.
2.147 - ClassIt(const Invalid&) : i(-1) { }
2.148 - };
2.149 - /// First member of class \c class_id.
2.150 - ClassIt& first(ClassIt& it, int class_id) const {
2.151 - it.i=tips[class_id].first;
2.152 - return it;
2.153 - }
2.154 - /// Next member.
2.155 - ClassIt& next(ClassIt& it) const {
2.156 - it.i=nodes[it.i].next;
2.157 - return it;
2.158 - }
2.159 - /// True iff the iterator is valid.
2.160 - bool valid(const ClassIt& it) const { return it.i!=-1; }
2.161 - };
2.162 -
2.163 - /*! \e
2.164 - */
2.165 - template <typename _Value>
2.166 - class LPSolverBase {
2.167 - public:
2.168 - /// \e
2.169 - typedef _Value Value;
2.170 - /// \e
2.171 - typedef IterablePartition<int>::ClassIt RowIt;
2.172 - /// \e
2.173 - typedef IterablePartition<int>::ClassIt ColIt;
2.174 - protected:
2.175 - /// \e
2.176 - IterablePartition<int> row_iter_map;
2.177 - /// \e
2.178 - IterablePartition<int> col_iter_map;
2.179 - /// \e
2.180 - const int VALID_ID;
2.181 - /// \e
2.182 - const int INVALID_ID;
2.183 - public:
2.184 - /// \e
2.185 - LPSolverBase() : row_iter_map(2),
2.186 - col_iter_map(2),
2.187 - VALID_ID(0), INVALID_ID(1) { }
2.188 - /// \e
2.189 - virtual ~LPSolverBase() { }
2.190 - /// \e
2.191 - virtual void setMinimize() = 0;
2.192 - /// \e
2.193 - virtual void setMaximize() = 0;
2.194 - /// \e
2.195 - virtual RowIt addRow() = 0;
2.196 - /// \e
2.197 - virtual ColIt addCol() = 0;
2.198 - /// temporally, glpk style indexing
2.199 - virtual void setRowCoeffs(RowIt row_it, int num,
2.200 - int* indices, _Value* doubles) = 0;
2.201 - //pair<RowIt, _Value>-bol kell megadni egy std range-et
2.202 - /// \e
2.203 - template <typename Begin, typename End>
2.204 - void setRowCoeffs(RowIt row_it, Begin begin, End end) {
2.205 - int mem_length=1+colNum();
2.206 - int* indices = new int[mem_length];
2.207 - _Value* doubles = new _Value[mem_length];
2.208 - int length=0;
2.209 - for ( ; begin!=end; ++begin) {
2.210 - ++length;
2.211 - indices[length]=col_iter_map[begin->first];
2.212 - doubles[length]=begin->second;
2.213 - }
2.214 - setRowCoeffs(row_it, length, indices, doubles);
2.215 - delete [] indices;
2.216 - delete [] doubles;
2.217 - }
2.218 - /// temporally, glpk style indexing
2.219 - virtual void setColCoeffs(ColIt col_it, int num,
2.220 - int* indices, _Value* doubles) = 0;
2.221 - //pair<ColIt, _Value>-bol kell megadni egy std range-et
2.222 - /// \e
2.223 - template <typename Begin, typename End>
2.224 - void setColCoeffs(ColIt col_it, Begin begin, End end) {
2.225 - int mem_length=1+rowNum();
2.226 - int* indices = new int[mem_length];
2.227 - _Value* doubles = new _Value[mem_length];
2.228 - int length=0;
2.229 - for ( ; begin!=end; ++begin) {
2.230 - ++length;
2.231 - indices[length]=row_iter_map[begin->first];
2.232 - doubles[length]=begin->second;
2.233 - }
2.234 - setColCoeffs(col_it, length, indices, doubles);
2.235 - delete [] indices;
2.236 - delete [] doubles;
2.237 - }
2.238 - /// \e
2.239 - virtual void eraseCol(const ColIt& col_it) = 0;
2.240 - /// \e
2.241 - virtual void eraseRow(const RowIt& row_it) = 0;
2.242 - /// \e
2.243 - virtual void setColBounds(const ColIt& col_it, int bound_type,
2.244 - _Value lo, _Value up) =0;
2.245 - /// \e
2.246 - virtual _Value getObjCoef(const ColIt& col_it) = 0;
2.247 - /// \e
2.248 - virtual void setRowBounds(const RowIt& row_it, int bound_type,
2.249 - _Value lo, _Value up) = 0;
2.250 - /// \e
2.251 - virtual void setObjCoef(const ColIt& col_it, _Value obj_coef) = 0;
2.252 - /// \e
2.253 - virtual void solveSimplex() = 0;
2.254 - /// \e
2.255 - virtual void solvePrimalSimplex() = 0;
2.256 - /// \e
2.257 - virtual void solveDualSimplex() = 0;
2.258 - /// \e
2.259 - virtual _Value getPrimal(const ColIt& col_it) = 0;
2.260 - /// \e
2.261 - virtual _Value getObjVal() = 0;
2.262 - /// \e
2.263 - virtual int rowNum() const = 0;
2.264 - /// \e
2.265 - virtual int colNum() const = 0;
2.266 - /// \e
2.267 - virtual int warmUp() = 0;
2.268 - /// \e
2.269 - virtual void printWarmUpStatus(int i) = 0;
2.270 - /// \e
2.271 - virtual int getPrimalStatus() = 0;
2.272 - /// \e
2.273 - virtual void printPrimalStatus(int i) = 0;
2.274 - /// \e
2.275 - virtual int getDualStatus() = 0;
2.276 - /// \e
2.277 - virtual void printDualStatus(int i) = 0;
2.278 - /// Returns the status of the slack variable assigned to row \c row_it.
2.279 - virtual int getRowStat(const RowIt& row_it) = 0;
2.280 - /// \e
2.281 - virtual void printRowStatus(int i) = 0;
2.282 - /// Returns the status of the variable assigned to column \c col_it.
2.283 - virtual int getColStat(const ColIt& col_it) = 0;
2.284 - /// \e
2.285 - virtual void printColStatus(int i) = 0;
2.286 - };
2.287 -
2.288 -
2.289 - /// \brief Wrappers for LP solvers
2.290 - ///
2.291 - /// This class implements a lemon wrapper for glpk.
2.292 - /// Later other LP-solvers will be wrapped into lemon.
2.293 - /// The aim of this class is to give a general surface to different
2.294 - /// solvers, i.e. it makes possible to write algorithms using LP's,
2.295 - /// in which the solver can be changed to an other one easily.
2.296 - class LPSolverWrapper : public LPSolverBase<double> {
2.297 - public:
2.298 - typedef LPSolverBase<double> Parent;
2.299 -
2.300 - // class Row {
2.301 - // protected:
2.302 - // int i;
2.303 - // public:
2.304 - // Row() { }
2.305 - // Row(const Invalid&) : i(0) { }
2.306 - // Row(const int& _i) : i(_i) { }
2.307 - // operator int() const { return i; }
2.308 - // };
2.309 - // class RowIt : public Row {
2.310 - // public:
2.311 - // RowIt(const Row& row) : Row(row) { }
2.312 - // };
2.313 -
2.314 - // class Col {
2.315 - // protected:
2.316 - // int i;
2.317 - // public:
2.318 - // Col() { }
2.319 - // Col(const Invalid&) : i(0) { }
2.320 - // Col(const int& _i) : i(_i) { }
2.321 - // operator int() const { return i; }
2.322 - // };
2.323 - // class ColIt : public Col {
2.324 - // ColIt(const Col& col) : Col(col) { }
2.325 - // };
2.326 -
2.327 - public:
2.328 - /// \e
2.329 - LPX* lp;
2.330 -
2.331 - public:
2.332 - /// \e
2.333 - LPSolverWrapper() : Parent(),
2.334 - lp(lpx_create_prob()) {
2.335 - lpx_set_int_parm(lp, LPX_K_DUAL, 1);
2.336 - }
2.337 - /// \e
2.338 - ~LPSolverWrapper() {
2.339 - lpx_delete_prob(lp);
2.340 - }
2.341 - /// \e
2.342 - void setMinimize() {
2.343 - lpx_set_obj_dir(lp, LPX_MIN);
2.344 - }
2.345 - /// \e
2.346 - void setMaximize() {
2.347 - lpx_set_obj_dir(lp, LPX_MAX);
2.348 - }
2.349 - /// \e
2.350 - ColIt addCol() {
2.351 - int i=lpx_add_cols(lp, 1);
2.352 - ColIt col_it;
2.353 - col_iter_map.first(col_it, INVALID_ID);
2.354 - if (col_iter_map.valid(col_it)) { //van hasznalhato hely
2.355 - col_iter_map.set(col_it, INVALID_ID, VALID_ID);
2.356 - col_iter_map[col_it]=i;
2.357 - //col_id_to_lp_col_id[col_iter_map[col_it]]=i;
2.358 - } else { //a cucc vegere kell inzertalni mert nincs szabad hely
2.359 - //col_id_to_lp_col_id.push_back(i);
2.360 - //int j=col_id_to_lp_col_id.size()-1;
2.361 - col_it=col_iter_map.push_back(i, VALID_ID);
2.362 - }
2.363 - // edge_index_map.set(e, i);
2.364 - // lpx_set_col_bnds(lp, i, LPX_DB, 0.0, 1.0);
2.365 - // lpx_set_obj_coef(lp, i, cost[e]);
2.366 - return col_it;
2.367 - }
2.368 - /// \e
2.369 - RowIt addRow() {
2.370 - int i=lpx_add_rows(lp, 1);
2.371 - RowIt row_it;
2.372 - row_iter_map.first(row_it, INVALID_ID);
2.373 - if (row_iter_map.valid(row_it)) { //van hasznalhato hely
2.374 - row_iter_map.set(row_it, INVALID_ID, VALID_ID);
2.375 - row_iter_map[row_it]=i;
2.376 - } else { //a cucc vegere kell inzertalni mert nincs szabad hely
2.377 - row_it=row_iter_map.push_back(i, VALID_ID);
2.378 - }
2.379 - return row_it;
2.380 - }
2.381 - using Parent::setRowCoeffs;
2.382 - void setRowCoeffs(RowIt row_it, int length,
2.383 - int* indices, double* doubles) {
2.384 - lpx_set_mat_row(lp, row_iter_map[row_it], length, indices, doubles);
2.385 - }
2.386 - using Parent::setColCoeffs;
2.387 - void setColCoeffs(ColIt col_it, int length,
2.388 - int* indices, double* doubles) {
2.389 - lpx_set_mat_col(lp, col_iter_map[col_it], length, indices, doubles);
2.390 - }
2.391 - // //pair<RowIt, double>-bol kell megadni egy std range-et
2.392 - // /// \e
2.393 - // template <typename Begin, typename End>
2.394 - // void setColCoeffs(const ColIt& col_it,
2.395 - // Begin begin, End end) {
2.396 - // int mem_length=1+lpx_get_num_rows(lp);
2.397 - // int* indices = new int[mem_length];
2.398 - // double* doubles = new double[mem_length];
2.399 - // int length=0;
2.400 - // for ( ; begin!=end; ++begin) {
2.401 - // ++length;
2.402 - // indices[length]=row_iter_map[begin->first];
2.403 - // doubles[length]=begin->second;
2.404 - // }
2.405 - // lpx_set_mat_col(lp, col_iter_map[col_it], length, indices, doubles);
2.406 - // delete [] indices;
2.407 - // delete [] doubles;
2.408 - // }
2.409 - // //pair<ColIt, double>-bol kell megadni egy std range-et
2.410 - // /// \e
2.411 - // template <typename Begin, typename End>
2.412 - // void setRowCoeffs(const RowIt& row_it,
2.413 - // Begin begin, End end) {
2.414 - // int mem_length=1+lpx_get_num_cols(lp);
2.415 - // int* indices = new int[mem_length];
2.416 - // double* doubles = new double[mem_length];
2.417 - // int length=0;
2.418 - // for ( ; begin!=end; ++begin) {
2.419 - // ++length;
2.420 - // indices[length]=col_iter_map[begin->first];
2.421 - // doubles[length]=begin->second;
2.422 - // }
2.423 - // lpx_set_mat_row(lp, row_iter_map[row_it], length, indices, doubles);
2.424 - // delete [] indices;
2.425 - // delete [] doubles;
2.426 - // }
2.427 - /// \e
2.428 - void eraseCol(const ColIt& col_it) {
2.429 - col_iter_map.set(col_it, VALID_ID, INVALID_ID);
2.430 - int cols[2];
2.431 - cols[1]=col_iter_map[col_it];
2.432 - lpx_del_cols(lp, 1, cols);
2.433 - col_iter_map[col_it]=0; //glpk specifikus
2.434 - ColIt it;
2.435 - for (col_iter_map.first(it, VALID_ID);
2.436 - col_iter_map.valid(it); col_iter_map.next(it)) {
2.437 - if (col_iter_map[it]>cols[1]) --col_iter_map[it];
2.438 - }
2.439 - }
2.440 - /// \e
2.441 - void eraseRow(const RowIt& row_it) {
2.442 - row_iter_map.set(row_it, VALID_ID, INVALID_ID);
2.443 - int rows[2];
2.444 - rows[1]=row_iter_map[row_it];
2.445 - lpx_del_rows(lp, 1, rows);
2.446 - row_iter_map[row_it]=0; //glpk specifikus
2.447 - RowIt it;
2.448 - for (row_iter_map.first(it, VALID_ID);
2.449 - row_iter_map.valid(it); row_iter_map.next(it)) {
2.450 - if (row_iter_map[it]>rows[1]) --row_iter_map[it];
2.451 - }
2.452 - }
2.453 - /// \e
2.454 - void setColBounds(const ColIt& col_it, int bound_type,
2.455 - double lo, double up) {
2.456 - lpx_set_col_bnds(lp, col_iter_map[col_it], bound_type, lo, up);
2.457 - }
2.458 - /// \e
2.459 - double getObjCoef(const ColIt& col_it) {
2.460 - return lpx_get_obj_coef(lp, col_iter_map[col_it]);
2.461 - }
2.462 - /// \e
2.463 - void setRowBounds(const RowIt& row_it, int bound_type,
2.464 - double lo, double up) {
2.465 - lpx_set_row_bnds(lp, row_iter_map[row_it], bound_type, lo, up);
2.466 - }
2.467 - /// \e
2.468 - void setObjCoef(const ColIt& col_it, double obj_coef) {
2.469 - lpx_set_obj_coef(lp, col_iter_map[col_it], obj_coef);
2.470 - }
2.471 - /// \e
2.472 - void solveSimplex() { lpx_simplex(lp); }
2.473 - /// \e
2.474 - void solvePrimalSimplex() { lpx_simplex(lp); }
2.475 - /// \e
2.476 - void solveDualSimplex() { lpx_simplex(lp); }
2.477 - /// \e
2.478 - double getPrimal(const ColIt& col_it) {
2.479 - return lpx_get_col_prim(lp, col_iter_map[col_it]);
2.480 - }
2.481 - /// \e
2.482 - double getObjVal() { return lpx_get_obj_val(lp); }
2.483 - /// \e
2.484 - int rowNum() const { return lpx_get_num_rows(lp); }
2.485 - /// \e
2.486 - int colNum() const { return lpx_get_num_cols(lp); }
2.487 - /// \e
2.488 - int warmUp() { return lpx_warm_up(lp); }
2.489 - /// \e
2.490 - void printWarmUpStatus(int i) {
2.491 - switch (i) {
2.492 - case LPX_E_OK: cout << "LPX_E_OK" << endl; break;
2.493 - case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;
2.494 - case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;
2.495 - case LPX_E_SING: cout << "LPX_E_SING" << endl; break;
2.496 - }
2.497 - }
2.498 - /// \e
2.499 - int getPrimalStatus() { return lpx_get_prim_stat(lp); }
2.500 - /// \e
2.501 - void printPrimalStatus(int i) {
2.502 - switch (i) {
2.503 - case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;
2.504 - case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;
2.505 - case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;
2.506 - case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;
2.507 - }
2.508 - }
2.509 - /// \e
2.510 - int getDualStatus() { return lpx_get_dual_stat(lp); }
2.511 - /// \e
2.512 - void printDualStatus(int i) {
2.513 - switch (i) {
2.514 - case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;
2.515 - case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;
2.516 - case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;
2.517 - case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
2.518 - }
2.519 - }
2.520 - /// Returns the status of the slack variable assigned to row \c row_it.
2.521 - int getRowStat(const RowIt& row_it) {
2.522 - return lpx_get_row_stat(lp, row_iter_map[row_it]);
2.523 - }
2.524 - /// \e
2.525 - void printRowStatus(int i) {
2.526 - switch (i) {
2.527 - case LPX_BS: cout << "LPX_BS" << endl; break;
2.528 - case LPX_NL: cout << "LPX_NL" << endl; break;
2.529 - case LPX_NU: cout << "LPX_NU" << endl; break;
2.530 - case LPX_NF: cout << "LPX_NF" << endl; break;
2.531 - case LPX_NS: cout << "LPX_NS" << endl; break;
2.532 - }
2.533 - }
2.534 - /// Returns the status of the variable assigned to column \c col_it.
2.535 - int getColStat(const ColIt& col_it) {
2.536 - return lpx_get_col_stat(lp, col_iter_map[col_it]);
2.537 - }
2.538 - /// \e
2.539 - void printColStatus(int i) {
2.540 - switch (i) {
2.541 - case LPX_BS: cout << "LPX_BS" << endl; break;
2.542 - case LPX_NL: cout << "LPX_NL" << endl; break;
2.543 - case LPX_NU: cout << "LPX_NU" << endl; break;
2.544 - case LPX_NF: cout << "LPX_NF" << endl; break;
2.545 - case LPX_NS: cout << "LPX_NS" << endl; break;
2.546 - }
2.547 - }
2.548 - };
2.549 -
2.550 - /// @}
2.551 -
2.552 -} //namespace lemon
2.553 -
2.554 -#endif //LEMON_LP_SOLVER_WRAPPER_H
3.1 --- a/src/work/marci/lp/lp_solver_wrapper_3.h Mon Jan 31 17:00:12 2005 +0000
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,822 +0,0 @@
3.4 -// -*- c++ -*-
3.5 -#ifndef LEMON_LP_SOLVER_WRAPPER_H
3.6 -#define LEMON_LP_SOLVER_WRAPPER_H
3.7 -
3.8 -///\ingroup misc
3.9 -///\file
3.10 -///\brief Dijkstra algorithm.
3.11 -
3.12 -// #include <stdio.h>
3.13 -#include <stdlib.h>
3.14 -#include <iostream>
3.15 -#include <map>
3.16 -#include <limits>
3.17 -// #include <stdio>
3.18 -//#include <stdlib>
3.19 -extern "C" {
3.20 -#include "glpk.h"
3.21 -}
3.22 -
3.23 -#include <iostream>
3.24 -#include <vector>
3.25 -#include <string>
3.26 -#include <list>
3.27 -#include <memory>
3.28 -#include <utility>
3.29 -
3.30 -//#include <sage_graph.h>
3.31 -//#include <lemon/list_graph.h>
3.32 -//#include <lemon/graph_wrapper.h>
3.33 -#include <lemon/invalid.h>
3.34 -#include <expression.h>
3.35 -//#include <bfs_dfs.h>
3.36 -//#include <stp.h>
3.37 -//#include <lemon/max_flow.h>
3.38 -//#include <augmenting_flow.h>
3.39 -//#include <iter_map.h>
3.40 -
3.41 -using std::cout;
3.42 -using std::cin;
3.43 -using std::endl;
3.44 -
3.45 -namespace lemon {
3.46 -
3.47 - /// \addtogroup misc
3.48 - /// @{
3.49 -
3.50 - /// \brief A partitioned vector with iterable classes.
3.51 - ///
3.52 - /// This class implements a container in which the data is stored in an
3.53 - /// stl vector, the range is partitioned into sets and each set is
3.54 - /// doubly linked in a list.
3.55 - /// That is, each class is iterable by lemon iterators, and any member of
3.56 - /// the vector can bo moved to an other class.
3.57 - template <typename T>
3.58 - class IterablePartition {
3.59 - protected:
3.60 - struct Node {
3.61 - T data;
3.62 - int prev; //invalid az -1
3.63 - int next;
3.64 - };
3.65 - std::vector<Node> nodes;
3.66 - struct Tip {
3.67 - int first;
3.68 - int last;
3.69 - };
3.70 - std::vector<Tip> tips;
3.71 - public:
3.72 - /// The classes are indexed by integers from \c 0 to \c classNum()-1.
3.73 - int classNum() const { return tips.size(); }
3.74 - /// This lemon style iterator iterates through a class.
3.75 - class ClassIt;
3.76 - /// Constructor. The number of classes is to be given which is fixed
3.77 - /// over the life of the container.
3.78 - /// The partition classes are indexed from 0 to class_num-1.
3.79 - IterablePartition(int class_num) {
3.80 - for (int i=0; i<class_num; ++i) {
3.81 - Tip t;
3.82 - t.first=t.last=-1;
3.83 - tips.push_back(t);
3.84 - }
3.85 - }
3.86 - protected:
3.87 - void befuz(ClassIt it, int class_id) {
3.88 - if (tips[class_id].first==-1) {
3.89 - if (tips[class_id].last==-1) {
3.90 - nodes[it.i].prev=nodes[it.i].next=-1;
3.91 - tips[class_id].first=tips[class_id].last=it.i;
3.92 - }
3.93 - } else {
3.94 - nodes[it.i].prev=tips[class_id].last;
3.95 - nodes[it.i].next=-1;
3.96 - nodes[tips[class_id].last].next=it.i;
3.97 - tips[class_id].last=it.i;
3.98 - }
3.99 - }
3.100 - void kifuz(ClassIt it, int class_id) {
3.101 - if (tips[class_id].first==it.i) {
3.102 - if (tips[class_id].last==it.i) {
3.103 - tips[class_id].first=tips[class_id].last=-1;
3.104 - } else {
3.105 - tips[class_id].first=nodes[it.i].next;
3.106 - nodes[nodes[it.i].next].prev=-1;
3.107 - }
3.108 - } else {
3.109 - if (tips[class_id].last==it.i) {
3.110 - tips[class_id].last=nodes[it.i].prev;
3.111 - nodes[nodes[it.i].prev].next=-1;
3.112 - } else {
3.113 - nodes[nodes[it.i].next].prev=nodes[it.i].prev;
3.114 - nodes[nodes[it.i].prev].next=nodes[it.i].next;
3.115 - }
3.116 - }
3.117 - }
3.118 - public:
3.119 - /// A new element with data \c t is pushed into the vector and into class
3.120 - /// \c class_id.
3.121 - ClassIt push_back(const T& t, int class_id) {
3.122 - Node n;
3.123 - n.data=t;
3.124 - nodes.push_back(n);
3.125 - int i=nodes.size()-1;
3.126 - befuz(i, class_id);
3.127 - return i;
3.128 - }
3.129 - /// A member is moved to an other class.
3.130 - void set(ClassIt it, int old_class_id, int new_class_id) {
3.131 - kifuz(it.i, old_class_id);
3.132 - befuz(it.i, new_class_id);
3.133 - }
3.134 - /// Returns the data pointed by \c it.
3.135 - T& operator[](ClassIt it) { return nodes[it.i].data; }
3.136 - /// Returns the data pointed by \c it.
3.137 - const T& operator[](ClassIt it) const { return nodes[it.i].data; }
3.138 - ///.
3.139 - class ClassIt {
3.140 - friend class IterablePartition;
3.141 - protected:
3.142 - int i;
3.143 - public:
3.144 - /// Default constructor.
3.145 - ClassIt() { }
3.146 - /// This constructor constructs an iterator which points
3.147 - /// to the member of th container indexed by the integer _i.
3.148 - ClassIt(const int& _i) : i(_i) { }
3.149 - /// Invalid constructor.
3.150 - ClassIt(const Invalid&) : i(-1) { }
3.151 - friend bool operator<(const ClassIt& x, const ClassIt& y);
3.152 - friend std::ostream& operator<<(std::ostream& os,
3.153 - const ClassIt& it);
3.154 - };
3.155 - friend bool operator<(const ClassIt& x, const ClassIt& y) {
3.156 - return (x.i < y.i);
3.157 - }
3.158 - friend std::ostream& operator<<(std::ostream& os,
3.159 - const ClassIt& it) {
3.160 - os << it.i;
3.161 - return os;
3.162 - }
3.163 - /// First member of class \c class_id.
3.164 - ClassIt& first(ClassIt& it, int class_id) const {
3.165 - it.i=tips[class_id].first;
3.166 - return it;
3.167 - }
3.168 - /// Next member.
3.169 - ClassIt& next(ClassIt& it) const {
3.170 - it.i=nodes[it.i].next;
3.171 - return it;
3.172 - }
3.173 - /// True iff the iterator is valid.
3.174 - bool valid(const ClassIt& it) const { return it.i!=-1; }
3.175 - };
3.176 -
3.177 -
3.178 - /*! \e
3.179 -
3.180 - \todo A[x,y]-t cserel. Jobboldal, baloldal csere.
3.181 - \todo LEKERDEZESEK!!!
3.182 - \todo DOKSI!!!! Doxygen group!!!
3.183 -
3.184 - */
3.185 - template <typename _Value>
3.186 - class LPSolverBase {
3.187 - public:
3.188 - /// \e
3.189 - typedef _Value Value;
3.190 - /// \e
3.191 - typedef IterablePartition<int>::ClassIt RowIt;
3.192 - /// \e
3.193 - typedef IterablePartition<int>::ClassIt ColIt;
3.194 - public:
3.195 - /// \e
3.196 - IterablePartition<int> row_iter_map;
3.197 - /// \e
3.198 - IterablePartition<int> col_iter_map;
3.199 - /// \e
3.200 - const int VALID_CLASS;
3.201 - /// \e
3.202 - const int INVALID_CLASS;
3.203 - /// \e
3.204 - static const _Value INF;
3.205 - public:
3.206 - /// \e
3.207 - LPSolverBase() : row_iter_map(2),
3.208 - col_iter_map(2),
3.209 - VALID_CLASS(0), INVALID_CLASS(1) { }
3.210 - /// \e
3.211 - virtual ~LPSolverBase() { }
3.212 -
3.213 - //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
3.214 -
3.215 - public:
3.216 - /// \e
3.217 - virtual void setMinimize() = 0;
3.218 - /// \e
3.219 - virtual void setMaximize() = 0;
3.220 -
3.221 - //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
3.222 -
3.223 - protected:
3.224 - /// \e
3.225 - virtual int _addRow() = 0;
3.226 - /// \e
3.227 - virtual int _addCol() = 0;
3.228 - /// \e
3.229 - virtual void _setRowCoeffs(int i,
3.230 - const std::vector<std::pair<int, _Value> >& coeffs) = 0;
3.231 - /// \e
3.232 - virtual void _setColCoeffs(int i,
3.233 - const std::vector<std::pair<int, _Value> >& coeffs) = 0;
3.234 - /// \e
3.235 - virtual void _eraseCol(int i) = 0;
3.236 - /// \e
3.237 - virtual void _eraseRow(int i) = 0;
3.238 - public:
3.239 - /// \e
3.240 - enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED };
3.241 - protected:
3.242 - /// \e
3.243 - /// The lower bound of a variable (column) have to be given by an
3.244 - /// extended number of type _Value, i.e. a finite number of type
3.245 - /// _Value or -INF.
3.246 - virtual void _setColLowerBound(int i, _Value value) = 0;
3.247 - /// \e
3.248 - /// The upper bound of a variable (column) have to be given by an
3.249 - /// extended number of type _Value, i.e. a finite number of type
3.250 - /// _Value or INF.
3.251 - virtual void _setColUpperBound(int i, _Value value) = 0;
3.252 - /// \e
3.253 - /// The lower bound of a variable (column) is an
3.254 - /// extended number of type _Value, i.e. a finite number of type
3.255 - /// _Value or -INF.
3.256 - virtual _Value _getColLowerBound(int i) = 0;
3.257 - /// \e
3.258 - /// The upper bound of a variable (column) is an
3.259 - /// extended number of type _Value, i.e. a finite number of type
3.260 - /// _Value or INF.
3.261 - virtual _Value _getColUpperBound(int i) = 0;
3.262 - /// \e
3.263 - virtual void _setColBounds(int i, Bound bound,
3.264 - _Value lo, _Value up) = 0;
3.265 - /// \e
3.266 - virtual void _setRowBounds(int i, Bound bound,
3.267 - _Value lo, _Value up) = 0;
3.268 - /// \e
3.269 - virtual void _setObjCoef(int i, _Value obj_coef) = 0;
3.270 - /// \e
3.271 - virtual _Value _getObjCoef(int i) = 0;
3.272 -
3.273 - //LOW LEVEL, SOLUTION RETRIEVING FUNCTIONS
3.274 -
3.275 - protected:
3.276 - virtual _Value _getPrimal(int i) = 0;
3.277 -
3.278 - //HIGH LEVEL INTERFACE, MATRIX MANIPULATING FUNTIONS
3.279 -
3.280 - public:
3.281 - /// \e
3.282 - RowIt addRow() {
3.283 - int i=_addRow();
3.284 - RowIt row_it;
3.285 - row_iter_map.first(row_it, INVALID_CLASS);
3.286 - if (row_iter_map.valid(row_it)) { //van hasznalhato hely
3.287 - row_iter_map.set(row_it, INVALID_CLASS, VALID_CLASS);
3.288 - row_iter_map[row_it]=i;
3.289 - } else { //a cucc vegere kell inzertalni mert nincs szabad hely
3.290 - row_it=row_iter_map.push_back(i, VALID_CLASS);
3.291 - }
3.292 - return row_it;
3.293 - }
3.294 - /// \e
3.295 - ColIt addCol() {
3.296 - int i=_addCol();
3.297 - ColIt col_it;
3.298 - col_iter_map.first(col_it, INVALID_CLASS);
3.299 - if (col_iter_map.valid(col_it)) { //van hasznalhato hely
3.300 - col_iter_map.set(col_it, INVALID_CLASS, VALID_CLASS);
3.301 - col_iter_map[col_it]=i;
3.302 - } else { //a cucc vegere kell inzertalni mert nincs szabad hely
3.303 - col_it=col_iter_map.push_back(i, VALID_CLASS);
3.304 - }
3.305 - return col_it;
3.306 - }
3.307 - /// \e
3.308 - template <typename Begin, typename End>
3.309 - void setRowCoeffs(RowIt row_it, Begin begin, End end) {
3.310 - std::vector<std::pair<int, double> > coeffs;
3.311 - for ( ; begin!=end; ++begin) {
3.312 - coeffs.push_back(std::
3.313 - make_pair(col_iter_map[begin->first], begin->second));
3.314 - }
3.315 - _setRowCoeffs(row_iter_map[row_it], coeffs);
3.316 - }
3.317 - /// \e
3.318 - template <typename Begin, typename End>
3.319 - void setColCoeffs(ColIt col_it, Begin begin, End end) {
3.320 - std::vector<std::pair<int, double> > coeffs;
3.321 - for ( ; begin!=end; ++begin) {
3.322 - coeffs.push_back(std::
3.323 - make_pair(row_iter_map[begin->first], begin->second));
3.324 - }
3.325 - _setColCoeffs(col_iter_map[col_it], coeffs);
3.326 - }
3.327 - /// \e
3.328 - void eraseCol(const ColIt& col_it) {
3.329 - col_iter_map.set(col_it, VALID_CLASS, INVALID_CLASS);
3.330 - int cols[2];
3.331 - cols[1]=col_iter_map[col_it];
3.332 - _eraseCol(cols[1]);
3.333 - col_iter_map[col_it]=0; //glpk specifikus, de kell ez??
3.334 - ColIt it;
3.335 - for (col_iter_map.first(it, VALID_CLASS);
3.336 - col_iter_map.valid(it); col_iter_map.next(it)) {
3.337 - if (col_iter_map[it]>cols[1]) --col_iter_map[it];
3.338 - }
3.339 - }
3.340 - /// \e
3.341 - void eraseRow(const RowIt& row_it) {
3.342 - row_iter_map.set(row_it, VALID_CLASS, INVALID_CLASS);
3.343 - int rows[2];
3.344 - rows[1]=row_iter_map[row_it];
3.345 - _eraseRow(rows[1]);
3.346 - row_iter_map[row_it]=0; //glpk specifikus, de kell ez??
3.347 - RowIt it;
3.348 - for (row_iter_map.first(it, VALID_CLASS);
3.349 - row_iter_map.valid(it); row_iter_map.next(it)) {
3.350 - if (row_iter_map[it]>rows[1]) --row_iter_map[it];
3.351 - }
3.352 - }
3.353 - /// \e
3.354 - void setColLowerBound(ColIt col_it, _Value lo) {
3.355 - _setColLowerBound(col_iter_map[col_it], lo);
3.356 - }
3.357 - /// \e
3.358 - void setColUpperBound(ColIt col_it, _Value up) {
3.359 - _setColUpperBound(col_iter_map[col_it], up);
3.360 - }
3.361 - /// \e
3.362 - _Value getColLowerBound(ColIt col_it) {
3.363 - return _getColLowerBound(col_iter_map[col_it]);
3.364 - }
3.365 - /// \e
3.366 - _Value getColUpperBound(ColIt col_it) {
3.367 - return _getColUpperBound(col_iter_map[col_it]);
3.368 - }
3.369 - /// \e
3.370 - void setColBounds(const ColIt& col_it, Bound bound,
3.371 - _Value lo, _Value up) {
3.372 - _setColBounds(col_iter_map[col_it], bound, lo, up);
3.373 - }
3.374 - /// \e
3.375 - void setRowBounds(const RowIt& row_it, Bound bound,
3.376 - _Value lo, _Value up) {
3.377 - _setRowBounds(row_iter_map[row_it], bound, lo, up);
3.378 - }
3.379 - /// \e
3.380 - void setObjCoef(const ColIt& col_it, _Value obj_coef) {
3.381 - _setObjCoef(col_iter_map[col_it], obj_coef);
3.382 - }
3.383 - /// \e
3.384 - _Value getObjCoef(const ColIt& col_it) {
3.385 - return _getObjCoef(col_iter_map[col_it]);
3.386 - }
3.387 -
3.388 - //MOST HIGH LEVEL, USER FRIEND FUNCTIONS
3.389 -
3.390 - /// \e
3.391 - typedef Expr<ColIt, _Value> Expression;
3.392 - /// \e
3.393 - typedef Expr<RowIt, _Value> DualExpression;
3.394 - /// \e
3.395 - void setRowCoeffs(RowIt row_it, const Expression& expr) {
3.396 - std::vector<std::pair<int, _Value> > row_coeffs;
3.397 - for(typename Expression::Data::const_iterator i=expr.data.begin();
3.398 - i!=expr.data.end(); ++i) {
3.399 - row_coeffs.push_back(std::make_pair
3.400 - (col_iter_map[(*i).first], (*i).second));
3.401 - }
3.402 - _setRowCoeffs(row_iter_map[row_it], row_coeffs);
3.403 - }
3.404 - /// \e
3.405 - void setColCoeffs(ColIt col_it, const DualExpression& expr) {
3.406 - std::vector<std::pair<int, _Value> > col_coeffs;
3.407 - for(typename DualExpression::Data::const_iterator i=expr.data.begin();
3.408 - i!=expr.data.end(); ++i) {
3.409 - col_coeffs.push_back(std::make_pair
3.410 - (row_iter_map[(*i).first], (*i).second));
3.411 - }
3.412 - _setColCoeffs(col_iter_map[col_it], col_coeffs);
3.413 - }
3.414 - /// \e
3.415 - void setObjCoeffs(const Expression& expr) {
3.416 - for(typename Expression::Data::const_iterator i=expr.data.begin();
3.417 - i!=expr.data.end(); ++i) {
3.418 - setObjCoef((*i).first, (*i).second);
3.419 - }
3.420 - }
3.421 - //SOLVER FUNCTIONS
3.422 -
3.423 - /// \e
3.424 - virtual void solveSimplex() = 0;
3.425 - /// \e
3.426 - virtual void solvePrimalSimplex() = 0;
3.427 - /// \e
3.428 - virtual void solveDualSimplex() = 0;
3.429 - /// \e
3.430 -
3.431 - //HIGH LEVEL, SOLUTION RETRIEVING FUNCTIONS
3.432 -
3.433 - public:
3.434 - _Value getPrimal(const ColIt& col_it) {
3.435 - return _getPrimal(col_iter_map[col_it]);
3.436 - }
3.437 - /// \e
3.438 - virtual _Value getObjVal() = 0;
3.439 -
3.440 - //OTHER FUNCTIONS
3.441 -
3.442 - /// \e
3.443 - virtual int rowNum() const = 0;
3.444 - /// \e
3.445 - virtual int colNum() const = 0;
3.446 - /// \e
3.447 - virtual int warmUp() = 0;
3.448 - /// \e
3.449 - virtual void printWarmUpStatus(int i) = 0;
3.450 - /// \e
3.451 - virtual int getPrimalStatus() = 0;
3.452 - /// \e
3.453 - virtual void printPrimalStatus(int i) = 0;
3.454 - /// \e
3.455 - virtual int getDualStatus() = 0;
3.456 - /// \e
3.457 - virtual void printDualStatus(int i) = 0;
3.458 - /// Returns the status of the slack variable assigned to row \c row_it.
3.459 - virtual int getRowStat(const RowIt& row_it) = 0;
3.460 - /// \e
3.461 - virtual void printRowStatus(int i) = 0;
3.462 - /// Returns the status of the variable assigned to column \c col_it.
3.463 - virtual int getColStat(const ColIt& col_it) = 0;
3.464 - /// \e
3.465 - virtual void printColStatus(int i) = 0;
3.466 - };
3.467 -
3.468 - template <typename _Value>
3.469 - const _Value LPSolverBase<_Value>::INF=std::numeric_limits<_Value>::infinity();
3.470 -
3.471 -
3.472 - /// \brief Wrappers for LP solvers
3.473 - ///
3.474 - /// This class implements a lemon wrapper for glpk.
3.475 - /// Later other LP-solvers will be wrapped into lemon.
3.476 - /// The aim of this class is to give a general surface to different
3.477 - /// solvers, i.e. it makes possible to write algorithms using LP's,
3.478 - /// in which the solver can be changed to an other one easily.
3.479 - class LPGLPK : public LPSolverBase<double> {
3.480 - public:
3.481 - typedef LPSolverBase<double> Parent;
3.482 -
3.483 - public:
3.484 - /// \e
3.485 - LPX* lp;
3.486 -
3.487 - public:
3.488 - /// \e
3.489 - LPGLPK() : Parent(),
3.490 - lp(lpx_create_prob()) {
3.491 - lpx_set_int_parm(lp, LPX_K_DUAL, 1);
3.492 - }
3.493 - /// \e
3.494 - ~LPGLPK() {
3.495 - lpx_delete_prob(lp);
3.496 - }
3.497 -
3.498 - //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
3.499 -
3.500 - /// \e
3.501 - void setMinimize() {
3.502 - lpx_set_obj_dir(lp, LPX_MIN);
3.503 - }
3.504 - /// \e
3.505 - void setMaximize() {
3.506 - lpx_set_obj_dir(lp, LPX_MAX);
3.507 - }
3.508 -
3.509 - //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
3.510 -
3.511 - protected:
3.512 - /// \e
3.513 - int _addCol() {
3.514 - int i=lpx_add_cols(lp, 1);
3.515 - _setColLowerBound(i, -INF);
3.516 - _setColUpperBound(i, INF);
3.517 - return i;
3.518 - }
3.519 - /// \e
3.520 - int _addRow() {
3.521 - int i=lpx_add_rows(lp, 1);
3.522 - return i;
3.523 - }
3.524 - /// \e
3.525 - virtual void _setRowCoeffs(int i,
3.526 - const std::vector<std::pair<int, double> >& coeffs) {
3.527 - int mem_length=1+colNum();
3.528 - int* indices = new int[mem_length];
3.529 - double* doubles = new double[mem_length];
3.530 - int length=0;
3.531 - for (std::vector<std::pair<int, double> >::
3.532 - const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
3.533 - ++length;
3.534 - indices[length]=it->first;
3.535 - doubles[length]=it->second;
3.536 -// std::cout << " " << indices[length] << " "
3.537 -// << doubles[length] << std::endl;
3.538 - }
3.539 -// std::cout << i << " " << length << std::endl;
3.540 - lpx_set_mat_row(lp, i, length, indices, doubles);
3.541 - delete [] indices;
3.542 - delete [] doubles;
3.543 - }
3.544 - /// \e
3.545 - virtual void _setColCoeffs(int i,
3.546 - const std::vector<std::pair<int, double> >& coeffs) {
3.547 - int mem_length=1+rowNum();
3.548 - int* indices = new int[mem_length];
3.549 - double* doubles = new double[mem_length];
3.550 - int length=0;
3.551 - for (std::vector<std::pair<int, double> >::
3.552 - const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
3.553 - ++length;
3.554 - indices[length]=it->first;
3.555 - doubles[length]=it->second;
3.556 - }
3.557 - lpx_set_mat_col(lp, i, length, indices, doubles);
3.558 - delete [] indices;
3.559 - delete [] doubles;
3.560 - }
3.561 - /// \e
3.562 - virtual void _eraseCol(int i) {
3.563 - int cols[2];
3.564 - cols[1]=i;
3.565 - lpx_del_cols(lp, 1, cols);
3.566 - }
3.567 - virtual void _eraseRow(int i) {
3.568 - int rows[2];
3.569 - rows[1]=i;
3.570 - lpx_del_rows(lp, 1, rows);
3.571 - }
3.572 - virtual void _setColLowerBound(int i, double lo) {
3.573 - if (lo==INF) {
3.574 - //FIXME error
3.575 - }
3.576 - int b=lpx_get_col_type(lp, i);
3.577 - double up=lpx_get_col_ub(lp, i);
3.578 - if (lo==-INF) {
3.579 - switch (b) {
3.580 - case LPX_FR:
3.581 - case LPX_LO:
3.582 - lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
3.583 - break;
3.584 - case LPX_UP:
3.585 - break;
3.586 - case LPX_DB:
3.587 - case LPX_FX:
3.588 - lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
3.589 - break;
3.590 - default: ;
3.591 - //FIXME error
3.592 - }
3.593 - } else {
3.594 - switch (b) {
3.595 - case LPX_FR:
3.596 - case LPX_LO:
3.597 - lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
3.598 - break;
3.599 - case LPX_UP:
3.600 - case LPX_DB:
3.601 - case LPX_FX:
3.602 - if (lo==up)
3.603 - lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
3.604 - else
3.605 - lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
3.606 - break;
3.607 - default: ;
3.608 - //FIXME error
3.609 - }
3.610 - }
3.611 - }
3.612 - virtual void _setColUpperBound(int i, double up) {
3.613 - if (up==-INF) {
3.614 - //FIXME error
3.615 - }
3.616 - int b=lpx_get_col_type(lp, i);
3.617 - double lo=lpx_get_col_lb(lp, i);
3.618 - if (up==INF) {
3.619 - switch (b) {
3.620 - case LPX_FR:
3.621 - case LPX_LO:
3.622 - break;
3.623 - case LPX_UP:
3.624 - lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
3.625 - break;
3.626 - case LPX_DB:
3.627 - case LPX_FX:
3.628 - lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
3.629 - break;
3.630 - default: ;
3.631 - //FIXME error
3.632 - }
3.633 - } else {
3.634 - switch (b) {
3.635 - case LPX_FR:
3.636 - lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
3.637 - case LPX_LO:
3.638 - if (lo==up)
3.639 - lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
3.640 - else
3.641 - lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
3.642 - break;
3.643 - case LPX_UP:
3.644 - lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
3.645 - break;
3.646 - case LPX_DB:
3.647 - case LPX_FX:
3.648 - if (lo==up)
3.649 - lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
3.650 - else
3.651 - lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
3.652 - break;
3.653 - default: ;
3.654 - //FIXME error
3.655 - }
3.656 - }
3.657 - }
3.658 - virtual double _getColLowerBound(int i) {
3.659 - int b=lpx_get_col_type(lp, i);
3.660 - switch (b) {
3.661 - case LPX_FR:
3.662 - return -INF;
3.663 - case LPX_LO:
3.664 - return lpx_get_col_lb(lp, i);
3.665 - case LPX_UP:
3.666 - return -INF;
3.667 - case LPX_DB:
3.668 - case LPX_FX:
3.669 - return lpx_get_col_lb(lp, i);
3.670 - default: ;
3.671 - //FIXME error
3.672 - return 0.0;
3.673 - }
3.674 - }
3.675 - virtual double _getColUpperBound(int i) {
3.676 - int b=lpx_get_col_type(lp, i);
3.677 - switch (b) {
3.678 - case LPX_FR:
3.679 - case LPX_LO:
3.680 - return INF;
3.681 - case LPX_UP:
3.682 - case LPX_DB:
3.683 - case LPX_FX:
3.684 - return lpx_get_col_ub(lp, i);
3.685 - default: ;
3.686 - //FIXME error
3.687 - return 0.0;
3.688 - }
3.689 - }
3.690 - virtual void _setColBounds(int i, Bound bound,
3.691 - double lo, double up) {
3.692 - switch (bound) {
3.693 - case FREE:
3.694 - lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
3.695 - break;
3.696 - case LOWER:
3.697 - lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
3.698 - break;
3.699 - case UPPER:
3.700 - lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
3.701 - break;
3.702 - case DOUBLE:
3.703 - lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
3.704 - break;
3.705 - case FIXED:
3.706 - lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
3.707 - break;
3.708 - }
3.709 - }
3.710 - virtual void _setRowBounds(int i, Bound bound,
3.711 - double lo, double up) {
3.712 - switch (bound) {
3.713 - case FREE:
3.714 - lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
3.715 - break;
3.716 - case LOWER:
3.717 - lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
3.718 - break;
3.719 - case UPPER:
3.720 - lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
3.721 - break;
3.722 - case DOUBLE:
3.723 - lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
3.724 - break;
3.725 - case FIXED:
3.726 - lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
3.727 - break;
3.728 - }
3.729 - }
3.730 - protected:
3.731 - /// \e
3.732 - virtual double _getObjCoef(int i) {
3.733 - return lpx_get_obj_coef(lp, i);
3.734 - }
3.735 - /// \e
3.736 - virtual void _setObjCoef(int i, double obj_coef) {
3.737 - lpx_set_obj_coef(lp, i, obj_coef);
3.738 - }
3.739 - public:
3.740 - /// \e
3.741 - void solveSimplex() { lpx_simplex(lp); }
3.742 - /// \e
3.743 - void solvePrimalSimplex() { lpx_simplex(lp); }
3.744 - /// \e
3.745 - void solveDualSimplex() { lpx_simplex(lp); }
3.746 - /// \e
3.747 - protected:
3.748 - virtual double _getPrimal(int i) {
3.749 - return lpx_get_col_prim(lp, i);
3.750 - }
3.751 - public:
3.752 - /// \e
3.753 - double getObjVal() { return lpx_get_obj_val(lp); }
3.754 - /// \e
3.755 - int rowNum() const { return lpx_get_num_rows(lp); }
3.756 - /// \e
3.757 - int colNum() const { return lpx_get_num_cols(lp); }
3.758 - /// \e
3.759 - int warmUp() { return lpx_warm_up(lp); }
3.760 - /// \e
3.761 - void printWarmUpStatus(int i) {
3.762 - switch (i) {
3.763 - case LPX_E_OK: cout << "LPX_E_OK" << endl; break;
3.764 - case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;
3.765 - case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;
3.766 - case LPX_E_SING: cout << "LPX_E_SING" << endl; break;
3.767 - }
3.768 - }
3.769 - /// \e
3.770 - int getPrimalStatus() { return lpx_get_prim_stat(lp); }
3.771 - /// \e
3.772 - void printPrimalStatus(int i) {
3.773 - switch (i) {
3.774 - case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;
3.775 - case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;
3.776 - case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;
3.777 - case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;
3.778 - }
3.779 - }
3.780 - /// \e
3.781 - int getDualStatus() { return lpx_get_dual_stat(lp); }
3.782 - /// \e
3.783 - void printDualStatus(int i) {
3.784 - switch (i) {
3.785 - case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;
3.786 - case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;
3.787 - case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;
3.788 - case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
3.789 - }
3.790 - }
3.791 - /// Returns the status of the slack variable assigned to row \c row_it.
3.792 - int getRowStat(const RowIt& row_it) {
3.793 - return lpx_get_row_stat(lp, row_iter_map[row_it]);
3.794 - }
3.795 - /// \e
3.796 - void printRowStatus(int i) {
3.797 - switch (i) {
3.798 - case LPX_BS: cout << "LPX_BS" << endl; break;
3.799 - case LPX_NL: cout << "LPX_NL" << endl; break;
3.800 - case LPX_NU: cout << "LPX_NU" << endl; break;
3.801 - case LPX_NF: cout << "LPX_NF" << endl; break;
3.802 - case LPX_NS: cout << "LPX_NS" << endl; break;
3.803 - }
3.804 - }
3.805 - /// Returns the status of the variable assigned to column \c col_it.
3.806 - int getColStat(const ColIt& col_it) {
3.807 - return lpx_get_col_stat(lp, col_iter_map[col_it]);
3.808 - }
3.809 - /// \e
3.810 - void printColStatus(int i) {
3.811 - switch (i) {
3.812 - case LPX_BS: cout << "LPX_BS" << endl; break;
3.813 - case LPX_NL: cout << "LPX_NL" << endl; break;
3.814 - case LPX_NU: cout << "LPX_NU" << endl; break;
3.815 - case LPX_NF: cout << "LPX_NF" << endl; break;
3.816 - case LPX_NS: cout << "LPX_NS" << endl; break;
3.817 - }
3.818 - }
3.819 - };
3.820 -
3.821 - /// @}
3.822 -
3.823 -} //namespace lemon
3.824 -
3.825 -#endif //LEMON_LP_SOLVER_WRAPPER_H
4.1 --- a/src/work/marci/lp/max_flow_expression.cc Mon Jan 31 17:00:12 2005 +0000
4.2 +++ b/src/work/marci/lp/max_flow_expression.cc Tue Feb 01 12:53:30 2005 +0000
4.3 @@ -6,7 +6,7 @@
4.4 #include <lemon/list_graph.h>
4.5 #include <lemon/dimacs.h>
4.6 #include <lemon/time_measure.h>
4.7 -#include <lp_solver_wrapper_3.h>
4.8 +#include <lp_solver_base.h>
4.9
4.10 using std::cout;
4.11 using std::endl;
4.12 @@ -51,15 +51,15 @@
4.13 EdgeIndexMap edge_index_map(g);
4.14 PrimalMap<Edge, EdgeIndexMap> flow(lp, edge_index_map);
4.15
4.16 - // capacity function
4.17 + // nonnegativity of flow and capacity function
4.18 for (Graph::EdgeIt e(g); e!=INVALID; ++e) {
4.19 ColIt col_it=lp.addCol();
4.20 edge_index_map.set(e, col_it);
4.21 // interesting property in GLPK:
4.22 // if you change the order of the following two lines, the
4.23 // two runs of GLPK are extremely different
4.24 + lp.setColLowerBound(col_it, 0);
4.25 lp.setColUpperBound(col_it, cap[e]);
4.26 - lp.setColLowerBound(col_it, 0);
4.27 }
4.28
4.29 for (Graph::NodeIt n(g); n!=INVALID; ++n) {
4.30 @@ -72,11 +72,12 @@
4.31 if (n==s) {
4.32 lp.setObjCoeffs(expr);
4.33 }
4.34 - // flow conservation
4.35 + // flow conservation constraints
4.36 if ((n!=s) && (n!=t)) {
4.37 RowIt row_it=lp.addRow();
4.38 lp.setRowCoeffs(row_it, expr);
4.39 - lp.setRowBounds(row_it, LPSolver::FIXED, 0.0, 0.0);
4.40 + lp.setRowLowerBound(row_it, 0.0);
4.41 + lp.setRowUpperBound(row_it, 0.0);
4.42 }
4.43 }
4.44 lp.solveSimplex();