COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/marci/lp/lp_solver_base.h @ 1152:1765ff9fefa1

Last change on this file since 1152:1765ff9fefa1 was 1152:1765ff9fefa1, checked in by marci, 16 years ago

small changes

File size: 29.3 KB
Line 
1// -*- c++ -*-
2#ifndef LEMON_LP_SOLVER_BASE_H
3#define LEMON_LP_SOLVER_BASE_H
4
5///\ingroup misc
6///\file
7
8// #include <stdio.h>
9#include <stdlib.h>
10#include <iostream>
11#include <map>
12#include <limits>
13// #include <stdio>
14//#include <stdlib>
15extern "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>
27#include <expression.h>
28//#include <stp.h>
29//#include <lemon/max_flow.h>
30//#include <augmenting_flow.h>
31//#include <iter_map.h>
32
33using std::cout;
34using std::cin;
35using std::endl;
36
37namespace 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.
67    class Class;
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:
79    void befuz(Class it, int class_id) {
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    }
92    void kifuz(Class it, int class_id) {
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.
113    Class push_back(const T& t, int class_id) {
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.
122    void set(Class it, int old_class_id, int new_class_id) {
123      kifuz(it.i, old_class_id);
124      befuz(it.i, new_class_id);
125    }
126    /// Returns the data pointed by \c it.
127    T& operator[](Class it) { return nodes[it.i].data; }
128    /// Returns the data pointed by \c it.
129    const T& operator[](Class it) const { return nodes[it.i].data; }
130    ///.
131    class Class {
132      friend class IterablePartition;
133    protected:
134      int i;
135    public:
136      /// Default constructor.
137      Class() { }
138      /// This constructor constructs an iterator which points
139      /// to the member of th container indexed by the integer _i.
140      Class(const int& _i) : i(_i) { }
141      /// Invalid constructor.
142      Class(const Invalid&) : i(-1) { }
143      friend bool operator<(const Class& x, const Class& y);
144      friend std::ostream& operator<<(std::ostream& os,
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;}
148    };
149    friend bool operator<(const Class& x, const Class& y) {
150      return (x.i < y.i);
151    }
152    friend std::ostream& operator<<(std::ostream& os,
153                                    const Class& it) {
154      os << it.i;
155      return os;
156    }
157    /// First member of class \c class_id.
158    Class& first(Class& it, int class_id) const {
159      it.i=tips[class_id].first;
160      return it;
161    }
162    /// Next member.
163    Class& next(Class& it) const {
164      it.i=nodes[it.i].next;
165      return it;
166    }
167    /// True iff the iterator is valid.
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
188  };
189
190
191  /*! \e
192    \todo kellenene uj iterable structure bele, mert ez nem az igazi
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.
199    \nosubgrouping
200  */
201  template <typename _Value>
202  class LPSolverBase {
203   
204    /*! @name Uncategorized functions and types (public members)
205    */
206    //@{
207  public:
208
209    //UNCATEGORIZED
210
211    /// \e
212    typedef IterablePartition<int> Rows;
213    /// \e
214    typedef IterablePartition<int> Cols;
215    /// \e
216    typedef _Value Value;
217    /// \e
218    typedef Rows::Class Row;
219    /// \e
220    typedef Cols::Class Col;
221  public:
222    /// \e
223    IterablePartition<int> row_iter_map;
224    /// \e
225    IterablePartition<int> col_iter_map;
226    /// \e
227    std::vector<Row> int_row_map;
228    /// \e
229    std::vector<Col> int_col_map;
230    /// \e
231    const int VALID_CLASS;
232    /// \e
233    const int INVALID_CLASS;
234    /// \e
235    static const _Value INF;
236  public:
237    /// \e
238    LPSolverBase() : row_iter_map(2),
239                     col_iter_map(2),
240                     VALID_CLASS(0), INVALID_CLASS(1) { }
241    /// \e
242    virtual ~LPSolverBase() { }
243    //@}
244
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:
255
256    //UNCATEGORIZED FUNCTIONS
257
258    /// \e
259    virtual void setMinimize() = 0;
260    /// \e
261    virtual void setMaximize() = 0;
262
263    //SOLVER FUNCTIONS
264
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;
295    /// Returns the status of the slack variable assigned to row \c row.
296    virtual int getRowStat(const Row& row) = 0;
297    /// \e
298    virtual void printRowStatus(int i) = 0;
299    /// Returns the status of the variable assigned to column \c col.
300    virtual int getColStat(const Col& col) = 0;
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    //@{
310  protected:
311
312    //MATRIX MANIPULATING FUNCTIONS
313
314    /// \e
315    virtual int _addCol() = 0;
316    /// \e
317    virtual int _addRow() = 0;
318    /// \e
319    virtual void _eraseCol(int i) = 0;
320    /// \e
321    virtual void _eraseRow(int i) = 0;
322    /// \e
323    virtual void _setRowCoeffs(int i,
324                               const std::vector<std::pair<int, _Value> >& coeffs) = 0;
325    /// \e
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;
329    /// \e
330    virtual void _setColCoeffs(int i,
331                               const std::vector<std::pair<int, _Value> >& coeffs) = 0;
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;
336    /// \e
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 };
343  protected:
344    /// \e
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
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
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
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;
369    /// \e
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;
384    /// \e
385    virtual void _setObjCoeff(int i, _Value obj_coef) = 0;
386    /// \e
387    virtual _Value _getObjCoeff(int i) = 0;
388   
389    //SOLUTION RETRIEVING
390
391    /// \e
392    virtual _Value _getPrimal(int i) = 0;
393    //@}
394   
395    /*! @name High level interface (public members)
396      Problem manipulating functions in the high level interface
397    */
398    //@{
399  public:
400
401    //MATRIX MANIPULATING FUNCTIONS
402
403    /// \e
404    Col addCol() {
405      int i=_addCol(); 
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;
411      } else { //a cucc vegere kell inzertalni mert nincs szabad hely
412        col=col_iter_map.push_back(i, VALID_CLASS);
413      }
414      int_col_map.push_back(col);
415      return col;
416    }
417    /// \e
418    Row addRow() {
419      int i=_addRow();
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;
425      } else { //a cucc vegere kell inzertalni mert nincs szabad hely
426        row=row_iter_map.push_back(i, VALID_CLASS);
427      }
428      int_row_map.push_back(row);
429      return row;
430    }
431    /// \e
432    void eraseCol(const Col& col) {
433      col_iter_map.set(col, VALID_CLASS, INVALID_CLASS);
434      int cols[2];
435      cols[1]=col_iter_map[col];
436      _eraseCol(cols[1]);
437      col_iter_map[col]=0; //glpk specifikus, de kell ez??
438      Col it;
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      }
443      int_col_map.erase(int_col_map.begin()+cols[1]);
444    }
445    /// \e
446    void eraseRow(const Row& row) {
447      row_iter_map.set(row, VALID_CLASS, INVALID_CLASS);
448      int rows[2];
449      rows[1]=row_iter_map[row];
450      _eraseRow(rows[1]);
451      row_iter_map[row]=0; //glpk specifikus, de kell ez??
452      Row it;
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      }
457      int_row_map.erase(int_row_map.begin()+rows[1]);
458    }
459    /// \e
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
468    void setColLowerBound(Col col, _Value lo) {
469      _setColLowerBound(col_iter_map[col], lo);
470    }
471    /// \e
472    _Value getColLowerBound(Col col) {
473      return _getColLowerBound(col_iter_map[col]);
474    }
475    /// \e
476    void setColUpperBound(Col col, _Value up) {
477      _setColUpperBound(col_iter_map[col], up);
478    }
479    /// \e
480    _Value getColUpperBound(Col col) {     
481      return _getColUpperBound(col_iter_map[col]);
482    }
483    /// \e
484    void setRowLowerBound(Row row, _Value lo) {
485      _setRowLowerBound(row_iter_map[row], lo);
486    }
487    /// \e
488    _Value getRowLowerBound(Row row) {
489      return _getRowLowerBound(row_iter_map[row]);
490    }
491    /// \e
492    void setRowUpperBound(Row row, _Value up) {
493      _setRowUpperBound(row_iter_map[row], up);
494    }
495    /// \e
496    _Value getRowUpperBound(Row row) {     
497      return _getRowUpperBound(row_iter_map[row]);
498    }
499    /// \e
500    void setObjCoeff(const Col& col, _Value obj_coef) {
501      _setObjCoeff(col_iter_map[col], obj_coef);
502    }
503    /// \e
504    _Value getObjCoeff(const Col& col) {
505      return _getObjCoeff(col_iter_map[col]);
506    }
507
508    //SOLUTION RETRIEVING FUNCTIONS
509
510    /// \e
511    _Value getPrimal(const Col& col) {
512      return _getPrimal(col_iter_map[col]);
513    }   
514
515    //@}
516
517    /*! @name User friend interface
518      Problem manipulating functions in the user friend interface
519    */
520    //@{
521
522    //EXPRESSION TYPES
523
524    /// \e
525    typedef Expr<Col, _Value> Expression;
526    /// \e
527    typedef Expr<Row, _Value> DualExpression;
528    /// \e
529    typedef Constr<Col, _Value> Constraint;
530
531    //MATRIX MANIPULATING FUNCTIONS
532
533    /// \e
534    void setRowCoeffs(Row row, const Expression& expr) {
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      }
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;
556    }
557    /// \e
558    /// This routine modifies \c expr by only adding to it.
559    void getRowCoeffs(Row row, Expression& expr) {
560      std::vector<std::pair<int, _Value> > row_coeffs;
561      _getRowCoeffs(row_iter_map[row], row_coeffs);
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
568    void setColCoeffs(Col col, const DualExpression& expr) {
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      }
575      _setColCoeffs(col_iter_map[col], col_coeffs);
576    }
577    /// \e
578    /// This routine modifies \c expr by only adding to it.
579    void getColCoeffs(Col col, DualExpression& expr) {
580      std::vector<std::pair<int, _Value> > col_coeffs;
581      _getColCoeffs(col_iter_map[col], col_coeffs);
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
588    void setObjCoeffs(const Expression& expr) {
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
593      for(typename Expression::Data::const_iterator i=expr.data.begin();
594          i!=expr.data.end(); ++i) {
595        setObjCoeff((*i).first, (*i).second);
596      }
597    }
598    /// \e
599    /// This routine modifies \c expr by only adding to it.
600    void getObjCoeffs(Expression& expr) {
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;
622  public:
623    /// \e
624    void setColCont(Col col) {
625      _setColCont(col_iter_map[col]);
626    }
627    /// \e
628    void setColInt(Col col) {
629      _setColInt(col_iter_map[col]);
630    }
631    //@}
632  };
633 
634  template <typename _Value>
635  const _Value LPSolverBase<_Value>::INF=std::numeric_limits<_Value>::infinity();
636
637
638  /// \brief Wrapper for GLPK solver
639  ///
640  /// This class implements a lemon wrapper for GLPK.
641  class LPGLPK : public LPSolverBase<double> {
642  public:
643    typedef LPSolverBase<double> Parent;
644
645  public:
646    /// \e
647    LPX* lp;
648
649  public:
650    /// \e
651    LPGLPK() : Parent(),
652                        lp(lpx_create_prob()) {
653      int_row_map.push_back(Row());
654      int_col_map.push_back(Col());
655      lpx_set_int_parm(lp, LPX_K_DUAL, 1);
656    }
657    /// \e
658    ~LPGLPK() {
659      lpx_delete_prob(lp);
660    }
661
662    //MATRIX INDEPEDENT MANIPULATING FUNCTIONS
663
664    /// \e
665    void setMinimize() {
666      lpx_set_obj_dir(lp, LPX_MIN);
667    }
668    /// \e
669    void setMaximize() {
670      lpx_set_obj_dir(lp, LPX_MAX);
671    }
672
673    //LOW LEVEL INTERFACE, MATRIX MANIPULATING FUNCTIONS
674
675  protected:
676    /// \e
677    int _addCol() {
678      int i=lpx_add_cols(lp, 1);
679      _setColLowerBound(i, -INF);
680      _setColUpperBound(i, INF);
681      return i;
682    }
683    /// \e
684    int _addRow() {
685      int i=lpx_add_rows(lp, 1);
686      return i;
687    }
688    /// \e
689    virtual void _setRowCoeffs(int i,
690                               const std::vector<std::pair<int, double> >& coeffs) {
691      int mem_length=1+colNum();
692      int* indices = new int[mem_length];
693      double* doubles = new double[mem_length];
694      int length=0;
695      for (std::vector<std::pair<int, double> >::
696             const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
697        ++length;
698        indices[length]=it->first;
699        doubles[length]=it->second;
700      }
701      lpx_set_mat_row(lp, i, length, indices, doubles);
702      delete [] indices;
703      delete [] doubles;
704    }
705    /// \e
706    virtual void _getRowCoeffs(int i,
707                               std::vector<std::pair<int, double> >& coeffs) {
708      int mem_length=1+colNum();
709      int* indices = new int[mem_length];
710      double* doubles = new double[mem_length];
711      int length=lpx_get_mat_row(lp, i, indices, doubles);
712      for (int i=1; i<=length; ++i) {
713        coeffs.push_back(std::make_pair(indices[i], doubles[i]));
714      }
715      delete [] indices;
716      delete [] doubles;
717    }
718    /// \e
719    virtual void _setColCoeffs(int i,
720                               const std::vector<std::pair<int, double> >& coeffs) {
721      int mem_length=1+rowNum();
722      int* indices = new int[mem_length];
723      double* doubles = new double[mem_length];
724      int length=0;
725      for (std::vector<std::pair<int, double> >::
726             const_iterator it=coeffs.begin(); it!=coeffs.end(); ++it) {
727        ++length;
728        indices[length]=it->first;
729        doubles[length]=it->second;
730      }
731      lpx_set_mat_col(lp, i, length, indices, doubles);
732      delete [] indices;
733      delete [] doubles;
734    }
735    /// \e
736    virtual void _getColCoeffs(int i,
737                               std::vector<std::pair<int, double> >& coeffs) {
738      int mem_length=1+rowNum();
739      int* indices = new int[mem_length];
740      double* doubles = new double[mem_length];
741      int length=lpx_get_mat_col(lp, i, indices, doubles);
742      for (int i=1; i<=length; ++i) {
743        coeffs.push_back(std::make_pair(indices[i], doubles[i]));
744      }
745      delete [] indices;
746      delete [] doubles;
747    }
748    /// \e
749    virtual void _eraseCol(int i) {
750      int cols[2];
751      cols[1]=i;
752      lpx_del_cols(lp, 1, cols);
753    }
754    virtual void _eraseRow(int i) {
755      int rows[2];
756      rows[1]=i;
757      lpx_del_rows(lp, 1, rows);
758    }
759    void _setCoeff(int col, int row, double value) {
760      /// FIXME not yet implemented
761    }
762    double _getCoeff(int col, int row) {
763      /// FIXME not yet implemented
764      return 0.0;
765    }
766    virtual void _setColLowerBound(int i, double lo) {
767      if (lo==INF) {
768        //FIXME error
769      }
770      int b=lpx_get_col_type(lp, i);
771      double up=lpx_get_col_ub(lp, i); 
772      if (lo==-INF) {
773        switch (b) {
774        case LPX_FR:
775        case LPX_LO:
776          lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
777          break;
778        case LPX_UP:
779          break;
780        case LPX_DB:
781        case LPX_FX:
782          lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
783          break;
784        default: ;
785          //FIXME error
786        }
787      } else {
788        switch (b) {
789        case LPX_FR:
790        case LPX_LO:
791          lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
792          break;
793        case LPX_UP:     
794        case LPX_DB:
795        case LPX_FX:
796          if (lo==up)
797            lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
798          else
799            lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
800          break;
801        default: ;
802          //FIXME error
803        }
804      }
805    }
806    virtual double _getColLowerBound(int i) {
807      int b=lpx_get_col_type(lp, i);
808      switch (b) {
809      case LPX_FR:
810        return -INF;
811      case LPX_LO:
812        return lpx_get_col_lb(lp, i);
813      case LPX_UP:
814        return -INF;
815      case LPX_DB:
816      case LPX_FX:
817        return lpx_get_col_lb(lp, i);
818      default: ;
819        //FIXME error
820        return 0.0;
821      }
822    }
823    virtual void _setColUpperBound(int i, double up) {
824      if (up==-INF) {
825        //FIXME error
826      }
827      int b=lpx_get_col_type(lp, i);
828      double lo=lpx_get_col_lb(lp, i);
829      if (up==INF) {
830        switch (b) {
831        case LPX_FR:
832        case LPX_LO:
833          break;
834        case LPX_UP:
835          lpx_set_col_bnds(lp, i, LPX_FR, lo, up);
836          break;
837        case LPX_DB:
838        case LPX_FX:
839          lpx_set_col_bnds(lp, i, LPX_LO, lo, up);
840          break;
841        default: ;
842          //FIXME error
843        }
844      } else {
845        switch (b) {
846        case LPX_FR:
847          lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
848        case LPX_LO:
849          if (lo==up)
850            lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
851          else
852            lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
853          break;
854        case LPX_UP:
855          lpx_set_col_bnds(lp, i, LPX_UP, lo, up);
856          break;
857        case LPX_DB:
858        case LPX_FX:
859          if (lo==up)
860            lpx_set_col_bnds(lp, i, LPX_FX, lo, up);
861          else
862            lpx_set_col_bnds(lp, i, LPX_DB, lo, up);
863          break;
864        default: ;
865          //FIXME error
866        }
867      }
868    }
869    virtual double _getColUpperBound(int i) {
870      int b=lpx_get_col_type(lp, i);
871      switch (b) {
872      case LPX_FR:
873      case LPX_LO:
874        return INF;
875      case LPX_UP:
876      case LPX_DB:
877      case LPX_FX:
878        return lpx_get_col_ub(lp, i);
879      default: ;
880        //FIXME error
881        return 0.0;
882      }
883    }
884    virtual void _setRowLowerBound(int i, double lo) {
885      if (lo==INF) {
886        //FIXME error
887      }
888      int b=lpx_get_row_type(lp, i);
889      double up=lpx_get_row_ub(lp, i); 
890      if (lo==-INF) {
891        switch (b) {
892        case LPX_FR:
893        case LPX_LO:
894          lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
895          break;
896        case LPX_UP:
897          break;
898        case LPX_DB:
899        case LPX_FX:
900          lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
901          break;
902        default: ;
903          //FIXME error
904        }
905      } else {
906        switch (b) {
907        case LPX_FR:
908        case LPX_LO:
909          lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
910          break;
911        case LPX_UP:     
912        case LPX_DB:
913        case LPX_FX:
914          if (lo==up)
915            lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
916          else
917            lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
918          break;
919        default: ;
920          //FIXME error
921        }
922      }
923    }
924    virtual double _getRowLowerBound(int i) {
925      int b=lpx_get_row_type(lp, i);
926      switch (b) {
927      case LPX_FR:
928        return -INF;
929      case LPX_LO:
930        return lpx_get_row_lb(lp, i);
931      case LPX_UP:
932        return -INF;
933      case LPX_DB:
934      case LPX_FX:
935        return lpx_get_row_lb(lp, i);
936      default: ;
937        //FIXME error
938        return 0.0;
939      }
940    }
941    virtual void _setRowUpperBound(int i, double up) {
942      if (up==-INF) {
943        //FIXME error
944      }
945      int b=lpx_get_row_type(lp, i);
946      double lo=lpx_get_row_lb(lp, i);
947      if (up==INF) {
948        switch (b) {
949        case LPX_FR:
950        case LPX_LO:
951          break;
952        case LPX_UP:
953          lpx_set_row_bnds(lp, i, LPX_FR, lo, up);
954          break;
955        case LPX_DB:
956        case LPX_FX:
957          lpx_set_row_bnds(lp, i, LPX_LO, lo, up);
958          break;
959        default: ;
960          //FIXME error
961        }
962      } else {
963        switch (b) {
964        case LPX_FR:
965          lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
966        case LPX_LO:
967          if (lo==up)
968            lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
969          else
970            lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
971          break;
972        case LPX_UP:
973          lpx_set_row_bnds(lp, i, LPX_UP, lo, up);
974          break;
975        case LPX_DB:
976        case LPX_FX:
977          if (lo==up)
978            lpx_set_row_bnds(lp, i, LPX_FX, lo, up);
979          else
980            lpx_set_row_bnds(lp, i, LPX_DB, lo, up);
981          break;
982        default: ;
983          //FIXME error
984        }
985      }
986    }
987    virtual double _getRowUpperBound(int i) {
988      int b=lpx_get_row_type(lp, i);
989      switch (b) {
990      case LPX_FR:
991      case LPX_LO:
992        return INF;
993      case LPX_UP:
994      case LPX_DB:
995      case LPX_FX:
996        return lpx_get_row_ub(lp, i);
997      default: ;
998        //FIXME error
999        return 0.0;
1000      }
1001    }
1002    /// \e
1003    virtual double _getObjCoeff(int i) {
1004      return lpx_get_obj_coef(lp, i);
1005    }
1006    /// \e
1007    virtual void _setObjCoeff(int i, double obj_coef) {
1008      lpx_set_obj_coef(lp, i, obj_coef);
1009    }
1010  public:
1011    /// \e
1012    void solveSimplex() { lpx_simplex(lp); }
1013    /// \e
1014    void solvePrimalSimplex() { lpx_simplex(lp); }
1015    /// \e
1016    void solveDualSimplex() { lpx_simplex(lp); }
1017  protected:
1018    virtual double _getPrimal(int i) {
1019      return lpx_get_col_prim(lp, i);
1020    }
1021  public:
1022    /// \e
1023    double getObjVal() { return lpx_get_obj_val(lp); }
1024    /// \e
1025    int rowNum() const { return lpx_get_num_rows(lp); }
1026    /// \e
1027    int colNum() const { return lpx_get_num_cols(lp); }
1028    /// \e
1029    int warmUp() { return lpx_warm_up(lp); }
1030    /// \e
1031    void printWarmUpStatus(int i) {
1032      switch (i) {
1033      case LPX_E_OK: cout << "LPX_E_OK" << endl; break;
1034      case LPX_E_EMPTY: cout << "LPX_E_EMPTY" << endl; break;   
1035      case LPX_E_BADB: cout << "LPX_E_BADB" << endl; break;
1036      case LPX_E_SING: cout << "LPX_E_SING" << endl; break;
1037      }
1038    }
1039    /// \e
1040    int getPrimalStatus() { return lpx_get_prim_stat(lp); }
1041    /// \e
1042    void printPrimalStatus(int i) {
1043      switch (i) {
1044      case LPX_P_UNDEF: cout << "LPX_P_UNDEF" << endl; break;
1045      case LPX_P_FEAS: cout << "LPX_P_FEAS" << endl; break;     
1046      case LPX_P_INFEAS: cout << "LPX_P_INFEAS" << endl; break;
1047      case LPX_P_NOFEAS: cout << "LPX_P_NOFEAS" << endl; break;
1048      }
1049    }
1050    /// \e
1051    int getDualStatus() { return lpx_get_dual_stat(lp); }
1052    /// \e
1053    void printDualStatus(int i) {
1054      switch (i) {
1055      case LPX_D_UNDEF: cout << "LPX_D_UNDEF" << endl; break;
1056      case LPX_D_FEAS: cout << "LPX_D_FEAS" << endl; break;     
1057      case LPX_D_INFEAS: cout << "LPX_D_INFEAS" << endl; break;
1058      case LPX_D_NOFEAS: cout << "LPX_D_NOFEAS" << endl; break;
1059      }
1060    }
1061    /// Returns the status of the slack variable assigned to row \c row.
1062    int getRowStat(const Row& row) {
1063      return lpx_get_row_stat(lp, row_iter_map[row]);
1064    }
1065    /// \e
1066    void printRowStatus(int i) {
1067      switch (i) {
1068      case LPX_BS: cout << "LPX_BS" << endl; break;
1069      case LPX_NL: cout << "LPX_NL" << endl; break;     
1070      case LPX_NU: cout << "LPX_NU" << endl; break;
1071      case LPX_NF: cout << "LPX_NF" << endl; break;
1072      case LPX_NS: cout << "LPX_NS" << endl; break;
1073      }
1074    }
1075    /// Returns the status of the variable assigned to column \c col.
1076    int getColStat(const Col& col) {
1077      return lpx_get_col_stat(lp, col_iter_map[col]);
1078    }
1079    /// \e
1080    void printColStatus(int i) {
1081      switch (i) {
1082      case LPX_BS: cout << "LPX_BS" << endl; break;
1083      case LPX_NL: cout << "LPX_NL" << endl; break;     
1084      case LPX_NU: cout << "LPX_NU" << endl; break;
1085      case LPX_NF: cout << "LPX_NF" << endl; break;
1086      case LPX_NS: cout << "LPX_NS" << endl; break;
1087      }
1088    }
1089
1090    // MIP
1091    /// \e
1092    void solveBandB() { lpx_integer(lp); }
1093    /// \e
1094    void setLP() { lpx_set_class(lp, LPX_LP); }
1095    /// \e
1096    void setMIP() { lpx_set_class(lp, LPX_MIP); }
1097  protected:
1098    /// \e
1099    void _setColCont(int i) {lpx_set_col_kind(lp, i, LPX_CV); }
1100    /// \e
1101    void _setColInt(int i) {lpx_set_col_kind(lp, i, LPX_IV); }
1102  };
1103 
1104  /// @}
1105
1106} //namespace lemon
1107
1108#endif //LEMON_LP_SOLVER_BASE_H
Note: See TracBrowser for help on using the repository browser.