lemon/soplex.h
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:26:13 +0100
changeset 806 fa6f37d7a25b
parent 576 745e182d0139
child 877 141f9c0db4a3
permissions -rw-r--r--
Entirely rework CapacityScaling (#180)

- Use the new interface similarly to NetworkSimplex.
- Rework the implementation using an efficient internal structure
for handling the residual network. This improvement made the
code much faster (up to 2-5 times faster on large graphs).
- Handle GEQ supply type (LEQ is not supported).
- Handle negative costs for arcs of finite capacity.
(Note that this algorithm cannot handle arcs of negative cost
and infinite upper bound, thus it returns UNBOUNDED if such
an arc exists.)
- Extend the documentation.
     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_SOPLEX_H
    20 #define LEMON_SOPLEX_H
    21 
    22 ///\file
    23 ///\brief Header of the LEMON-SOPLEX lp solver interface.
    24 
    25 #include <vector>
    26 #include <string>
    27 
    28 #include <lemon/lp_base.h>
    29 
    30 // Forward declaration
    31 namespace soplex {
    32   class SoPlex;
    33 }
    34 
    35 namespace lemon {
    36 
    37   /// \ingroup lp_group
    38   ///
    39   /// \brief Interface for the SOPLEX solver
    40   ///
    41   /// This class implements an interface for the SoPlex LP solver.
    42   /// The SoPlex library is an object oriented lp solver library
    43   /// developed at the Konrad-Zuse-Zentrum für Informationstechnik
    44   /// Berlin (ZIB). You can find detailed information about it at the
    45   /// <tt>http://soplex.zib.de</tt> address.
    46   class SoplexLp : public LpSolver {
    47   private:
    48 
    49     soplex::SoPlex* soplex;
    50 
    51     std::vector<std::string> _col_names;
    52     std::map<std::string, int> _col_names_ref;
    53 
    54     std::vector<std::string> _row_names;
    55     std::map<std::string, int> _row_names_ref;
    56 
    57   private:
    58 
    59     // these values cannot be retrieved element by element
    60     mutable std::vector<Value> _primal_values;
    61     mutable std::vector<Value> _dual_values;
    62 
    63     mutable std::vector<Value> _primal_ray;
    64     mutable std::vector<Value> _dual_ray;
    65 
    66     void _clear_temporals();
    67 
    68   public:
    69 
    70     /// \e
    71     SoplexLp();
    72     /// \e
    73     SoplexLp(const SoplexLp&);
    74     /// \e
    75     ~SoplexLp();
    76     /// \e
    77     virtual SoplexLp* newSolver() const;
    78     /// \e
    79     virtual SoplexLp* cloneSolver() const;
    80 
    81   protected:
    82 
    83     virtual const char* _solverName() const;
    84 
    85     virtual int _addCol();
    86     virtual int _addRow();
    87     virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
    88 
    89     virtual void _eraseCol(int i);
    90     virtual void _eraseRow(int i);
    91 
    92     virtual void _eraseColId(int i);
    93     virtual void _eraseRowId(int i);
    94 
    95     virtual void _getColName(int col, std::string& name) const;
    96     virtual void _setColName(int col, const std::string& name);
    97     virtual int _colByName(const std::string& name) const;
    98 
    99     virtual void _getRowName(int row, std::string& name) const;
   100     virtual void _setRowName(int row, const std::string& name);
   101     virtual int _rowByName(const std::string& name) const;
   102 
   103     virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e);
   104     virtual void _getRowCoeffs(int i, InsertIterator b) const;
   105 
   106     virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e);
   107     virtual void _getColCoeffs(int i, InsertIterator b) const;
   108 
   109     virtual void _setCoeff(int row, int col, Value value);
   110     virtual Value _getCoeff(int row, int col) const;
   111 
   112     virtual void _setColLowerBound(int i, Value value);
   113     virtual Value _getColLowerBound(int i) const;
   114     virtual void _setColUpperBound(int i, Value value);
   115     virtual Value _getColUpperBound(int i) const;
   116 
   117     virtual void _setRowLowerBound(int i, Value value);
   118     virtual Value _getRowLowerBound(int i) const;
   119     virtual void _setRowUpperBound(int i, Value value);
   120     virtual Value _getRowUpperBound(int i) const;
   121 
   122     virtual void _setObjCoeffs(ExprIterator b, ExprIterator e);
   123     virtual void _getObjCoeffs(InsertIterator b) const;
   124 
   125     virtual void _setObjCoeff(int i, Value obj_coef);
   126     virtual Value _getObjCoeff(int i) const;
   127 
   128     virtual void _setSense(Sense sense);
   129     virtual Sense _getSense() const;
   130 
   131     virtual SolveExitStatus _solve();
   132     virtual Value _getPrimal(int i) const;
   133     virtual Value _getDual(int i) const;
   134 
   135     virtual Value _getPrimalValue() const;
   136 
   137     virtual Value _getPrimalRay(int i) const;
   138     virtual Value _getDualRay(int i) const;
   139 
   140     virtual VarStatus _getColStatus(int i) const;
   141     virtual VarStatus _getRowStatus(int i) const;
   142 
   143     virtual ProblemType _getPrimalType() const;
   144     virtual ProblemType _getDualType() const;
   145 
   146     virtual void _clear();
   147 
   148     void _messageLevel(MessageLevel m);
   149     void _applyMessageLevel();
   150 
   151     int _message_level;
   152 
   153   };
   154 
   155 } //END OF NAMESPACE LEMON
   156 
   157 #endif //LEMON_SOPLEX_H
   158