lemon/clp.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 03 Apr 2009 18:59:15 +0200
changeset 608 6ac5d9ae1d3d
parent 461 08d495d48089
child 540 9db62975c32b
permissions -rw-r--r--
Support real types + numerical stability fix in NS (#254)

- Real types are supported by appropriate inicialization.
- A feature of the XTI spanning tree structure is removed to ensure
numerical stability (could cause problems using integer types).
The node potentials are updated always on the lower subtree,
in order to prevent overflow problems.
The former method isn't notably faster during to our tests.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_CLP_H
    20 #define LEMON_CLP_H
    21 
    22 ///\file
    23 ///\brief Header of the LEMON-CLP lp solver interface.
    24 
    25 #include <vector>
    26 #include <string>
    27 
    28 #include <lemon/lp_base.h>
    29 
    30 class ClpSimplex;
    31 
    32 namespace lemon {
    33 
    34   /// \ingroup lp_group
    35   ///
    36   /// \brief Interface for the CLP solver
    37   ///
    38   /// This class implements an interface for the Clp LP solver.  The
    39   /// Clp library is an object oriented lp solver library developed at
    40   /// the IBM. The CLP is part of the COIN-OR package and it can be
    41   /// used with Common Public License.
    42   class ClpLp : public LpSolver {
    43   protected:
    44 
    45     ClpSimplex* _prob;
    46 
    47     std::map<std::string, int> _col_names_ref;
    48     std::map<std::string, int> _row_names_ref;
    49 
    50   public:
    51 
    52     /// \e
    53     ClpLp();
    54     /// \e
    55     ClpLp(const ClpLp&);
    56     /// \e
    57     ~ClpLp();
    58 
    59   protected:
    60 
    61     mutable double* _primal_ray;
    62     mutable double* _dual_ray;
    63 
    64     void _init_temporals();
    65     void _clear_temporals();
    66 
    67   protected:
    68 
    69     virtual ClpLp* _newSolver() const;
    70     virtual ClpLp* _cloneSolver() const;
    71 
    72     virtual const char* _solverName() const;
    73 
    74     virtual int _addCol();
    75     virtual int _addRow();
    76 
    77     virtual void _eraseCol(int i);
    78     virtual void _eraseRow(int i);
    79 
    80     virtual void _eraseColId(int i);
    81     virtual void _eraseRowId(int i);
    82 
    83     virtual void _getColName(int col, std::string& name) const;
    84     virtual void _setColName(int col, const std::string& name);
    85     virtual int _colByName(const std::string& name) const;
    86 
    87     virtual void _getRowName(int row, std::string& name) const;
    88     virtual void _setRowName(int row, const std::string& name);
    89     virtual int _rowByName(const std::string& name) const;
    90 
    91     virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e);
    92     virtual void _getRowCoeffs(int i, InsertIterator b) const;
    93 
    94     virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e);
    95     virtual void _getColCoeffs(int i, InsertIterator b) const;
    96 
    97     virtual void _setCoeff(int row, int col, Value value);
    98     virtual Value _getCoeff(int row, int col) const;
    99 
   100     virtual void _setColLowerBound(int i, Value value);
   101     virtual Value _getColLowerBound(int i) const;
   102     virtual void _setColUpperBound(int i, Value value);
   103     virtual Value _getColUpperBound(int i) const;
   104 
   105     virtual void _setRowLowerBound(int i, Value value);
   106     virtual Value _getRowLowerBound(int i) const;
   107     virtual void _setRowUpperBound(int i, Value value);
   108     virtual Value _getRowUpperBound(int i) const;
   109 
   110     virtual void _setObjCoeffs(ExprIterator, ExprIterator);
   111     virtual void _getObjCoeffs(InsertIterator) const;
   112 
   113     virtual void _setObjCoeff(int i, Value obj_coef);
   114     virtual Value _getObjCoeff(int i) const;
   115 
   116     virtual void _setSense(Sense sense);
   117     virtual Sense _getSense() const;
   118 
   119     virtual SolveExitStatus _solve();
   120 
   121     virtual Value _getPrimal(int i) const;
   122     virtual Value _getDual(int i) const;
   123 
   124     virtual Value _getPrimalValue() const;
   125 
   126     virtual Value _getPrimalRay(int i) const;
   127     virtual Value _getDualRay(int i) const;
   128 
   129     virtual VarStatus _getColStatus(int i) const;
   130     virtual VarStatus _getRowStatus(int i) const;
   131 
   132     virtual ProblemType _getPrimalType() const;
   133     virtual ProblemType _getDualType() const;
   134 
   135     virtual void _clear();
   136 
   137   public:
   138 
   139     ///Solves LP with primal simplex method.
   140     SolveExitStatus solvePrimal();
   141 
   142     ///Solves LP with dual simplex method.
   143     SolveExitStatus solveDual();
   144 
   145     ///Solves LP with barrier method.
   146     SolveExitStatus solveBarrier();
   147 
   148     ///Returns the constraint identifier understood by CLP.
   149     int clpRow(Row r) const { return rows(id(r)); }
   150 
   151     ///Returns the variable identifier understood by CLP.
   152     int clpCol(Col c) const { return cols(id(c)); }
   153 
   154     ///Enum for \c messageLevel() parameter
   155     enum MessageLevel {
   156       /// no output (default value)
   157       MESSAGE_NO_OUTPUT = 0,
   158       /// print final solution
   159       MESSAGE_FINAL_SOLUTION = 1,
   160       /// print factorization
   161       MESSAGE_FACTORIZATION = 2,
   162       /// normal output
   163       MESSAGE_NORMAL_OUTPUT = 3,
   164       /// verbose output
   165       MESSAGE_VERBOSE_OUTPUT = 4
   166     };
   167     ///Set the verbosity of the messages
   168 
   169     ///Set the verbosity of the messages
   170     ///
   171     ///\param m is the level of the messages output by the solver routines.
   172     void messageLevel(MessageLevel m);
   173 
   174   };
   175 
   176 } //END OF NAMESPACE LEMON
   177 
   178 #endif //LEMON_CLP_H
   179