1 // $Id$
2 // Copyright (C) 2000, 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 CglTreeInfo_H
7 #define CglTreeInfo_H
8
9 #include "OsiCuts.hpp"
10 #include "OsiSolverInterface.hpp"
11 #include "CoinHelperFunctions.hpp"
12 class CglStored;
13 /** Information about where the cut generator is invoked from. */
14
15 class CglTreeInfo {
16 public:
17 /// The level of the search tree node
18 int level;
19 /** How many times the cut generator was already invoked in this search tree
20 node */
21 int pass;
22 /** The number of rows in the original formulation. Some generators may not
23 want to consider already generated rows when generating new ones. */
24 int formulation_rows;
25 /** Options
26 1 - treat costed integers as important
27 2 - switch off some stuff as variables semi-integer
28 4 - set global cut flag if at root node
29 8 - set global cut flag if at root node and first pass
30 16 - set global cut flag and make cuts globally valid
31 32 - last round of cuts did nothing - maybe be more aggressive
32 64 - in preprocessing stage
33 128 - looks like solution
34 256 - want alternate cuts
35 512 - in sub tree (i.e. parent model)
36 1024 - in must call again mode or after everything mode
37 */
38 int options;
39 /// Set true if in tree (to avoid ambiguity at first branch)
40 bool inTree;
41 /** nonzero if called from child of main model
42 1 if heuristic run
43 2 if doing full search
44 */
45 int hasParent;
46 /// parent solver
47 OsiSolverInterface *parentSolver;
48 /// Original columns (if preprocessed)
49 int *originalColumns;
50 /** Replacement array. Before Branch and Cut it may be beneficial to strengthen rows
51 rather than adding cuts. If this array is not NULL then the cut generator can
52 place a pointer to the stronger cut in this array which is number of rows in size.
53
54 A null (i.e. zero elements and free rhs) cut indicates that the row is useless
55 and can be removed.
56
57 The calling function can then replace those rows.
58 */
59 OsiRowCut **strengthenRow;
60 /// Optional pointer to thread specific random number generator
61 CoinThreadRandom *randomNumberGenerator;
62 /// Default constructor
63 CglTreeInfo();
64
65 /// Copy constructor
66 CglTreeInfo(
67 const CglTreeInfo &);
68 /// Clone
69 virtual CglTreeInfo *clone() const;
70
71 /// Assignment operator
72 CglTreeInfo &
73 operator=(
74 const CglTreeInfo &rhs);
75
76 /// Destructor
77 virtual ~CglTreeInfo();
78 /// Take action if cut generator can fix a variable (toValue -1 for down, +1 for up)
fixes(int,int,int,bool)79 virtual bool fixes(int, int, int, bool) { return false; }
80 /** Initalizes fixing arrays etc - returns >0 if we want to save info
81 0 if we don't and -1 if is to be used */
initializeFixing(const OsiSolverInterface *)82 virtual int initializeFixing(const OsiSolverInterface *) { return 0; }
83 };
84
85 /** Derived class to pick up probing info. */
86 typedef struct {
87 //unsigned int oneFixed:1; // nonzero if variable to 1 fixes all
88 //unsigned int sequence:31; // variable (in matrix) (but also see cliqueRow_)
89 unsigned int fixes;
90 } CliqueEntry;
91
92 class CglTreeProbingInfo : public CglTreeInfo {
93 public:
94 /// Default constructor
95 CglTreeProbingInfo();
96 /// Constructor from model
97 CglTreeProbingInfo(const OsiSolverInterface *model);
98
99 /// Copy constructor
100 CglTreeProbingInfo(
101 const CglTreeProbingInfo &);
102 /// Clone
103 virtual CglTreeInfo *clone() const;
104
105 /// Assignment operator
106 CglTreeProbingInfo &
107 operator=(
108 const CglTreeProbingInfo &rhs);
109
110 /// Destructor
111 virtual ~CglTreeProbingInfo();
112 OsiSolverInterface *analyze(const OsiSolverInterface &si, int createSolver = 0,
113 int numberExtraCliques = 0, const CoinBigIndex *starts = NULL,
114 const CliqueEntry *entries = NULL, const char *type = NULL);
115 /** Take action if cut generator can fix a variable
116 (toValue -1 for down, +1 for up)
117 Returns true if still room, false if not */
118 virtual bool fixes(int variable, int toValue, int fixedVariable, bool fixedToLower);
119 /** Initalizes fixing arrays etc - returns >0 if we want to save info
120 0 if we don't and -1 if is to be used */
121 virtual int initializeFixing(const OsiSolverInterface *model);
122 /// Fix entries in a solver using implications
123 int fixColumns(OsiSolverInterface &si) const;
124 /// Fix entries in a solver using implications for one variable
125 int fixColumns(int iColumn, int value, OsiSolverInterface &si) const;
126 /// Packs down entries
127 int packDown();
128 /// Generate cuts from implications
129 void generateCuts(const OsiSolverInterface &si, OsiCuts &cs,
130 const CglTreeInfo info) const;
131 /// Entries for fixing variables
fixEntries()132 inline CliqueEntry *fixEntries()
133 {
134 convert();
135 return fixEntry_;
136 }
137 /// Starts of integer variable going to zero
toZero()138 inline int *toZero()
139 {
140 convert();
141 return toZero_;
142 }
143 /// Starts of integer variable going to one
toOne()144 inline int *toOne()
145 {
146 convert();
147 return toOne_;
148 }
149 /// List of 0-1 integer variables
integerVariable() const150 inline int *integerVariable() const
151 {
152 return integerVariable_;
153 }
154 /// Backward look up
backward() const155 inline int *backward() const
156 {
157 return backward_;
158 }
159 /// Number of variables
numberVariables() const160 inline int numberVariables() const
161 {
162 return numberVariables_;
163 }
164 /// Number of 0-1 variables
numberIntegers() const165 inline int numberIntegers() const
166 {
167 return numberIntegers_;
168 }
169
170 private:
171 /// Converts to ordered
172 void convert();
173
174 protected:
175 /// Entries for fixing variables
176 CliqueEntry *fixEntry_;
177 /// Starts of integer variable going to zero
178 int *toZero_;
179 /// Starts of integer variable going to one
180 int *toOne_;
181 /// List of 0-1 integer variables
182 int *integerVariable_;
183 /// Backward look up
184 int *backward_;
185 /// Entries for fixing variable when collecting
186 int *fixingEntry_;
187 /// Number of variables
188 int numberVariables_;
189 /// Number of 0-1 variables
190 int numberIntegers_;
191 /// Maximum number in fixEntry_
192 int maximumEntries_;
193 /// Number entries in fixingEntry_ (and fixEntry_) or -2 if correct style
194 int numberEntries_;
195 };
sequenceInCliqueEntry(const CliqueEntry & cEntry)196 inline int sequenceInCliqueEntry(const CliqueEntry &cEntry)
197 {
198 return cEntry.fixes & 0x7fffffff;
199 }
setSequenceInCliqueEntry(CliqueEntry & cEntry,int sequence)200 inline void setSequenceInCliqueEntry(CliqueEntry &cEntry, int sequence)
201 {
202 cEntry.fixes = sequence | (cEntry.fixes & 0x80000000);
203 }
oneFixesInCliqueEntry(const CliqueEntry & cEntry)204 inline bool oneFixesInCliqueEntry(const CliqueEntry &cEntry)
205 {
206 return (cEntry.fixes & 0x80000000) != 0;
207 }
setOneFixesInCliqueEntry(CliqueEntry & cEntry,bool oneFixes)208 inline void setOneFixesInCliqueEntry(CliqueEntry &cEntry, bool oneFixes)
209 {
210 cEntry.fixes = (oneFixes ? 0x80000000 : 0) | (cEntry.fixes & 0x7fffffff);
211 }
212
213 #endif
214
215 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
216 */
217