Changeset 1573


Ignore:
Timestamp:
May 12, 2020 2:59:29 PM (2 months ago)
Author:
samuelbrito
Message:

Comments added to CglBKClique, CglCliqueStrengthening? and CglOddWheel?

Location:
trunk/src
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/CglBKClique/CglBKClique.cpp

    r1559 r1573  
     1/**
     2 *
     3 * This file is part of the COIN-OR CBC MIP Solver
     4 *
     5 * Class responsible for separating clique cuts.
     6 * It uses the Bron-Kerbosch (BK) algorithm.
     7 *
     8 * @file CglBKClique.hpp
     9 * @brief Clique cut separator
     10 * @author Samuel Souza Brito and Haroldo Gambini Santos
     11 * Contact: samuelbrito@ufop.edu.br and haroldo@ufop.edu.br
     12 * @date 03/27/2020
     13 *
     14 * \copyright{Copyright 2020 Brito, S.S. and Santos, H.G.}
     15 * \license{This This code is licensed under the terms of the Eclipse Public License (EPL).}
     16 *
     17 **/
     18
    119#include <cstdio>
    220#include <cassert>
     
    257275        const size_t *clqEl = initialCliques->cliqueElements(i);
    258276        const size_t nClqEl = initialCliques->cliqueSize(i);
    259         const size_t nNewClqs = clqe.extendClique(clqEl, nClqEl);
     277        const bool extended = clqe.extendClique(clqEl, nClqEl);
    260278
    261279        /* adds clique if it is not extended */
    262         if (!nNewClqs) {
     280        if (!extended) {
    263281            extCliques->addClique(nClqEl, clqEl);
    264282        }
  • trunk/src/CglBKClique/CglBKClique.hpp

    r1560 r1573  
     1/**
     2 *
     3 * This file is part of the COIN-OR CBC MIP Solver
     4 *
     5 * Class responsible for separating clique cuts.
     6 * It uses the Bron-Kerbosch (BK) algorithm.
     7 *
     8 * @file CglBKClique.hpp
     9 * @brief Clique cut separator
     10 * @author Samuel Souza Brito and Haroldo Gambini Santos
     11 * Contact: samuelbrito@ufop.edu.br and haroldo@ufop.edu.br
     12 * @date 03/27/2020
     13 *
     14 * \copyright{Copyright 2020 Brito, S.S. and Santos, H.G.}
     15 * \license{This This code is licensed under the terms of the Eclipse Public License (EPL).}
     16 *
     17 **/
     18
    119#ifndef _CglBKClique_h_
    220#define _CglBKClique_h_
     
    725class CoinConflictGraph;
    826
     27/**
     28 * Class responsible for separating clique cuts.
     29 * It uses the Bron-Kerbosch algorithm.
     30 **/
    931class CGLLIB_EXPORT CglBKClique : public CglCutGenerator {
    1032public:
    11     CglBKClique();
    12     CglBKClique(const CglBKClique& rhs);
    13     virtual CglCutGenerator * clone() const;
    14     virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info = CglTreeInfo());
    15     virtual ~CglBKClique();
    16     virtual void refreshSolver(OsiSolverInterface *solver);
    17 
    18     void setMaxCallsBK(size_t maxCallsBK);
    19     size_t getMaxCallsBK() const { return maxCallsBK_; }
    20     void setExtendingMethod(size_t extMethod);
    21     size_t getExtendingMethod() const { return extMethod_; }
    22     size_t getNumCallsBK() const { return callsBK_; }
    23 
    24     const double getMinFrac() const { return minFrac_; }
    25     const double getMinViol() const { return minViol_; }
    26     const double getMinWeight() const { return minWeight_; }
    27     void setMinFrac(const double minFrac);
    28     void setMinViol(const double minViol);
    29     void setPivotingStrategy(const size_t pivotingStrategy);
    30 
    31     static size_t sepCuts_;
    32     static double sepTime_;
     33  /**
     34   * Default constructor
     35   **/
     36  CglBKClique();
     37
     38  /**
     39   * Copy constructor
     40   **/
     41  CglBKClique(const CglBKClique& rhs);
     42
     43  /**
     44   * Clone
     45   **/
     46  virtual CglCutGenerator * clone() const;
     47
     48  /**
     49   * Generate clique cuts for the model data contained
     50   * in si. The generated cuts are inserted into and returned
     51   * in the collection of cuts cs.
     52   **/
     53  virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info = CglTreeInfo());
     54 
     55  /**
     56   * Destructor
     57   **/
     58  virtual ~CglBKClique();
     59
     60  /**
     61   * Refresh the conflict graph if necessary.
     62   **/
     63  virtual void refreshSolver(OsiSolverInterface *solver);
     64
     65  /**
     66   * Set the maximum number of recursive calls to be made
     67   * by BK algorithm.
     68   **/
     69  void setMaxCallsBK(size_t maxCallsBK);
     70
     71  /**
     72   * Return the maximum number of recursive calls to be made
     73   * by BK algorithm.
     74   **/
     75  size_t getMaxCallsBK() const { return maxCallsBK_; }
     76
     77  /**
     78   * Set the strategy used to extend cliques:
     79   * 0 = no extension; 1 = random; 2 = max degree;
     80   * 3 = max modified degree; 4 = reduced cost (inversely proportional);
     81   * 5 = reduced cost (inversely proportional) + modified degree.
     82   **/
     83  void setExtendingMethod(size_t extMethod);
     84
     85  /**
     86   * Return the strategy used to extend cliques.
     87   **/
     88  size_t getExtendingMethod() const { return extMethod_; }
     89
     90  /**
     91   * Return the number of calls made by BK algorithm.
     92   **/
     93  size_t getNumCallsBK() const { return callsBK_; }
     94
     95  /**
     96   * Return the minimum value that a variable must have
     97   * in the LP relaxation to be considered in the cut
     98   * separation.
     99   **/
     100  const double getMinFrac() const { return minFrac_; }
     101
     102  /**
     103   * Return the minimum violation of a clique to be
     104   * stored by the cut separator.
     105   **/
     106  const double getMinViol() const { return minViol_; }
     107
     108  /**
     109   * Set the minimum value that a variable must have
     110   * in the LP relaxation to be considered in the cut
     111   * separation.
     112   **/
     113  void setMinFrac(const double minFrac);
     114
     115  /**
     116   * Set the minimum violation of a clique to be
     117   * stored by the cut separator.
     118   **/
     119  void setMinViol(const double minViol);
     120
     121  /**
     122   * Set the pivoting strategy used in BK algorithm:
     123   * 0 = off; 1 = random; 2 = degree; 3 = weight; 4 = modified degree;
     124   * 5 = modified weight; 6 = modified degree + modified weight.
     125   **/
     126  void setPivotingStrategy(const size_t pivotingStrategy);
     127
     128  /**
     129   * Number of cuts separated.
     130   **/
     131  static size_t sepCuts_;
     132
     133  /**
     134   * Execution time spent for the clique
     135   * cut separator.
     136   **/
     137  static double sepTime_;
    33138
    34139private:
    35     void checkMemory(const size_t newNumCols);
    36     CoinCliqueList* separateCliques(const OsiSolverInterface &si);
    37     CoinCliqueList* extendCliques(const OsiSolverInterface &si, const CoinCliqueList *initialCliques);
    38     void insertCuts(const OsiSolverInterface &si, const CglTreeInfo &info, const CoinCliqueList *cliques, OsiCuts &cs);
    39 
    40     size_t cap_;
    41     double *rc_;
    42     int *idxs_, *idxMap_;
    43     double *coefs_;
    44     size_t *inducedVert_, *currClq_;
    45     double *vertexWeight_;
    46 
    47     double minFrac_;
    48     double minViol_;
    49     double minWeight_;
    50 
    51     size_t pivotingStrategy_;
    52     size_t extMethod_;
    53     size_t maxCallsBK_;
    54     size_t callsBK_;
    55     bool completeBK_;
    56 
    57     OsiRowCut osrc_;
     140  /**
     141   * Check if it is necessary realloc the memory
     142   * for the data structures.
     143   **/
     144  void checkMemory(const size_t newNumCols);
     145
     146  /**
     147   * Execute the clique cut separation.
     148   * Return a list of violated cliques.
     149   **/
     150  CoinCliqueList* separateCliques(const OsiSolverInterface &si);
     151 
     152  /**
     153   * Execute the clique extension procedure.
     154   * Return a list of violated cliques.
     155   **/
     156  CoinCliqueList* extendCliques(const OsiSolverInterface &si, const CoinCliqueList *initialCliques);
     157 
     158  /**
     159   * Insert the violated cuts in OsiCuts cs.
     160   **/
     161  void insertCuts(const OsiSolverInterface &si, const CglTreeInfo &info, const CoinCliqueList *cliques, OsiCuts &cs);
     162
     163  /**
     164   * Capacity of storage of the data structures.
     165   **/
     166  size_t cap_;
     167
     168  /**
     169   * Reduced costs of the variables.
     170   **/
     171  double *rc_;
     172
     173  /**
     174   * Auxiliary arrays used to store the indexes
     175   * of a clique.
     176   **/
     177  int *idxs_, *idxMap_;
     178
     179  /**
     180   * Auxiliary array used to store the coefficients
     181   * of a clique.
     182   **/
     183  double *coefs_;
     184
     185  /**
     186   * Auxiliary array that stores the indexes
     187   * to construct a induced subgraph.
     188   **/
     189  size_t *inducedVert_;
     190
     191  /**
     192   * Auxiliary array for storing the current
     193   * clique.
     194   **/
     195  size_t *currClq_;
     196
     197  /**
     198   * Weight of each vertex.
     199   **/
     200  double *vertexWeight_;
     201
     202  /**
     203   * Minimum value that a variable must have
     204   * in the LP relaxation to be considered in the cut
     205   * separation.
     206   **/
     207  double minFrac_;
     208
     209  /**
     210   * Minimum violation of a clique to be
     211   * stored by the cut separator.
     212   **/
     213  double minViol_;
     214
     215  /**
     216   * Convert minViol_ to a integer value,
     217   * to made further computations easier.
     218   **/
     219  double minWeight_;
     220
     221  /**
     222   * Pivoting strategy employed in the BK algorithm.
     223   **/
     224  size_t pivotingStrategy_;
     225
     226  /**
     227   * Strategy used to extend cliques.
     228   **/
     229  size_t extMethod_;
     230
     231  /**
     232   * Maximum number of recursive calls to be made
     233   * by BK algorithm.
     234   **/
     235  size_t maxCallsBK_;
     236
     237  /**
     238   * Number of calls made by BK algorithm.
     239   **/
     240  size_t callsBK_;
     241
     242  /**
     243   * Check if BK ran completely (without
     244   * stopping by maxCallsBK).
     245   **/
     246  bool completeBK_;
     247
     248  /**
     249   * Auxiliary structure used to temporary
     250   * store a cut.
     251   **/
     252  OsiRowCut osrc_;
    58253};
    59254
  • trunk/src/CglCliqueStrengthening/CglCliqueStrengthening.cpp

    r1570 r1573  
     1/**
     2 *
     3 * This file is part of the COIN-OR CBC MIP Solver
     4 *
     5 * Class that implements a conflict-based preprocessing.
     6 * It tries to extend set packing constraints considering
     7 * the conflict graph and using a greedy strategy.
     8 *
     9 * @file CglCliqueStrengthening.cpp
     10 * @brief Conflict-based preprocessing
     11 * @author Samuel Souza Brito and Haroldo Gambini Santos
     12 * Contact: samuelbrito@ufop.edu.br and haroldo@ufop.edu.br
     13 * @date 03/27/2020
     14 *
     15 * \copyright{Copyright 2020 Brito, S.S. and Santos, H.G.}
     16 * \license{This This code is licensed under the terms of the Eclipse Public License (EPL).}
     17 *
     18 **/
     19
    120#include <cfloat>
    221#include <cassert>
  • trunk/src/CglCliqueStrengthening/CglCliqueStrengthening.hpp

    r1560 r1573  
     1/**
     2 *
     3 * This file is part of the COIN-OR CBC MIP Solver
     4 *
     5 * Class that implements a conflict-based preprocessing.
     6 * It tries to extend set packing constraints considering
     7 * the conflict graph and using a greedy strategy.
     8 *
     9 * @file CglCliqueStrengthening.hpp
     10 * @brief Conflict-based preprocessing
     11 * @author Samuel Souza Brito and Haroldo Gambini Santos
     12 * Contact: samuelbrito@ufop.edu.br and haroldo@ufop.edu.br
     13 * @date 03/27/2020
     14 *
     15 * \copyright{Copyright 2020 Brito, S.S. and Santos, H.G.}
     16 * \license{This This code is licensed under the terms of the Eclipse Public License (EPL).}
     17 *
     18 **/
     19
    120#ifndef CGLCLIQUESTRENGTHENING_HPP
    221#define CGLCLIQUESTRENGTHENING_HPP
     
    827class CoinConflictGraph;
    928
     29/**
     30 * Class that implements a conflict-based preprocessing.
     31 * It tries to extend set packing constraints considering
     32 * the conflict graph and using a greedy strategy.
     33 **/
    1034class CGLLIB_EXPORT CglCliqueStrengthening {
    1135public:
    12     CglCliqueStrengthening();
    13     CglCliqueStrengthening(const CglCliqueStrengthening &rhs);
    14     CglCliqueStrengthening &operator=(const CglCliqueStrengthening &rhs);
    15     ~CglCliqueStrengthening();
    16     void gutsOfDestructor();
     36  /**
     37   * Default constructor
     38   **/
     39  CglCliqueStrengthening();
    1740
    18     void strengthenCliques(OsiSolverInterface &model, size_t extMethod = 4);
    19     int constraintsExtended() const { return nExtended_; }
    20     int constraintsDominated() const { return nDominated_; }
     41  /**
     42   * Copy constructor
     43   **/
     44  CglCliqueStrengthening(const CglCliqueStrengthening &rhs);
    2145
    22     /**@name Message handling */
    23     //@{
    24     /// Pass in Message handler (not deleted at end)
    25     void passInMessageHandler(CoinMessageHandler * handler);
    26     /// Set language
    27     void newLanguage(CoinMessages::Language language);
    28     inline void setLanguage(CoinMessages::Language language)
    29     {newLanguage(language);}
    30     /// Return handler
    31     inline CoinMessageHandler * messageHandler() const
    32     {return handler_;}
    33     /// Return messages
    34     inline CoinMessages messages()
    35     {return messages_;}
    36     /// Return pointer to messages
    37     inline CoinMessages * messagesPointer()
    38     {return &messages_;}
    39     //@}
     46  /**
     47   * Assignment operator
     48   **/
     49  CglCliqueStrengthening &operator=(const CglCliqueStrengthening &rhs);
     50
     51  /**
     52   * Destructor
     53   **/
     54  ~CglCliqueStrengthening();
     55
     56  /**
     57   * Clears out as much as possible
     58   **/
     59  void gutsOfDestructor();
     60
     61  /**
     62   * Try to extend the set packing constraints of a model.
     63   * Extension method: 0 = no extension;1 = random;
     64   * 2 = max degree; 3 = max modified degree;
     65   * 4 = reduced cost (inversely proportional);
     66   * 5 = reduced cost (inversely proportional) + modified degree.
     67   **/
     68  void strengthenCliques(OsiSolverInterface &model, size_t extMethod = 4);
     69
     70  /**
     71   * Return the number of set packing constraints extended.
     72   **/
     73  int constraintsExtended() const { return nExtended_; }
     74
     75  /**
     76   * Return the number of set packing constraints dominated
     77   * by the extended constraints.
     78   **/
     79  int constraintsDominated() const { return nDominated_; }
     80
     81  /**
     82   * Pass in Message handler (not deleted at end)
     83   **/
     84  void passInMessageHandler(CoinMessageHandler * handler);
     85 
     86  /**
     87   * Set language
     88   **/
     89  void newLanguage(CoinMessages::Language language);
     90 
     91  /**
     92   * New language
     93   **/
     94  inline void setLanguage(CoinMessages::Language language)
     95  {newLanguage(language);}
     96
     97  /**
     98   * Return message handler
     99   **/
     100  inline CoinMessageHandler * messageHandler() const
     101  {return handler_;}
     102
     103  /**
     104   * Return messages
     105   **/
     106  inline CoinMessages messages()
     107  {return messages_;}
     108
     109  /**
     110   * Return a pointer to messages
     111   **/
     112  inline CoinMessages * messagesPointer()
     113  {return &messages_;}
    40114
    41115private:
    42     int nExtended_, nDominated_;
     116  /**
     117   * Number of extended constraints.
     118   **/
     119  int nExtended_;
    43120
    44     CoinMessageHandler * handler_;
    45     bool defaultHandler_;
    46     CoinMessages messages_;
     121  /**
     122   * Number of dominated constraints.
     123   **/
     124  int nDominated_;
     125
     126  /**
     127   * Message handler
     128   **/
     129  CoinMessageHandler * handler_;
     130
     131  /**
     132   * Flag to say if handler_ is the default handler.
     133   * The default handler is deleted when the model
     134   * is deleted. Other handlers (supplied by the client)
     135   * will not be deleted.
     136   **/
     137  bool defaultHandler_;
     138
     139  /**
     140   * Messages
     141   **/
     142  CoinMessages messages_;
    47143};
    48144
  • trunk/src/CglOddWheel/CglOddWheel.cpp

    r1559 r1573  
     1/**
     2 *
     3 * This file is part of the COIN-OR CBC MIP Solver
     4 *
     5 * Class for separating violated odd-cycles. It contains
     6 * a lifting module that tries to transform the odd-cycles
     7 * into odd-wheels.
     8 *
     9 * @file CglOddWheel.cpp
     10 * @brief Odd-wheel cut separator
     11 * @author Samuel Souza Brito and Haroldo Gambini Santos
     12 * Contact: samuelbrito@ufop.edu.br and haroldo@ufop.edu.br
     13 * @date 03/27/2020
     14 *
     15 * \copyright{Copyright 2020 Brito, S.S. and Santos, H.G.}
     16 * \license{This This code is licensed under the terms of the Eclipse Public License (EPL).}
     17 *
     18 **/
     19
    120#include <cstdio>
    221#include <cassert>
  • trunk/src/CglOddWheel/CglOddWheel.hpp

    r1560 r1573  
     1/**
     2 *
     3 * This file is part of the COIN-OR CBC MIP Solver
     4 *
     5 * Class for separating violated odd-cycles. It contains
     6 * a lifting module that tries to transform the odd-cycles
     7 * into odd-wheels.
     8 *
     9 * @file CglOddWheel.hpp
     10 * @brief Odd-wheel cut separator
     11 * @author Samuel Souza Brito and Haroldo Gambini Santos
     12 * Contact: samuelbrito@ufop.edu.br and haroldo@ufop.edu.br
     13 * @date 03/27/2020
     14 *
     15 * \copyright{Copyright 2020 Brito, S.S. and Santos, H.G.}
     16 * \license{This This code is licensed under the terms of the Eclipse Public License (EPL).}
     17 *
     18 **/
     19
    120#ifndef _CglOddWheel_h_
    221#define _CglOddWheel_h_
     
    726class CoinConflictGraph;
    827
     28/**
     29 * Class for separating violated odd-cycles. It contains
     30 * a lifting module that tries to transform the odd-cycles
     31 * into odd-wheels.
     32 **/
    933class CGLLIB_EXPORT CglOddWheel : public CglCutGenerator
    1034{
    1135public:
     36  /**
     37   * Number of cuts separated.
     38   **/
     39  static size_t sepCuts;
    1240
    13     static size_t sepCuts;
    14     static double sepTime;
     41  /**
     42   * Execution time spent for the clique
     43   * cut separator.
     44   **/
     45  static double sepTime;
    1546
    16     CglOddWheel(size_t extMethod = 2);
    17     CglOddWheel(const CglOddWheel& rhs);
    18     virtual CglCutGenerator * clone() const;
    19     virtual void generateCuts( const OsiSolverInterface & si, OsiCuts & cs, const CglTreeInfo info = CglTreeInfo() );
    20     virtual ~CglOddWheel();
    21     virtual void refreshSolver(OsiSolverInterface *solver);
     47  /**
     48   * Default constructor
     49   *
     50   * @param extMethod strategy that will be used to lift odd cycles,
     51   * transforming them into odd wheels: 0 = no lifting, 1 = only one
     52   * variable as wheel center, 2 = a clique as wheel center.
     53   **/
     54  CglOddWheel(size_t extMethod = 2);
    2255
    23     void setExtendingMethod(size_t extMethod);
    24     size_t getExtendingMethod() const { return extMethod_; }
     56  /**
     57   * Copy constructor
     58   **/
     59  CglOddWheel(const CglOddWheel& rhs);
     60
     61  /**
     62   * Clone
     63   **/
     64  virtual CglCutGenerator * clone() const;
     65
     66  /**
     67   * Generate clique cuts for the model data contained
     68   * in si. The generated cuts are inserted into and returned
     69   * in the collection of cuts cs.
     70   **/
     71  virtual void generateCuts( const OsiSolverInterface & si, OsiCuts & cs, const CglTreeInfo info = CglTreeInfo() );
     72 
     73  /**
     74   * Destructor
     75   **/
     76  virtual ~CglOddWheel();
     77
     78  /**
     79   * Refresh the conflict graph if necessary.
     80   **/
     81  virtual void refreshSolver(OsiSolverInterface *solver);
     82
     83  /**
     84   * Set the strategy that will be used to lift odd cycles,
     85   * transforming them into odd wheels: 0 = no lifting, 1 = only one
     86   * variable as wheel center, 2 = a clique as wheel center.
     87   **/
     88  void setExtendingMethod(size_t extMethod);
     89
     90  /**
     91   * Return the strategy used to lift odd cycles.
     92   **/
     93  size_t getExtendingMethod() const { return extMethod_; }
    2594
    2695private:
    27     void checkMemory(const size_t newNumCols);
     96  /**
     97   * Check if it is necessary realloc the memory
     98   * for the data structures.
     99   **/
     100  void checkMemory(const size_t newNumCols);
    28101
    29     size_t cap_;
    30     int *idxs_, *idxMap_;
    31     double *coefs_;
     102  /**
     103   * Capacity of storage of the data structures.
     104   **/
     105  size_t cap_;
    32106
    33     double *x_, *rc_;
     107  /**
     108   * Auxiliary arrays used to store the indexes
     109   * of a clique.
     110   **/
     111  int *idxs_, *idxMap_;
    34112
    35     OsiRowCut osrc_;
     113  /**
     114   * Auxiliary array used to store the coefficients
     115   * of a clique.
     116   **/
     117  double *coefs_;
    36118
    37     /*Extending method:
    38      * 0 - no extension
    39      * 1 - wheel center with only one variable
    40      * 2 - wheel center formed by a clique
    41     */
    42     size_t extMethod_;
     119  /**
     120   * Current solution of the LP relaxation
     121   **/
     122  double *x_;
     123
     124  /**
     125   * Current reduced costs of the variables
     126   **/
     127  double *rc_;
     128
     129  /**
     130   * Auxiliary structure used to temporary
     131   * store a cut.
     132   **/
     133  OsiRowCut osrc_;
     134
     135  /**
     136   * Lifting strategy: 0 = no lifting,
     137   * 1 = only one variable as wheel center,
     138   * 2 = a clique as wheel center
     139   **/
     140  size_t extMethod_;
    43141};
    44142
Note: See TracChangeset for help on using the changeset viewer.