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

Last change on this file since 912 was 912, checked in by ladanyi, 13 years ago

Incorporated changes from branches/heur

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 42.2 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  ~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  ~CbcSOS ();
127 
128  using CbcObject::infeasibility ;
129  /// Infeasibility - large is 0.5
130  virtual double infeasibility(int & preferredWay) const;
131
132  using CbcObject::feasibleRegion ;
133  /// This looks at solution and sets bounds to contain solution
134  virtual void feasibleRegion();
135
136  using CbcObject::createBranch ;
137  /// Creates a branching object
138  virtual CbcBranchingObject * createBranch(int way) ;
139
140  using CbcObject::solverBranch ;
141  /** Create an OsiSolverBranch object
142
143      This returns NULL if branch not represented by bound changes
144  */
145  virtual OsiSolverBranch * solverBranch() const;
146  /// Redoes data when sequence numbers change
147  virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns);
148 
149  /// Construct an OsiSOS object
150  OsiSOS * osiObject(const OsiSolverInterface * solver) const;
151  /// Number of members
152  inline int numberMembers() const
153  {return numberMembers_;}
154
155  /// Members (indices in range 0 ... numberColumns-1)
156  inline const int * members() const
157  {return members_;}
158
159  /// SOS type
160  inline int sosType() const
161  {return sosType_;}
162
163  /** Array of weights */
164  inline const double * weights() const
165  { return weights_;}
166
167  /// Set number of members
168  inline void setNumberMembers(int n)
169  {numberMembers_ = n;}
170
171  /// Members (indices in range 0 ... numberColumns-1)
172  inline int * mutableMembers() const
173  {return members_;}
174
175  /** Array of weights */
176  inline double * mutableWeights() const
177  { return weights_;}
178
179  /** \brief Return true if object can take part in normal heuristics
180  */
181  virtual bool canDoHeuristics() const 
182  {return (sosType_==1&&integerValued_);}
183  /// Set whether set is integer valued or not
184  inline void setIntegerValued(bool yesNo)
185  { integerValued_=yesNo;}
186private:
187  /// data
188
189  /// Members (indices in range 0 ... numberColumns-1)
190  int * members_;
191  /// Weights
192  double * weights_;
193
194  /// Number of members
195  int numberMembers_;
196  /// SOS type
197   int sosType_;
198  /// Whether integer valued
199  bool integerValued_;
200};
201
202/// Define a single integer class
203
204
205class CbcSimpleInteger : public CbcObject {
206
207public:
208
209  // Default Constructor
210  CbcSimpleInteger ();
211
212  // Useful constructor - passed model and index
213  CbcSimpleInteger (CbcModel * model,  int iColumn, double breakEven=0.5);
214 
215  // Useful constructor - passed model and Osi object
216  CbcSimpleInteger (CbcModel * model,  const OsiSimpleInteger * object);
217 
218  // Copy constructor
219  CbcSimpleInteger ( const CbcSimpleInteger &);
220   
221  /// Clone
222  virtual CbcObject * clone() const;
223
224  // Assignment operator
225  CbcSimpleInteger & operator=( const CbcSimpleInteger& rhs);
226
227  // Destructor
228  ~CbcSimpleInteger ();
229  /// Construct an OsiSimpleInteger object
230  OsiSimpleInteger * osiObject() const;
231  using CbcObject::infeasibility ;
232  /// Infeasibility - large is 0.5
233  virtual double infeasibility(const OsiSolverInterface * solver, 
234                               const OsiBranchingInformation * info, int & preferredWay) const;
235
236  using CbcObject::feasibleRegion ;
237  /** Set bounds to fix the variable at the current (integer) value.
238
239    Given an integer value, set the lower and upper bounds to fix the
240    variable. Returns amount it had to move variable.
241  */
242  virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
243
244  using CbcObject::createBranch ;
245  /** Create a branching object and indicate which way to branch first.
246     
247      The branching object has to know how to create branches (fix
248      variables, etc.)
249  */
250  virtual CbcBranchingObject * createBranch(OsiSolverInterface * solver,
251                                            const OsiBranchingInformation * info, int way) ;
252  /// Fills in a created branching object
253  void fillCreateBranch(CbcIntegerBranchingObject * branching, const OsiBranchingInformation * info, int way) ;
254
255  using CbcObject::solverBranch ;
256  /** Create an OsiSolverBranch object
257
258      This returns NULL if branch not represented by bound changes
259  */
260  virtual OsiSolverBranch * solverBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
261  /// Infeasibility - large is 0.5
262  virtual double infeasibility(int & preferredWay) const;
263
264  /** Set bounds to fix the variable at the current (integer) value.
265
266    Given an integer value, set the lower and upper bounds to fix the
267    variable. The algorithm takes a bit of care in order to compensate for
268    minor numerical inaccuracy.
269  */
270  virtual void feasibleRegion();
271
272  /** Creates a branching object
273
274    The preferred direction is set by \p way, -1 for down, +1 for up.
275  */
276  virtual CbcBranchingObject * createBranch(int way) ;
277  /** Column number if single column object -1 otherwise,
278      so returns >= 0
279      Used by heuristics
280  */
281  virtual int columnNumber() const;
282  /// Set column number
283  inline void setColumnNumber(int value)
284  { columnNumber_ = value;}
285
286  /** Reset variable bounds to their original values.
287 
288    Bounds may be tightened, so it may be good to be able to set this info in object.
289   */
290  virtual void resetBounds(const OsiSolverInterface * solver) ;
291  /**  Change column numbers after preprocessing
292   */
293  virtual void resetSequenceEtc(int numberColumns, const int * originalColumns) ;
294  /// Original bounds
295  inline double originalLowerBound() const
296  { return originalLower_;}
297  inline void setOriginalLowerBound(double value)
298  { originalLower_=value;}
299  inline double originalUpperBound() const
300  { return originalUpper_;}
301  inline void setOriginalUpperBound(double value)
302  { originalUpper_=value;}
303  /// Breakeven e.g 0.7 -> >= 0.7 go up first
304  inline double breakEven() const
305  { return breakEven_;}
306  /// Set breakeven e.g 0.7 -> >= 0.7 go up first
307  inline void setBreakEven(double value)
308  { breakEven_=value;}
309
310
311protected:
312  /// data
313
314  /// Original lower bound
315  double originalLower_;
316  /// Original upper bound
317  double originalUpper_;
318  /// Breakeven i.e. >= this preferred is up
319  double breakEven_;
320  /// Column number in model
321  int columnNumber_;
322  /// If -1 down always chosen first, +1 up always, 0 normal
323  int preferredWay_;
324};
325/** Define an n-way class for variables.
326    Only valid value is one at UB others at LB
327    Normally 0-1
328*/
329
330
331class CbcNWay : public CbcObject {
332
333public:
334
335  // Default Constructor
336  CbcNWay ();
337
338  /** Useful constructor (which are matrix indices)
339  */
340  CbcNWay (CbcModel * model, int numberMembers,
341             const int * which, int identifier);
342 
343  // Copy constructor
344  CbcNWay ( const CbcNWay &);
345   
346  /// Clone
347  virtual CbcObject * clone() const;
348
349  /// Assignment operator
350  CbcNWay & operator=( const CbcNWay& rhs);
351
352  /// Destructor
353  ~CbcNWay ();
354
355  /// Set up a consequence for a single member
356  void setConsequence(int iColumn, const CbcConsequence & consequence);
357 
358  /// Applies a consequence for a single member
359  void applyConsequence(int iSequence, int state) const;
360 
361  using CbcObject::infeasibility ;
362  /// Infeasibility - large is 0.5 (and 0.5 will give this)
363  virtual double infeasibility(int & preferredWay) const;
364
365  using CbcObject::feasibleRegion ;
366  /// This looks at solution and sets bounds to contain solution
367  virtual void feasibleRegion();
368
369  using CbcObject::createBranch ;
370  /// Creates a branching object
371  virtual CbcBranchingObject * createBranch(int way) ;
372
373  /// Number of members
374  inline int numberMembers() const
375  {return numberMembers_;}
376
377  /// Members (indices in range 0 ... numberColumns-1)
378  inline const int * members() const
379  {return members_;}
380  /// Redoes data when sequence numbers change
381  virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns);
382
383protected:
384  /// data
385  /// Number of members
386  int numberMembers_;
387
388  /// Members (indices in range 0 ... numberColumns-1)
389  int * members_;
390  /// Consequences (normally NULL)
391  CbcConsequence ** consequence_;
392};
393
394/** Simple branching object for an integer variable
395
396  This object can specify a two-way branch on an integer variable. For each
397  arm of the branch, the upper and lower bounds on the variable can be
398  independently specified.
399 
400  Variable_ holds the index of the integer variable in the integerVariable_
401  array of the model.
402*/
403
404class CbcIntegerBranchingObject : public CbcBranchingObject {
405
406public:
407
408  /// Default constructor
409  CbcIntegerBranchingObject ();
410
411  /** Create a standard floor/ceiling branch object
412
413    Specifies a simple two-way branch. Let \p value = x*. One arm of the
414    branch will be lb <= x <= floor(x*), the other ceil(x*) <= x <= ub.
415    Specify way = -1 to set the object state to perform the down arm first,
416    way = 1 for the up arm.
417  */
418  CbcIntegerBranchingObject (CbcModel *model, int variable,
419                             int way , double value) ;
420 
421  /** Create a degenerate branch object
422
423    Specifies a `one-way branch'. Calling branch() for this object will
424    always result in lowerValue <= x <= upperValue. Used to fix a variable
425    when lowerValue = upperValue.
426  */
427
428  CbcIntegerBranchingObject (CbcModel *model, int variable, int way,
429                             double lowerValue, double upperValue) ;
430 
431  /// Copy constructor
432  CbcIntegerBranchingObject ( const CbcIntegerBranchingObject &);
433   
434  /// Assignment operator
435  CbcIntegerBranchingObject & operator= (const CbcIntegerBranchingObject& rhs);
436
437  /// Clone
438  virtual CbcBranchingObject * clone() const;
439
440  /// Destructor
441  virtual ~CbcIntegerBranchingObject ();
442
443  /// Does part of constructor
444  void fillPart ( int variable, int way , double value) ;
445  using CbcBranchingObject::branch ;
446  /** \brief Sets the bounds for the variable according to the current arm
447             of the branch and advances the object state to the next arm.
448             Returns change in guessed objective on next branch
449  */
450  virtual double branch();
451
452#if 0
453  // No need to override. Default works fine.
454  /** Reset every information so that the branching object appears to point to
455      the previous child. This method does not need to modify anything in any
456      solver. */
457  virtual void previousBranch();
458#endif
459
460  using CbcBranchingObject::print ;
461  /** \brief Print something about branch - only if log level high
462  */
463  virtual void print();
464
465  /// Lower and upper bounds for down branch
466  inline const double * downBounds() const
467  { return down_;}
468  /// Lower and upper bounds for up branch
469  inline const double * upBounds() const
470  { return up_;}
471  /// Set lower and upper bounds for down branch
472  inline void setDownBounds(const double bounds[2])
473  { memcpy(down_,bounds,2*sizeof(double));}
474  /// Set lower and upper bounds for up branch
475  inline void setUpBounds(const double bounds[2])
476  { memcpy(up_,bounds,2*sizeof(double));}
477#ifdef FUNNY_BRANCHING
478  /** Which variable (top bit if upper bound changing,
479      next bit if on down branch */
480  inline const int * variables() const
481  { return variables_;}
482  // New bound
483  inline const double * newBounds() const
484  { return newBounds_;}
485  /// Number of bound changes
486  inline int numberExtraChangedBounds() const
487  { return numberExtraChangedBounds_;}
488  /// Just apply extra bounds to one variable - COIN_DBL_MAX ignore
489  int applyExtraBounds(int iColumn, double lower, double upper, int way) ;
490  /// Deactivate bounds for branching
491  void deactivate();
492  /// Are active bounds for branching
493  inline bool active() const
494  { return (down_[1]!=-COIN_DBL_MAX);}
495#endif
496
497  /** Return the type (an integer identifier) of \c this */
498  virtual int type() const { return 100; }
499
500  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
501      same type and must have the same original object, but they may have
502      different feasible regions.
503      Return the appropriate CbcRangeCompare value (first argument being the
504      sub/superset if that's the case). In case of overlap (and if \c
505      replaceIfOverlap is true) replace the current branching object with one
506      whose feasible region is the overlap.
507   */
508  virtual CbcRangeCompare compareBranchingObject
509  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
510
511protected:
512  /// Lower [0] and upper [1] bounds for the down arm (way_ = -1)
513  double down_[2];
514  /// Lower [0] and upper [1] bounds for the up arm (way_ = 1)
515  double up_[2];
516#ifdef FUNNY_BRANCHING
517  /** Which variable (top bit if upper bound changing)
518      next bit if chnaging on down branch only */
519  int * variables_;
520  // New bound
521  double * newBounds_;
522  /// Number of Extra bound changes
523  int numberExtraChangedBounds_;
524#endif
525};
526
527
528/// Define a single integer class but with pseudo costs
529
530
531class CbcSimpleIntegerPseudoCost : public CbcSimpleInteger {
532
533public:
534
535  // Default Constructor
536  CbcSimpleIntegerPseudoCost ();
537
538  // Useful constructor - passed model index
539  CbcSimpleIntegerPseudoCost (CbcModel * model, int iColumn, double breakEven=0.5);
540 
541  // Useful constructor - passed and model index and pseudo costs
542  CbcSimpleIntegerPseudoCost (CbcModel * model, int iColumn, 
543                              double downPseudoCost, double upPseudoCost);
544  // Useful constructor - passed and model index and pseudo costs
545  CbcSimpleIntegerPseudoCost (CbcModel * model, int dummy,int iColumn, 
546                              double downPseudoCost, double upPseudoCost);
547 
548  // Copy constructor
549  CbcSimpleIntegerPseudoCost ( const CbcSimpleIntegerPseudoCost &);
550   
551  /// Clone
552  virtual CbcObject * clone() const;
553
554  // Assignment operator
555  CbcSimpleIntegerPseudoCost & operator=( const CbcSimpleIntegerPseudoCost& rhs);
556
557  // Destructor
558  ~CbcSimpleIntegerPseudoCost ();
559 
560  using CbcObject::infeasibility ;
561  /// Infeasibility - large is 0.5
562  virtual double infeasibility(int & preferredWay) const;
563
564  using CbcObject::createBranch ;
565  /// Creates a branching object
566  virtual CbcBranchingObject * createBranch(int way) ;
567
568  /// Down pseudo cost
569  inline double downPseudoCost() const
570  { return downPseudoCost_;}
571  /// Set down pseudo cost
572  inline void setDownPseudoCost(double value)
573  { downPseudoCost_=value;}
574
575  /// Up pseudo cost
576  inline double upPseudoCost() const
577  { return upPseudoCost_;}
578  /// Set up pseudo cost
579  inline void setUpPseudoCost(double value)
580  { upPseudoCost_=value;}
581
582  /// Up down separator
583  inline double upDownSeparator() const
584  { return upDownSeparator_;}
585  /// Set up down separator
586  inline void setUpDownSeparator(double value)
587  { upDownSeparator_=value;}
588
589  /// Return "up" estimate
590  virtual double upEstimate() const;
591  /// Return "down" estimate (default 1.0e-5)
592  virtual double downEstimate() const;
593 
594  /// method - see below for details
595  inline int method() const
596  { return method_;}
597  /// Set method
598  inline void setMethod(int value)
599  { method_=value;}
600
601protected:
602  /// data
603
604  /// Down pseudo cost
605  double downPseudoCost_;
606  /// Up pseudo cost
607  double upPseudoCost_;
608  /** Up/down separator
609      If >0.0 then do first branch up if value-floor(value)
610      >= this value
611  */
612  double upDownSeparator_;
613  /** Method -
614      0 - normal - return min (up,down)
615      1 - if before any solution return max(up,down)
616      2 - if before branched solution return max(up,down)
617      3 - always return max(up,down)
618  */
619  int method_;
620};
621
622
623/** Simple branching object for an integer variable with pseudo costs
624
625  This object can specify a two-way branch on an integer variable. For each
626  arm of the branch, the upper and lower bounds on the variable can be
627  independently specified.
628 
629  Variable_ holds the index of the integer variable in the integerVariable_
630  array of the model.
631*/
632
633class CbcIntegerPseudoCostBranchingObject : public CbcIntegerBranchingObject {
634
635public:
636
637  /// Default constructor
638  CbcIntegerPseudoCostBranchingObject ();
639
640  /** Create a standard floor/ceiling branch object
641
642    Specifies a simple two-way branch. Let \p value = x*. One arm of the
643    branch will be is lb <= x <= floor(x*), the other ceil(x*) <= x <= ub.
644    Specify way = -1 to set the object state to perform the down arm first,
645    way = 1 for the up arm.
646  */
647  CbcIntegerPseudoCostBranchingObject (CbcModel *model, int variable,
648                             int way , double value) ;
649 
650  /** Create a degenerate branch object
651
652    Specifies a `one-way branch'. Calling branch() for this object will
653    always result in lowerValue <= x <= upperValue. Used to fix a variable
654    when lowerValue = upperValue.
655  */
656
657  CbcIntegerPseudoCostBranchingObject (CbcModel *model, int variable, int way,
658                             double lowerValue, double upperValue) ;
659 
660  /// Copy constructor
661  CbcIntegerPseudoCostBranchingObject ( const CbcIntegerPseudoCostBranchingObject &);
662   
663  /// Assignment operator
664  CbcIntegerPseudoCostBranchingObject & operator= (const CbcIntegerPseudoCostBranchingObject& rhs);
665
666  /// Clone
667  virtual CbcBranchingObject * clone() const;
668
669  /// Destructor
670  virtual ~CbcIntegerPseudoCostBranchingObject ();
671 
672  using CbcBranchingObject::branch ;
673  /** \brief Sets the bounds for the variable according to the current arm
674             of the branch and advances the object state to the next arm.
675             This version also changes guessed objective value
676  */
677  virtual double branch();
678
679  /// Change in guessed
680  inline double changeInGuessed() const
681  { return changeInGuessed_;}
682  /// Set change in guessed
683  inline void setChangeInGuessed(double value)
684  { changeInGuessed_=value;}
685
686  /** Return the type (an integer identifier) of \c this */
687  virtual int type() const { return 101; }
688
689  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
690      same type and must have the same original object, but they may have
691      different feasible regions.
692      Return the appropriate CbcRangeCompare value (first argument being the
693      sub/superset if that's the case). In case of overlap (and if \c
694      replaceIfOverlap is true) replace the current branching object with one
695      whose feasible region is the overlap.
696   */
697  virtual CbcRangeCompare compareBranchingObject
698  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
699
700protected:
701  /// Change in guessed objective value for next branch
702  double changeInGuessed_;
703};
704
705
706/** Branching object for unordered cliques
707
708    Intended for cliques which are long enough to make it worthwhile
709    but <= 64 members.  There will also be ones for long cliques.
710
711    Variable_ is the clique id number (redundant, as the object also holds a
712    pointer to the clique.
713 */
714class CbcCliqueBranchingObject : public CbcBranchingObject {
715
716public:
717
718  // Default Constructor
719  CbcCliqueBranchingObject ();
720
721  // Useful constructor
722  CbcCliqueBranchingObject (CbcModel * model,  const CbcClique * clique,
723                            int way,
724                            int numberOnDownSide, const int * down,
725                            int numberOnUpSide, const int * up);
726 
727  // Copy constructor
728  CbcCliqueBranchingObject ( const CbcCliqueBranchingObject &);
729   
730  // Assignment operator
731  CbcCliqueBranchingObject & operator=( const CbcCliqueBranchingObject& rhs);
732
733  /// Clone
734  virtual CbcBranchingObject * clone() const;
735
736  // Destructor
737  virtual ~CbcCliqueBranchingObject ();
738 
739  using CbcBranchingObject::branch ;
740  /// Does next branch and updates state
741  virtual double branch();
742
743#if 0
744  // No need to override. Default works fine.
745  /** Reset every information so that the branching object appears to point to
746      the previous child. This method does not need to modify anything in any
747      solver. */
748  virtual void previousBranch();
749#endif
750
751  using CbcBranchingObject::print ;
752  /** \brief Print something about branch - only if log level high
753  */
754  virtual void print();
755
756  /** Return the type (an integer identifier) of \c this */
757  virtual int type() const { return 102; }
758
759  /** Compare the original object of \c this with the original object of \c
760      brObj. Assumes that there is an ordering of the original objects.
761      This method should be invoked only if \c this and brObj are of the same
762      type.
763      Return negative/0/positive depending on whether \c this is
764      smaller/same/larger than the argument.
765  */
766  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
767
768  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
769      same type and must have the same original object, but they may have
770      different feasible regions.
771      Return the appropriate CbcRangeCompare value (first argument being the
772      sub/superset if that's the case). In case of overlap (and if \c
773      replaceIfOverlap is true) replace the current branching object with one
774      whose feasible region is the overlap.
775   */
776  virtual CbcRangeCompare compareBranchingObject
777  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
778
779private:
780  /// data
781  const CbcClique * clique_;
782  /// downMask - bit set to fix to weak bounds, not set to leave unfixed
783  unsigned int downMask_[2];
784  /// upMask - bit set to fix to weak bounds, not set to leave unfixed
785  unsigned int upMask_[2];
786};
787
788
789/** Unordered Clique Branching Object class.
790    These are for cliques which are > 64 members
791    Variable is number of clique.
792 */
793class CbcLongCliqueBranchingObject : public CbcBranchingObject {
794
795public:
796
797  // Default Constructor
798  CbcLongCliqueBranchingObject ();
799
800  // Useful constructor
801  CbcLongCliqueBranchingObject (CbcModel * model,  const CbcClique * clique,
802                                 int way,
803                            int numberOnDownSide, const int * down,
804                            int numberOnUpSide, const int * up);
805 
806  // Copy constructor
807  CbcLongCliqueBranchingObject ( const CbcLongCliqueBranchingObject &);
808   
809  // Assignment operator
810  CbcLongCliqueBranchingObject & operator=( const CbcLongCliqueBranchingObject& rhs);
811
812  /// Clone
813  virtual CbcBranchingObject * clone() const;
814
815  // Destructor
816  virtual ~CbcLongCliqueBranchingObject ();
817 
818  using CbcBranchingObject::branch ;
819  /// Does next branch and updates state
820  virtual double branch();
821
822#if 0
823  // No need to override. Default works fine.
824  /** Reset every information so that the branching object appears to point to
825      the previous child. This method does not need to modify anything in any
826      solver. */
827  virtual void previousBranch();
828#endif
829
830  using CbcBranchingObject::print ;
831  /** \brief Print something about branch - only if log level high
832  */
833  virtual void print();
834
835  /** Return the type (an integer identifier) of \c this */
836  virtual int type() const { return 103; }
837
838  /** Compare the original object of \c this with the original object of \c
839      brObj. Assumes that there is an ordering of the original objects.
840      This method should be invoked only if \c this and brObj are of the same
841      type.
842      Return negative/0/positive depending on whether \c this is
843      smaller/same/larger than the argument.
844  */
845  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
846
847  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
848      same type and must have the same original object, but they may have
849      different feasible regions.
850      Return the appropriate CbcRangeCompare value (first argument being the
851      sub/superset if that's the case). In case of overlap (and if \c
852      replaceIfOverlap is true) replace the current branching object with one
853      whose feasible region is the overlap.
854   */
855  virtual CbcRangeCompare compareBranchingObject
856  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
857
858private:
859  /// data
860  const CbcClique * clique_;
861  /// downMask - bit set to fix to weak bounds, not set to leave unfixed
862  unsigned int * downMask_;
863  /// upMask - bit set to fix to weak bounds, not set to leave unfixed
864  unsigned int * upMask_;
865};
866
867/** Branching object for Special ordered sets
868
869    Variable_ is the set id number (redundant, as the object also holds a
870    pointer to the set.
871 */
872class CbcSOSBranchingObject : public CbcBranchingObject {
873
874public:
875
876  // Default Constructor
877  CbcSOSBranchingObject ();
878
879  // Useful constructor
880  CbcSOSBranchingObject (CbcModel * model,  const CbcSOS * clique,
881                            int way,
882                         double separator);
883 
884  // Copy constructor
885  CbcSOSBranchingObject ( const CbcSOSBranchingObject &);
886   
887  // Assignment operator
888  CbcSOSBranchingObject & operator=( const CbcSOSBranchingObject& rhs);
889
890  /// Clone
891  virtual CbcBranchingObject * clone() const;
892
893  // Destructor
894  virtual ~CbcSOSBranchingObject ();
895 
896  using CbcBranchingObject::branch ;
897  /// Does next branch and updates state
898  virtual double branch();
899
900  /** Reset every information so that the branching object appears to point to
901      the previous child. This method does not need to modify anything in any
902      solver. */
903  virtual void previousBranch() {
904    CbcBranchingObject::previousBranch();
905    computeNonzeroRange();
906  }
907
908  using CbcBranchingObject::print ;
909  /** \brief Print something about branch - only if log level high
910  */
911  virtual void print();
912
913  /** Return the type (an integer identifier) of \c this */
914  virtual int type() const { return 104; }
915
916  /** Compare the original object of \c this with the original object of \c
917      brObj. Assumes that there is an ordering of the original objects.
918      This method should be invoked only if \c this and brObj are of the same
919      type.
920      Return negative/0/positive depending on whether \c this is
921      smaller/same/larger than the argument.
922  */
923  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
924
925  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
926      same type and must have the same original object, but they may have
927      different feasible regions.
928      Return the appropriate CbcRangeCompare value (first argument being the
929      sub/superset if that's the case). In case of overlap (and if \c
930      replaceIfOverlap is true) replace the current branching object with one
931      whose feasible region is the overlap.
932   */
933  virtual CbcRangeCompare compareBranchingObject
934  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
935
936  /** Fill out the \c firstNonzero_ and \c lastNonzero_ data members */
937  void computeNonzeroRange();
938
939private:
940  /// data
941  const CbcSOS * set_;
942  /// separator
943  double separator_;
944  /** The following two members describe the range in the members_ of the
945      original object that whose upper bound is not fixed to 0. This is not
946      necessary for Cbc to function correctly, this is there for heuristics so
947      that separate branching decisions on the same object can be pooled into
948      one branching object. */
949  int firstNonzero_;
950  int lastNonzero_;
951};
952
953/** N way branching Object class.
954    Variable is number of set.
955 */
956class CbcNWayBranchingObject : public CbcBranchingObject {
957
958public:
959
960  // Default Constructor
961  CbcNWayBranchingObject ();
962
963  /** Useful constructor - order had matrix indices
964      way_ -1 corresponds to setting first, +1 to second, +3 etc.
965      this is so -1 and +1 have similarity to normal
966  */
967  CbcNWayBranchingObject (CbcModel * model,  const CbcNWay * nway,
968                          int numberBranches, const int * order);
969 
970  // Copy constructor
971  CbcNWayBranchingObject ( const CbcNWayBranchingObject &);
972   
973  // Assignment operator
974  CbcNWayBranchingObject & operator=( const CbcNWayBranchingObject& rhs);
975
976  /// Clone
977  virtual CbcBranchingObject * clone() const;
978
979  // Destructor
980  virtual ~CbcNWayBranchingObject ();
981 
982  using CbcBranchingObject::branch ;
983  /// Does next branch and updates state
984  virtual double branch();
985
986#if 0
987  // FIXME: what do we need to do here?
988  /** Reset every information so that the branching object appears to point to
989      the previous child. This method does not need to modify anything in any
990      solver. */
991  virtual void previousBranch();
992#endif
993
994  using CbcBranchingObject::print ;
995  /** \brief Print something about branch - only if log level high
996  */
997  virtual void print();
998  /** The number of branch arms created for this branching object
999  */
1000  virtual int numberBranches() const
1001  {return numberInSet_;}
1002  /// Is this a two way object (-1 down, +1 up)
1003  virtual bool twoWay() const
1004  { return false;}
1005
1006  /** Return the type (an integer identifier) of \c this */
1007  virtual int type() const { return 105; }
1008
1009  /** Compare the original object of \c this with the original object of \c
1010      brObj. Assumes that there is an ordering of the original objects.
1011      This method should be invoked only if \c this and brObj are of the same
1012      type.
1013      Return negative/0/positive depending on whether \c this is
1014      smaller/same/larger than the argument.
1015  */
1016  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
1017
1018  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
1019      same type and must have the same original object, but they may have
1020      different feasible regions.
1021      Return the appropriate CbcRangeCompare value (first argument being the
1022      sub/superset if that's the case). In case of overlap (and if \c
1023      replaceIfOverlap is true) replace the current branching object with one
1024      whose feasible region is the overlap.
1025   */
1026  virtual CbcRangeCompare compareBranchingObject
1027  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
1028
1029private:
1030  /// order of branching - points back to CbcNWay
1031  int * order_;
1032  /// Points back to object
1033  const CbcNWay * object_;
1034  /// Number in set
1035  int numberInSet_;
1036};
1037
1038/** Branching decision default class
1039
1040  This class implements a simple default algorithm
1041  (betterBranch()) for choosing a branching variable.
1042*/
1043
1044class CbcBranchDefaultDecision : public CbcBranchDecision {
1045public:
1046  // Default Constructor
1047  CbcBranchDefaultDecision ();
1048
1049  // Copy constructor
1050  CbcBranchDefaultDecision ( const CbcBranchDefaultDecision &);
1051
1052  virtual ~CbcBranchDefaultDecision();
1053
1054  /// Clone
1055  virtual CbcBranchDecision * clone() const;
1056
1057  /// Initialize, <i>e.g.</i> before the start of branch selection at a node
1058  virtual void initialize(CbcModel * model);
1059
1060  /** \brief Compare two branching objects. Return nonzero if \p thisOne is
1061             better than \p bestSoFar.
1062
1063    The routine compares branches using the values supplied in \p numInfUp and
1064    \p numInfDn until a solution is found by search, after which it uses the
1065    values supplied in \p changeUp and \p changeDn. The best branching object
1066    seen so far and the associated parameter values are remembered in the
1067    \c CbcBranchDefaultDecision object. The nonzero return value is +1 if the
1068    up branch is preferred, -1 if the down branch is preferred.
1069
1070    As the names imply, the assumption is that the values supplied for
1071    \p numInfUp and \p numInfDn will be the number of infeasibilities reported
1072    by the branching object, and \p changeUp and \p changeDn will be the
1073    estimated change in objective. Other measures can be used if desired.
1074
1075    Because an \c CbcBranchDefaultDecision object remembers the current best
1076    branching candidate (#bestObject_) as well as the values used in the
1077    comparison, the parameter \p bestSoFar is redundant, hence unused.
1078 */
1079  virtual int betterBranch(CbcBranchingObject * thisOne,
1080                            CbcBranchingObject * bestSoFar,
1081                            double changeUp, int numInfUp,
1082                            double changeDn, int numInfDn);
1083  /** Sets or gets best criterion so far */
1084  virtual void setBestCriterion(double value);
1085  virtual double getBestCriterion() const;
1086
1087  /** \brief Compare N branching objects. Return index of best
1088      and sets way of branching in chosen object.
1089   
1090    This routine is used only after strong branching.
1091  */
1092
1093  virtual int
1094  bestBranch (CbcBranchingObject ** objects, int numberObjects, int numberUnsatisfied,
1095              double * changeUp, int * numberInfeasibilitiesUp,
1096              double * changeDown, int * numberInfeasibilitiesDown,
1097              double objectiveValue) ;
1098private:
1099 
1100  /// Illegal Assignment operator
1101  CbcBranchDefaultDecision & operator=(const CbcBranchDefaultDecision& rhs);
1102
1103  /// data
1104
1105  /// "best" so far
1106  double bestCriterion_;
1107
1108  /// Change up for best
1109  double bestChangeUp_;
1110
1111  /// Number of infeasibilities for up
1112  int bestNumberUp_;
1113
1114  /// Change down for best
1115  double bestChangeDown_;
1116
1117  /// Pointer to best branching object
1118  CbcBranchingObject * bestObject_;
1119
1120  /// Number of infeasibilities for down
1121  int bestNumberDown_;
1122
1123};
1124
1125/** Define a follow on class.
1126    The idea of this is that in air-crew scheduling problems crew may fly in on flight A
1127    and out on flight B or on some other flight.  A useful branch is one which on one side
1128    fixes all which go out on flight B to 0, while the other branch fixes all those that do NOT
1129    go out on flight B to 0.
1130
1131    This branching rule should be in addition to normal rules and have a high priority.
1132*/
1133
1134
1135
1136class CbcFollowOn : public CbcObject {
1137
1138public:
1139
1140  // Default Constructor
1141  CbcFollowOn ();
1142
1143  /** Useful constructor
1144  */
1145  CbcFollowOn (CbcModel * model);
1146 
1147  // Copy constructor
1148  CbcFollowOn ( const CbcFollowOn &);
1149   
1150  /// Clone
1151  virtual CbcObject * clone() const;
1152
1153  // Assignment operator
1154  CbcFollowOn & operator=( const CbcFollowOn& rhs);
1155
1156  // Destructor
1157  ~CbcFollowOn ();
1158 
1159  using CbcObject::infeasibility ;
1160  /// Infeasibility - large is 0.5
1161  virtual double infeasibility(int & preferredWay) const;
1162
1163  using CbcObject::feasibleRegion ;
1164  /// This looks at solution and sets bounds to contain solution
1165  virtual void feasibleRegion();
1166
1167  using CbcObject::createBranch ;
1168  /// Creates a branching object
1169  virtual CbcBranchingObject * createBranch(int way) ;
1170  /// As some computation is needed in more than one place - returns row
1171  virtual int gutsOfFollowOn(int & otherRow, int & preferredWay) const;
1172
1173protected:
1174  /// data
1175  /// Matrix
1176  CoinPackedMatrix matrix_;
1177  /// Matrix by row
1178  CoinPackedMatrix matrixByRow_; 
1179  /// Possible rhs (if 0 then not possible)
1180  int * rhs_;
1181};
1182/** General Branching Object class.
1183    Each way fixes some variables to lower bound
1184 */
1185class CbcFixingBranchingObject : public CbcBranchingObject {
1186
1187public:
1188
1189  // Default Constructor
1190  CbcFixingBranchingObject ();
1191
1192  // Useful constructor
1193  CbcFixingBranchingObject (CbcModel * model, 
1194                            int way,
1195                            int numberOnDownSide, const int * down,
1196                            int numberOnUpSide, const int * up);
1197 
1198  // Copy constructor
1199  CbcFixingBranchingObject ( const CbcFixingBranchingObject &);
1200   
1201  // Assignment operator
1202  CbcFixingBranchingObject & operator=( const CbcFixingBranchingObject& rhs);
1203
1204  /// Clone
1205  virtual CbcBranchingObject * clone() const;
1206
1207  // Destructor
1208  virtual ~CbcFixingBranchingObject ();
1209 
1210  using CbcBranchingObject::branch ;
1211  /// Does next branch and updates state
1212  virtual double branch();
1213
1214#if 0
1215  // No need to override. Default works fine.
1216  /** Reset every information so that the branching object appears to point to
1217      the previous child. This method does not need to modify anything in any
1218      solver. */
1219  virtual void previousBranch();
1220#endif
1221
1222  using CbcBranchingObject::print ;
1223  /** \brief Print something about branch - only if log level high
1224  */
1225  virtual void print();
1226
1227  /** Return the type (an integer identifier) of \c this */
1228  virtual int type() const { return 106; }
1229
1230  /** Compare the original object of \c this with the original object of \c
1231      brObj. Assumes that there is an ordering of the original objects.
1232      This method should be invoked only if \c this and brObj are of the same
1233      type.
1234      Return negative/0/positive depending on whether \c this is
1235      smaller/same/larger than the argument.
1236  */
1237  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
1238
1239  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
1240      same type and must have the same original object, but they may have
1241      different feasible regions.
1242      Return the appropriate CbcRangeCompare value (first argument being the
1243      sub/superset if that's the case). In case of overlap (and if \c
1244      replaceIfOverlap is true) replace the current branching object with one
1245      whose feasible region is the overlap.
1246   */
1247  virtual CbcRangeCompare compareBranchingObject
1248  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
1249
1250private:
1251  /// data
1252  /// Number on down list
1253  int numberDown_;
1254  /// Number on up list
1255  int numberUp_;
1256  /// downList - variables to fix to lb on down branch
1257  int * downList_;
1258  /// upList - variables to fix to lb on up branch
1259  int * upList_;
1260};
1261/** Class for consequent bounds.
1262    When a variable is branched on it normally interacts with other variables by
1263    means of equations.  There are cases where we want to step outside LP and do something
1264    more directly e.g. fix bounds.  This class is for that.
1265
1266    A state of -9999 means at LB, +9999 means at UB,
1267    others mean if fixed to that value.
1268
1269 */
1270
1271class CbcFixVariable : public CbcConsequence {
1272
1273public:
1274
1275  // Default Constructor
1276  CbcFixVariable ();
1277
1278  // One useful Constructor
1279  CbcFixVariable (int numberStates,const int * states, const int * numberNewLower, const int ** newLowerValue,
1280                  const int ** lowerColumn,
1281                  const int * numberNewUpper, const int ** newUpperValue,
1282                  const int ** upperColumn);
1283
1284  // Copy constructor
1285  CbcFixVariable ( const CbcFixVariable & rhs);
1286   
1287  // Assignment operator
1288  CbcFixVariable & operator=( const CbcFixVariable & rhs);
1289
1290  /// Clone
1291  virtual CbcConsequence * clone() const;
1292
1293  /// Destructor
1294  virtual ~CbcFixVariable ();
1295
1296  /** Apply to an LP solver.  Action depends on state
1297   */
1298  virtual void applyToSolver(OsiSolverInterface * solver, int state) const;
1299 
1300protected:
1301  /// Number of states
1302  int numberStates_;
1303  /// Values of integers for various states
1304  int * states_;
1305  /// Start of information for each state (setting new lower)
1306  int * startLower_;
1307  /// Start of information for each state (setting new upper)
1308  int * startUpper_;
1309  /// For each variable new bounds
1310  double * newBound_;
1311  /// Variable
1312  int * variable_;
1313};
1314/** Dummy branching object
1315
1316  This object specifies a one-way dummy branch.
1317  This is so one can carry on branching even when it looks feasible
1318*/
1319
1320class CbcDummyBranchingObject : public CbcBranchingObject {
1321
1322public:
1323
1324  /// Default constructor
1325  CbcDummyBranchingObject (CbcModel * model=NULL);
1326
1327  /// Copy constructor
1328  CbcDummyBranchingObject ( const CbcDummyBranchingObject &);
1329   
1330  /// Assignment operator
1331  CbcDummyBranchingObject & operator= (const CbcDummyBranchingObject& rhs);
1332
1333  /// Clone
1334  virtual CbcBranchingObject * clone() const;
1335
1336  /// Destructor
1337  virtual ~CbcDummyBranchingObject ();
1338 
1339  using CbcBranchingObject::branch ;
1340  /** \brief Dummy branch
1341  */
1342  virtual double branch();
1343
1344#if 0
1345  // No need to override. Default works fine.
1346  /** Reset every information so that the branching object appears to point to
1347      the previous child. This method does not need to modify anything in any
1348      solver. */
1349  virtual void previousBranch();
1350#endif
1351
1352  using CbcBranchingObject::print ;
1353  /** \brief Print something about branch - only if log level high
1354  */
1355  virtual void print();
1356
1357  /** Return the type (an integer identifier) of \c this */
1358  virtual int type() const { return 107; }
1359
1360  /** Compare the original object of \c this with the original object of \c
1361      brObj. Assumes that there is an ordering of the original objects.
1362      This method should be invoked only if \c this and brObj are of the same
1363      type.
1364      Return negative/0/positive depending on whether \c this is
1365      smaller/same/larger than the argument.
1366  */
1367  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
1368
1369  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
1370      same type and must have the same original object, but they may have
1371      different feasible regions.
1372      Return the appropriate CbcRangeCompare value (first argument being the
1373      sub/superset if that's the case). In case of overlap (and if \c
1374      replaceIfOverlap is true) replace the current branching object with one
1375      whose feasible region is the overlap.
1376   */
1377  virtual CbcRangeCompare compareBranchingObject
1378  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
1379
1380};
1381
1382
1383#endif
Note: See TracBrowser for help on using the repository browser.