diff options
Diffstat (limited to 'thirdparty/linux/include/coin/CbcFathomDynamicProgramming.hpp')
| -rw-r--r-- | thirdparty/linux/include/coin/CbcFathomDynamicProgramming.hpp | 169 |
1 files changed, 169 insertions, 0 deletions
diff --git a/thirdparty/linux/include/coin/CbcFathomDynamicProgramming.hpp b/thirdparty/linux/include/coin/CbcFathomDynamicProgramming.hpp new file mode 100644 index 0000000..7f38987 --- /dev/null +++ b/thirdparty/linux/include/coin/CbcFathomDynamicProgramming.hpp @@ -0,0 +1,169 @@ +/* $Id: CbcFathomDynamicProgramming.hpp 1573 2011-01-05 01:12:36Z lou $ */ +// Copyright (C) 2004, International Business Machines +// Corporation and others. All Rights Reserved. +// This code is licensed under the terms of the Eclipse Public License (EPL). + +#ifndef CbcFathomDynamicProgramming_H +#define CbcFathomDynamicProgramming_H + +#include "CbcFathom.hpp" + +//############################################################################# +/** FathomDynamicProgramming class. + + The idea is that after some branching the problem will be effectively smaller than + the original problem and maybe there will be a more specialized technique which can completely + fathom this branch quickly. + + This is a dynamic programming implementation which is very fast for some + specialized problems. It expects small integral rhs, an all integer problem + and positive integral coefficients. At present it can not do general set covering + problems just set partitioning. It can find multiple optima for various rhs + combinations. + + The main limiting factor is size of state space. Each 1 rhs doubles the size of the problem. + 2 or 3 rhs quadruples, 4,5,6,7 by 8 etc. + */ + +class CbcFathomDynamicProgramming : public CbcFathom { +public: + // Default Constructor + CbcFathomDynamicProgramming (); + + // Constructor with model - assumed before cuts + CbcFathomDynamicProgramming (CbcModel & model); + // Copy constructor + CbcFathomDynamicProgramming(const CbcFathomDynamicProgramming & rhs); + + virtual ~CbcFathomDynamicProgramming(); + + /// update model (This is needed if cliques update matrix etc) + virtual void setModel(CbcModel * model); + + /// Clone + virtual CbcFathom * clone() const; + + /// Resets stuff if model changes + virtual void resetModel(CbcModel * model); + + /** returns 0 if no fathoming attempted, 1 fully fathomed , + 2 incomplete search, 3 incomplete search but treat as complete. + If solution then newSolution will not be NULL and + will be freed by CbcModel. It is expected that the solution is better + than best so far but CbcModel will double check. + + If returns 3 then of course there is no guarantee of global optimum + */ + virtual int fathom(double *& newSolution); + + /// Maximum size allowed + inline int maximumSize() const { + return maximumSizeAllowed_; + } + inline void setMaximumSize(int value) { + maximumSizeAllowed_ = value; + } + /// Returns type of algorithm and sets up arrays + int checkPossible(int allowableSize = 0); + // set algorithm + inline void setAlgorithm(int value) { + algorithm_ = value; + } + /** Tries a column + returns true if was used in making any changes. + */ + bool tryColumn(int numberElements, const int * rows, + const double * coefficients, double cost, + int upper = COIN_INT_MAX); + /// Returns cost array + inline const double * cost() const { + return cost_; + } + /// Returns back array + inline const int * back() const { + return back_; + } + /// Gets bit pattern for target result + inline int target() const { + return target_; + } + /// Sets bit pattern for target result + inline void setTarget(int value) { + target_ = value; + } +private: + /// Does deleteions + void gutsOfDelete(); + + /** Adds one attempt of one column of type 0, + returns true if was used in making any changes + */ + bool addOneColumn0(int numberElements, const int * rows, + double cost); + /** Adds one attempt of one column of type 1, + returns true if was used in making any changes. + At present the user has to call it once for each possible value + */ + bool addOneColumn1(int numberElements, const int * rows, + const int * coefficients, double cost); + /** Adds one attempt of one column of type 1, + returns true if was used in making any changes. + At present the user has to call it once for each possible value. + This version is when there are enough 1 rhs to do faster + */ + bool addOneColumn1A(int numberElements, const int * rows, + const int * coefficients, double cost); + /// Gets bit pattern from original column + int bitPattern(int numberElements, const int * rows, + const int * coefficients); + /// Gets bit pattern from original column + int bitPattern(int numberElements, const int * rows, + const double * coefficients); + /// Fills in original column (dense) from bit pattern - returning number nonzero + int decodeBitPattern(int bitPattern, int * values, int numberRows); + +protected: + + /// Size of states (power of 2 unless just one constraint) + int size_; + /** Type - 0 coefficients and rhs all 1, + 1 - coefficients > 1 or rhs > 1 + */ + int type_; + /// Space for states + double * cost_; + /// Which state produced this cheapest one + int * back_; + /// Some rows may be satisified so we need a lookup + int * lookup_; + /// Space for sorted indices + int * indices_; + /// Number of active rows + int numberActive_; + /// Maximum size allowed + int maximumSizeAllowed_; + /// Start bit for each active row + int * startBit_; + /// Number bits for each active row + int * numberBits_; + /// Effective rhs + int * rhs_; + /// Space for sorted coefficients + int * coefficients_; + /// Target pattern + int target_; + /// Number of Non 1 rhs + int numberNonOne_; + /// Current bit pattern + int bitPattern_; + /// Current algorithm + int algorithm_; +private: + + /// Illegal Assignment operator + CbcFathomDynamicProgramming & operator=(const CbcFathomDynamicProgramming& rhs); + +}; + +#endif + |