source: trunk/Cbc/src/CbcBranchActual.hpp @ 1121

Last change on this file since 1121 was 1121, checked in by forrest, 11 years ago

compiler warnings, deterministic parallel and stability

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 53.3 KB
Line 
1// Copyright (C) 2002, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#ifndef CbcBranchActual_H
4#define CbcBranchActual_H
5
6#include "CbcBranchBase.hpp"
7#include "CoinPackedMatrix.hpp"
8class CbcIntegerBranchingObject;
9/// Define a clique class
10
11
12class CbcClique : public CbcObject {
13
14public:
15
16  // Default Constructor
17  CbcClique ();
18
19  /** Useful constructor (which are integer indices)
20      slack can denote a slack in set.
21      If type == NULL then as if 1
22  */
23  CbcClique (CbcModel * model, int cliqueType, int numberMembers,
24             const int * which, const char * type,
25             int identifier,int slack=-1);
26 
27  // Copy constructor
28  CbcClique ( const CbcClique &);
29   
30  /// Clone
31  virtual CbcObject * clone() const;
32
33  // Assignment operator
34  CbcClique & operator=( const CbcClique& rhs);
35
36  // Destructor
37  virtual ~CbcClique ();
38 
39  using CbcObject::infeasibility ;
40  /// Infeasibility - large is 0.5
41  virtual double infeasibility(int & preferredWay) const;
42
43  using CbcObject::feasibleRegion ;
44  /// This looks at solution and sets bounds to contain solution
45  virtual void feasibleRegion();
46
47  using CbcObject::createBranch ;
48  /// Creates a branching object
49  virtual CbcBranchingObject * createBranch(int way) ;
50  /// Number of members
51  inline int numberMembers() const
52  {return numberMembers_;}
53
54  /// Number of Non SOS members i.e. fixing to zero is strong
55  inline int numberNonSOSMembers() const
56  {return numberNonSOSMembers_;}
57
58  /// Members (indices in range 0 ... numberIntegers_-1)
59  inline const int * members() const
60  {return members_;}
61
62  /** Type of each member i.e. which way is strong 0=non SOS, 1 =SOS,
63      index is 0 ... numberMembers_-1 */
64  inline char type(int index) const
65  {if (type_) return type_[index]; else return 1;}
66
67  /// Clique type - 0 <=, 1 ==
68  inline int cliqueType() const
69  {return cliqueType_;}
70  /// Redoes data when sequence numbers change
71  virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns);
72
73protected:
74  /// data
75  /// Number of members
76  int numberMembers_;
77
78  /// Number of Non SOS members i.e. fixing to zero is strong
79  int numberNonSOSMembers_;
80
81  /// Members (indices in range 0 ... numberIntegers_-1)
82  int * members_;
83
84  /// Type of each member 0=SOS, 1 =clique
85  char * type_;
86
87  /// Clique type - 0 <=, 1 ==
88   int cliqueType_;
89
90  /// Which one is slack (if any) sequence within this set
91  int slack_;
92};
93
94/** Define Special Ordered Sets of type 1 and 2.  These do not have to be
95    integer - so do not appear in lists of integers.
96   
97    which_ points directly to columns of matrix
98*/
99
100
101class CbcSOS : public CbcObject {
102
103public:
104
105  // Default Constructor
106  CbcSOS ();
107
108  /** Useful constructor - which are indices
109      and  weights are also given.  If null then 0,1,2..
110      type is SOS type
111  */
112  CbcSOS (CbcModel * model, int numberMembers,
113           const int * which, const double * weights, int identifier,
114          int type=1);
115 
116  // Copy constructor
117  CbcSOS ( const CbcSOS &);
118   
119  /// Clone
120  virtual CbcObject * clone() const;
121
122  // Assignment operator
123  CbcSOS & operator=( const CbcSOS& rhs);
124
125  // Destructor
126  virtual ~CbcSOS ();
127 
128  using CbcObject::infeasibility ;
129  /// Infeasibility - large is 0.5
130  virtual double infeasibility(int & preferredWay) const;
131  /// Infeasibility - large is 0.5
132  virtual double infeasibility(const OsiBranchingInformation * info, 
133                               int & preferredWay) const;
134
135  using CbcObject::feasibleRegion ;
136  /// This looks at solution and sets bounds to contain solution
137  virtual void feasibleRegion();
138
139  using CbcObject::createBranch ;
140  /// Creates a branching object
141  virtual CbcBranchingObject * createBranch(int way) ;
142
143
144
145  /** Pass in information on branch just done and create CbcObjectUpdateData instance.
146      If object does not need data then backward pointer will be NULL.
147      Assumes can get information from solver */
148  virtual CbcObjectUpdateData createUpdateInformation(const OsiSolverInterface * solver, 
149                                                        const CbcNode * node,
150                                                        const CbcBranchingObject * branchingObject);
151  /// Update object by CbcObjectUpdateData
152  virtual void updateInformation(const CbcObjectUpdateData & data) ;
153  using CbcObject::solverBranch ;
154  /** Create an OsiSolverBranch object
155
156      This returns NULL if branch not represented by bound changes
157  */
158  virtual OsiSolverBranch * solverBranch() const;
159  /// Redoes data when sequence numbers change
160  virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns);
161 
162  /// Construct an OsiSOS object
163  OsiSOS * osiObject(const OsiSolverInterface * solver) const;
164  /// Number of members
165  inline int numberMembers() const
166  {return numberMembers_;}
167
168  /// Members (indices in range 0 ... numberColumns-1)
169  inline const int * members() const
170  {return members_;}
171
172  /// SOS type
173  inline int sosType() const
174  {return sosType_;}
175  /// Down number times
176  inline int numberTimesDown() const
177  { return numberTimesDown_;}
178  /// Up number times
179  inline int numberTimesUp() const
180  { return numberTimesUp_;}
181
182  /** Array of weights */
183  inline const double * weights() const
184  { return weights_;}
185
186  /// Set number of members
187  inline void setNumberMembers(int n)
188  {numberMembers_ = n;}
189
190  /// Members (indices in range 0 ... numberColumns-1)
191  inline int * mutableMembers() const
192  {return members_;}
193
194  /** Array of weights */
195  inline double * mutableWeights() const
196  { return weights_;}
197
198  /** \brief Return true if object can take part in normal heuristics
199  */
200  virtual bool canDoHeuristics() const 
201  {return (sosType_==1&&integerValued_);}
202  /// Set whether set is integer valued or not
203  inline void setIntegerValued(bool yesNo)
204  { integerValued_=yesNo;}
205private:
206  /// data
207
208  /// Members (indices in range 0 ... numberColumns-1)
209  int * members_;
210  /// Weights
211  double * weights_;
212  /// Current pseudo-shadow price estimate down
213  mutable double shadowEstimateDown_;
214  /// Current pseudo-shadow price estimate up
215  mutable double shadowEstimateUp_;
216  /// Down pseudo ratio
217  double downDynamicPseudoRatio_;
218  /// Up pseudo ratio
219  double upDynamicPseudoRatio_;
220  /// Number of times we have gone down
221  int numberTimesDown_;
222  /// Number of times we have gone up
223  int numberTimesUp_;
224  /// Number of members
225  int numberMembers_;
226  /// SOS type
227  int sosType_;
228  /// Whether integer valued
229  bool integerValued_;
230};
231
232/// Define a single integer class
233
234
235class CbcSimpleInteger : public CbcObject {
236
237public:
238
239  // Default Constructor
240  CbcSimpleInteger ();
241
242  // Useful constructor - passed model and index
243  CbcSimpleInteger (CbcModel * model,  int iColumn, double breakEven=0.5);
244 
245  // Useful constructor - passed model and Osi object
246  CbcSimpleInteger (CbcModel * model,  const OsiSimpleInteger * object);
247 
248  // Copy constructor
249  CbcSimpleInteger ( const CbcSimpleInteger &);
250   
251  /// Clone
252  virtual CbcObject * clone() const;
253
254  // Assignment operator
255  CbcSimpleInteger & operator=( const CbcSimpleInteger& rhs);
256
257  // Destructor
258  virtual ~CbcSimpleInteger ();
259  /// Construct an OsiSimpleInteger object
260  OsiSimpleInteger * osiObject() const;
261  using CbcObject::infeasibility ;
262  /// Infeasibility - large is 0.5
263  virtual double infeasibility(const OsiSolverInterface * solver, 
264                               const OsiBranchingInformation * info, int & preferredWay) const;
265
266  using CbcObject::feasibleRegion ;
267  /** Set bounds to fix the variable at the current (integer) value.
268
269    Given an integer value, set the lower and upper bounds to fix the
270    variable. Returns amount it had to move variable.
271  */
272  virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
273
274  using CbcObject::createBranch ;
275  /** Create a branching object and indicate which way to branch first.
276     
277      The branching object has to know how to create branches (fix
278      variables, etc.)
279  */
280  virtual CbcBranchingObject * createBranch(OsiSolverInterface * solver,
281                                            const OsiBranchingInformation * info, int way) ;
282  /// Fills in a created branching object
283  void fillCreateBranch(CbcIntegerBranchingObject * branching, const OsiBranchingInformation * info, int way) ;
284
285  using CbcObject::solverBranch ;
286  /** Create an OsiSolverBranch object
287
288      This returns NULL if branch not represented by bound changes
289  */
290  virtual OsiSolverBranch * solverBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
291  /// Infeasibility - large is 0.5
292  virtual double infeasibility(int & preferredWay) const;
293
294  /** Set bounds to fix the variable at the current (integer) value.
295
296    Given an integer value, set the lower and upper bounds to fix the
297    variable. The algorithm takes a bit of care in order to compensate for
298    minor numerical inaccuracy.
299  */
300  virtual void feasibleRegion();
301
302  /** Creates a branching object
303
304    The preferred direction is set by \p way, -1 for down, +1 for up.
305  */
306  virtual CbcBranchingObject * createBranch(int way) ;
307  /** Column number if single column object -1 otherwise,
308      so returns >= 0
309      Used by heuristics
310  */
311  virtual int columnNumber() const;
312  /// Set column number
313  inline void setColumnNumber(int value)
314  { columnNumber_ = value;}
315
316  /** Reset variable bounds to their original values.
317 
318    Bounds may be tightened, so it may be good to be able to set this info in object.
319   */
320  virtual void resetBounds(const OsiSolverInterface * solver) ;
321  /**  Change column numbers after preprocessing
322   */
323  virtual void resetSequenceEtc(int numberColumns, const int * originalColumns) ;
324  /// Original bounds
325  inline double originalLowerBound() const
326  { return originalLower_;}
327  inline void setOriginalLowerBound(double value)
328  { originalLower_=value;}
329  inline double originalUpperBound() const
330  { return originalUpper_;}
331  inline void setOriginalUpperBound(double value)
332  { originalUpper_=value;}
333  /// Breakeven e.g 0.7 -> >= 0.7 go up first
334  inline double breakEven() const
335  { return breakEven_;}
336  /// Set breakeven e.g 0.7 -> >= 0.7 go up first
337  inline void setBreakEven(double value)
338  { breakEven_=value;}
339
340
341protected:
342  /// data
343
344  /// Original lower bound
345  double originalLower_;
346  /// Original upper bound
347  double originalUpper_;
348  /// Breakeven i.e. >= this preferred is up
349  double breakEven_;
350  /// Column number in model
351  int columnNumber_;
352  /// If -1 down always chosen first, +1 up always, 0 normal
353  int preferredWay_;
354};
355/** Define an n-way class for variables.
356    Only valid value is one at UB others at LB
357    Normally 0-1
358*/
359
360
361class CbcNWay : public CbcObject {
362
363public:
364
365  // Default Constructor
366  CbcNWay ();
367
368  /** Useful constructor (which are matrix indices)
369  */
370  CbcNWay (CbcModel * model, int numberMembers,
371             const int * which, int identifier);
372 
373  // Copy constructor
374  CbcNWay ( const CbcNWay &);
375   
376  /// Clone
377  virtual CbcObject * clone() const;
378
379  /// Assignment operator
380  CbcNWay & operator=( const CbcNWay& rhs);
381
382  /// Destructor
383  virtual ~CbcNWay ();
384
385  /// Set up a consequence for a single member
386  void setConsequence(int iColumn, const CbcConsequence & consequence);
387 
388  /// Applies a consequence for a single member
389  void applyConsequence(int iSequence, int state) const;
390 
391  using CbcObject::infeasibility ;
392  /// Infeasibility - large is 0.5 (and 0.5 will give this)
393  virtual double infeasibility(int & preferredWay) const;
394
395  using CbcObject::feasibleRegion ;
396  /// This looks at solution and sets bounds to contain solution
397  virtual void feasibleRegion();
398
399  using CbcObject::createBranch ;
400  /// Creates a branching object
401  virtual CbcBranchingObject * createBranch(int way) ;
402
403  /// Number of members
404  inline int numberMembers() const
405  {return numberMembers_;}
406
407  /// Members (indices in range 0 ... numberColumns-1)
408  inline const int * members() const
409  {return members_;}
410  /// Redoes data when sequence numbers change
411  virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns);
412
413protected:
414  /// data
415  /// Number of members
416  int numberMembers_;
417
418  /// Members (indices in range 0 ... numberColumns-1)
419  int * members_;
420  /// Consequences (normally NULL)
421  CbcConsequence ** consequence_;
422};
423
424/** Simple branching object for an integer variable
425
426  This object can specify a two-way branch on an integer variable. For each
427  arm of the branch, the upper and lower bounds on the variable can be
428  independently specified.
429 
430  Variable_ holds the index of the integer variable in the integerVariable_
431  array of the model.
432*/
433
434class CbcIntegerBranchingObject : public CbcBranchingObject {
435
436public:
437
438  /// Default constructor
439  CbcIntegerBranchingObject ();
440
441  /** Create a standard floor/ceiling branch object
442
443    Specifies a simple two-way branch. Let \p value = x*. One arm of the
444    branch will be lb <= x <= floor(x*), the other ceil(x*) <= x <= ub.
445    Specify way = -1 to set the object state to perform the down arm first,
446    way = 1 for the up arm.
447  */
448  CbcIntegerBranchingObject (CbcModel *model, int variable,
449                             int way , double value) ;
450 
451  /** Create a degenerate branch object
452
453    Specifies a `one-way branch'. Calling branch() for this object will
454    always result in lowerValue <= x <= upperValue. Used to fix a variable
455    when lowerValue = upperValue.
456  */
457
458  CbcIntegerBranchingObject (CbcModel *model, int variable, int way,
459                             double lowerValue, double upperValue) ;
460 
461  /// Copy constructor
462  CbcIntegerBranchingObject ( const CbcIntegerBranchingObject &);
463   
464  /// Assignment operator
465  CbcIntegerBranchingObject & operator= (const CbcIntegerBranchingObject& rhs);
466
467  /// Clone
468  virtual CbcBranchingObject * clone() const;
469
470  /// Destructor
471  virtual ~CbcIntegerBranchingObject ();
472
473  /// Does part of constructor
474  void fillPart ( int variable, int way , double value) ;
475  using CbcBranchingObject::branch ;
476  /** \brief Sets the bounds for the variable according to the current arm
477             of the branch and advances the object state to the next arm.
478             Returns change in guessed objective on next branch
479  */
480  virtual double branch();
481  /** Update bounds in solver as in 'branch' and update given bounds.
482      branchState is -1 for 'down' +1 for 'up' */
483  virtual void fix(OsiSolverInterface * solver,
484                   double * lower, double * upper,
485                   int branchState) const ;
486
487#if 0
488  // No need to override. Default works fine.
489  /** Reset every information so that the branching object appears to point to
490      the previous child. This method does not need to modify anything in any
491      solver. */
492  virtual void previousBranch();
493#endif
494
495  using CbcBranchingObject::print ;
496  /** \brief Print something about branch - only if log level high
497  */
498  virtual void print();
499
500  /// Lower and upper bounds for down branch
501  inline const double * downBounds() const
502  { return down_;}
503  /// Lower and upper bounds for up branch
504  inline const double * upBounds() const
505  { return up_;}
506  /// Set lower and upper bounds for down branch
507  inline void setDownBounds(const double bounds[2])
508  { memcpy(down_,bounds,2*sizeof(double));}
509  /// Set lower and upper bounds for up branch
510  inline void setUpBounds(const double bounds[2])
511  { memcpy(up_,bounds,2*sizeof(double));}
512#ifdef FUNNY_BRANCHING
513  /** Which variable (top bit if upper bound changing,
514      next bit if on down branch */
515  inline const int * variables() const
516  { return variables_;}
517  // New bound
518  inline const double * newBounds() const
519  { return newBounds_;}
520  /// Number of bound changes
521  inline int numberExtraChangedBounds() const
522  { return numberExtraChangedBounds_;}
523  /// Just apply extra bounds to one variable - COIN_DBL_MAX ignore
524  int applyExtraBounds(int iColumn, double lower, double upper, int way) ;
525  /// Deactivate bounds for branching
526  void deactivate();
527  /// Are active bounds for branching
528  inline bool active() const
529  { return (down_[1]!=-COIN_DBL_MAX);}
530#endif
531
532  /** Return the type (an integer identifier) of \c this */
533  virtual int type() const { return 100; }
534
535  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
536      same type and must have the same original object, but they may have
537      different feasible regions.
538      Return the appropriate CbcRangeCompare value (first argument being the
539      sub/superset if that's the case). In case of overlap (and if \c
540      replaceIfOverlap is true) replace the current branching object with one
541      whose feasible region is the overlap.
542   */
543  virtual CbcRangeCompare compareBranchingObject
544  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
545
546protected:
547  /// Lower [0] and upper [1] bounds for the down arm (way_ = -1)
548  double down_[2];
549  /// Lower [0] and upper [1] bounds for the up arm (way_ = 1)
550  double up_[2];
551#ifdef FUNNY_BRANCHING
552  /** Which variable (top bit if upper bound changing)
553      next bit if changing on down branch only */
554  int * variables_;
555  // New bound
556  double * newBounds_;
557  /// Number of Extra bound changes
558  int numberExtraChangedBounds_;
559#endif
560};
561
562
563/// Define a single integer class but with pseudo costs
564
565
566class CbcSimpleIntegerPseudoCost : public CbcSimpleInteger {
567
568public:
569
570  // Default Constructor
571  CbcSimpleIntegerPseudoCost ();
572
573  // Useful constructor - passed model index
574  CbcSimpleIntegerPseudoCost (CbcModel * model, int iColumn, double breakEven=0.5);
575 
576  // Useful constructor - passed and model index and pseudo costs
577  CbcSimpleIntegerPseudoCost (CbcModel * model, int iColumn, 
578                              double downPseudoCost, double upPseudoCost);
579  // Useful constructor - passed and model index and pseudo costs
580  CbcSimpleIntegerPseudoCost (CbcModel * model, int dummy,int iColumn, 
581                              double downPseudoCost, double upPseudoCost);
582 
583  // Copy constructor
584  CbcSimpleIntegerPseudoCost ( const CbcSimpleIntegerPseudoCost &);
585   
586  /// Clone
587  virtual CbcObject * clone() const;
588
589  // Assignment operator
590  CbcSimpleIntegerPseudoCost & operator=( const CbcSimpleIntegerPseudoCost& rhs);
591
592  // Destructor
593  virtual ~CbcSimpleIntegerPseudoCost ();
594 
595  using CbcObject::infeasibility ;
596  /// Infeasibility - large is 0.5
597  virtual double infeasibility(int & preferredWay) const;
598
599  using CbcObject::createBranch ;
600  /// Creates a branching object
601  virtual CbcBranchingObject * createBranch(int way) ;
602
603  /// Down pseudo cost
604  inline double downPseudoCost() const
605  { return downPseudoCost_;}
606  /// Set down pseudo cost
607  inline void setDownPseudoCost(double value)
608  { downPseudoCost_=value;}
609
610  /// Up pseudo cost
611  inline double upPseudoCost() const
612  { return upPseudoCost_;}
613  /// Set up pseudo cost
614  inline void setUpPseudoCost(double value)
615  { upPseudoCost_=value;}
616
617  /// Up down separator
618  inline double upDownSeparator() const
619  { return upDownSeparator_;}
620  /// Set up down separator
621  inline void setUpDownSeparator(double value)
622  { upDownSeparator_=value;}
623
624  /// Return "up" estimate
625  virtual double upEstimate() const;
626  /// Return "down" estimate (default 1.0e-5)
627  virtual double downEstimate() const;
628 
629  /// method - see below for details
630  inline int method() const
631  { return method_;}
632  /// Set method
633  inline void setMethod(int value)
634  { method_=value;}
635
636protected:
637  /// data
638
639  /// Down pseudo cost
640  double downPseudoCost_;
641  /// Up pseudo cost
642  double upPseudoCost_;
643  /** Up/down separator
644      If >0.0 then do first branch up if value-floor(value)
645      >= this value
646  */
647  double upDownSeparator_;
648  /** Method -
649      0 - normal - return min (up,down)
650      1 - if before any solution return CoinMax(up,down)
651      2 - if before branched solution return CoinMax(up,down)
652      3 - always return CoinMax(up,down)
653  */
654  int method_;
655};
656
657
658/** Simple branching object for an integer variable with pseudo costs
659
660  This object can specify a two-way branch on an integer variable. For each
661  arm of the branch, the upper and lower bounds on the variable can be
662  independently specified.
663 
664  Variable_ holds the index of the integer variable in the integerVariable_
665  array of the model.
666*/
667
668class CbcIntegerPseudoCostBranchingObject : public CbcIntegerBranchingObject {
669
670public:
671
672  /// Default constructor
673  CbcIntegerPseudoCostBranchingObject ();
674
675  /** Create a standard floor/ceiling branch object
676
677    Specifies a simple two-way branch. Let \p value = x*. One arm of the
678    branch will be is lb <= x <= floor(x*), the other ceil(x*) <= x <= ub.
679    Specify way = -1 to set the object state to perform the down arm first,
680    way = 1 for the up arm.
681  */
682  CbcIntegerPseudoCostBranchingObject (CbcModel *model, int variable,
683                             int way , double value) ;
684 
685  /** Create a degenerate branch object
686
687    Specifies a `one-way branch'. Calling branch() for this object will
688    always result in lowerValue <= x <= upperValue. Used to fix a variable
689    when lowerValue = upperValue.
690  */
691
692  CbcIntegerPseudoCostBranchingObject (CbcModel *model, int variable, int way,
693                             double lowerValue, double upperValue) ;
694 
695  /// Copy constructor
696  CbcIntegerPseudoCostBranchingObject ( const CbcIntegerPseudoCostBranchingObject &);
697   
698  /// Assignment operator
699  CbcIntegerPseudoCostBranchingObject & operator= (const CbcIntegerPseudoCostBranchingObject& rhs);
700
701  /// Clone
702  virtual CbcBranchingObject * clone() const;
703
704  /// Destructor
705  virtual ~CbcIntegerPseudoCostBranchingObject ();
706 
707  using CbcBranchingObject::branch ;
708  /** \brief Sets the bounds for the variable according to the current arm
709             of the branch and advances the object state to the next arm.
710             This version also changes guessed objective value
711  */
712  virtual double branch();
713
714  /// Change in guessed
715  inline double changeInGuessed() const
716  { return changeInGuessed_;}
717  /// Set change in guessed
718  inline void setChangeInGuessed(double value)
719  { changeInGuessed_=value;}
720
721  /** Return the type (an integer identifier) of \c this */
722  virtual int type() const { return 101; }
723
724  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
725      same type and must have the same original object, but they may have
726      different feasible regions.
727      Return the appropriate CbcRangeCompare value (first argument being the
728      sub/superset if that's the case). In case of overlap (and if \c
729      replaceIfOverlap is true) replace the current branching object with one
730      whose feasible region is the overlap.
731   */
732  virtual CbcRangeCompare compareBranchingObject
733  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
734
735protected:
736  /// Change in guessed objective value for next branch
737  double changeInGuessed_;
738};
739
740
741/** Branching object for unordered cliques
742
743    Intended for cliques which are long enough to make it worthwhile
744    but <= 64 members.  There will also be ones for long cliques.
745
746    Variable_ is the clique id number (redundant, as the object also holds a
747    pointer to the clique.
748 */
749class CbcCliqueBranchingObject : public CbcBranchingObject {
750
751public:
752
753  // Default Constructor
754  CbcCliqueBranchingObject ();
755
756  // Useful constructor
757  CbcCliqueBranchingObject (CbcModel * model,  const CbcClique * clique,
758                            int way,
759                            int numberOnDownSide, const int * down,
760                            int numberOnUpSide, const int * up);
761 
762  // Copy constructor
763  CbcCliqueBranchingObject ( const CbcCliqueBranchingObject &);
764   
765  // Assignment operator
766  CbcCliqueBranchingObject & operator=( const CbcCliqueBranchingObject& rhs);
767
768  /// Clone
769  virtual CbcBranchingObject * clone() const;
770
771  // Destructor
772  virtual ~CbcCliqueBranchingObject ();
773 
774  using CbcBranchingObject::branch ;
775  /// Does next branch and updates state
776  virtual double branch();
777
778#if 0
779  // No need to override. Default works fine.
780  /** Reset every information so that the branching object appears to point to
781      the previous child. This method does not need to modify anything in any
782      solver. */
783  virtual void previousBranch();
784#endif
785
786  using CbcBranchingObject::print ;
787  /** \brief Print something about branch - only if log level high
788  */
789  virtual void print();
790
791  /** Return the type (an integer identifier) of \c this */
792  virtual int type() const { return 102; }
793
794  /** Compare the original object of \c this with the original object of \c
795      brObj. Assumes that there is an ordering of the original objects.
796      This method should be invoked only if \c this and brObj are of the same
797      type.
798      Return negative/0/positive depending on whether \c this is
799      smaller/same/larger than the argument.
800  */
801  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
802
803  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
804      same type and must have the same original object, but they may have
805      different feasible regions.
806      Return the appropriate CbcRangeCompare value (first argument being the
807      sub/superset if that's the case). In case of overlap (and if \c
808      replaceIfOverlap is true) replace the current branching object with one
809      whose feasible region is the overlap.
810   */
811  virtual CbcRangeCompare compareBranchingObject
812  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
813
814private:
815  /// data
816  const CbcClique * clique_;
817  /// downMask - bit set to fix to weak bounds, not set to leave unfixed
818  unsigned int downMask_[2];
819  /// upMask - bit set to fix to weak bounds, not set to leave unfixed
820  unsigned int upMask_[2];
821};
822
823
824/** Unordered Clique Branching Object class.
825    These are for cliques which are > 64 members
826    Variable is number of clique.
827 */
828class CbcLongCliqueBranchingObject : public CbcBranchingObject {
829
830public:
831
832  // Default Constructor
833  CbcLongCliqueBranchingObject ();
834
835  // Useful constructor
836  CbcLongCliqueBranchingObject (CbcModel * model,  const CbcClique * clique,
837                                 int way,
838                            int numberOnDownSide, const int * down,
839                            int numberOnUpSide, const int * up);
840 
841  // Copy constructor
842  CbcLongCliqueBranchingObject ( const CbcLongCliqueBranchingObject &);
843   
844  // Assignment operator
845  CbcLongCliqueBranchingObject & operator=( const CbcLongCliqueBranchingObject& rhs);
846
847  /// Clone
848  virtual CbcBranchingObject * clone() const;
849
850  // Destructor
851  virtual ~CbcLongCliqueBranchingObject ();
852 
853  using CbcBranchingObject::branch ;
854  /// Does next branch and updates state
855  virtual double branch();
856
857#if 0
858  // No need to override. Default works fine.
859  /** Reset every information so that the branching object appears to point to
860      the previous child. This method does not need to modify anything in any
861      solver. */
862  virtual void previousBranch();
863#endif
864
865  using CbcBranchingObject::print ;
866  /** \brief Print something about branch - only if log level high
867  */
868  virtual void print();
869
870  /** Return the type (an integer identifier) of \c this */
871  virtual int type() const { return 103; }
872
873  /** Compare the original object of \c this with the original object of \c
874      brObj. Assumes that there is an ordering of the original objects.
875      This method should be invoked only if \c this and brObj are of the same
876      type.
877      Return negative/0/positive depending on whether \c this is
878      smaller/same/larger than the argument.
879  */
880  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
881
882  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
883      same type and must have the same original object, but they may have
884      different feasible regions.
885      Return the appropriate CbcRangeCompare value (first argument being the
886      sub/superset if that's the case). In case of overlap (and if \c
887      replaceIfOverlap is true) replace the current branching object with one
888      whose feasible region is the overlap.
889   */
890  virtual CbcRangeCompare compareBranchingObject
891  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
892
893private:
894  /// data
895  const CbcClique * clique_;
896  /// downMask - bit set to fix to weak bounds, not set to leave unfixed
897  unsigned int * downMask_;
898  /// upMask - bit set to fix to weak bounds, not set to leave unfixed
899  unsigned int * upMask_;
900};
901
902/** Branching object for Special ordered sets
903
904    Variable_ is the set id number (redundant, as the object also holds a
905    pointer to the set.
906 */
907class CbcSOSBranchingObject : public CbcBranchingObject {
908
909public:
910
911  // Default Constructor
912  CbcSOSBranchingObject ();
913
914  // Useful constructor
915  CbcSOSBranchingObject (CbcModel * model,  const CbcSOS * clique,
916                            int way,
917                         double separator);
918 
919  // Copy constructor
920  CbcSOSBranchingObject ( const CbcSOSBranchingObject &);
921   
922  // Assignment operator
923  CbcSOSBranchingObject & operator=( const CbcSOSBranchingObject& rhs);
924
925  /// Clone
926  virtual CbcBranchingObject * clone() const;
927
928  // Destructor
929  virtual ~CbcSOSBranchingObject ();
930 
931  using CbcBranchingObject::branch ;
932  /// Does next branch and updates state
933  virtual double branch();
934  /** Update bounds in solver as in 'branch' and update given bounds.
935      branchState is -1 for 'down' +1 for 'up' */
936  virtual void fix(OsiSolverInterface * solver,
937                   double * lower, double * upper,
938                   int branchState) const ;
939
940  /** Reset every information so that the branching object appears to point to
941      the previous child. This method does not need to modify anything in any
942      solver. */
943  virtual void previousBranch() {
944    CbcBranchingObject::previousBranch();
945    computeNonzeroRange();
946  }
947
948  using CbcBranchingObject::print ;
949  /** \brief Print something about branch - only if log level high
950  */
951  virtual void print();
952
953  /** Return the type (an integer identifier) of \c this */
954  virtual int type() const { return 104; }
955
956  /** Compare the original object of \c this with the original object of \c
957      brObj. Assumes that there is an ordering of the original objects.
958      This method should be invoked only if \c this and brObj are of the same
959      type.
960      Return negative/0/positive depending on whether \c this is
961      smaller/same/larger than the argument.
962  */
963  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
964
965  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
966      same type and must have the same original object, but they may have
967      different feasible regions.
968      Return the appropriate CbcRangeCompare value (first argument being the
969      sub/superset if that's the case). In case of overlap (and if \c
970      replaceIfOverlap is true) replace the current branching object with one
971      whose feasible region is the overlap.
972   */
973  virtual CbcRangeCompare compareBranchingObject
974  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
975
976  /** Fill out the \c firstNonzero_ and \c lastNonzero_ data members */
977  void computeNonzeroRange();
978
979private:
980  /// data
981  const CbcSOS * set_;
982  /// separator
983  double separator_;
984  /** The following two members describe the range in the members_ of the
985      original object that whose upper bound is not fixed to 0. This is not
986      necessary for Cbc to function correctly, this is there for heuristics so
987      that separate branching decisions on the same object can be pooled into
988      one branching object. */
989  int firstNonzero_;
990  int lastNonzero_;
991};
992
993/** N way branching Object class.
994    Variable is number of set.
995 */
996class CbcNWayBranchingObject : public CbcBranchingObject {
997
998public:
999
1000  // Default Constructor
1001  CbcNWayBranchingObject ();
1002
1003  /** Useful constructor - order had matrix indices
1004      way_ -1 corresponds to setting first, +1 to second, +3 etc.
1005      this is so -1 and +1 have similarity to normal
1006  */
1007  CbcNWayBranchingObject (CbcModel * model,  const CbcNWay * nway,
1008                          int numberBranches, const int * order);
1009 
1010  // Copy constructor
1011  CbcNWayBranchingObject ( const CbcNWayBranchingObject &);
1012   
1013  // Assignment operator
1014  CbcNWayBranchingObject & operator=( const CbcNWayBranchingObject& rhs);
1015
1016  /// Clone
1017  virtual CbcBranchingObject * clone() const;
1018
1019  // Destructor
1020  virtual ~CbcNWayBranchingObject ();
1021 
1022  using CbcBranchingObject::branch ;
1023  /// Does next branch and updates state
1024  virtual double branch();
1025
1026#if 0
1027  // FIXME: what do we need to do here?
1028  /** Reset every information so that the branching object appears to point to
1029      the previous child. This method does not need to modify anything in any
1030      solver. */
1031  virtual void previousBranch();
1032#endif
1033
1034  using CbcBranchingObject::print ;
1035  /** \brief Print something about branch - only if log level high
1036  */
1037  virtual void print();
1038  /** The number of branch arms created for this branching object
1039  */
1040  virtual int numberBranches() const
1041  {return numberInSet_;}
1042  /// Is this a two way object (-1 down, +1 up)
1043  virtual bool twoWay() const
1044  { return false;}
1045
1046  /** Return the type (an integer identifier) of \c this */
1047  virtual int type() const { return 105; }
1048
1049  /** Compare the original object of \c this with the original object of \c
1050      brObj. Assumes that there is an ordering of the original objects.
1051      This method should be invoked only if \c this and brObj are of the same
1052      type.
1053      Return negative/0/positive depending on whether \c this is
1054      smaller/same/larger than the argument.
1055  */
1056  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
1057
1058  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
1059      same type and must have the same original object, but they may have
1060      different feasible regions.
1061      Return the appropriate CbcRangeCompare value (first argument being the
1062      sub/superset if that's the case). In case of overlap (and if \c
1063      replaceIfOverlap is true) replace the current branching object with one
1064      whose feasible region is the overlap.
1065   */
1066  virtual CbcRangeCompare compareBranchingObject
1067  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
1068
1069private:
1070  /// order of branching - points back to CbcNWay
1071  int * order_;
1072  /// Points back to object
1073  const CbcNWay * object_;
1074  /// Number in set
1075  int numberInSet_;
1076};
1077
1078/** Branching decision default class
1079
1080  This class implements a simple default algorithm
1081  (betterBranch()) for choosing a branching variable.
1082*/
1083
1084class CbcBranchDefaultDecision : public CbcBranchDecision {
1085public:
1086  // Default Constructor
1087  CbcBranchDefaultDecision ();
1088
1089  // Copy constructor
1090  CbcBranchDefaultDecision ( const CbcBranchDefaultDecision &);
1091
1092  virtual ~CbcBranchDefaultDecision();
1093
1094  /// Clone
1095  virtual CbcBranchDecision * clone() const;
1096
1097  /// Initialize, <i>e.g.</i> before the start of branch selection at a node
1098  virtual void initialize(CbcModel * model);
1099
1100  /** \brief Compare two branching objects. Return nonzero if \p thisOne is
1101             better than \p bestSoFar.
1102
1103    The routine compares branches using the values supplied in \p numInfUp and
1104    \p numInfDn until a solution is found by search, after which it uses the
1105    values supplied in \p changeUp and \p changeDn. The best branching object
1106    seen so far and the associated parameter values are remembered in the
1107    \c CbcBranchDefaultDecision object. The nonzero return value is +1 if the
1108    up branch is preferred, -1 if the down branch is preferred.
1109
1110    As the names imply, the assumption is that the values supplied for
1111    \p numInfUp and \p numInfDn will be the number of infeasibilities reported
1112    by the branching object, and \p changeUp and \p changeDn will be the
1113    estimated change in objective. Other measures can be used if desired.
1114
1115    Because an \c CbcBranchDefaultDecision object remembers the current best
1116    branching candidate (#bestObject_) as well as the values used in the
1117    comparison, the parameter \p bestSoFar is redundant, hence unused.
1118 */
1119  virtual int betterBranch(CbcBranchingObject * thisOne,
1120                            CbcBranchingObject * bestSoFar,
1121                            double changeUp, int numInfUp,
1122                            double changeDn, int numInfDn);
1123  /** Sets or gets best criterion so far */
1124  virtual void setBestCriterion(double value);
1125  virtual double getBestCriterion() const;
1126
1127  /** \brief Compare N branching objects. Return index of best
1128      and sets way of branching in chosen object.
1129   
1130    This routine is used only after strong branching.
1131  */
1132
1133  virtual int
1134  bestBranch (CbcBranchingObject ** objects, int numberObjects, int numberUnsatisfied,
1135              double * changeUp, int * numberInfeasibilitiesUp,
1136              double * changeDown, int * numberInfeasibilitiesDown,
1137              double objectiveValue) ;
1138private:
1139 
1140  /// Illegal Assignment operator
1141  CbcBranchDefaultDecision & operator=(const CbcBranchDefaultDecision& rhs);
1142
1143  /// data
1144
1145  /// "best" so far
1146  double bestCriterion_;
1147
1148  /// Change up for best
1149  double bestChangeUp_;
1150
1151  /// Number of infeasibilities for up
1152  int bestNumberUp_;
1153
1154  /// Change down for best
1155  double bestChangeDown_;
1156
1157  /// Pointer to best branching object
1158  CbcBranchingObject * bestObject_;
1159
1160  /// Number of infeasibilities for down
1161  int bestNumberDown_;
1162
1163};
1164
1165/** Define a follow on class.
1166    The idea of this is that in air-crew scheduling problems crew may fly in on flight A
1167    and out on flight B or on some other flight.  A useful branch is one which on one side
1168    fixes all which go out on flight B to 0, while the other branch fixes all those that do NOT
1169    go out on flight B to 0.
1170
1171    This branching rule should be in addition to normal rules and have a high priority.
1172*/
1173
1174
1175
1176class CbcFollowOn : public CbcObject {
1177
1178public:
1179
1180  // Default Constructor
1181  CbcFollowOn ();
1182
1183  /** Useful constructor
1184  */
1185  CbcFollowOn (CbcModel * model);
1186 
1187  // Copy constructor
1188  CbcFollowOn ( const CbcFollowOn &);
1189   
1190  /// Clone
1191  virtual CbcObject * clone() const;
1192
1193  // Assignment operator
1194  CbcFollowOn & operator=( const CbcFollowOn& rhs);
1195
1196  // Destructor
1197  ~CbcFollowOn ();
1198 
1199  using CbcObject::infeasibility ;
1200  /// Infeasibility - large is 0.5
1201  virtual double infeasibility(int & preferredWay) const;
1202
1203  using CbcObject::feasibleRegion ;
1204  /// This looks at solution and sets bounds to contain solution
1205  virtual void feasibleRegion();
1206
1207  using CbcObject::createBranch ;
1208  /// Creates a branching object
1209  virtual CbcBranchingObject * createBranch(int way) ;
1210  /// As some computation is needed in more than one place - returns row
1211  virtual int gutsOfFollowOn(int & otherRow, int & preferredWay) const;
1212
1213protected:
1214  /// data
1215  /// Matrix
1216  CoinPackedMatrix matrix_;
1217  /// Matrix by row
1218  CoinPackedMatrix matrixByRow_; 
1219  /// Possible rhs (if 0 then not possible)
1220  int * rhs_;
1221};
1222/** General Branching Object class.
1223    Each way fixes some variables to lower bound
1224 */
1225class CbcFixingBranchingObject : public CbcBranchingObject {
1226
1227public:
1228
1229  // Default Constructor
1230  CbcFixingBranchingObject ();
1231
1232  // Useful constructor
1233  CbcFixingBranchingObject (CbcModel * model, 
1234                            int way,
1235                            int numberOnDownSide, const int * down,
1236                            int numberOnUpSide, const int * up);
1237 
1238  // Copy constructor
1239  CbcFixingBranchingObject ( const CbcFixingBranchingObject &);
1240   
1241  // Assignment operator
1242  CbcFixingBranchingObject & operator=( const CbcFixingBranchingObject& rhs);
1243
1244  /// Clone
1245  virtual CbcBranchingObject * clone() const;
1246
1247  // Destructor
1248  virtual ~CbcFixingBranchingObject ();
1249 
1250  using CbcBranchingObject::branch ;
1251  /// Does next branch and updates state
1252  virtual double branch();
1253
1254#if 0
1255  // No need to override. Default works fine.
1256  /** Reset every information so that the branching object appears to point to
1257      the previous child. This method does not need to modify anything in any
1258      solver. */
1259  virtual void previousBranch();
1260#endif
1261
1262  using CbcBranchingObject::print ;
1263  /** \brief Print something about branch - only if log level high
1264  */
1265  virtual void print();
1266
1267  /** Return the type (an integer identifier) of \c this */
1268  virtual int type() const { return 106; }
1269
1270  /** Compare the original object of \c this with the original object of \c
1271      brObj. Assumes that there is an ordering of the original objects.
1272      This method should be invoked only if \c this and brObj are of the same
1273      type.
1274      Return negative/0/positive depending on whether \c this is
1275      smaller/same/larger than the argument.
1276  */
1277  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
1278
1279  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
1280      same type and must have the same original object, but they may have
1281      different feasible regions.
1282      Return the appropriate CbcRangeCompare value (first argument being the
1283      sub/superset if that's the case). In case of overlap (and if \c
1284      replaceIfOverlap is true) replace the current branching object with one
1285      whose feasible region is the overlap.
1286   */
1287  virtual CbcRangeCompare compareBranchingObject
1288  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
1289
1290private:
1291  /// data
1292  /// Number on down list
1293  int numberDown_;
1294  /// Number on up list
1295  int numberUp_;
1296  /// downList - variables to fix to lb on down branch
1297  int * downList_;
1298  /// upList - variables to fix to lb on up branch
1299  int * upList_;
1300};
1301/** Class for consequent bounds.
1302    When a variable is branched on it normally interacts with other variables by
1303    means of equations.  There are cases where we want to step outside LP and do something
1304    more directly e.g. fix bounds.  This class is for that.
1305
1306    A state of -9999 means at LB, +9999 means at UB,
1307    others mean if fixed to that value.
1308
1309 */
1310
1311class CbcFixVariable : public CbcConsequence {
1312
1313public:
1314
1315  // Default Constructor
1316  CbcFixVariable ();
1317
1318  // One useful Constructor
1319  CbcFixVariable (int numberStates,const int * states, const int * numberNewLower, const int ** newLowerValue,
1320                  const int ** lowerColumn,
1321                  const int * numberNewUpper, const int ** newUpperValue,
1322                  const int ** upperColumn);
1323
1324  // Copy constructor
1325  CbcFixVariable ( const CbcFixVariable & rhs);
1326   
1327  // Assignment operator
1328  CbcFixVariable & operator=( const CbcFixVariable & rhs);
1329
1330  /// Clone
1331  virtual CbcConsequence * clone() const;
1332
1333  /// Destructor
1334  virtual ~CbcFixVariable ();
1335
1336  /** Apply to an LP solver.  Action depends on state
1337   */
1338  virtual void applyToSolver(OsiSolverInterface * solver, int state) const;
1339 
1340protected:
1341  /// Number of states
1342  int numberStates_;
1343  /// Values of integers for various states
1344  int * states_;
1345  /// Start of information for each state (setting new lower)
1346  int * startLower_;
1347  /// Start of information for each state (setting new upper)
1348  int * startUpper_;
1349  /// For each variable new bounds
1350  double * newBound_;
1351  /// Variable
1352  int * variable_;
1353};
1354/** Dummy branching object
1355
1356  This object specifies a one-way dummy branch.
1357  This is so one can carry on branching even when it looks feasible
1358*/
1359
1360class CbcDummyBranchingObject : public CbcBranchingObject {
1361
1362public:
1363
1364  /// Default constructor
1365  CbcDummyBranchingObject (CbcModel * model=NULL);
1366
1367  /// Copy constructor
1368  CbcDummyBranchingObject ( const CbcDummyBranchingObject &);
1369   
1370  /// Assignment operator
1371  CbcDummyBranchingObject & operator= (const CbcDummyBranchingObject& rhs);
1372
1373  /// Clone
1374  virtual CbcBranchingObject * clone() const;
1375
1376  /// Destructor
1377  virtual ~CbcDummyBranchingObject ();
1378 
1379  using CbcBranchingObject::branch ;
1380  /** \brief Dummy branch
1381  */
1382  virtual double branch();
1383
1384#if 0
1385  // No need to override. Default works fine.
1386  /** Reset every information so that the branching object appears to point to
1387      the previous child. This method does not need to modify anything in any
1388      solver. */
1389  virtual void previousBranch();
1390#endif
1391
1392  using CbcBranchingObject::print ;
1393  /** \brief Print something about branch - only if log level high
1394  */
1395  virtual void print();
1396
1397  /** Return the type (an integer identifier) of \c this */
1398  virtual int type() const { return 107; }
1399
1400  /** Compare the original object of \c this with the original object of \c
1401      brObj. Assumes that there is an ordering of the original objects.
1402      This method should be invoked only if \c this and brObj are of the same
1403      type.
1404      Return negative/0/positive depending on whether \c this is
1405      smaller/same/larger than the argument.
1406  */
1407  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
1408
1409  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
1410      same type and must have the same original object, but they may have
1411      different feasible regions.
1412      Return the appropriate CbcRangeCompare value (first argument being the
1413      sub/superset if that's the case). In case of overlap (and if \c
1414      replaceIfOverlap is true) replace the current branching object with one
1415      whose feasible region is the overlap.
1416   */
1417  virtual CbcRangeCompare compareBranchingObject
1418  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
1419
1420};
1421
1422/** Define a catch all class.
1423    This will create a list of subproblems
1424*/
1425
1426
1427class CbcGeneral : public CbcObject {
1428
1429public:
1430
1431  // Default Constructor
1432  CbcGeneral ();
1433
1434  /** Useful constructor
1435      Just needs to point to model.
1436  */
1437  CbcGeneral (CbcModel * model);
1438 
1439  // Copy constructor
1440  CbcGeneral ( const CbcGeneral &);
1441   
1442  /// Clone
1443  virtual CbcObject * clone() const=0;
1444
1445  // Assignment operator
1446  CbcGeneral & operator=( const CbcGeneral& rhs);
1447
1448  // Destructor
1449  ~CbcGeneral ();
1450 
1451  using CbcObject::infeasibility ;
1452  /// Infeasibility - large is 0.5
1453  virtual double infeasibility(int & preferredWay) const=0;
1454
1455  using CbcObject::feasibleRegion ;
1456  /// This looks at solution and sets bounds to contain solution
1457  virtual void feasibleRegion()=0;
1458
1459  using CbcObject::createBranch ;
1460  /// Creates a branching object
1461  virtual CbcBranchingObject * createBranch(int way)=0 ;
1462
1463  /// Redoes data when sequence numbers change
1464  virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns)=0;
1465
1466protected:
1467  /// data
1468};
1469#ifdef COIN_HAS_CLP
1470
1471/** Define a catch all class.
1472    This will create a list of subproblems using partial evaluation
1473*/
1474#include "ClpSimplex.hpp"
1475#include "ClpNode.hpp"
1476
1477class CbcGeneralDepth : public CbcGeneral {
1478
1479public:
1480
1481  // Default Constructor
1482  CbcGeneralDepth ();
1483
1484  /** Useful constructor
1485      Just needs to point to model.
1486      Initial version does evaluation to depth N
1487      This is stored in CbcModel but may be
1488      better here
1489  */
1490  CbcGeneralDepth (CbcModel * model, int maximumDepth);
1491 
1492  // Copy constructor
1493  CbcGeneralDepth ( const CbcGeneralDepth &);
1494   
1495  /// Clone
1496  virtual CbcObject * clone() const;
1497
1498  // Assignment operator
1499  CbcGeneralDepth & operator=( const CbcGeneralDepth& rhs);
1500
1501  // Destructor
1502  ~CbcGeneralDepth ();
1503 
1504  using CbcObject::infeasibility ;
1505  /// Infeasibility - large is 0.5
1506  virtual double infeasibility(int & preferredWay) const;
1507
1508  using CbcObject::feasibleRegion ;
1509  /// This looks at solution and sets bounds to contain solution
1510  virtual void feasibleRegion();
1511
1512  using CbcObject::createBranch ;
1513  /// Creates a branching object
1514  virtual CbcBranchingObject * createBranch(int way) ;
1515  /// Return maximum number of nodes
1516  int maximumNodes() const;
1517  /// Get maximum depth
1518  inline int maximumDepth() const
1519  {return maximumDepth_;}
1520  /// Set maximum depth
1521  inline void setMaximumDepth(int value)
1522  {maximumDepth_ = value;}
1523  /// Get which solution
1524  inline int whichSolution() const
1525  {return whichSolution_;}
1526  /// Get ClpNode info
1527  inline ClpNode * nodeInfo(int which)
1528  { return nodeInfo_->nodeInfo_[which];}
1529
1530  /// Redoes data when sequence numbers change
1531  virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns);
1532
1533protected:
1534  /// data
1535  /// Maximum depth
1536  int maximumDepth_;
1537  /// Which node has solution (or -1)
1538  mutable int whichSolution_;
1539  /// Number of valid nodes (including whichSolution_)
1540  mutable int numberNodes_;
1541  /// For solving nodes
1542  mutable ClpNodeStuff * nodeInfo_;
1543};
1544
1545/** Defines a general subproblem
1546    Basis will be made more compact later
1547*/
1548class CoinWarmStartDiff;
1549class CbcSubProblem {
1550
1551public:
1552
1553  /// Default constructor
1554  CbcSubProblem ();
1555
1556  /// Constructor from model
1557  CbcSubProblem (const OsiSolverInterface * solver,
1558                 const double * lowerBefore,
1559                 const double * upperBefore,
1560                 const unsigned char * status,
1561                 int depth);
1562
1563  /// Copy constructor
1564  CbcSubProblem ( const CbcSubProblem &);
1565   
1566  /// Assignment operator
1567  CbcSubProblem & operator= (const CbcSubProblem& rhs);
1568
1569  /// Destructor
1570  virtual ~CbcSubProblem ();
1571
1572  /// Apply subproblem (1=bounds, 2=basis, 3=both)
1573  void apply(OsiSolverInterface * model, int what=3) const;
1574
1575public:
1576  /// Value of objective
1577  double objectiveValue_;
1578  /// Sum of infeasibilities
1579  double sumInfeasibilities_;
1580  /** Which variable (top bit if upper bound changing)
1581      next bit if changing on down branch only */
1582  int * variables_;
1583  /// New bound
1584  double * newBounds_;
1585  /// Status
1586  mutable CoinWarmStartBasis * status_;
1587  /// Depth
1588  int depth_;
1589  /// Number of Extra bound changes
1590  int numberChangedBounds_;
1591  /// Number of infeasibilities
1592  int numberInfeasibilities_;
1593};
1594
1595/** Branching object for general objects
1596
1597 */
1598class CbcNode;
1599class CbcGeneralBranchingObject : public CbcBranchingObject {
1600
1601public:
1602
1603  // Default Constructor
1604  CbcGeneralBranchingObject ();
1605
1606  // Useful constructor
1607  CbcGeneralBranchingObject (CbcModel * model);
1608 
1609  // Copy constructor
1610  CbcGeneralBranchingObject ( const CbcGeneralBranchingObject &);
1611   
1612  // Assignment operator
1613  CbcGeneralBranchingObject & operator=( const CbcGeneralBranchingObject& rhs);
1614
1615  /// Clone
1616  virtual CbcBranchingObject * clone() const;
1617
1618  // Destructor
1619  virtual ~CbcGeneralBranchingObject ();
1620 
1621  using CbcBranchingObject::branch ;
1622  /// Does next branch and updates state
1623  virtual double branch();
1624  /** Double checks in case node can change its mind!
1625      Can change objective etc */
1626  virtual void checkIsCutoff(double cutoff);
1627
1628  using CbcBranchingObject::print ;
1629  /** \brief Print something about branch - only if log level high
1630  */
1631  virtual void print();
1632  /// Fill in current objective etc
1633  void state(double & objectiveValue,double & sumInfeasibilities,
1634             int & numberUnsatisfied,int which) const;
1635  /// Set CbcNode
1636  inline void setNode(CbcNode * node)
1637  { node_ = node;}
1638  /** Return the type (an integer identifier) of \c this */
1639  virtual int type() const { return 108; }
1640
1641  /** Compare the original object of \c this with the original object of \c
1642      brObj. Assumes that there is an ordering of the original objects.
1643      This method should be invoked only if \c this and brObj are of the same
1644      type.
1645      Return negative/0/positive depending on whether \c this is
1646      smaller/same/larger than the argument.
1647  */
1648  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
1649
1650  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
1651      same type and must have the same original object, but they may have
1652      different feasible regions.
1653      Return the appropriate CbcRangeCompare value (first argument being the
1654      sub/superset if that's the case). In case of overlap (and if \c
1655      replaceIfOverlap is true) replace the current branching object with one
1656      whose feasible region is the overlap.
1657   */
1658  virtual CbcRangeCompare compareBranchingObject
1659  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
1660  /// Number of subproblems
1661  inline int numberSubProblems() const
1662  { return numberSubProblems_;}
1663  /// Decrement number left and return number
1664  inline int decrementNumberLeft()
1665  { numberSubLeft_--; return numberSubLeft_;}
1666  /// Which node we want to use
1667  inline int whichNode() const
1668  { return whichNode_;}
1669  /// Set which node we want to use
1670  inline void setWhichNode(int value)
1671  { whichNode_ = value;}
1672  // Sub problem
1673  const CbcSubProblem * subProblem(int which) const
1674  { return subProblems_+which;}
1675
1676public:
1677  /// data
1678  // Sub problems
1679  CbcSubProblem * subProblems_;
1680  /// Node
1681  CbcNode * node_;
1682  /// Number of subproblems
1683  int numberSubProblems_;
1684  /// Number of subproblems left
1685  int numberSubLeft_;
1686  /// Which node we want to use (-1 for default)
1687  int whichNode_;
1688  /// Number of rows
1689  int numberRows_;
1690};
1691
1692/** Branching object for general objects - just one
1693
1694 */
1695class CbcOneGeneralBranchingObject : public CbcBranchingObject {
1696
1697public:
1698
1699  // Default Constructor
1700  CbcOneGeneralBranchingObject ();
1701
1702  // Useful constructor
1703  CbcOneGeneralBranchingObject (CbcModel * model,
1704                                 CbcGeneralBranchingObject * object,
1705                                 int whichOne);
1706 
1707  // Copy constructor
1708  CbcOneGeneralBranchingObject ( const CbcOneGeneralBranchingObject &);
1709   
1710  // Assignment operator
1711  CbcOneGeneralBranchingObject & operator=( const CbcOneGeneralBranchingObject& rhs);
1712
1713  /// Clone
1714  virtual CbcBranchingObject * clone() const;
1715
1716  // Destructor
1717  virtual ~CbcOneGeneralBranchingObject ();
1718 
1719  using CbcBranchingObject::branch ;
1720  /// Does next branch and updates state
1721  virtual double branch();
1722  /** Double checks in case node can change its mind!
1723      Can change objective etc */
1724  virtual void checkIsCutoff(double cutoff);
1725
1726  using CbcBranchingObject::print ;
1727  /** \brief Print something about branch - only if log level high
1728  */
1729  virtual void print();
1730  /** Return the type (an integer identifier) of \c this */
1731  virtual int type() const { return 110; }
1732
1733  /** Compare the original object of \c this with the original object of \c
1734      brObj. Assumes that there is an ordering of the original objects.
1735      This method should be invoked only if \c this and brObj are of the same
1736      type.
1737      Return negative/0/positive depending on whether \c this is
1738      smaller/same/larger than the argument.
1739  */
1740  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
1741
1742  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
1743      same type and must have the same original object, but they may have
1744      different feasible regions.
1745      Return the appropriate CbcRangeCompare value (first argument being the
1746      sub/superset if that's the case). In case of overlap (and if \c
1747      replaceIfOverlap is true) replace the current branching object with one
1748      whose feasible region is the overlap.
1749   */
1750  virtual CbcRangeCompare compareBranchingObject
1751  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
1752
1753public:
1754  /// data
1755  /// Object
1756  CbcGeneralBranchingObject * object_;
1757  /// Which one
1758  int whichOne_;
1759};
1760#endif
1761#endif
Note: See TracBrowser for help on using the repository browser.