lemon/soplex.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_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 
    77   protected:
    78 
    79     virtual SoplexLp* _newSolver() const;
    80     virtual SoplexLp* _cloneSolver() const;
    81 
    82     virtual const char* _solverName() const;
    83 
    84     virtual int _addCol();
    85     virtual int _addRow();
    86 
    87     virtual void _eraseCol(int i);
    88     virtual void _eraseRow(int i);
    89 
    90     virtual void _eraseColId(int i);
    91     virtual void _eraseRowId(int i);
    92 
    93     virtual void _getColName(int col, std::string& name) const;
    94     virtual void _setColName(int col, const std::string& name);
    95     virtual int _colByName(const std::string& name) const;
    96 
    97     virtual void _getRowName(int row, std::string& name) const;
    98     virtual void _setRowName(int row, const std::string& name);
    99     virtual int _rowByName(const std::string& name) const;
   100 
   101     virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e);
   102     virtual void _getRowCoeffs(int i, InsertIterator b) const;
   103 
   104     virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e);
   105     virtual void _getColCoeffs(int i, InsertIterator b) const;
   106 
   107     virtual void _setCoeff(int row, int col, Value value);
   108     virtual Value _getCoeff(int row, int col) const;
   109 
   110     virtual void _setColLowerBound(int i, Value value);
   111     virtual Value _getColLowerBound(int i) const;
   112     virtual void _setColUpperBound(int i, Value value);
   113     virtual Value _getColUpperBound(int i) const;
   114 
   115     virtual void _setRowLowerBound(int i, Value value);
   116     virtual Value _getRowLowerBound(int i) const;
   117     virtual void _setRowUpperBound(int i, Value value);
   118     virtual Value _getRowUpperBound(int i) const;
   119 
   120     virtual void _setObjCoeffs(ExprIterator b, ExprIterator e);
   121     virtual void _getObjCoeffs(InsertIterator b) const;
   122 
   123     virtual void _setObjCoeff(int i, Value obj_coef);
   124     virtual Value _getObjCoeff(int i) const;
   125 
   126     virtual void _setSense(Sense sense);
   127     virtual Sense _getSense() const;
   128 
   129     virtual SolveExitStatus _solve();
   130     virtual Value _getPrimal(int i) const;
   131     virtual Value _getDual(int i) const;
   132 
   133     virtual Value _getPrimalValue() const;
   134 
   135     virtual Value _getPrimalRay(int i) const;
   136     virtual Value _getDualRay(int i) const;
   137 
   138     virtual VarStatus _getColStatus(int i) const;
   139     virtual VarStatus _getRowStatus(int i) const;
   140 
   141     virtual ProblemType _getPrimalType() const;
   142     virtual ProblemType _getDualType() const;
   143 
   144     virtual void _clear();
   145 
   146   };
   147 
   148 } //END OF NAMESPACE LEMON
   149 
   150 #endif //LEMON_SOPLEX_H
   151