1// Copyright (C) 2006, International Business Machines
2// Corporation and others. All Rights Reserved.
3// This code is licensed under the terms of the Eclipse Public License (EPL).
4
5#ifndef OsiChooseVariable_H
6#define OsiChooseVariable_H
7
8#include <string>
9#include <vector>
10
11#include "CoinWarmStartBasis.hpp"
12#include "OsiBranchingObject.hpp"
13
14class OsiSolverInterface;
15class OsiHotInfo;
16
17/** This class chooses a variable to branch on
18
19 The base class just chooses the variable and direction without strong branching but it
20 has information which would normally be used by strong branching e.g. to re-enter
21 having fixed a variable but using same candidates for strong branching.
22
23 The flow is :
24 a) initialize the process. This decides on strong branching list
25 and stores indices of all infeasible objects
26 b) do strong branching on list. If list is empty then just
27 choose one candidate and return without strong branching. If not empty then
28 go through list and return best. However we may find that the node is infeasible
29 or that we can fix a variable. If so we return and it is up to user to call
30 again (after fixing a variable).
31*/
32
33class OsiChooseVariable {
34
35public:
36
37 /// Default Constructor
38 OsiChooseVariable ();
39
40 /// Constructor from solver (so we can set up arrays etc)
41 OsiChooseVariable (const OsiSolverInterface * solver);
42
43 /// Copy constructor
44 OsiChooseVariable (const OsiChooseVariable &);
45
46 /// Assignment operator
47 OsiChooseVariable & operator= (const OsiChooseVariable& rhs);
48
49 /// Clone
50 virtual OsiChooseVariable * clone() const;
51
52 /// Destructor
53 virtual ~OsiChooseVariable ();
54
55 /** Sets up strong list and clears all if initialize is true.
56 Returns number of infeasibilities.
57 If returns -1 then has worked out node is infeasible!
58 */
59 virtual int setupList ( OsiBranchingInformation *info, bool initialize);
60 /** Choose a variable
61 Returns -
62 -1 Node is infeasible
63 0 Normal termination - we have a candidate
64 1 All looks satisfied - no candidate
65 2 We can change the bound on a variable - but we also have a strong branching candidate
66 3 We can change the bound on a variable - but we have a non-strong branching candidate
67 4 We can change the bound on a variable - no other candidates
68 We can pick up branch from bestObjectIndex() and bestWhichWay()
69 We can pick up a forced branch (can change bound) from firstForcedObjectIndex() and firstForcedWhichWay()
70 If we have a solution then we can pick up from goodObjectiveValue() and goodSolution()
71 If fixVariables is true then 2,3,4 are all really same as problem changed
72 */
73 virtual int chooseVariable( OsiSolverInterface * solver, OsiBranchingInformation *info, bool fixVariables);
74 /// Returns true if solution looks feasible against given objects
75 virtual bool feasibleSolution(const OsiBranchingInformation * info,
76 const double * solution,
77 int numberObjects,
78 const OsiObject ** objects);
79 /// Saves a good solution
80 void saveSolution(const OsiSolverInterface * solver);
81 /// Clears out good solution after use
82 void clearGoodSolution();
83 /// Given a candidate fill in useful information e.g. estimates
84 virtual void updateInformation( const OsiBranchingInformation *info,
85 int branch, OsiHotInfo * hotInfo);
86#if 1
87 /// Given a branch fill in useful information e.g. estimates
88 virtual void updateInformation( int whichObject, int branch,
89 double changeInObjective, double changeInValue,
90 int status);
91#endif
92 /// Objective value for feasible solution
93 inline double goodObjectiveValue() const
94 { return goodObjectiveValue_;}
95 /// Estimate of up change or change on chosen if n-way
96 inline double upChange() const
97 { return upChange_;}
98 /// Estimate of down change or max change on other possibilities if n-way
99 inline double downChange() const
100 { return downChange_;}
101 /// Good solution - deleted by finalize
102 inline const double * goodSolution() const
103 { return goodSolution_;}
104 /// Index of chosen object
105 inline int bestObjectIndex() const
106 { return bestObjectIndex_;}
107 /// Set index of chosen object
108 inline void setBestObjectIndex(int value)
109 { bestObjectIndex_ = value;}
110 /// Preferred way of chosen object
111 inline int bestWhichWay() const
112 { return bestWhichWay_;}
113 /// Set preferred way of chosen object
114 inline void setBestWhichWay(int value)
115 { bestWhichWay_ = value;}
116 /// Index of forced object
117 inline int firstForcedObjectIndex() const
118 { return firstForcedObjectIndex_;}
119 /// Set index of forced object
120 inline void setFirstForcedObjectIndex(int value)
121 { firstForcedObjectIndex_ = value;}
122 /// Preferred way of forced object
123 inline int firstForcedWhichWay() const
124 { return firstForcedWhichWay_;}
125 /// Set preferred way of forced object
126 inline void setFirstForcedWhichWay(int value)
127 { firstForcedWhichWay_ = value;}
128 /// Get the number of objects unsatisfied at this node - accurate on first pass
129 inline int numberUnsatisfied() const
130 {return numberUnsatisfied_;}
131 /// Number of objects to choose for strong branching
132 inline int numberStrong() const
133 { return numberStrong_;}
134 /// Set number of objects to choose for strong branching
135 inline void setNumberStrong(int value)
136 { numberStrong_ = value;}
137 /// Number left on strong list
138 inline int numberOnList() const
139 { return numberOnList_;}
140 /// Number of strong branches actually done
141 inline int numberStrongDone() const
142 { return numberStrongDone_;}
143 /// Number of strong iterations actually done
144 inline int numberStrongIterations() const
145 { return numberStrongIterations_;}
146 /// Number of strong branches which changed bounds
147 inline int numberStrongFixed() const
148 { return numberStrongFixed_;}
149 /// List of candidates
150 inline const int * candidates() const
151 { return list_;}
152 /// Trust results from strong branching for changing bounds
153 inline bool trustStrongForBound() const
154 { return trustStrongForBound_;}
155 /// Set trust results from strong branching for changing bounds
156 inline void setTrustStrongForBound(bool yesNo)
157 { trustStrongForBound_ = yesNo;}
158 /// Trust results from strong branching for valid solution
159 inline bool trustStrongForSolution() const
160 { return trustStrongForSolution_;}
161 /// Set trust results from strong branching for valid solution
162 inline void setTrustStrongForSolution(bool yesNo)
163 { trustStrongForSolution_ = yesNo;}
164 /// Set solver and redo arrays
165 void setSolver (const OsiSolverInterface * solver);
166 /** Return status -
167 -1 Node is infeasible
168 0 Normal termination - we have a candidate
169 1 All looks satisfied - no candidate
170 2 We can change the bound on a variable - but we also have a strong branching candidate
171 3 We can change the bound on a variable - but we have a non-strong branching candidate
172 4 We can change the bound on a variable - no other candidates
173 We can pick up branch from bestObjectIndex() and bestWhichWay()
174 We can pick up a forced branch (can change bound) from firstForcedObjectIndex() and firstForcedWhichWay()
175 If we have a solution then we can pick up from goodObjectiveValue() and goodSolution()
176 */
177 inline int status() const
178 { return status_;}
179 inline void setStatus(int value)
180 { status_ = value;}
181
182
183protected:
184 // Data
185 /// Objective value for feasible solution
186 double goodObjectiveValue_;
187 /// Estimate of up change or change on chosen if n-way
188 double upChange_;
189 /// Estimate of down change or max change on other possibilities if n-way
190 double downChange_;
191 /// Good solution - deleted by finalize
192 double * goodSolution_;
193 /// List of candidates
194 int * list_;
195 /// Useful array (for sorting etc)
196 double * useful_;
197 /// Pointer to solver
198 const OsiSolverInterface * solver_;
199 /* Status -
200 -1 Node is infeasible
201 0 Normal termination - we have a candidate
202 1 All looks satisfied - no candidate
203 2 We can change the bound on a variable - but we also have a strong branching candidate
204 3 We can change the bound on a variable - but we have a non-strong branching candidate
205 4 We can change the bound on a variable - no other candidates
206 */
207 int status_;
208 /// Index of chosen object
209 int bestObjectIndex_;
210 /// Preferred way of chosen object
211 int bestWhichWay_;
212 /// Index of forced object
213 int firstForcedObjectIndex_;
214 /// Preferred way of forced object
215 int firstForcedWhichWay_;
216 /// The number of objects unsatisfied at this node.
217 int numberUnsatisfied_;
218 /// Number of objects to choose for strong branching
219 int numberStrong_;
220 /// Number left on strong list
221 int numberOnList_;
222 /// Number of strong branches actually done
223 int numberStrongDone_;
224 /// Number of strong iterations actually done
225 int numberStrongIterations_;
226 /// Number of bound changes due to strong branching
227 int numberStrongFixed_;
228 /// List of unsatisfied objects - first numberOnList_ for strong branching
229 /// Trust results from strong branching for changing bounds
230 bool trustStrongForBound_;
231 /// Trust results from strong branching for valid solution
232 bool trustStrongForSolution_;
233};
234
235/** This class is the placeholder for the pseudocosts used by OsiChooseStrong.
236 It can also be used by any other pseudocost based strong branching
237 algorithm.
238*/
239
240class OsiPseudoCosts {
241protected:
242 // Data
243 /// Total of all changes up
244 double * upTotalChange_;
245 /// Total of all changes down
246 double * downTotalChange_;
247 /// Number of times up
248 int * upNumber_;
249 /// Number of times down
250 int * downNumber_;
251 /// Number of objects (could be found from solver)
252 int numberObjects_;
253 /// Number before we trust
254 int numberBeforeTrusted_;
255
256private:
257 void gutsOfDelete();
258 void gutsOfCopy(const OsiPseudoCosts& rhs);
259
260public:
261 OsiPseudoCosts();
262 virtual ~OsiPseudoCosts();
263 OsiPseudoCosts(const OsiPseudoCosts& rhs);
264 OsiPseudoCosts& operator=(const OsiPseudoCosts& rhs);
265
266 /// Number of times before trusted
267 inline int numberBeforeTrusted() const
268 { return numberBeforeTrusted_; }
269 /// Set number of times before trusted
270 inline void setNumberBeforeTrusted(int value)
271 { numberBeforeTrusted_ = value; }
272 /// Initialize the pseudocosts with n entries
273 void initialize(int n);
274 /// Give the number of objects for which pseudo costs are stored
275 inline int numberObjects() const
276 { return numberObjects_; }
277
278 /** @name Accessor methods to pseudo costs data */
279 //@{
280 inline double* upTotalChange() { return upTotalChange_; }
281 inline const double* upTotalChange() const { return upTotalChange_; }
282
283 inline double* downTotalChange() { return downTotalChange_; }
284 inline const double* downTotalChange() const { return downTotalChange_; }
285
286 inline int* upNumber() { return upNumber_; }
287 inline const int* upNumber() const { return upNumber_; }
288
289 inline int* downNumber() { return downNumber_; }
290 inline const int* downNumber() const { return downNumber_; }
291 //@}
292
293 /// Given a candidate fill in useful information e.g. estimates
294 virtual void updateInformation(const OsiBranchingInformation *info,
295 int branch, OsiHotInfo * hotInfo);
296#if 1
297 /// Given a branch fill in useful information e.g. estimates
298 virtual void updateInformation( int whichObject, int branch,
299 double changeInObjective, double changeInValue,
300 int status);
301#endif
302};
303
304/** This class chooses a variable to branch on
305
306 This chooses the variable and direction with reliability strong branching.
307
308 The flow is :
309 a) initialize the process. This decides on strong branching list
310 and stores indices of all infeasible objects
311 b) do strong branching on list. If list is empty then just
312 choose one candidate and return without strong branching. If not empty then
313 go through list and return best. However we may find that the node is infeasible
314 or that we can fix a variable. If so we return and it is up to user to call
315 again (after fixing a variable).
316*/
317
318class OsiChooseStrong : public OsiChooseVariable {
319
320public:
321
322 /// Default Constructor
323 OsiChooseStrong ();
324
325 /// Constructor from solver (so we can set up arrays etc)
326 OsiChooseStrong (const OsiSolverInterface * solver);
327
328 /// Copy constructor
329 OsiChooseStrong (const OsiChooseStrong &);
330
331 /// Assignment operator
332 OsiChooseStrong & operator= (const OsiChooseStrong& rhs);
333
334 /// Clone
335 virtual OsiChooseVariable * clone() const override;
336
337 /// Destructor
338 virtual ~OsiChooseStrong ();
339
340 /** Sets up strong list and clears all if initialize is true.
341 Returns number of infeasibilities.
342 If returns -1 then has worked out node is infeasible!
343 */
344 virtual int setupList ( OsiBranchingInformation *info, bool initialize) override;
345 /** Choose a variable
346 Returns -
347 -1 Node is infeasible
348 0 Normal termination - we have a candidate
349 1 All looks satisfied - no candidate
350 2 We can change the bound on a variable - but we also have a strong branching candidate
351 3 We can change the bound on a variable - but we have a non-strong branching candidate
352 4 We can change the bound on a variable - no other candidates
353 We can pick up branch from bestObjectIndex() and bestWhichWay()
354 We can pick up a forced branch (can change bound) from firstForcedObjectIndex() and firstForcedWhichWay()
355 If we have a solution then we can pick up from goodObjectiveValue() and goodSolution()
356 If fixVariables is true then 2,3,4 are all really same as problem changed
357 */
358 virtual int chooseVariable( OsiSolverInterface * solver, OsiBranchingInformation *info, bool fixVariables) override;
359
360 /** Pseudo Shadow Price mode
361 0 - off
362 1 - use if no strong info
363 2 - use if strong not trusted
364 3 - use even if trusted
365 */
366 inline int shadowPriceMode() const
367 { return shadowPriceMode_;}
368 /// Set Shadow price mode
369 inline void setShadowPriceMode(int value)
370 { shadowPriceMode_ = value;}
371
372 /** Accessor method to pseudo cost object*/
373 const OsiPseudoCosts& pseudoCosts() const
374 { return pseudoCosts_; }
375
376 /** Accessor method to pseudo cost object*/
377 OsiPseudoCosts& pseudoCosts()
378 { return pseudoCosts_; }
379
380 /** A feww pass-through methods to access members of pseudoCosts_ as if they
381 were members of OsiChooseStrong object */
382 inline int numberBeforeTrusted() const {
383 return pseudoCosts_.numberBeforeTrusted(); }
384 inline void setNumberBeforeTrusted(int value) {
385 pseudoCosts_.setNumberBeforeTrusted(value); }
386 inline int numberObjects() const {
387 return pseudoCosts_.numberObjects(); }
388
389protected:
390
391 /** This is a utility function which does strong branching on
392 a list of objects and stores the results in OsiHotInfo.objects.
393 On entry the object sequence is stored in the OsiHotInfo object
394 and maybe more.
395 It returns -
396 -1 - one branch was infeasible both ways
397 0 - all inspected - nothing can be fixed
398 1 - all inspected - some can be fixed (returnCriterion==0)
399 2 - may be returning early - one can be fixed (last one done) (returnCriterion==1)
400 3 - returning because max time
401
402 */
403 int doStrongBranching( OsiSolverInterface * solver,
404 OsiBranchingInformation *info,
405 int numberToDo, int returnCriterion);
406
407 /** Clear out the results array */
408 void resetResults(int num);
409
410protected:
411 /** Pseudo Shadow Price mode
412 0 - off
413 1 - use and multiply by strong info
414 2 - use
415 */
416 int shadowPriceMode_;
417
418 /** The pseudo costs for the chooser */
419 OsiPseudoCosts pseudoCosts_;
420
421 /** The results of the strong branching done on the candidates where the
422 pseudocosts were not sufficient */
423 OsiHotInfo* results_;
424 /** The number of OsiHotInfo objetcs that contain information */
425 int numResults_;
426};
427
428/** This class contains the result of strong branching on a variable
429 When created it stores enough information for strong branching
430*/
431
432class OsiHotInfo {
433
434public:
435
436 /// Default Constructor
437 OsiHotInfo ();
438
439 /// Constructor from useful information
440 OsiHotInfo ( OsiSolverInterface * solver,
441 const OsiBranchingInformation *info,
442 const OsiObject * const * objects,
443 int whichObject);
444
445 /// Copy constructor
446 OsiHotInfo (const OsiHotInfo &);
447
448 /// Assignment operator
449 OsiHotInfo & operator= (const OsiHotInfo& rhs);
450
451 /// Clone
452 virtual OsiHotInfo * clone() const;
453
454 /// Destructor
455 virtual ~OsiHotInfo ();
456
457 /** Fill in useful information after strong branch.
458 Return status
459 */
460 int updateInformation( const OsiSolverInterface * solver, const OsiBranchingInformation * info,
461 OsiChooseVariable * choose);
462 /// Original objective value
463 inline double originalObjectiveValue() const
464 { return originalObjectiveValue_;}
465 /// Up change - invalid if n-way
466 inline double upChange() const
467 { assert (branchingObject_->numberBranches()==2); return changes_[1];}
468 /// Down change - invalid if n-way
469 inline double downChange() const
470 { assert (branchingObject_->numberBranches()==2); return changes_[0];}
471 /// Set up change - invalid if n-way
472 inline void setUpChange(double value)
473 { assert (branchingObject_->numberBranches()==2); changes_[1] = value;}
474 /// Set down change - invalid if n-way
475 inline void setDownChange(double value)
476 { assert (branchingObject_->numberBranches()==2); changes_[0] = value;}
477 /// Change on way k
478 inline double change(int k) const
479 { return changes_[k];}
480
481 /// Up iteration count - invalid if n-way
482 inline int upIterationCount() const
483 { assert (branchingObject_->numberBranches()==2); return iterationCounts_[1];}
484 /// Down iteration count - invalid if n-way
485 inline int downIterationCount() const
486 { assert (branchingObject_->numberBranches()==2); return iterationCounts_[0];}
487 /// Iteration count on way k
488 inline int iterationCount(int k) const
489 { return iterationCounts_[k];}
490
491 /// Up status - invalid if n-way
492 inline int upStatus() const
493 { assert (branchingObject_->numberBranches()==2); return statuses_[1];}
494 /// Down status - invalid if n-way
495 inline int downStatus() const
496 { assert (branchingObject_->numberBranches()==2); return statuses_[0];}
497 /// Set up status - invalid if n-way
498 inline void setUpStatus(int value)
499 { assert (branchingObject_->numberBranches()==2); statuses_[1] = value;}
500 /// Set down status - invalid if n-way
501 inline void setDownStatus(int value)
502 { assert (branchingObject_->numberBranches()==2); statuses_[0] = value;}
503 /// Status on way k
504 inline int status(int k) const
505 { return statuses_[k];}
506 /// Branching object
507 inline OsiBranchingObject * branchingObject() const
508 { return branchingObject_;}
509 inline int whichObject() const
510 { return whichObject_;}
511
512protected:
513 // Data
514 /// Original objective value
515 double originalObjectiveValue_;
516 /// Objective changes
517 double * changes_;
518 /// Iteration counts
519 int * iterationCounts_;
520 /** Status
521 -1 - not done
522 0 - feasible and finished
523 1 - infeasible
524 2 - not finished
525 */
526 int * statuses_;
527 /// Branching object
528 OsiBranchingObject * branchingObject_;
529 /// Which object on list
530 int whichObject_;
531};
532
533
534#endif
535