lemon/lp_skeleton.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 20 Feb 2010 18:39:03 +0100
changeset 839 f3bc4e9b5f3a
parent 576 745e182d0139
child 877 141f9c0db4a3
permissions -rw-r--r--
New heuristics for MCF algorithms (#340)
and some implementation improvements.

- A useful heuristic is added to NetworkSimplex to make the
initial pivots faster.
- A powerful global update heuristic is added to CostScaling
and the implementation is reworked with various improvements.
- Better relabeling in CostScaling to improve numerical stability
and make the code faster.
- A small improvement is made in CapacityScaling for better
delta computation.
- Add notes to the classes about the usage of vector<char> instead
of vector<bool> for efficiency reasons.
     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_LP_SKELETON_H
    20 #define LEMON_LP_SKELETON_H
    21 
    22 #include <lemon/lp_base.h>
    23 
    24 ///\file
    25 ///\brief Skeleton file to implement LP/MIP solver interfaces
    26 ///  
    27 ///The classes in this file do nothing, but they can serve as skeletons when
    28 ///implementing an interface to new solvers.
    29 namespace lemon {
    30 
    31   ///A skeleton class to implement LP/MIP solver base interface
    32   
    33   ///This class does nothing, but it can serve as a skeleton when
    34   ///implementing an interface to new solvers.
    35   class SkeletonSolverBase : public virtual LpBase {
    36     int col_num,row_num;
    37 
    38   protected:
    39 
    40     SkeletonSolverBase()
    41       : col_num(-1), row_num(-1) {}
    42 
    43     /// \e
    44     virtual int _addCol();
    45     /// \e
    46     virtual int _addRow();
    47     /// \e
    48     virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u);
    49     /// \e
    50     virtual void _eraseCol(int i);
    51     /// \e
    52     virtual void _eraseRow(int i);
    53 
    54     /// \e
    55     virtual void _getColName(int col, std::string& name) const;
    56     /// \e
    57     virtual void _setColName(int col, const std::string& name);
    58     /// \e
    59     virtual int _colByName(const std::string& name) const;
    60 
    61     /// \e
    62     virtual void _getRowName(int row, std::string& name) const;
    63     /// \e
    64     virtual void _setRowName(int row, const std::string& name);
    65     /// \e
    66     virtual int _rowByName(const std::string& name) const;
    67 
    68     /// \e
    69     virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e);
    70     /// \e
    71     virtual void _getRowCoeffs(int i, InsertIterator b) const;
    72     /// \e
    73     virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e);
    74     /// \e
    75     virtual void _getColCoeffs(int i, InsertIterator b) const;
    76 
    77     /// Set one element of the coefficient matrix
    78     virtual void _setCoeff(int row, int col, Value value);
    79 
    80     /// Get one element of the coefficient matrix
    81     virtual Value _getCoeff(int row, int col) const;
    82 
    83     /// The lower bound of a variable (column) have to be given by an
    84     /// extended number of type Value, i.e. a finite number of type
    85     /// Value or -\ref INF.
    86     virtual void _setColLowerBound(int i, Value value);
    87     /// \e
    88 
    89     /// The lower bound of a variable (column) is an
    90     /// extended number of type Value, i.e. a finite number of type
    91     /// Value or -\ref INF.
    92     virtual Value _getColLowerBound(int i) const;
    93 
    94     /// The upper bound of a variable (column) have to be given by an
    95     /// extended number of type Value, i.e. a finite number of type
    96     /// Value or \ref INF.
    97     virtual void _setColUpperBound(int i, Value value);
    98     /// \e
    99 
   100     /// The upper bound of a variable (column) is an
   101     /// extended number of type Value, i.e. a finite number of type
   102     /// Value or \ref INF.
   103     virtual Value _getColUpperBound(int i) const;
   104 
   105     /// The lower bound of a constraint (row) have to be given by an
   106     /// extended number of type Value, i.e. a finite number of type
   107     /// Value or -\ref INF.
   108     virtual void _setRowLowerBound(int i, Value value);
   109     /// \e
   110 
   111     /// The lower bound of a constraint (row) is an
   112     /// extended number of type Value, i.e. a finite number of type
   113     /// Value or -\ref INF.
   114     virtual Value _getRowLowerBound(int i) const;
   115 
   116     /// The upper bound of a constraint (row) have to be given by an
   117     /// extended number of type Value, i.e. a finite number of type
   118     /// Value or \ref INF.
   119     virtual void _setRowUpperBound(int i, Value value);
   120     /// \e
   121 
   122     /// The upper bound of a constraint (row) is an
   123     /// extended number of type Value, i.e. a finite number of type
   124     /// Value or \ref INF.
   125     virtual Value _getRowUpperBound(int i) const;
   126 
   127     /// \e
   128     virtual void _setObjCoeffs(ExprIterator b, ExprIterator e);
   129     /// \e
   130     virtual void _getObjCoeffs(InsertIterator b) const;
   131 
   132     /// \e
   133     virtual void _setObjCoeff(int i, Value obj_coef);
   134     /// \e
   135     virtual Value _getObjCoeff(int i) const;
   136 
   137     ///\e
   138     virtual void _setSense(Sense);
   139     ///\e
   140     virtual Sense _getSense() const;
   141 
   142     ///\e
   143     virtual void _clear();
   144 
   145     ///\e
   146     virtual void _messageLevel(MessageLevel);
   147   };
   148 
   149   /// \brief Skeleton class for an LP solver interface
   150   ///
   151   ///This class does nothing, but it can serve as a skeleton when
   152   ///implementing an interface to new solvers.
   153 
   154   ///\ingroup lp_group
   155   class LpSkeleton : public LpSolver, public SkeletonSolverBase {
   156   public:
   157     ///\e
   158     LpSkeleton() : LpSolver(), SkeletonSolverBase() {}
   159     ///\e
   160     virtual LpSkeleton* newSolver() const;
   161     ///\e
   162     virtual LpSkeleton* cloneSolver() const;
   163   protected:
   164 
   165     ///\e
   166     virtual SolveExitStatus _solve();
   167 
   168     ///\e
   169     virtual Value _getPrimal(int i) const;
   170     ///\e
   171     virtual Value _getDual(int i) const;
   172 
   173     ///\e
   174     virtual Value _getPrimalValue() const;
   175 
   176     ///\e
   177     virtual Value _getPrimalRay(int i) const;
   178     ///\e
   179     virtual Value _getDualRay(int i) const;
   180 
   181     ///\e
   182     virtual ProblemType _getPrimalType() const;
   183     ///\e
   184     virtual ProblemType _getDualType() const;
   185 
   186     ///\e
   187     virtual VarStatus _getColStatus(int i) const;
   188     ///\e
   189     virtual VarStatus _getRowStatus(int i) const;
   190 
   191     ///\e
   192     virtual const char* _solverName() const;
   193 
   194   };
   195 
   196   /// \brief Skeleton class for a MIP solver interface
   197   ///
   198   ///This class does nothing, but it can serve as a skeleton when
   199   ///implementing an interface to new solvers.
   200   ///\ingroup lp_group
   201   class MipSkeleton : public MipSolver, public SkeletonSolverBase {
   202   public:
   203     ///\e
   204     MipSkeleton() : MipSolver(), SkeletonSolverBase() {}
   205     ///\e
   206     virtual MipSkeleton* newSolver() const;
   207     ///\e
   208     virtual MipSkeleton* cloneSolver() const;
   209 
   210   protected:
   211     ///\e
   212     virtual SolveExitStatus _solve();
   213 
   214     ///\e
   215     virtual Value _getSol(int i) const;
   216 
   217     ///\e
   218     virtual Value _getSolValue() const;
   219 
   220     ///\e
   221     virtual ProblemType _getType() const;
   222 
   223     ///\e
   224     virtual const char* _solverName() const;
   225   };
   226 
   227 } //namespace lemon
   228 
   229 #endif