[1031] | 1 | // -*- c++ -*- |
---|
[1152] | 2 | #ifndef LEMON_LP_SOLVER_BASE_H |
---|
| 3 | #define LEMON_LP_SOLVER_BASE_H |
---|
[1031] | 4 | |
---|
| 5 | ///\ingroup misc |
---|
| 6 | ///\file |
---|
| 7 | |
---|
| 8 | // #include <stdio.h> |
---|
| 9 | #include <stdlib.h> |
---|
[1097] | 10 | #include <iostream> |
---|
| 11 | #include <map> |
---|
[1104] | 12 | #include <limits> |
---|
[1031] | 13 | // #include <stdio> |
---|
| 14 | //#include <stdlib> |
---|
| 15 | extern "C" { |
---|
| 16 | #include "glpk.h" |
---|
| 17 | } |
---|
| 18 | |
---|
| 19 | #include <iostream> |
---|
| 20 | #include <vector> |
---|
| 21 | #include <string> |
---|
| 22 | #include <list> |
---|
| 23 | #include <memory> |
---|
| 24 | #include <utility> |
---|
| 25 | |
---|
| 26 | #include <lemon/invalid.h> |
---|
[1099] | 27 | #include <expression.h> |
---|
[1031] | 28 | //#include <stp.h> |
---|
| 29 | //#include <lemon/max_flow.h> |
---|
| 30 | //#include <augmenting_flow.h> |
---|
| 31 | //#include <iter_map.h> |
---|
| 32 | |
---|
| 33 | using std::cout; |
---|
| 34 | using std::cin; |
---|
| 35 | using std::endl; |
---|
| 36 | |
---|
| 37 | namespace lemon { |
---|
| 38 | |
---|
| 39 | /// \addtogroup misc |
---|
| 40 | /// @{ |
---|
| 41 | |
---|
| 42 | /// \brief A partitioned vector with iterable classes. |
---|
| 43 | /// |
---|
| 44 | /// This class implements a container in which the data is stored in an |
---|
| 45 | /// stl vector, the range is partitioned into sets and each set is |
---|
| 46 | /// doubly linked in a list. |
---|
| 47 | /// That is, each class is iterable by lemon iterators, and any member of |
---|
| 48 | /// the vector can bo moved to an other class. |
---|
| 49 | template <typename T> |
---|
| 50 | class IterablePartition { |
---|
| 51 | protected: |
---|
| 52 | struct Node { |
---|
| 53 | T data; |
---|
| 54 | int prev; //invalid az -1 |
---|
| 55 | int next; |
---|
| 56 | }; |
---|
| 57 | std::vector<Node> nodes; |
---|
| 58 | struct Tip { |
---|
| 59 | int first; |
---|
| 60 | int last; |
---|
| 61 | }; |
---|
| 62 | std::vector<Tip> tips; |
---|
| 63 | public: |
---|
| 64 | /// The classes are indexed by integers from \c 0 to \c classNum()-1. |
---|
| 65 | int classNum() const { return tips.size(); } |
---|
| 66 | /// This lemon style iterator iterates through a class. |
---|
[1152] | 67 | class Class; |
---|
[1031] | 68 | /// Constructor. The number of classes is to be given which is fixed |
---|
| 69 | /// over the life of the container. |
---|
| 70 | /// The partition classes are indexed from 0 to class_num-1. |
---|
| 71 | IterablePartition(int class_num) { |
---|
| 72 | for (int i=0; i<class_num; ++i) { |
---|
| 73 | Tip t; |
---|
| 74 | t.first=t.last=-1; |
---|
| 75 | tips.push_back(t); |
---|
| 76 | } |
---|
| 77 | } |
---|
| 78 | protected: |
---|
[1152] | 79 | void befuz(Class it, int class_id) { |
---|
[1031] | 80 | if (tips[class_id].first==-1) { |
---|
| 81 | if (tips[class_id].last==-1) { |
---|
| 82 | nodes[it.i].prev=nodes[it.i].next=-1; |
---|
| 83 | tips[class_id].first=tips[class_id].last=it.i; |
---|
| 84 | } |
---|
| 85 | } else { |
---|
| 86 | nodes[it.i].prev=tips[class_id].last; |
---|
| 87 | nodes[it.i].next=-1; |
---|
| 88 | nodes[tips[class_id].last].next=it.i; |
---|
| 89 | tips[class_id].last=it.i; |
---|
| 90 | } |
---|
| 91 | } |
---|
[1152] | 92 | void kifuz(Class it, int class_id) { |
---|
[1031] | 93 | if (tips[class_id].first==it.i) { |
---|
| 94 | if (tips[class_id].last==it.i) { |
---|
| 95 | tips[class_id].first=tips[class_id].last=-1; |
---|
| 96 | } else { |
---|
| 97 | tips[class_id].first=nodes[it.i].next; |
---|
| 98 | nodes[nodes[it.i].next].prev=-1; |
---|
| 99 | } |
---|
| 100 | } else { |
---|
| 101 | if (tips[class_id].last==it.i) { |
---|
| 102 | tips[class_id].last=nodes[it.i].prev; |
---|
| 103 | nodes[nodes[it.i].prev].next=-1; |
---|
| 104 | } else { |
---|
| 105 | nodes[nodes[it.i].next].prev=nodes[it.i].prev; |
---|
| 106 | nodes[nodes[it.i].prev].next=nodes[it.i].next; |
---|
| 107 | } |
---|
| 108 | } |
---|
| 109 | } |
---|
| 110 | public: |
---|
| 111 | /// A new element with data \c t is pushed into the vector and into class |
---|
| 112 | /// \c class_id. |
---|
[1152] | 113 | Class push_back(const T& t, int class_id) { |
---|
[1031] | 114 | Node n; |
---|
| 115 | n.data=t; |
---|
| 116 | nodes.push_back(n); |
---|
| 117 | int i=nodes.size()-1; |
---|
| 118 | befuz(i, class_id); |
---|
| 119 | return i; |
---|
| 120 | } |
---|
| 121 | /// A member is moved to an other class. |
---|
[1152] | 122 | void set(Class it, int old_class_id, int new_class_id) { |
---|
[1031] | 123 | kifuz(it.i, old_class_id); |
---|
| 124 | befuz(it.i, new_class_id); |
---|
| 125 | } |
---|
| 126 | /// Returns the data pointed by \c it. |
---|
[1152] | 127 | T& operator[](Class it) { return nodes[it.i].data; } |
---|
[1031] | 128 | /// Returns the data pointed by \c it. |
---|
[1152] | 129 | const T& operator[](Class it) const { return nodes[it.i].data; } |
---|
[1031] | 130 | ///. |
---|
[1152] | 131 | class Class { |
---|
[1031] | 132 | friend class IterablePartition; |
---|
| 133 | protected: |
---|
| 134 | int i; |
---|
| 135 | public: |
---|
| 136 | /// Default constructor. |
---|
[1152] | 137 | Class() { } |
---|
[1031] | 138 | /// This constructor constructs an iterator which points |
---|
| 139 | /// to the member of th container indexed by the integer _i. |
---|
[1152] | 140 | Class(const int& _i) : i(_i) { } |
---|
[1031] | 141 | /// Invalid constructor. |
---|
[1152] | 142 | Class(const Invalid&) : i(-1) { } |
---|
| 143 | friend bool operator<(const Class& x, const Class& y); |
---|
[1099] | 144 | friend std::ostream& operator<<(std::ostream& os, |
---|
[1152] | 145 | const Class& it); |
---|
| 146 | bool operator==(const Class& node) const {return i == node.i;} |
---|
| 147 | bool operator!=(const Class& node) const {return i != node.i;} |
---|
[1031] | 148 | }; |
---|
[1152] | 149 | friend bool operator<(const Class& x, const Class& y) { |
---|
[1099] | 150 | return (x.i < y.i); |
---|
| 151 | } |
---|
| 152 | friend std::ostream& operator<<(std::ostream& os, |
---|
[1152] | 153 | const Class& it) { |
---|
[1099] | 154 | os << it.i; |
---|
| 155 | return os; |
---|
| 156 | } |
---|
[1031] | 157 | /// First member of class \c class_id. |
---|
[1152] | 158 | Class& first(Class& it, int class_id) const { |
---|
[1031] | 159 | it.i=tips[class_id].first; |
---|
| 160 | return it; |
---|
| 161 | } |
---|
| 162 | /// Next member. |
---|
[1152] | 163 | Class& next(Class& it) const { |
---|
[1031] | 164 | it.i=nodes[it.i].next; |
---|
| 165 | return it; |
---|
| 166 | } |
---|
| 167 | /// True iff the iterator is valid. |
---|
[1152] | 168 | bool valid(const Class& it) const { return it.i!=-1; } |
---|
| 169 | |
---|
| 170 | class ClassIt : public Class { |
---|
| 171 | const IterablePartition* iterable_partition; |
---|
| 172 | public: |
---|
| 173 | ClassIt() { } |
---|
| 174 | ClassIt(Invalid i) : Class(i) { } |
---|
| 175 | ClassIt(const IterablePartition& _iterable_partition, |
---|
| 176 | const int& i) : iterable_partition(&_iterable_partition) { |
---|
| 177 | _iterable_partition.first(*this, i); |
---|
| 178 | } |
---|
| 179 | ClassIt(const IterablePartition& _iterable_partition, |
---|
| 180 | const Class& _class) : |
---|
| 181 | Class(_class), iterable_partition(&_iterable_partition) { } |
---|
| 182 | ClassIt& operator++() { |
---|
| 183 | iterable_partition->next(*this); |
---|
| 184 | return *this; |
---|
| 185 | } |
---|
| 186 | }; |
---|
| 187 | |
---|
[1031] | 188 | }; |
---|
| 189 | |
---|
[1097] | 190 | |
---|
[1031] | 191 | /*! \e |
---|
[1143] | 192 | \todo kellenene uj iterable structure bele, mert ez nem az igazi |
---|
[1111] | 193 | \todo A[x,y]-t cserel. Jobboldal, baloldal csere. |
---|
| 194 | \todo LEKERDEZESEK!!! |
---|
| 195 | \todo DOKSI!!!! Doxygen group!!! |
---|
| 196 | The aim of this class is to give a general surface to different |
---|
| 197 | solvers, i.e. it makes possible to write algorithms using LP's, |
---|
| 198 | in which the solver can be changed to an other one easily. |
---|
[1112] | 199 | \nosubgrouping |
---|
[1111] | 200 | */ |
---|
[1048] | 201 | template <typename _Value> |
---|
[1031] | 202 | class LPSolverBase { |
---|
[1112] | 203 | |
---|
[1113] | 204 | /*! @name Uncategorized functions and types (public members) |
---|
[1112] | 205 | */ |
---|
| 206 | //@{ |
---|
[1031] | 207 | public: |
---|
[1112] | 208 | |
---|
| 209 | //UNCATEGORIZED |
---|
| 210 | |
---|
[1031] | 211 | /// \e |
---|
[1152] | 212 | typedef IterablePartition<int> Rows; |
---|
| 213 | /// \e |
---|
| 214 | typedef IterablePartition<int> Cols; |
---|
| 215 | /// \e |
---|
[1048] | 216 | typedef _Value Value; |
---|
| 217 | /// \e |
---|
[1152] | 218 | typedef Rows::Class Row; |
---|
[1031] | 219 | /// \e |
---|
[1152] | 220 | typedef Cols::Class Col; |
---|
[1074] | 221 | public: |
---|
[1031] | 222 | /// \e |
---|
| 223 | IterablePartition<int> row_iter_map; |
---|
| 224 | /// \e |
---|
| 225 | IterablePartition<int> col_iter_map; |
---|
| 226 | /// \e |
---|
[1144] | 227 | std::vector<Row> int_row_map; |
---|
[1143] | 228 | /// \e |
---|
[1144] | 229 | std::vector<Col> int_col_map; |
---|
[1143] | 230 | /// \e |
---|
[1074] | 231 | const int VALID_CLASS; |
---|
[1031] | 232 | /// \e |
---|
[1074] | 233 | const int INVALID_CLASS; |
---|
[1104] | 234 | /// \e |
---|
| 235 | static const _Value INF; |
---|
[1031] | 236 | public: |
---|
| 237 | /// \e |
---|
| 238 | LPSolverBase() : row_iter_map(2), |
---|
| 239 | col_iter_map(2), |
---|
[1074] | 240 | VALID_CLASS(0), INVALID_CLASS(1) { } |
---|
[1031] | 241 | /// \e |
---|
| 242 | virtual ~LPSolverBase() { } |
---|
[1112] | 243 | //@} |
---|
[1081] | 244 | |
---|
[1112] | 245 | /*! @name Medium level interface (public members) |
---|
| 246 | These functions appear in the low level and also in the high level |
---|
| 247 | interfaces thus these each of these functions have to be implemented |
---|
| 248 | only once in the different interfaces. |
---|
| 249 | This means that these functions have to be reimplemented for all of the |
---|
| 250 | different lp solvers. These are basic functions, and have the same |
---|
| 251 | parameter lists in the low and high level interfaces. |
---|
| 252 | */ |
---|
| 253 | //@{ |
---|
| 254 | public: |
---|
[1081] | 255 | |
---|
[1112] | 256 | //UNCATEGORIZED FUNCTIONS |
---|
| 257 | |
---|
[1031] | 258 | /// \e |
---|
| 259 | virtual void setMinimize() = 0; |
---|
| 260 | /// \e |
---|
| 261 | virtual void setMaximize() = 0; |
---|
[1081] | 262 | |
---|
[1112] | 263 | //SOLVER FUNCTIONS |
---|
[1081] | 264 | |
---|
[1112] | 265 | /// \e |
---|
| 266 | virtual void solveSimplex() = 0; |
---|
| 267 | /// \e |
---|
| 268 | virtual void solvePrimalSimplex() = 0; |
---|
| 269 | /// \e |
---|
| 270 | virtual void solveDualSimplex() = 0; |
---|
| 271 | |
---|
| 272 | //SOLUTION RETRIEVING |
---|
| 273 | |
---|
| 274 | /// \e |
---|
| 275 | virtual _Value getObjVal() = 0; |
---|
| 276 | |
---|
| 277 | //OTHER FUNCTIONS |
---|
| 278 | |
---|
| 279 | /// \e |
---|
| 280 | virtual int rowNum() const = 0; |
---|
| 281 | /// \e |
---|
| 282 | virtual int colNum() const = 0; |
---|
| 283 | /// \e |
---|
| 284 | virtual int warmUp() = 0; |
---|
| 285 | /// \e |
---|
| 286 | virtual void printWarmUpStatus(int i) = 0; |
---|
| 287 | /// \e |
---|
| 288 | virtual int getPrimalStatus() = 0; |
---|
| 289 | /// \e |
---|
| 290 | virtual void printPrimalStatus(int i) = 0; |
---|
| 291 | /// \e |
---|
| 292 | virtual int getDualStatus() = 0; |
---|
| 293 | /// \e |
---|
| 294 | virtual void printDualStatus(int i) = 0; |
---|
[1144] | 295 | /// Returns the status of the slack variable assigned to row \c row. |
---|
| 296 | virtual int getRowStat(const Row& row) = 0; |
---|
[1112] | 297 | /// \e |
---|
| 298 | virtual void printRowStatus(int i) = 0; |
---|
[1144] | 299 | /// Returns the status of the variable assigned to column \c col. |
---|
| 300 | virtual int getColStat(const Col& col) = 0; |
---|
[1112] | 301 | /// \e |
---|
| 302 | virtual void printColStatus(int i) = 0; |
---|
| 303 | |
---|
| 304 | //@} |
---|
| 305 | |
---|
| 306 | /*! @name Low level interface (protected members) |
---|
| 307 | Problem manipulating functions in the low level interface |
---|
| 308 | */ |
---|
| 309 | //@{ |
---|
[1074] | 310 | protected: |
---|
[1112] | 311 | |
---|
| 312 | //MATRIX MANIPULATING FUNCTIONS |
---|
| 313 | |
---|
[1031] | 314 | /// \e |
---|
[1111] | 315 | virtual int _addCol() = 0; |
---|
| 316 | /// \e |
---|
[1074] | 317 | virtual int _addRow() = 0; |
---|
[1031] | 318 | /// \e |
---|
[1111] | 319 | virtual void _eraseCol(int i) = 0; |
---|
| 320 | /// \e |
---|
| 321 | virtual void _eraseRow(int i) = 0; |
---|
[1081] | 322 | /// \e |
---|
| 323 | virtual void _setRowCoeffs(int i, |
---|
[1104] | 324 | const std::vector<std::pair<int, _Value> >& coeffs) = 0; |
---|
[1081] | 325 | /// \e |
---|
[1143] | 326 | /// This routine modifies \c coeffs only by the \c push_back method. |
---|
| 327 | virtual void _getRowCoeffs(int i, |
---|
| 328 | std::vector<std::pair<int, _Value> >& coeffs) = 0; |
---|
[1152] | 329 | /// \e |
---|
[1081] | 330 | virtual void _setColCoeffs(int i, |
---|
[1104] | 331 | const std::vector<std::pair<int, _Value> >& coeffs) = 0; |
---|
[1143] | 332 | /// \e |
---|
| 333 | /// This routine modifies \c coeffs only by the \c push_back method. |
---|
| 334 | virtual void _getColCoeffs(int i, |
---|
| 335 | std::vector<std::pair<int, _Value> >& coeffs) = 0; |
---|
[1081] | 336 | /// \e |
---|
[1152] | 337 | virtual void _setCoeff(int col, int row, _Value value) = 0; |
---|
| 338 | /// \e |
---|
| 339 | virtual _Value _getCoeff(int col, int row) = 0; |
---|
| 340 | // public: |
---|
| 341 | // /// \e |
---|
| 342 | // enum Bound { FREE, LOWER, UPPER, DOUBLE, FIXED }; |
---|
[1081] | 343 | protected: |
---|
| 344 | /// \e |
---|
[1110] | 345 | /// The lower bound of a variable (column) have to be given by an |
---|
| 346 | /// extended number of type _Value, i.e. a finite number of type |
---|
| 347 | /// _Value or -INF. |
---|
| 348 | virtual void _setColLowerBound(int i, _Value value) = 0; |
---|
| 349 | /// \e |
---|
[1111] | 350 | /// The lower bound of a variable (column) is an |
---|
| 351 | /// extended number of type _Value, i.e. a finite number of type |
---|
| 352 | /// _Value or -INF. |
---|
| 353 | virtual _Value _getColLowerBound(int i) = 0; |
---|
| 354 | /// \e |
---|
[1110] | 355 | /// The upper bound of a variable (column) have to be given by an |
---|
| 356 | /// extended number of type _Value, i.e. a finite number of type |
---|
| 357 | /// _Value or INF. |
---|
| 358 | virtual void _setColUpperBound(int i, _Value value) = 0; |
---|
| 359 | /// \e |
---|
| 360 | /// The upper bound of a variable (column) is an |
---|
| 361 | /// extended number of type _Value, i.e. a finite number of type |
---|
| 362 | /// _Value or INF. |
---|
| 363 | virtual _Value _getColUpperBound(int i) = 0; |
---|
| 364 | /// \e |
---|
[1111] | 365 | /// The lower bound of a linear expression (row) have to be given by an |
---|
| 366 | /// extended number of type _Value, i.e. a finite number of type |
---|
| 367 | /// _Value or -INF. |
---|
| 368 | virtual void _setRowLowerBound(int i, _Value value) = 0; |
---|
[1081] | 369 | /// \e |
---|
[1111] | 370 | /// The lower bound of a linear expression (row) is an |
---|
| 371 | /// extended number of type _Value, i.e. a finite number of type |
---|
| 372 | /// _Value or -INF. |
---|
| 373 | virtual _Value _getRowLowerBound(int i) = 0; |
---|
| 374 | /// \e |
---|
| 375 | /// The upper bound of a linear expression (row) have to be given by an |
---|
| 376 | /// extended number of type _Value, i.e. a finite number of type |
---|
| 377 | /// _Value or INF. |
---|
| 378 | virtual void _setRowUpperBound(int i, _Value value) = 0; |
---|
| 379 | /// \e |
---|
| 380 | /// The upper bound of a linear expression (row) is an |
---|
| 381 | /// extended number of type _Value, i.e. a finite number of type |
---|
| 382 | /// _Value or INF. |
---|
| 383 | virtual _Value _getRowUpperBound(int i) = 0; |
---|
[1081] | 384 | /// \e |
---|
[1152] | 385 | virtual void _setObjCoeff(int i, _Value obj_coef) = 0; |
---|
[1081] | 386 | /// \e |
---|
[1152] | 387 | virtual _Value _getObjCoeff(int i) = 0; |
---|
[1112] | 388 | |
---|
| 389 | //SOLUTION RETRIEVING |
---|
[1081] | 390 | |
---|
[1111] | 391 | /// \e |
---|
[1081] | 392 | virtual _Value _getPrimal(int i) = 0; |
---|
[1112] | 393 | //@} |
---|
| 394 | |
---|
| 395 | /*! @name High level interface (public members) |
---|
| 396 | Problem manipulating functions in the high level interface |
---|
| 397 | */ |
---|
| 398 | //@{ |
---|
| 399 | public: |
---|
[1081] | 400 | |
---|
[1112] | 401 | //MATRIX MANIPULATING FUNCTIONS |
---|
[1081] | 402 | |
---|
[1074] | 403 | /// \e |
---|
[1144] | 404 | Col addCol() { |
---|
[1074] | 405 | int i=_addCol(); |
---|
[1144] | 406 | Col col; |
---|
| 407 | col_iter_map.first(col, INVALID_CLASS); |
---|
| 408 | if (col_iter_map.valid(col)) { //van hasznalhato hely |
---|
| 409 | col_iter_map.set(col, INVALID_CLASS, VALID_CLASS); |
---|
| 410 | col_iter_map[col]=i; |
---|
[1074] | 411 | } else { //a cucc vegere kell inzertalni mert nincs szabad hely |
---|
[1144] | 412 | col=col_iter_map.push_back(i, VALID_CLASS); |
---|
[1074] | 413 | } |
---|
[1144] | 414 | int_col_map.push_back(col); |
---|
| 415 | return col; |
---|
[1074] | 416 | } |
---|
| 417 | /// \e |
---|
[1144] | 418 | Row addRow() { |
---|
[1111] | 419 | int i=_addRow(); |
---|
[1144] | 420 | Row row; |
---|
| 421 | row_iter_map.first(row, INVALID_CLASS); |
---|
| 422 | if (row_iter_map.valid(row)) { //van hasznalhato hely |
---|
| 423 | row_iter_map.set(row, INVALID_CLASS, VALID_CLASS); |
---|
| 424 | row_iter_map[row]=i; |
---|
[1111] | 425 | } else { //a cucc vegere kell inzertalni mert nincs szabad hely |
---|
[1144] | 426 | row=row_iter_map.push_back(i, VALID_CLASS); |
---|
[1031] | 427 | } |
---|
[1144] | 428 | int_row_map.push_back(row); |
---|
| 429 | return row; |
---|
[1074] | 430 | } |
---|
| 431 | /// \e |
---|
[1144] | 432 | void eraseCol(const Col& col) { |
---|
| 433 | col_iter_map.set(col, VALID_CLASS, INVALID_CLASS); |
---|
[1074] | 434 | int cols[2]; |
---|
[1144] | 435 | cols[1]=col_iter_map[col]; |
---|
[1074] | 436 | _eraseCol(cols[1]); |
---|
[1144] | 437 | col_iter_map[col]=0; //glpk specifikus, de kell ez?? |
---|
| 438 | Col it; |
---|
[1074] | 439 | for (col_iter_map.first(it, VALID_CLASS); |
---|
| 440 | col_iter_map.valid(it); col_iter_map.next(it)) { |
---|
| 441 | if (col_iter_map[it]>cols[1]) --col_iter_map[it]; |
---|
| 442 | } |
---|
[1143] | 443 | int_col_map.erase(int_col_map.begin()+cols[1]); |
---|
[1031] | 444 | } |
---|
| 445 | /// \e |
---|
[1144] | 446 | void eraseRow(const Row& row) { |
---|
| 447 | row_iter_map.set(row, VALID_CLASS, INVALID_CLASS); |
---|
[1074] | 448 | int rows[2]; |
---|
[1144] | 449 | rows[1]=row_iter_map[row]; |
---|
[1074] | 450 | _eraseRow(rows[1]); |
---|
[1144] | 451 | row_iter_map[row]=0; //glpk specifikus, de kell ez?? |
---|
| 452 | Row it; |
---|
[1074] | 453 | for (row_iter_map.first(it, VALID_CLASS); |
---|
| 454 | row_iter_map.valid(it); row_iter_map.next(it)) { |
---|
| 455 | if (row_iter_map[it]>rows[1]) --row_iter_map[it]; |
---|
| 456 | } |
---|
[1143] | 457 | int_row_map.erase(int_row_map.begin()+rows[1]); |
---|
[1074] | 458 | } |
---|
[1031] | 459 | /// \e |
---|
[1152] | 460 | void setCoeff(Col col, Row row, _Value value) { |
---|
| 461 | _setCoeff(col_iter_map[col], row_iter_map[row], value); |
---|
| 462 | } |
---|
| 463 | /// \e |
---|
| 464 | _Value getCoeff(Col col, Row row) { |
---|
| 465 | return _getCoeff(col_iter_map[col], row_iter_map[row], value); |
---|
| 466 | } |
---|
| 467 | /// \e |
---|
[1144] | 468 | void setColLowerBound(Col col, _Value lo) { |
---|
| 469 | _setColLowerBound(col_iter_map[col], lo); |
---|
[1111] | 470 | } |
---|
| 471 | /// \e |
---|
[1144] | 472 | _Value getColLowerBound(Col col) { |
---|
| 473 | return _getColLowerBound(col_iter_map[col]); |
---|
[1111] | 474 | } |
---|
| 475 | /// \e |
---|
[1144] | 476 | void setColUpperBound(Col col, _Value up) { |
---|
| 477 | _setColUpperBound(col_iter_map[col], up); |
---|
[1110] | 478 | } |
---|
| 479 | /// \e |
---|
[1144] | 480 | _Value getColUpperBound(Col col) { |
---|
| 481 | return _getColUpperBound(col_iter_map[col]); |
---|
[1111] | 482 | } |
---|
| 483 | /// \e |
---|
[1144] | 484 | void setRowLowerBound(Row row, _Value lo) { |
---|
| 485 | _setRowLowerBound(row_iter_map[row], lo); |
---|
[1110] | 486 | } |
---|
| 487 | /// \e |
---|
[1144] | 488 | _Value getRowLowerBound(Row row) { |
---|
| 489 | return _getRowLowerBound(row_iter_map[row]); |
---|
[1110] | 490 | } |
---|
| 491 | /// \e |
---|
[1144] | 492 | void setRowUpperBound(Row row, _Value up) { |
---|
| 493 | _setRowUpperBound(row_iter_map[row], up); |
---|
[1081] | 494 | } |
---|
[1031] | 495 | /// \e |
---|
[1144] | 496 | _Value getRowUpperBound(Row row) { |
---|
| 497 | return _getRowUpperBound(row_iter_map[row]); |
---|
[1111] | 498 | } |
---|
| 499 | /// \e |
---|
[1152] | 500 | void setObjCoeff(const Col& col, _Value obj_coef) { |
---|
| 501 | _setObjCoeff(col_iter_map[col], obj_coef); |
---|
[1111] | 502 | } |
---|
| 503 | /// \e |
---|
[1152] | 504 | _Value getObjCoeff(const Col& col) { |
---|
| 505 | return _getObjCoeff(col_iter_map[col]); |
---|
[1081] | 506 | } |
---|
| 507 | |
---|
[1112] | 508 | //SOLUTION RETRIEVING FUNCTIONS |
---|
| 509 | |
---|
| 510 | /// \e |
---|
[1144] | 511 | _Value getPrimal(const Col& col) { |
---|
| 512 | return _getPrimal(col_iter_map[col]); |
---|
[1112] | 513 | } |
---|
| 514 | |
---|
| 515 | //@} |
---|
| 516 | |
---|
| 517 | /*! @name User friend interface |
---|
| 518 | Problem manipulating functions in the user friend interface |
---|
| 519 | */ |
---|
| 520 | //@{ |
---|
| 521 | |
---|
| 522 | //EXPRESSION TYPES |
---|
[1099] | 523 | |
---|
| 524 | /// \e |
---|
[1144] | 525 | typedef Expr<Col, _Value> Expression; |
---|
[1099] | 526 | /// \e |
---|
[1144] | 527 | typedef Expr<Row, _Value> DualExpression; |
---|
| 528 | /// \e |
---|
| 529 | typedef Constr<Col, _Value> Constraint; |
---|
[1112] | 530 | |
---|
| 531 | //MATRIX MANIPULATING FUNCTIONS |
---|
| 532 | |
---|
[1099] | 533 | /// \e |
---|
[1144] | 534 | void setRowCoeffs(Row row, const Expression& expr) { |
---|
[1099] | 535 | std::vector<std::pair<int, _Value> > row_coeffs; |
---|
| 536 | for(typename Expression::Data::const_iterator i=expr.data.begin(); |
---|
| 537 | i!=expr.data.end(); ++i) { |
---|
| 538 | row_coeffs.push_back(std::make_pair |
---|
| 539 | (col_iter_map[(*i).first], (*i).second)); |
---|
| 540 | } |
---|
[1144] | 541 | _setRowCoeffs(row_iter_map[row], row_coeffs); |
---|
| 542 | } |
---|
| 543 | /// \e |
---|
| 544 | void setRow(Row row, const Constraint& constr) { |
---|
| 545 | setRowCoeffs(row, constr.expr); |
---|
| 546 | setRowLowerBound(row, constr.lo); |
---|
| 547 | setRowUpperBound(row, constr.up); |
---|
| 548 | } |
---|
| 549 | /// \e |
---|
| 550 | Row addRow(const Constraint& constr) { |
---|
| 551 | Row row=addRow(); |
---|
| 552 | setRowCoeffs(row, constr.expr); |
---|
| 553 | setRowLowerBound(row, constr.lo); |
---|
| 554 | setRowUpperBound(row, constr.up); |
---|
| 555 | return row; |
---|
[1099] | 556 | } |
---|
| 557 | /// \e |
---|
[1143] | 558 | /// This routine modifies \c expr by only adding to it. |
---|
[1144] | 559 | void getRowCoeffs(Row row, Expression& expr) { |
---|
[1143] | 560 | std::vector<std::pair<int, _Value> > row_coeffs; |
---|
[1144] | 561 | _getRowCoeffs(row_iter_map[row], row_coeffs); |
---|
[1143] | 562 | for(typename std::vector<std::pair<int, _Value> >::const_iterator |
---|
| 563 | i=row_coeffs.begin(); i!=row_coeffs.end(); ++i) { |
---|
| 564 | expr+= (*i).second*int_col_map[(*i).first]; |
---|
| 565 | } |
---|
| 566 | } |
---|
| 567 | /// \e |
---|
[1144] | 568 | void setColCoeffs(Col col, const DualExpression& expr) { |
---|
[1099] | 569 | std::vector<std::pair<int, _Value> > col_coeffs; |
---|
| 570 | for(typename DualExpression::Data::const_iterator i=expr.data.begin(); |
---|
| 571 | i!=expr.data.end(); ++i) { |
---|
| 572 | col_coeffs.push_back(std::make_pair |
---|
| 573 | (row_iter_map[(*i).first], (*i).second)); |
---|
| 574 | } |
---|
[1144] | 575 | _setColCoeffs(col_iter_map[col], col_coeffs); |
---|
[1099] | 576 | } |
---|
| 577 | /// \e |
---|
[1143] | 578 | /// This routine modifies \c expr by only adding to it. |
---|
[1144] | 579 | void getColCoeffs(Col col, DualExpression& expr) { |
---|
[1143] | 580 | std::vector<std::pair<int, _Value> > col_coeffs; |
---|
[1144] | 581 | _getColCoeffs(col_iter_map[col], col_coeffs); |
---|
[1143] | 582 | for(typename std::vector<std::pair<int, _Value> >::const_iterator |
---|
| 583 | i=col_coeffs.begin(); i!=col_coeffs.end(); ++i) { |
---|
| 584 | expr+= (*i).second*int_row_map[(*i).first]; |
---|
| 585 | } |
---|
| 586 | } |
---|
| 587 | /// \e |
---|
[1099] | 588 | void setObjCoeffs(const Expression& expr) { |
---|
[1152] | 589 | // writing zero everywhere |
---|
| 590 | for(Cols::ClassIt it(col_iter_map, VALID_CLASS); it!=INVALID; ++it) |
---|
| 591 | setObjCoeff(it, 0.0); |
---|
| 592 | // writing the data needed |
---|
[1099] | 593 | for(typename Expression::Data::const_iterator i=expr.data.begin(); |
---|
| 594 | i!=expr.data.end(); ++i) { |
---|
[1152] | 595 | setObjCoeff((*i).first, (*i).second); |
---|
[1099] | 596 | } |
---|
| 597 | } |
---|
[1143] | 598 | /// \e |
---|
| 599 | /// This routine modifies \c expr by only adding to it. |
---|
| 600 | void getObjCoeffs(Expression& expr) { |
---|
[1152] | 601 | for(Cols::ClassIt it(col_iter_map, VALID_CLASS); it!=INVALID; ++it) |
---|
| 602 | expr+=getObjCoeff(it)*it; |
---|
| 603 | } |
---|
| 604 | //@} |
---|
| 605 | |
---|
| 606 | |
---|
| 607 | /*! @name MIP functions and types (public members) |
---|
| 608 | */ |
---|
| 609 | //@{ |
---|
| 610 | public: |
---|
| 611 | /// \e |
---|
| 612 | virtual void solveBandB() = 0; |
---|
| 613 | /// \e |
---|
| 614 | virtual void setLP() = 0; |
---|
| 615 | /// \e |
---|
| 616 | virtual void setMIP() = 0; |
---|
| 617 | protected: |
---|
| 618 | /// \e |
---|
| 619 | virtual void _setColCont(int i) = 0; |
---|
| 620 | /// \e |
---|
| 621 | virtual void _setColInt(int i) = 0; |
---|
[1153] | 622 | /// \e |
---|
| 623 | virtual _Value _getMIPPrimal(int i) = 0; |
---|
[1152] | 624 | public: |
---|
| 625 | /// \e |
---|
| 626 | void setColCont(Col col) { |
---|
| 627 | _setColCont(col_iter_map[col]); |
---|
| 628 | } |
---|
| 629 | /// \e |
---|
| 630 | void setColInt(Col col) { |
---|
| 631 | _setColInt(col_iter_map[col]); |
---|
[1143] | 632 | } |
---|
[1153] | 633 | /// \e |
---|
| 634 | _Value getMIPPrimal(Col col) { |
---|
| 635 | return _getMIPPrimal(col_iter_map[col]); |
---|
| 636 | } |
---|
[1112] | 637 | //@} |
---|
[1031] | 638 | }; |
---|
| 639 | |
---|
[1104] | 640 | template <typename _Value> |
---|
| 641 | const _Value LPSolverBase<_Value>::INF=std::numeric_limits<_Value>::infinity(); |
---|
| 642 | |
---|
[1048] | 643 | |
---|
[1111] | 644 | /// \brief Wrapper for GLPK solver |
---|
[1031] | 645 | /// |
---|
[1111] | 646 | /// This class implements a lemon wrapper for GLPK. |
---|
[1081] | 647 | class LPGLPK : public LPSolverBase<double> { |
---|
[1031] | 648 | public: |
---|
[1048] | 649 | typedef LPSolverBase<double> Parent; |
---|
[1031] | 650 | |
---|
| 651 | public: |
---|
| 652 | /// \e |
---|
| 653 | LPX* lp; |
---|
| 654 | |
---|
| 655 | public: |
---|
| 656 | /// \e |
---|
[1081] | 657 | LPGLPK() : Parent(), |
---|
[1031] | 658 | lp(lpx_create_prob()) { |
---|
[1144] | 659 | int_row_map.push_back(Row()); |
---|
| 660 | int_col_map.push_back(Col()); |
---|
[1031] | 661 | lpx_set_int_parm(lp, LPX_K_DUAL, 1); |
---|
| 662 | } |
---|
| 663 | /// \e |
---|
[1081] | 664 | ~LPGLPK() { |
---|
[1031] | 665 | lpx_delete_prob(lp); |
---|
| 666 | } |
---|
[1081] | 667 | |
---|
| 668 | //MATRIX INDEPEDENT MANIPULATING FUNCTIONS |
---|
| 669 | |
---|
[1031] | 670 | /// \e |
---|
| 671 | void setMinimize() { |
---|
| 672 | lpx_set_obj_dir(lp, LPX_MIN); |
---|
| 673 | } |
---|
| 674 | /// \e |
---|
| 675 | void setMaximize() { |
---|
| 676 | lpx_set_obj_dir(lp, LPX_MAX); |
---|
| 677 | } |
---|
[1081] | 678 | |
---|
| 679 | //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS |
---|
| 680 | |
---|
[1074] | 681 | protected: |
---|
[1031] | 682 | /// \e |
---|
[1074] | 683 | int _addCol() { |
---|
[1110] | 684 | int i=lpx_add_cols(lp, 1); |
---|
| 685 | _setColLowerBound(i, -INF); |
---|
| 686 | _setColUpperBound(i, INF); |
---|
| 687 | return i; |
---|
[1031] | 688 | } |
---|
| 689 | /// \e |
---|
[1074] | 690 | int _addRow() { |
---|
[1110] | 691 | int i=lpx_add_rows(lp, 1); |
---|
| 692 | return i; |
---|
[1074] | 693 | } |
---|
| 694 | /// \e |
---|
[1081] | 695 | virtual void _setRowCoeffs(int i, |
---|
[1104] | 696 | const std::vector<std::pair<int, double> >& coeffs) { |
---|
[1074] | 697 | int mem_length=1+colNum(); |
---|
| 698 | int* indices = new int[mem_length]; |
---|
| 699 | double* doubles = new double[mem_length]; |
---|
| 700 | int length=0; |
---|
| 701 | for (std::vector<std::pair<int, double> >:: |
---|
| 702 | const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) { |
---|
| 703 | ++length; |
---|
| 704 | indices[length]=it->first; |
---|
| 705 | doubles[length]=it->second; |
---|
[1031] | 706 | } |
---|
[1074] | 707 | lpx_set_mat_row(lp, i, length, indices, doubles); |
---|
| 708 | delete [] indices; |
---|
| 709 | delete [] doubles; |
---|
[1031] | 710 | } |
---|
[1074] | 711 | /// \e |
---|
[1143] | 712 | virtual void _getRowCoeffs(int i, |
---|
| 713 | std::vector<std::pair<int, double> >& coeffs) { |
---|
| 714 | int mem_length=1+colNum(); |
---|
| 715 | int* indices = new int[mem_length]; |
---|
| 716 | double* doubles = new double[mem_length]; |
---|
| 717 | int length=lpx_get_mat_row(lp, i, indices, doubles); |
---|
| 718 | for (int i=1; i<=length; ++i) { |
---|
| 719 | coeffs.push_back(std::make_pair(indices[i], doubles[i])); |
---|
| 720 | } |
---|
| 721 | delete [] indices; |
---|
| 722 | delete [] doubles; |
---|
| 723 | } |
---|
| 724 | /// \e |
---|
[1081] | 725 | virtual void _setColCoeffs(int i, |
---|
[1104] | 726 | const std::vector<std::pair<int, double> >& coeffs) { |
---|
[1074] | 727 | int mem_length=1+rowNum(); |
---|
| 728 | int* indices = new int[mem_length]; |
---|
| 729 | double* doubles = new double[mem_length]; |
---|
| 730 | int length=0; |
---|
| 731 | for (std::vector<std::pair<int, double> >:: |
---|
| 732 | const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) { |
---|
| 733 | ++length; |
---|
| 734 | indices[length]=it->first; |
---|
| 735 | doubles[length]=it->second; |
---|
| 736 | } |
---|
| 737 | lpx_set_mat_col(lp, i, length, indices, doubles); |
---|
| 738 | delete [] indices; |
---|
| 739 | delete [] doubles; |
---|
[1031] | 740 | } |
---|
| 741 | /// \e |
---|
[1143] | 742 | virtual void _getColCoeffs(int i, |
---|
| 743 | std::vector<std::pair<int, double> >& coeffs) { |
---|
| 744 | int mem_length=1+rowNum(); |
---|
| 745 | int* indices = new int[mem_length]; |
---|
| 746 | double* doubles = new double[mem_length]; |
---|
| 747 | int length=lpx_get_mat_col(lp, i, indices, doubles); |
---|
| 748 | for (int i=1; i<=length; ++i) { |
---|
| 749 | coeffs.push_back(std::make_pair(indices[i], doubles[i])); |
---|
| 750 | } |
---|
| 751 | delete [] indices; |
---|
| 752 | delete [] doubles; |
---|
| 753 | } |
---|
| 754 | /// \e |
---|
[1074] | 755 | virtual void _eraseCol(int i) { |
---|
[1031] | 756 | int cols[2]; |
---|
[1074] | 757 | cols[1]=i; |
---|
[1031] | 758 | lpx_del_cols(lp, 1, cols); |
---|
| 759 | } |
---|
[1074] | 760 | virtual void _eraseRow(int i) { |
---|
[1031] | 761 | int rows[2]; |
---|
[1074] | 762 | rows[1]=i; |
---|
[1031] | 763 | lpx_del_rows(lp, 1, rows); |
---|
| 764 | } |
---|
[1152] | 765 | void _setCoeff(int col, int row, double value) { |
---|
| 766 | /// FIXME not yet implemented |
---|
| 767 | } |
---|
| 768 | double _getCoeff(int col, int row) { |
---|
| 769 | /// FIXME not yet implemented |
---|
| 770 | return 0.0; |
---|
| 771 | } |
---|
[1110] | 772 | virtual void _setColLowerBound(int i, double lo) { |
---|
| 773 | if (lo==INF) { |
---|
| 774 | //FIXME error |
---|
| 775 | } |
---|
| 776 | int b=lpx_get_col_type(lp, i); |
---|
| 777 | double up=lpx_get_col_ub(lp, i); |
---|
| 778 | if (lo==-INF) { |
---|
| 779 | switch (b) { |
---|
| 780 | case LPX_FR: |
---|
| 781 | case LPX_LO: |
---|
| 782 | lpx_set_col_bnds(lp, i, LPX_FR, lo, up); |
---|
| 783 | break; |
---|
| 784 | case LPX_UP: |
---|
| 785 | break; |
---|
| 786 | case LPX_DB: |
---|
| 787 | case LPX_FX: |
---|
| 788 | lpx_set_col_bnds(lp, i, LPX_UP, lo, up); |
---|
| 789 | break; |
---|
| 790 | default: ; |
---|
| 791 | //FIXME error |
---|
| 792 | } |
---|
| 793 | } else { |
---|
| 794 | switch (b) { |
---|
| 795 | case LPX_FR: |
---|
| 796 | case LPX_LO: |
---|
| 797 | lpx_set_col_bnds(lp, i, LPX_LO, lo, up); |
---|
| 798 | break; |
---|
| 799 | case LPX_UP: |
---|
| 800 | case LPX_DB: |
---|
| 801 | case LPX_FX: |
---|
| 802 | if (lo==up) |
---|
| 803 | lpx_set_col_bnds(lp, i, LPX_FX, lo, up); |
---|
| 804 | else |
---|
| 805 | lpx_set_col_bnds(lp, i, LPX_DB, lo, up); |
---|
| 806 | break; |
---|
| 807 | default: ; |
---|
| 808 | //FIXME error |
---|
| 809 | } |
---|
| 810 | } |
---|
| 811 | } |
---|
[1111] | 812 | virtual double _getColLowerBound(int i) { |
---|
| 813 | int b=lpx_get_col_type(lp, i); |
---|
| 814 | switch (b) { |
---|
| 815 | case LPX_FR: |
---|
| 816 | return -INF; |
---|
| 817 | case LPX_LO: |
---|
| 818 | return lpx_get_col_lb(lp, i); |
---|
| 819 | case LPX_UP: |
---|
| 820 | return -INF; |
---|
| 821 | case LPX_DB: |
---|
| 822 | case LPX_FX: |
---|
| 823 | return lpx_get_col_lb(lp, i); |
---|
| 824 | default: ; |
---|
| 825 | //FIXME error |
---|
| 826 | return 0.0; |
---|
| 827 | } |
---|
| 828 | } |
---|
[1110] | 829 | virtual void _setColUpperBound(int i, double up) { |
---|
| 830 | if (up==-INF) { |
---|
| 831 | //FIXME error |
---|
| 832 | } |
---|
| 833 | int b=lpx_get_col_type(lp, i); |
---|
| 834 | double lo=lpx_get_col_lb(lp, i); |
---|
| 835 | if (up==INF) { |
---|
| 836 | switch (b) { |
---|
| 837 | case LPX_FR: |
---|
| 838 | case LPX_LO: |
---|
| 839 | break; |
---|
| 840 | case LPX_UP: |
---|
| 841 | lpx_set_col_bnds(lp, i, LPX_FR, lo, up); |
---|
| 842 | break; |
---|
| 843 | case LPX_DB: |
---|
| 844 | case LPX_FX: |
---|
| 845 | lpx_set_col_bnds(lp, i, LPX_LO, lo, up); |
---|
| 846 | break; |
---|
| 847 | default: ; |
---|
| 848 | //FIXME error |
---|
| 849 | } |
---|
| 850 | } else { |
---|
| 851 | switch (b) { |
---|
| 852 | case LPX_FR: |
---|
| 853 | lpx_set_col_bnds(lp, i, LPX_UP, lo, up); |
---|
| 854 | case LPX_LO: |
---|
| 855 | if (lo==up) |
---|
| 856 | lpx_set_col_bnds(lp, i, LPX_FX, lo, up); |
---|
| 857 | else |
---|
| 858 | lpx_set_col_bnds(lp, i, LPX_DB, lo, up); |
---|
| 859 | break; |
---|
| 860 | case LPX_UP: |
---|
| 861 | lpx_set_col_bnds(lp, i, LPX_UP, lo, up); |
---|
| 862 | break; |
---|
| 863 | case LPX_DB: |
---|
| 864 | case LPX_FX: |
---|
| 865 | if (lo==up) |
---|
| 866 | lpx_set_col_bnds(lp, i, LPX_FX, lo, up); |
---|
| 867 | else |
---|
| 868 | lpx_set_col_bnds(lp, i, LPX_DB, lo, up); |
---|
| 869 | break; |
---|
| 870 | default: ; |
---|
| 871 | //FIXME error |
---|
| 872 | } |
---|
| 873 | } |
---|
| 874 | } |
---|
| 875 | virtual double _getColUpperBound(int i) { |
---|
| 876 | int b=lpx_get_col_type(lp, i); |
---|
| 877 | switch (b) { |
---|
| 878 | case LPX_FR: |
---|
| 879 | case LPX_LO: |
---|
| 880 | return INF; |
---|
| 881 | case LPX_UP: |
---|
| 882 | case LPX_DB: |
---|
| 883 | case LPX_FX: |
---|
| 884 | return lpx_get_col_ub(lp, i); |
---|
| 885 | default: ; |
---|
| 886 | //FIXME error |
---|
| 887 | return 0.0; |
---|
| 888 | } |
---|
| 889 | } |
---|
[1111] | 890 | virtual void _setRowLowerBound(int i, double lo) { |
---|
| 891 | if (lo==INF) { |
---|
| 892 | //FIXME error |
---|
[1081] | 893 | } |
---|
[1111] | 894 | int b=lpx_get_row_type(lp, i); |
---|
| 895 | double up=lpx_get_row_ub(lp, i); |
---|
| 896 | if (lo==-INF) { |
---|
| 897 | switch (b) { |
---|
| 898 | case LPX_FR: |
---|
| 899 | case LPX_LO: |
---|
| 900 | lpx_set_row_bnds(lp, i, LPX_FR, lo, up); |
---|
| 901 | break; |
---|
| 902 | case LPX_UP: |
---|
| 903 | break; |
---|
| 904 | case LPX_DB: |
---|
| 905 | case LPX_FX: |
---|
| 906 | lpx_set_row_bnds(lp, i, LPX_UP, lo, up); |
---|
| 907 | break; |
---|
| 908 | default: ; |
---|
| 909 | //FIXME error |
---|
| 910 | } |
---|
| 911 | } else { |
---|
| 912 | switch (b) { |
---|
| 913 | case LPX_FR: |
---|
| 914 | case LPX_LO: |
---|
| 915 | lpx_set_row_bnds(lp, i, LPX_LO, lo, up); |
---|
| 916 | break; |
---|
| 917 | case LPX_UP: |
---|
| 918 | case LPX_DB: |
---|
| 919 | case LPX_FX: |
---|
| 920 | if (lo==up) |
---|
| 921 | lpx_set_row_bnds(lp, i, LPX_FX, lo, up); |
---|
| 922 | else |
---|
| 923 | lpx_set_row_bnds(lp, i, LPX_DB, lo, up); |
---|
| 924 | break; |
---|
| 925 | default: ; |
---|
| 926 | //FIXME error |
---|
| 927 | } |
---|
[1081] | 928 | } |
---|
[1111] | 929 | } |
---|
| 930 | virtual double _getRowLowerBound(int i) { |
---|
| 931 | int b=lpx_get_row_type(lp, i); |
---|
| 932 | switch (b) { |
---|
| 933 | case LPX_FR: |
---|
| 934 | return -INF; |
---|
| 935 | case LPX_LO: |
---|
| 936 | return lpx_get_row_lb(lp, i); |
---|
| 937 | case LPX_UP: |
---|
| 938 | return -INF; |
---|
| 939 | case LPX_DB: |
---|
| 940 | case LPX_FX: |
---|
| 941 | return lpx_get_row_lb(lp, i); |
---|
| 942 | default: ; |
---|
| 943 | //FIXME error |
---|
| 944 | return 0.0; |
---|
| 945 | } |
---|
| 946 | } |
---|
| 947 | virtual void _setRowUpperBound(int i, double up) { |
---|
| 948 | if (up==-INF) { |
---|
| 949 | //FIXME error |
---|
| 950 | } |
---|
| 951 | int b=lpx_get_row_type(lp, i); |
---|
| 952 | double lo=lpx_get_row_lb(lp, i); |
---|
| 953 | if (up==INF) { |
---|
| 954 | switch (b) { |
---|
| 955 | case LPX_FR: |
---|
| 956 | case LPX_LO: |
---|
| 957 | break; |
---|
| 958 | case LPX_UP: |
---|
| 959 | lpx_set_row_bnds(lp, i, LPX_FR, lo, up); |
---|
| 960 | break; |
---|
| 961 | case LPX_DB: |
---|
| 962 | case LPX_FX: |
---|
| 963 | lpx_set_row_bnds(lp, i, LPX_LO, lo, up); |
---|
| 964 | break; |
---|
| 965 | default: ; |
---|
| 966 | //FIXME error |
---|
| 967 | } |
---|
| 968 | } else { |
---|
| 969 | switch (b) { |
---|
| 970 | case LPX_FR: |
---|
| 971 | lpx_set_row_bnds(lp, i, LPX_UP, lo, up); |
---|
| 972 | case LPX_LO: |
---|
| 973 | if (lo==up) |
---|
| 974 | lpx_set_row_bnds(lp, i, LPX_FX, lo, up); |
---|
| 975 | else |
---|
| 976 | lpx_set_row_bnds(lp, i, LPX_DB, lo, up); |
---|
| 977 | break; |
---|
| 978 | case LPX_UP: |
---|
| 979 | lpx_set_row_bnds(lp, i, LPX_UP, lo, up); |
---|
| 980 | break; |
---|
| 981 | case LPX_DB: |
---|
| 982 | case LPX_FX: |
---|
| 983 | if (lo==up) |
---|
| 984 | lpx_set_row_bnds(lp, i, LPX_FX, lo, up); |
---|
| 985 | else |
---|
| 986 | lpx_set_row_bnds(lp, i, LPX_DB, lo, up); |
---|
| 987 | break; |
---|
| 988 | default: ; |
---|
| 989 | //FIXME error |
---|
| 990 | } |
---|
| 991 | } |
---|
| 992 | } |
---|
| 993 | virtual double _getRowUpperBound(int i) { |
---|
| 994 | int b=lpx_get_row_type(lp, i); |
---|
| 995 | switch (b) { |
---|
| 996 | case LPX_FR: |
---|
| 997 | case LPX_LO: |
---|
| 998 | return INF; |
---|
| 999 | case LPX_UP: |
---|
| 1000 | case LPX_DB: |
---|
| 1001 | case LPX_FX: |
---|
| 1002 | return lpx_get_row_ub(lp, i); |
---|
| 1003 | default: ; |
---|
| 1004 | //FIXME error |
---|
| 1005 | return 0.0; |
---|
| 1006 | } |
---|
| 1007 | } |
---|
[1031] | 1008 | /// \e |
---|
[1152] | 1009 | virtual double _getObjCoeff(int i) { |
---|
[1081] | 1010 | return lpx_get_obj_coef(lp, i); |
---|
[1031] | 1011 | } |
---|
| 1012 | /// \e |
---|
[1152] | 1013 | virtual void _setObjCoeff(int i, double obj_coef) { |
---|
[1081] | 1014 | lpx_set_obj_coef(lp, i, obj_coef); |
---|
[1031] | 1015 | } |
---|
[1081] | 1016 | public: |
---|
[1031] | 1017 | /// \e |
---|
| 1018 | void solveSimplex() { lpx_simplex(lp); } |
---|
| 1019 | /// \e |
---|
| 1020 | void solvePrimalSimplex() { lpx_simplex(lp); } |
---|
| 1021 | /// \e |
---|
| 1022 | void solveDualSimplex() { lpx_simplex(lp); } |
---|
[1081] | 1023 | protected: |
---|
| 1024 | virtual double _getPrimal(int i) { |
---|
| 1025 | return lpx_get_col_prim(lp, i); |
---|
[1031] | 1026 | } |
---|
[1081] | 1027 | public: |
---|
[1031] | 1028 | /// \e |
---|
| 1029 | double getObjVal() { return lpx_get_obj_val(lp); } |
---|
| 1030 | /// \e |
---|
| 1031 | int rowNum() const { return lpx_get_num_rows(lp); } |
---|
| 1032 | /// \e |
---|
| 1033 | int colNum() const { return lpx_get_num_cols(lp); } |
---|
| 1034 | /// \e |
---|
| 1035 | int warmUp() { return lpx_warm_up(lp); } |
---|
| 1036 | /// \e |
---|
| 1037 | void printWarmUpStatus(int i) { |
---|
| 1038 | switch (i) { |
---|
| 1039 | case LPX_E_OK: cout << "LPX_E_OK" << endl; break; |
---|
| 1040 | case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break; |
---|
| 1041 | case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break; |
---|
| 1042 | case LPX_E_SING: cout << "LPX_E_SING" << endl; break; |
---|
| 1043 | } |
---|
| 1044 | } |
---|
| 1045 | /// \e |
---|
| 1046 | int getPrimalStatus() { return lpx_get_prim_stat(lp); } |
---|
| 1047 | /// \e |
---|
| 1048 | void printPrimalStatus(int i) { |
---|
| 1049 | switch (i) { |
---|
| 1050 | case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break; |
---|
| 1051 | case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break; |
---|
| 1052 | case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break; |
---|
| 1053 | case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break; |
---|
| 1054 | } |
---|
| 1055 | } |
---|
| 1056 | /// \e |
---|
| 1057 | int getDualStatus() { return lpx_get_dual_stat(lp); } |
---|
| 1058 | /// \e |
---|
| 1059 | void printDualStatus(int i) { |
---|
| 1060 | switch (i) { |
---|
| 1061 | case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break; |
---|
| 1062 | case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break; |
---|
| 1063 | case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break; |
---|
| 1064 | case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break; |
---|
| 1065 | } |
---|
| 1066 | } |
---|
[1144] | 1067 | /// Returns the status of the slack variable assigned to row \c row. |
---|
| 1068 | int getRowStat(const Row& row) { |
---|
| 1069 | return lpx_get_row_stat(lp, row_iter_map[row]); |
---|
[1031] | 1070 | } |
---|
| 1071 | /// \e |
---|
| 1072 | void printRowStatus(int i) { |
---|
| 1073 | switch (i) { |
---|
| 1074 | case LPX_BS: cout << "LPX_BS" << endl; break; |
---|
| 1075 | case LPX_NL: cout << "LPX_NL" << endl; break; |
---|
| 1076 | case LPX_NU: cout << "LPX_NU" << endl; break; |
---|
| 1077 | case LPX_NF: cout << "LPX_NF" << endl; break; |
---|
| 1078 | case LPX_NS: cout << "LPX_NS" << endl; break; |
---|
| 1079 | } |
---|
| 1080 | } |
---|
[1144] | 1081 | /// Returns the status of the variable assigned to column \c col. |
---|
| 1082 | int getColStat(const Col& col) { |
---|
| 1083 | return lpx_get_col_stat(lp, col_iter_map[col]); |
---|
[1031] | 1084 | } |
---|
| 1085 | /// \e |
---|
| 1086 | void printColStatus(int i) { |
---|
| 1087 | switch (i) { |
---|
| 1088 | case LPX_BS: cout << "LPX_BS" << endl; break; |
---|
| 1089 | case LPX_NL: cout << "LPX_NL" << endl; break; |
---|
| 1090 | case LPX_NU: cout << "LPX_NU" << endl; break; |
---|
| 1091 | case LPX_NF: cout << "LPX_NF" << endl; break; |
---|
| 1092 | case LPX_NS: cout << "LPX_NS" << endl; break; |
---|
| 1093 | } |
---|
| 1094 | } |
---|
[1152] | 1095 | |
---|
| 1096 | // MIP |
---|
| 1097 | /// \e |
---|
| 1098 | void solveBandB() { lpx_integer(lp); } |
---|
| 1099 | /// \e |
---|
| 1100 | void setLP() { lpx_set_class(lp, LPX_LP); } |
---|
| 1101 | /// \e |
---|
| 1102 | void setMIP() { lpx_set_class(lp, LPX_MIP); } |
---|
| 1103 | protected: |
---|
| 1104 | /// \e |
---|
[1153] | 1105 | void _setColCont(int i) { lpx_set_col_kind(lp, i, LPX_CV); } |
---|
[1152] | 1106 | /// \e |
---|
[1153] | 1107 | void _setColInt(int i) { lpx_set_col_kind(lp, i, LPX_IV); } |
---|
| 1108 | /// \e |
---|
| 1109 | double _getMIPPrimal(int i) { return lpx_mip_col_val(lp, i); } |
---|
[1031] | 1110 | }; |
---|
| 1111 | |
---|
| 1112 | /// @} |
---|
| 1113 | |
---|
| 1114 | } //namespace lemon |
---|
| 1115 | |
---|
[1152] | 1116 | #endif //LEMON_LP_SOLVER_BASE_H |
---|