source: trunk/Cbc/src/CbcHeuristicGreedy.hpp @ 2122

Last change on this file since 2122 was 1585, checked in by forrest, 8 years ago

add some more heuristics

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 8.5 KB
Line 
1/* $Id: CbcHeuristicGreedy.hpp 1585 2011-01-11 19:04:34Z forrest $ */
2// Copyright (C) 2005, International Business Machines
3// Corporation and others.  All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6#ifndef CbcHeuristicGreedy_H
7#define CbcHeuristicGreedy_H
8
9#include "CbcHeuristic.hpp"
10/** Greedy heuristic classes
11 */
12
13class CbcHeuristicGreedyCover : public CbcHeuristic {
14public:
15
16    // Default Constructor
17    CbcHeuristicGreedyCover ();
18
19    /* Constructor with model - assumed before cuts
20       Initial version does not do Lps
21    */
22    CbcHeuristicGreedyCover (CbcModel & model);
23
24    // Copy constructor
25    CbcHeuristicGreedyCover ( const CbcHeuristicGreedyCover &);
26
27    // Destructor
28    ~CbcHeuristicGreedyCover ();
29
30    /// Clone
31    virtual CbcHeuristic * clone() const;
32    /// Assignment operator
33    CbcHeuristicGreedyCover & operator=(const CbcHeuristicGreedyCover& rhs);
34    /// Create C++ lines to get to current state
35    virtual void generateCpp( FILE * fp) ;
36
37    /// update model (This is needed if cliques update matrix etc)
38    virtual void setModel(CbcModel * model);
39
40    using CbcHeuristic::solution ;
41    /** returns 0 if no solution, 1 if valid solution.
42        Sets solution values if good, sets objective value (only if good)
43        We leave all variables which are at one at this node of the
44        tree to that value and will
45        initially set all others to zero.  We then sort all variables in order of their cost
46        divided by the number of entries in rows which are not yet covered.  We randomize that
47        value a bit so that ties will be broken in different ways on different runs of the heuristic.
48        We then choose the best one and set it to one and repeat the exercise.
49
50    */
51    virtual int solution(double & objectiveValue,
52                         double * newSolution);
53    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
54    virtual void validate() ;
55    /// Resets stuff if model changes
56    virtual void resetModel(CbcModel * model);
57    /* Algorithm
58       0 - use current upper bounds
59       1 - use original upper bounds
60       If 10 added perturb ratios more
61       if 100 added round up all >=0.5
62    */
63    inline int algorithm() const {
64        return algorithm_;
65    }
66    inline void setAlgorithm(int value) {
67        algorithm_ = value;
68    }
69    // Only do this many times
70    inline int numberTimes() const {
71        return numberTimes_;
72    }
73    inline void setNumberTimes(int value) {
74        numberTimes_ = value;
75    }
76
77protected:
78    /// Guts of constructor from a CbcModel
79    void gutsOfConstructor(CbcModel * model);
80    // Data
81
82    // Original matrix by column
83    CoinPackedMatrix matrix_;
84    // original number of rows
85    int originalNumberRows_;
86    /* Algorithm
87       0 - use current upper bounds
88       1 - use original upper bounds
89       If 10 added perturb ratios more
90    */
91    int algorithm_;
92    /// Do this many times
93    int numberTimes_;
94
95};
96
97
98class CbcHeuristicGreedyEquality : public CbcHeuristic {
99public:
100
101    // Default Constructor
102    CbcHeuristicGreedyEquality ();
103
104    /* Constructor with model - assumed before cuts
105       Initial version does not do Lps
106    */
107    CbcHeuristicGreedyEquality (CbcModel & model);
108
109    // Copy constructor
110    CbcHeuristicGreedyEquality ( const CbcHeuristicGreedyEquality &);
111
112    // Destructor
113    ~CbcHeuristicGreedyEquality ();
114
115    /// Clone
116    virtual CbcHeuristic * clone() const;
117    /// Assignment operator
118    CbcHeuristicGreedyEquality & operator=(const CbcHeuristicGreedyEquality& rhs);
119    /// Create C++ lines to get to current state
120    virtual void generateCpp( FILE * fp) ;
121
122    /// update model (This is needed if cliques update matrix etc)
123    virtual void setModel(CbcModel * model);
124
125    using CbcHeuristic::solution ;
126    /** returns 0 if no solution, 1 if valid solution.
127        Sets solution values if good, sets objective value (only if good)
128        We leave all variables which are at one at this node of the
129        tree to that value and will
130        initially set all others to zero.  We then sort all variables in order of their cost
131        divided by the number of entries in rows which are not yet covered.  We randomize that
132        value a bit so that ties will be broken in different ways on different runs of the heuristic.
133        We then choose the best one and set it to one and repeat the exercise.
134
135    */
136    virtual int solution(double & objectiveValue,
137                         double * newSolution);
138    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
139    virtual void validate() ;
140    /// Resets stuff if model changes
141    virtual void resetModel(CbcModel * model);
142    /* Algorithm
143       0 - use current upper bounds
144       1 - use original upper bounds
145       If 10 added perturb ratios more
146       if 100 added round up all >=0.5
147    */
148    inline int algorithm() const {
149        return algorithm_;
150    }
151    inline void setAlgorithm(int value) {
152        algorithm_ = value;
153    }
154    // Fraction of rhs to cover before branch and cut
155    inline void setFraction(double value) {
156        fraction_ = value;
157    }
158    inline double fraction() const {
159        return fraction_;
160    }
161    // Only do this many times
162    inline int numberTimes() const {
163        return numberTimes_;
164    }
165    inline void setNumberTimes(int value) {
166        numberTimes_ = value;
167    }
168protected:
169    /// Guts of constructor from a CbcModel
170    void gutsOfConstructor(CbcModel * model);
171    // Data
172
173    // Original matrix by column
174    CoinPackedMatrix matrix_;
175    // Fraction of rhs to cover before branch and cut
176    double fraction_;
177    // original number of rows
178    int originalNumberRows_;
179    /* Algorithm
180       0 - use current upper bounds
181       1 - use original upper bounds
182       If 10 added perturb ratios more
183    */
184    int algorithm_;
185    /// Do this many times
186    int numberTimes_;
187
188};
189
190/** Greedy heuristic for SOS and L rows (and positive elements)
191 */
192
193class CbcHeuristicGreedySOS : public CbcHeuristic {
194public:
195
196    // Default Constructor
197    CbcHeuristicGreedySOS ();
198
199    /* Constructor with model - assumed before cuts
200       Initial version does not do Lps
201    */
202    CbcHeuristicGreedySOS (CbcModel & model);
203
204    // Copy constructor
205    CbcHeuristicGreedySOS ( const CbcHeuristicGreedySOS &);
206
207    // Destructor
208    ~CbcHeuristicGreedySOS ();
209
210    /// Clone
211    virtual CbcHeuristic * clone() const;
212    /// Assignment operator
213    CbcHeuristicGreedySOS & operator=(const CbcHeuristicGreedySOS& rhs);
214    /// Create C++ lines to get to current state
215    virtual void generateCpp( FILE * fp) ;
216
217    /// update model (This is needed if cliques update matrix etc)
218    virtual void setModel(CbcModel * model);
219
220    using CbcHeuristic::solution ;
221    /** returns 0 if no solution, 1 if valid solution.
222        Sets solution values if good, sets objective value (only if good)
223        We leave all variables which are at one at this node of the
224        tree to that value and will
225        initially set all others to zero.  We then sort all variables in order of their cost
226        divided by the number of entries in rows which are not yet covered.  We randomize that
227        value a bit so that ties will be broken in different ways on different runs of the heuristic.
228        We then choose the best one and set it to one and repeat the exercise.
229
230    */
231    virtual int solution(double & objectiveValue,
232                         double * newSolution);
233    /// Validate model i.e. sets when_ to 0 if necessary (may be NULL)
234    virtual void validate() ;
235    /// Resets stuff if model changes
236    virtual void resetModel(CbcModel * model);
237    /* Algorithm
238       Bits
239       1 bit - use current model, otherwise original
240       2 - use current solution as starting point, otherwise pure greedy
241       4 - as 2 but use merit not merit/size
242       8 - use duals to modify greedy
243       16 - use duals on GUB/SOS in special way
244    */
245    inline int algorithm() const {
246        return algorithm_;
247    }
248    inline void setAlgorithm(int value) {
249        algorithm_ = value;
250    }
251    // Only do this many times
252    inline int numberTimes() const {
253        return numberTimes_;
254    }
255    inline void setNumberTimes(int value) {
256        numberTimes_ = value;
257    }
258
259protected:
260    /// Guts of constructor from a CbcModel
261    void gutsOfConstructor(CbcModel * model);
262    // Data
263
264    // Original RHS - if -1.0 then SOS otherwise <= value
265    double * originalRhs_;
266    // Original matrix by column
267    CoinPackedMatrix matrix_;
268    // original number of rows
269    int originalNumberRows_;
270    /* Algorithm
271    */
272    int algorithm_;
273    /// Do this many times
274    int numberTimes_;
275
276};
277
278
279#endif
280
Note: See TracBrowser for help on using the repository browser.