lemon/cplex.h
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 461 08d495d48089
child 540 9db62975c32b
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
     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_CPLEX_H
    20 #define LEMON_CPLEX_H
    21 
    22 ///\file
    23 ///\brief Header of the LEMON-CPLEX lp solver interface.
    24 
    25 #include <lemon/lp_base.h>
    26 
    27 struct cpxenv;
    28 struct cpxlp;
    29 
    30 namespace lemon {
    31 
    32   /// \brief Reference counted wrapper around cpxenv pointer
    33   ///
    34   /// The cplex uses environment object which is responsible for
    35   /// checking the proper license usage. This class provides a simple
    36   /// interface for share the environment object between different
    37   /// problems.
    38   class CplexEnv {
    39     friend class CplexBase;
    40   private:
    41     cpxenv* _env;
    42     mutable int* _cnt;
    43 
    44   public:
    45 
    46     /// \brief This exception is thrown when the license check is not
    47     /// sufficient
    48     class LicenseError : public Exception {
    49       friend class CplexEnv;
    50     private:
    51 
    52       LicenseError(int status);
    53       char _message[510];
    54 
    55     public:
    56 
    57       /// The short error message
    58       virtual const char* what() const throw() {
    59         return _message;
    60       }
    61     };
    62 
    63     /// Constructor
    64     CplexEnv();
    65     /// Shallow copy constructor
    66     CplexEnv(const CplexEnv&);
    67     /// Shallow assignement
    68     CplexEnv& operator=(const CplexEnv&);
    69     /// Destructor
    70     virtual ~CplexEnv();
    71 
    72   protected:
    73 
    74     cpxenv* cplexEnv() { return _env; }
    75     const cpxenv* cplexEnv() const { return _env; }
    76   };
    77 
    78   /// \brief Base interface for the CPLEX LP and MIP solver
    79   ///
    80   /// This class implements the common interface of the CPLEX LP and
    81   /// MIP solvers.  
    82   /// \ingroup lp_group
    83   class CplexBase : virtual public LpBase {
    84   protected:
    85 
    86     CplexEnv _env;
    87     cpxlp* _prob;
    88 
    89     CplexBase();
    90     CplexBase(const CplexEnv&);
    91     CplexBase(const CplexBase &);
    92     virtual ~CplexBase();
    93 
    94     virtual int _addCol();
    95     virtual int _addRow();
    96 
    97     virtual void _eraseCol(int i);
    98     virtual void _eraseRow(int i);
    99 
   100     virtual void _eraseColId(int i);
   101     virtual void _eraseRowId(int i);
   102 
   103     virtual void _getColName(int col, std::string& name) const;
   104     virtual void _setColName(int col, const std::string& name);
   105     virtual int _colByName(const std::string& name) const;
   106 
   107     virtual void _getRowName(int row, std::string& name) const;
   108     virtual void _setRowName(int row, const std::string& name);
   109     virtual int _rowByName(const std::string& name) const;
   110 
   111     virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e);
   112     virtual void _getRowCoeffs(int i, InsertIterator b) const;
   113 
   114     virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e);
   115     virtual void _getColCoeffs(int i, InsertIterator b) const;
   116 
   117     virtual void _setCoeff(int row, int col, Value value);
   118     virtual Value _getCoeff(int row, int col) const;
   119 
   120     virtual void _setColLowerBound(int i, Value value);
   121     virtual Value _getColLowerBound(int i) const;
   122 
   123     virtual void _setColUpperBound(int i, Value value);
   124     virtual Value _getColUpperBound(int i) const;
   125 
   126   private:
   127     void _set_row_bounds(int i, Value lb, Value ub);
   128   protected:
   129 
   130     virtual void _setRowLowerBound(int i, Value value);
   131     virtual Value _getRowLowerBound(int i) const;
   132 
   133     virtual void _setRowUpperBound(int i, Value value);
   134     virtual Value _getRowUpperBound(int i) const;
   135 
   136     virtual void _setObjCoeffs(ExprIterator b, ExprIterator e);
   137     virtual void _getObjCoeffs(InsertIterator b) const;
   138 
   139     virtual void _setObjCoeff(int i, Value obj_coef);
   140     virtual Value _getObjCoeff(int i) const;
   141 
   142     virtual void _setSense(Sense sense);
   143     virtual Sense _getSense() const;
   144 
   145     virtual void _clear();
   146 
   147   public:
   148 
   149     /// Returns the used \c CplexEnv instance
   150     const CplexEnv& env() const { return _env; }
   151     ///
   152     const cpxenv* cplexEnv() const { return _env.cplexEnv(); }
   153 
   154     cpxlp* cplexLp() { return _prob; }
   155     const cpxlp* cplexLp() const { return _prob; }
   156 
   157   };
   158 
   159   /// \brief Interface for the CPLEX LP solver
   160   ///
   161   /// This class implements an interface for the CPLEX LP solver.
   162   ///\ingroup lp_group
   163   class CplexLp : public CplexBase, public LpSolver {
   164   public:
   165     /// \e
   166     CplexLp();
   167     /// \e
   168     CplexLp(const CplexEnv&);
   169     /// \e
   170     CplexLp(const CplexLp&);
   171     /// \e
   172     virtual ~CplexLp();
   173 
   174   private:
   175 
   176     // these values cannot retrieved element by element
   177     mutable std::vector<int> _col_status;
   178     mutable std::vector<int> _row_status;
   179 
   180     mutable std::vector<Value> _primal_ray;
   181     mutable std::vector<Value> _dual_ray;
   182 
   183     void _clear_temporals();
   184 
   185     SolveExitStatus convertStatus(int status);
   186 
   187   protected:
   188 
   189     virtual CplexLp* _cloneSolver() const;
   190     virtual CplexLp* _newSolver() const;
   191 
   192     virtual const char* _solverName() const;
   193 
   194     virtual SolveExitStatus _solve();
   195     virtual Value _getPrimal(int i) const;
   196     virtual Value _getDual(int i) const;
   197     virtual Value _getPrimalValue() const;
   198 
   199     virtual VarStatus _getColStatus(int i) const;
   200     virtual VarStatus _getRowStatus(int i) const;
   201 
   202     virtual Value _getPrimalRay(int i) const;
   203     virtual Value _getDualRay(int i) const;
   204 
   205     virtual ProblemType _getPrimalType() const;
   206     virtual ProblemType _getDualType() const;
   207 
   208   public:
   209 
   210     /// Solve with primal simplex method
   211     SolveExitStatus solvePrimal();
   212 
   213     /// Solve with dual simplex method
   214     SolveExitStatus solveDual();
   215 
   216     /// Solve with barrier method
   217     SolveExitStatus solveBarrier();
   218 
   219   };
   220 
   221   /// \brief Interface for the CPLEX MIP solver
   222   ///
   223   /// This class implements an interface for the CPLEX MIP solver.
   224   ///\ingroup lp_group
   225   class CplexMip : public CplexBase, public MipSolver {
   226   public:
   227     /// \e
   228     CplexMip();
   229     /// \e
   230     CplexMip(const CplexEnv&);
   231     /// \e
   232     CplexMip(const CplexMip&);
   233     /// \e
   234     virtual ~CplexMip();
   235 
   236   protected:
   237 
   238     virtual CplexMip* _cloneSolver() const;
   239     virtual CplexMip* _newSolver() const;
   240 
   241     virtual const char* _solverName() const;
   242 
   243     virtual ColTypes _getColType(int col) const;
   244     virtual void _setColType(int col, ColTypes col_type);
   245 
   246     virtual SolveExitStatus _solve();
   247     virtual ProblemType _getType() const;
   248     virtual Value _getSol(int i) const;
   249     virtual Value _getSolValue() const;
   250 
   251   };
   252 
   253 } //END OF NAMESPACE LEMON
   254 
   255 #endif //LEMON_CPLEX_H
   256