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

Last change on this file since 720 was 720, checked in by forrest, 12 years ago

message handling and sos to CbcSolver?

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 29.1 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"
8
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  /// Infeasibility - large is 0.5
40  virtual double infeasibility(int & preferredWay) const;
41
42  /// This looks at solution and sets bounds to contain solution
43  virtual void feasibleRegion();
44  /// Creates a branching object
45  virtual CbcBranchingObject * createBranch(int way) ;
46  /// Number of members
47  inline int numberMembers() const
48  {return numberMembers_;}
49
50  /// Number of Non SOS members i.e. fixing to zero is strong
51  inline int numberNonSOSMembers() const
52  {return numberNonSOSMembers_;}
53
54  /// Members (indices in range 0 ... numberIntegers_-1)
55  inline const int * members() const
56  {return members_;}
57
58  /** Type of each member i.e. which way is strong 0=non SOS, 1 =SOS,
59      index is 0 ... numberMembers_-1 */
60  inline char type(int index) const
61  {if (type_) return type_[index]; else return 1;}
62
63  /// Clique type - 0 <=, 1 ==
64  inline int cliqueType() const
65  {return cliqueType_;}
66  /// Redoes data when sequence numbers change
67  virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns);
68
69protected:
70  /// data
71  /// Number of members
72  int numberMembers_;
73
74  /// Number of Non SOS members i.e. fixing to zero is strong
75  int numberNonSOSMembers_;
76
77  /// Members (indices in range 0 ... numberIntegers_-1)
78  int * members_;
79
80  /// Type of each member 0=SOS, 1 =clique
81  char * type_;
82
83  /// Clique type - 0 <=, 1 ==
84   int cliqueType_;
85
86  /// Which one is slack (if any) sequence within this set
87  int slack_;
88};
89
90/** Define Special Ordered Sets of type 1 and 2.  These do not have to be
91    integer - so do not appear in lists of integers.
92   
93    which_ points directly to columns of matrix
94*/
95
96
97class CbcSOS : public CbcObject {
98
99public:
100
101  // Default Constructor
102  CbcSOS ();
103
104  /** Useful constructor - which are indices
105      and  weights are also given.  If null then 0,1,2..
106      type is SOS type
107  */
108  CbcSOS (CbcModel * model, int numberMembers,
109           const int * which, const double * weights, int identifier,
110          int type=1);
111 
112  // Copy constructor
113  CbcSOS ( const CbcSOS &);
114   
115  /// Clone
116  virtual CbcObject * clone() const;
117
118  // Assignment operator
119  CbcSOS & operator=( const CbcSOS& rhs);
120
121  // Destructor
122  ~CbcSOS ();
123 
124  /// Infeasibility - large is 0.5
125  virtual double infeasibility(int & preferredWay) const;
126
127  /// This looks at solution and sets bounds to contain solution
128  virtual void feasibleRegion();
129  /// Creates a branching object
130  virtual CbcBranchingObject * createBranch(int way) ;
131
132  /** Create an OsiSolverBranch object
133
134      This returns NULL if branch not represented by bound changes
135  */
136  virtual OsiSolverBranch * solverBranch() const;
137  /// Redoes data when sequence numbers change
138  virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns);
139 
140  /// Construct an OsiSOS object
141  OsiSOS * osiObject(const OsiSolverInterface * solver) const;
142  /// Number of members
143  inline int numberMembers() const
144  {return numberMembers_;}
145
146  /// Members (indices in range 0 ... numberColumns-1)
147  inline const int * members() const
148  {return members_;}
149
150  /// SOS type
151  inline int sosType() const
152  {return sosType_;}
153
154  /** Array of weights */
155  inline const double * weights() const
156  { return weights_;}
157
158  /// Set number of members
159  inline void setNumberMembers(int n)
160  {numberMembers_ = n;}
161
162  /// Members (indices in range 0 ... numberColumns-1)
163  inline int * mutableMembers() const
164  {return members_;}
165
166  /** Array of weights */
167  inline double * mutableWeights() const
168  { return weights_;}
169
170  /** \brief Return true if object can take part in normal heuristics
171  */
172  virtual bool canDoHeuristics() const 
173  {return (sosType_==1&&integerValued_);}
174  /// Set whether set is integer valued or not
175  inline void setIntegerValued(bool yesNo)
176  { integerValued_=yesNo;}
177private:
178  /// data
179
180  /// Members (indices in range 0 ... numberColumns-1)
181  int * members_;
182  /// Weights
183  double * weights_;
184
185  /// Number of members
186  int numberMembers_;
187  /// SOS type
188   int sosType_;
189  /// Whether integer valued
190  bool integerValued_;
191};
192
193/// Define a single integer class
194
195
196class CbcSimpleInteger : public CbcObject {
197
198public:
199
200  // Default Constructor
201  CbcSimpleInteger ();
202
203  // Useful constructor - passed model and index
204  CbcSimpleInteger (CbcModel * model,  int iColumn, double breakEven=0.5);
205 
206  // Useful constructor - passed model and Osi object
207  CbcSimpleInteger (CbcModel * model,  const OsiSimpleInteger * object);
208 
209  // Copy constructor
210  CbcSimpleInteger ( const CbcSimpleInteger &);
211   
212  /// Clone
213  virtual CbcObject * clone() const;
214
215  // Assignment operator
216  CbcSimpleInteger & operator=( const CbcSimpleInteger& rhs);
217
218  // Destructor
219  ~CbcSimpleInteger ();
220  /// Construct an OsiSimpleInteger object
221  OsiSimpleInteger * osiObject() const;
222  /// Infeasibility - large is 0.5
223  virtual double infeasibility(const OsiSolverInterface * solver, 
224                               const OsiBranchingInformation * info, int & preferredWay) const;
225
226  /** Set bounds to fix the variable at the current (integer) value.
227
228    Given an integer value, set the lower and upper bounds to fix the
229    variable. Returns amount it had to move variable.
230  */
231  virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
232
233  /** Create a branching object and indicate which way to branch first.
234     
235      The branching object has to know how to create branches (fix
236      variables, etc.)
237  */
238  virtual CbcBranchingObject * createBranch(OsiSolverInterface * solver,
239                                            const OsiBranchingInformation * info, int way) ;
240  /** Create an OsiSolverBranch object
241
242      This returns NULL if branch not represented by bound changes
243  */
244  virtual OsiSolverBranch * solverBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
245  /// Infeasibility - large is 0.5
246  virtual double infeasibility(int & preferredWay) const;
247
248  /** Set bounds to fix the variable at the current (integer) value.
249
250    Given an integer value, set the lower and upper bounds to fix the
251    variable. The algorithm takes a bit of care in order to compensate for
252    minor numerical inaccuracy.
253  */
254  virtual void feasibleRegion();
255
256  /** Creates a branching object
257
258    The preferred direction is set by \p way, -1 for down, +1 for up.
259  */
260  virtual CbcBranchingObject * createBranch(int way) ;
261  /** Column number if single column object -1 otherwise,
262      so returns >= 0
263      Used by heuristics
264  */
265  virtual int columnNumber() const;
266  /// Set column number
267  inline void setColumnNumber(int value)
268  { columnNumber_ = value;}
269
270  /** Reset variable bounds to their original values.
271 
272    Bounds may be tightened, so it may be good to be able to set this info in object.
273   */
274  virtual void resetBounds(const OsiSolverInterface * solver) ;
275  /**  Change column numbers after preprocessing
276   */
277  virtual void resetSequenceEtc(int numberColumns, const int * originalColumns) ;
278  /// Original bounds
279  inline double originalLowerBound() const
280  { return originalLower_;}
281  inline void setOriginalLowerBound(double value)
282  { originalLower_=value;}
283  inline double originalUpperBound() const
284  { return originalUpper_;}
285  inline void setOriginalUpperBound(double value)
286  { originalUpper_=value;}
287  /// Breakeven e.g 0.7 -> >= 0.7 go up first
288  inline double breakEven() const
289  { return breakEven_;}
290  /// Set breakeven e.g 0.7 -> >= 0.7 go up first
291  inline void setBreakEven(double value)
292  { breakEven_=value;}
293
294
295protected:
296  /// data
297
298  /// Original lower bound
299  double originalLower_;
300  /// Original upper bound
301  double originalUpper_;
302  /// Breakeven i.e. >= this preferred is up
303  double breakEven_;
304  /// Column number in model
305  int columnNumber_;
306  /// If -1 down always chosen first, +1 up always, 0 normal
307  int preferredWay_;
308};
309/** Define an n-way class for variables.
310    Only valid value is one at UB others at LB
311    Normally 0-1
312*/
313
314
315class CbcNWay : public CbcObject {
316
317public:
318
319  // Default Constructor
320  CbcNWay ();
321
322  /** Useful constructor (which are matrix indices)
323  */
324  CbcNWay (CbcModel * model, int numberMembers,
325             const int * which, int identifier);
326 
327  // Copy constructor
328  CbcNWay ( const CbcNWay &);
329   
330  /// Clone
331  virtual CbcObject * clone() const;
332
333  /// Assignment operator
334  CbcNWay & operator=( const CbcNWay& rhs);
335
336  /// Destructor
337  ~CbcNWay ();
338
339  /// Set up a consequence for a single member
340  void setConsequence(int iColumn, const CbcConsequence & consequence);
341 
342  /// Applies a consequence for a single member
343  void applyConsequence(int iSequence, int state) const;
344 
345  /// Infeasibility - large is 0.5 (and 0.5 will give this)
346  virtual double infeasibility(int & preferredWay) const;
347
348  /// This looks at solution and sets bounds to contain solution
349  virtual void feasibleRegion();
350  /// Creates a branching object
351  virtual CbcBranchingObject * createBranch(int way) ;
352  /// Number of members
353  inline int numberMembers() const
354  {return numberMembers_;}
355
356  /// Members (indices in range 0 ... numberColumns-1)
357  inline const int * members() const
358  {return members_;}
359  /// Redoes data when sequence numbers change
360  virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns);
361
362protected:
363  /// data
364  /// Number of members
365  int numberMembers_;
366
367  /// Members (indices in range 0 ... numberColumns-1)
368  int * members_;
369  /// Consequences (normally NULL)
370  CbcConsequence ** consequence_;
371};
372
373/** Simple branching object for an integer variable
374
375  This object can specify a two-way branch on an integer variable. For each
376  arm of the branch, the upper and lower bounds on the variable can be
377  independently specified.
378 
379  Variable_ holds the index of the integer variable in the integerVariable_
380  array of the model.
381*/
382
383class CbcIntegerBranchingObject : public CbcBranchingObject {
384
385public:
386
387  /// Default constructor
388  CbcIntegerBranchingObject ();
389
390  /** Create a standard floor/ceiling branch object
391
392    Specifies a simple two-way branch. Let \p value = x*. One arm of the
393    branch will be lb <= x <= floor(x*), the other ceil(x*) <= x <= ub.
394    Specify way = -1 to set the object state to perform the down arm first,
395    way = 1 for the up arm.
396  */
397  CbcIntegerBranchingObject (CbcModel *model, int variable,
398                             int way , double value) ;
399 
400  /** Create a degenerate branch object
401
402    Specifies a `one-way branch'. Calling branch() for this object will
403    always result in lowerValue <= x <= upperValue. Used to fix a variable
404    when lowerValue = upperValue.
405  */
406
407  CbcIntegerBranchingObject (CbcModel *model, int variable, int way,
408                             double lowerValue, double upperValue) ;
409 
410  /// Copy constructor
411  CbcIntegerBranchingObject ( const CbcIntegerBranchingObject &);
412   
413  /// Assignment operator
414  CbcIntegerBranchingObject & operator= (const CbcIntegerBranchingObject& rhs);
415
416  /// Clone
417  virtual CbcBranchingObject * clone() const;
418
419  /// Destructor
420  virtual ~CbcIntegerBranchingObject ();
421 
422  /** \brief Sets the bounds for the variable according to the current arm
423             of the branch and advances the object state to the next arm.
424             Returns change in guessed objective on next branch
425  */
426  virtual double branch();
427
428  /** \brief Print something about branch - only if log level high
429  */
430  virtual void print();
431
432protected:
433  /// Lower [0] and upper [1] bounds for the down arm (way_ = -1)
434  double down_[2];
435  /// Lower [0] and upper [1] bounds for the up arm (way_ = 1)
436  double up_[2];
437};
438
439
440/// Define a single integer class but with pseudo costs
441
442
443class CbcSimpleIntegerPseudoCost : public CbcSimpleInteger {
444
445public:
446
447  // Default Constructor
448  CbcSimpleIntegerPseudoCost ();
449
450  // Useful constructor - passed model index
451  CbcSimpleIntegerPseudoCost (CbcModel * model, int iColumn, double breakEven=0.5);
452 
453  // Useful constructor - passed and model index and pseudo costs
454  CbcSimpleIntegerPseudoCost (CbcModel * model, int iColumn, 
455                              double downPseudoCost, double upPseudoCost);
456  // Useful constructor - passed and model index and pseudo costs
457  CbcSimpleIntegerPseudoCost (CbcModel * model, int dummy,int iColumn, 
458                              double downPseudoCost, double upPseudoCost);
459 
460  // Copy constructor
461  CbcSimpleIntegerPseudoCost ( const CbcSimpleIntegerPseudoCost &);
462   
463  /// Clone
464  virtual CbcObject * clone() const;
465
466  // Assignment operator
467  CbcSimpleIntegerPseudoCost & operator=( const CbcSimpleIntegerPseudoCost& rhs);
468
469  // Destructor
470  ~CbcSimpleIntegerPseudoCost ();
471 
472  /// Infeasibility - large is 0.5
473  virtual double infeasibility(int & preferredWay) const;
474
475  /// Creates a branching object
476  virtual CbcBranchingObject * createBranch(int way) ;
477
478  /// Down pseudo cost
479  inline double downPseudoCost() const
480  { return downPseudoCost_;}
481  /// Set down pseudo cost
482  inline void setDownPseudoCost(double value)
483  { downPseudoCost_=value;}
484
485  /// Up pseudo cost
486  inline double upPseudoCost() const
487  { return upPseudoCost_;}
488  /// Set up pseudo cost
489  inline void setUpPseudoCost(double value)
490  { upPseudoCost_=value;}
491
492  /// Up down separator
493  inline double upDownSeparator() const
494  { return upDownSeparator_;}
495  /// Set up down separator
496  inline void setUpDownSeparator(double value)
497  { upDownSeparator_=value;}
498
499  /// Return "up" estimate
500  virtual double upEstimate() const;
501  /// Return "down" estimate (default 1.0e-5)
502  virtual double downEstimate() const;
503 
504  /// method - see below for details
505  inline int method() const
506  { return method_;}
507  /// Set method
508  inline void setMethod(int value)
509  { method_=value;}
510
511protected:
512  /// data
513
514  /// Down pseudo cost
515  double downPseudoCost_;
516  /// Up pseudo cost
517  double upPseudoCost_;
518  /** Up/down separator
519      If >0.0 then do first branch up if value-floor(value)
520      >= this value
521  */
522  double upDownSeparator_;
523  /** Method -
524      0 - normal - return min (up,down)
525      1 - if before any solution return max(up,down)
526      2 - if before branched solution return max(up,down)
527      3 - always return max(up,down)
528  */
529  int method_;
530};
531
532
533/** Simple branching object for an integer variable with pseudo costs
534
535  This object can specify a two-way branch on an integer variable. For each
536  arm of the branch, the upper and lower bounds on the variable can be
537  independently specified.
538 
539  Variable_ holds the index of the integer variable in the integerVariable_
540  array of the model.
541*/
542
543class CbcIntegerPseudoCostBranchingObject : public CbcIntegerBranchingObject {
544
545public:
546
547  /// Default constructor
548  CbcIntegerPseudoCostBranchingObject ();
549
550  /** Create a standard floor/ceiling branch object
551
552    Specifies a simple two-way branch. Let \p value = x*. One arm of the
553    branch will be is lb <= x <= floor(x*), the other ceil(x*) <= x <= ub.
554    Specify way = -1 to set the object state to perform the down arm first,
555    way = 1 for the up arm.
556  */
557  CbcIntegerPseudoCostBranchingObject (CbcModel *model, int variable,
558                             int way , double value) ;
559 
560  /** Create a degenerate branch object
561
562    Specifies a `one-way branch'. Calling branch() for this object will
563    always result in lowerValue <= x <= upperValue. Used to fix a variable
564    when lowerValue = upperValue.
565  */
566
567  CbcIntegerPseudoCostBranchingObject (CbcModel *model, int variable, int way,
568                             double lowerValue, double upperValue) ;
569 
570  /// Copy constructor
571  CbcIntegerPseudoCostBranchingObject ( const CbcIntegerPseudoCostBranchingObject &);
572   
573  /// Assignment operator
574  CbcIntegerPseudoCostBranchingObject & operator= (const CbcIntegerPseudoCostBranchingObject& rhs);
575
576  /// Clone
577  virtual CbcBranchingObject * clone() const;
578
579  /// Destructor
580  virtual ~CbcIntegerPseudoCostBranchingObject ();
581 
582  /** \brief Sets the bounds for the variable according to the current arm
583             of the branch and advances the object state to the next arm.
584             This version also changes guessed objective value
585  */
586  virtual double branch();
587
588  /// Change in guessed
589  inline double changeInGuessed() const
590  { return changeInGuessed_;}
591  /// Set change in guessed
592  inline void setChangeInGuessed(double value)
593  { changeInGuessed_=value;}
594protected:
595  /// Change in guessed objective value for next branch
596  double changeInGuessed_;
597};
598
599
600/** Branching object for unordered cliques
601
602    Intended for cliques which are long enough to make it worthwhile
603    but <= 64 members.  There will also be ones for long cliques.
604
605    Variable_ is the clique id number (redundant, as the object also holds a
606    pointer to the clique.
607 */
608class CbcCliqueBranchingObject : public CbcBranchingObject {
609
610public:
611
612  // Default Constructor
613  CbcCliqueBranchingObject ();
614
615  // Useful constructor
616  CbcCliqueBranchingObject (CbcModel * model,  const CbcClique * clique,
617                            int way,
618                            int numberOnDownSide, const int * down,
619                            int numberOnUpSide, const int * up);
620 
621  // Copy constructor
622  CbcCliqueBranchingObject ( const CbcCliqueBranchingObject &);
623   
624  // Assignment operator
625  CbcCliqueBranchingObject & operator=( const CbcCliqueBranchingObject& rhs);
626
627  /// Clone
628  virtual CbcBranchingObject * clone() const;
629
630  // Destructor
631  virtual ~CbcCliqueBranchingObject ();
632 
633  /// Does next branch and updates state
634  virtual double branch();
635
636  /** \brief Print something about branch - only if log level high
637  */
638  virtual void print();
639private:
640  /// data
641  const CbcClique * clique_;
642  /// downMask - bit set to fix to weak bounds, not set to leave unfixed
643  unsigned int downMask_[2];
644  /// upMask - bit set to fix to weak bounds, not set to leave unfixed
645  unsigned int upMask_[2];
646};
647
648
649/** Unordered Clique Branching Object class.
650    These are for cliques which are > 64 members
651    Variable is number of clique.
652 */
653class CbcLongCliqueBranchingObject : public CbcBranchingObject {
654
655public:
656
657  // Default Constructor
658  CbcLongCliqueBranchingObject ();
659
660  // Useful constructor
661  CbcLongCliqueBranchingObject (CbcModel * model,  const CbcClique * clique,
662                                 int way,
663                            int numberOnDownSide, const int * down,
664                            int numberOnUpSide, const int * up);
665 
666  // Copy constructor
667  CbcLongCliqueBranchingObject ( const CbcLongCliqueBranchingObject &);
668   
669  // Assignment operator
670  CbcLongCliqueBranchingObject & operator=( const CbcLongCliqueBranchingObject& rhs);
671
672  /// Clone
673  virtual CbcBranchingObject * clone() const;
674
675  // Destructor
676  virtual ~CbcLongCliqueBranchingObject ();
677 
678  /// Does next branch and updates state
679  virtual double branch();
680
681  /** \brief Print something about branch - only if log level high
682  */
683  virtual void print();
684private:
685  /// data
686  const CbcClique * clique_;
687  /// downMask - bit set to fix to weak bounds, not set to leave unfixed
688  unsigned int * downMask_;
689  /// upMask - bit set to fix to weak bounds, not set to leave unfixed
690  unsigned int * upMask_;
691};
692
693/** Branching object for Special ordered sets
694
695    Variable_ is the set id number (redundant, as the object also holds a
696    pointer to the set.
697 */
698class CbcSOSBranchingObject : public CbcBranchingObject {
699
700public:
701
702  // Default Constructor
703  CbcSOSBranchingObject ();
704
705  // Useful constructor
706  CbcSOSBranchingObject (CbcModel * model,  const CbcSOS * clique,
707                            int way,
708                         double separator);
709 
710  // Copy constructor
711  CbcSOSBranchingObject ( const CbcSOSBranchingObject &);
712   
713  // Assignment operator
714  CbcSOSBranchingObject & operator=( const CbcSOSBranchingObject& rhs);
715
716  /// Clone
717  virtual CbcBranchingObject * clone() const;
718
719  // Destructor
720  virtual ~CbcSOSBranchingObject ();
721 
722  /// Does next branch and updates state
723  virtual double branch();
724
725  /** \brief Print something about branch - only if log level high
726  */
727  virtual void print();
728private:
729  /// data
730  const CbcSOS * set_;
731  /// separator
732  double separator_;
733};
734
735/** N way branching Object class.
736    Variable is number of set.
737 */
738class CbcNWayBranchingObject : public CbcBranchingObject {
739
740public:
741
742  // Default Constructor
743  CbcNWayBranchingObject ();
744
745  /** Useful constructor - order had matrix indices
746      way_ -1 corresponds to setting first, +1 to second, +3 etc.
747      this is so -1 and +1 have similarity to normal
748  */
749  CbcNWayBranchingObject (CbcModel * model,  const CbcNWay * nway,
750                          int numberBranches, const int * order);
751 
752  // Copy constructor
753  CbcNWayBranchingObject ( const CbcNWayBranchingObject &);
754   
755  // Assignment operator
756  CbcNWayBranchingObject & operator=( const CbcNWayBranchingObject& rhs);
757
758  /// Clone
759  virtual CbcBranchingObject * clone() const;
760
761  // Destructor
762  virtual ~CbcNWayBranchingObject ();
763 
764  /// Does next branch and updates state
765  virtual double branch();
766
767  /** \brief Print something about branch - only if log level high
768  */
769  virtual void print();
770  /** The number of branch arms created for this branching object
771  */
772  virtual int numberBranches() const
773  {return numberInSet_;}
774  /// Is this a two way object (-1 down, +1 up)
775  virtual bool twoWay() const
776  { return false;}
777private:
778  /// order of branching - points back to CbcNWay
779  int * order_;
780  /// Points back to object
781  const CbcNWay * object_;
782  /// Number in set
783  int numberInSet_;
784};
785
786/** Branching decision default class
787
788  This class implements a simple default algorithm
789  (betterBranch()) for choosing a branching variable.
790*/
791
792class CbcBranchDefaultDecision : public CbcBranchDecision {
793public:
794  // Default Constructor
795  CbcBranchDefaultDecision ();
796
797  // Copy constructor
798  CbcBranchDefaultDecision ( const CbcBranchDefaultDecision &);
799
800  virtual ~CbcBranchDefaultDecision();
801
802  /// Clone
803  virtual CbcBranchDecision * clone() const;
804
805  /// Initialize, <i>e.g.</i> before the start of branch selection at a node
806  virtual void initialize(CbcModel * model);
807
808  /** \brief Compare two branching objects. Return nonzero if \p thisOne is
809             better than \p bestSoFar.
810
811    The routine compares branches using the values supplied in \p numInfUp and
812    \p numInfDn until a solution is found by search, after which it uses the
813    values supplied in \p changeUp and \p changeDn. The best branching object
814    seen so far and the associated parameter values are remembered in the
815    \c CbcBranchDefaultDecision object. The nonzero return value is +1 if the
816    up branch is preferred, -1 if the down branch is preferred.
817
818    As the names imply, the assumption is that the values supplied for
819    \p numInfUp and \p numInfDn will be the number of infeasibilities reported
820    by the branching object, and \p changeUp and \p changeDn will be the
821    estimated change in objective. Other measures can be used if desired.
822
823    Because an \c CbcBranchDefaultDecision object remembers the current best
824    branching candidate (#bestObject_) as well as the values used in the
825    comparison, the parameter \p bestSoFar is redundant, hence unused.
826 */
827  virtual int betterBranch(CbcBranchingObject * thisOne,
828                            CbcBranchingObject * bestSoFar,
829                            double changeUp, int numInfUp,
830                            double changeDn, int numInfDn);
831  /** Sets or gets best criterion so far */
832  virtual void setBestCriterion(double value);
833  virtual double getBestCriterion() const;
834
835  /** \brief Compare N branching objects. Return index of best
836      and sets way of branching in chosen object.
837   
838    This routine is used only after strong branching.
839  */
840
841  virtual int
842  bestBranch (CbcBranchingObject ** objects, int numberObjects, int numberUnsatisfied,
843              double * changeUp, int * numberInfeasibilitiesUp,
844              double * changeDown, int * numberInfeasibilitiesDown,
845              double objectiveValue) ;
846private:
847 
848  /// Illegal Assignment operator
849  CbcBranchDefaultDecision & operator=(const CbcBranchDefaultDecision& rhs);
850
851  /// data
852
853  /// "best" so far
854  double bestCriterion_;
855
856  /// Change up for best
857  double bestChangeUp_;
858
859  /// Number of infeasibilities for up
860  int bestNumberUp_;
861
862  /// Change down for best
863  double bestChangeDown_;
864
865  /// Pointer to best branching object
866  CbcBranchingObject * bestObject_;
867
868  /// Number of infeasibilities for down
869  int bestNumberDown_;
870
871};
872
873/** Define a follow on class.
874    The idea of this is that in air-crew scheduling problems crew may fly in on flight A
875    and out on flight B or on some other flight.  A useful branch is one which on one side
876    fixes all which go out on flight B to 0, while the other branch fixes all those that do NOT
877    go out on flight B to 0.
878
879    This branching rule should be in addition to normal rules and have a high priority.
880*/
881
882
883
884class CbcFollowOn : public CbcObject {
885
886public:
887
888  // Default Constructor
889  CbcFollowOn ();
890
891  /** Useful constructor
892  */
893  CbcFollowOn (CbcModel * model);
894 
895  // Copy constructor
896  CbcFollowOn ( const CbcFollowOn &);
897   
898  /// Clone
899  virtual CbcObject * clone() const;
900
901  // Assignment operator
902  CbcFollowOn & operator=( const CbcFollowOn& rhs);
903
904  // Destructor
905  ~CbcFollowOn ();
906 
907  /// Infeasibility - large is 0.5
908  virtual double infeasibility(int & preferredWay) const;
909
910  /// This looks at solution and sets bounds to contain solution
911  virtual void feasibleRegion();
912  /// Creates a branching object
913  virtual CbcBranchingObject * createBranch(int way) ;
914  /// As some computation is needed in more than one place - returns row
915  virtual int gutsOfFollowOn(int & otherRow, int & preferredWay) const;
916
917protected:
918  /// data
919  /// Matrix
920  CoinPackedMatrix matrix_;
921  /// Matrix by row
922  CoinPackedMatrix matrixByRow_; 
923  /// Possible rhs (if 0 then not possible)
924  int * rhs_;
925};
926/** General Branching Object class.
927    Each way fixes some variables to lower bound
928 */
929class CbcFixingBranchingObject : public CbcBranchingObject {
930
931public:
932
933  // Default Constructor
934  CbcFixingBranchingObject ();
935
936  // Useful constructor
937  CbcFixingBranchingObject (CbcModel * model, 
938                            int way,
939                            int numberOnDownSide, const int * down,
940                            int numberOnUpSide, const int * up);
941 
942  // Copy constructor
943  CbcFixingBranchingObject ( const CbcFixingBranchingObject &);
944   
945  // Assignment operator
946  CbcFixingBranchingObject & operator=( const CbcFixingBranchingObject& rhs);
947
948  /// Clone
949  virtual CbcBranchingObject * clone() const;
950
951  // Destructor
952  virtual ~CbcFixingBranchingObject ();
953 
954  /// Does next branch and updates state
955  virtual double branch();
956
957  /** \brief Print something about branch - only if log level high
958  */
959  virtual void print();
960private:
961  /// data
962  /// Number on down list
963  int numberDown_;
964  /// Number on up list
965  int numberUp_;
966  /// downList - variables to fix to lb on down branch
967  int * downList_;
968  /// upList - variables to fix to lb on up branch
969  int * upList_;
970};
971/** Class for consequent bounds.
972    When a variable is branched on it normally interacts with other variables by
973    means of equations.  There are cases where we want to step outside LP and do something
974    more directly e.g. fix bounds.  This class is for that.
975
976    A state of -9999 means at LB, +9999 means at UB,
977    others mean if fixed to that value.
978
979 */
980
981class CbcFixVariable : public CbcConsequence {
982
983public:
984
985  // Default Constructor
986  CbcFixVariable ();
987
988  // One useful Constructor
989  CbcFixVariable (int numberStates,const int * states, const int * numberNewLower, const int ** newLowerValue,
990                  const int ** lowerColumn,
991                  const int * numberNewUpper, const int ** newUpperValue,
992                  const int ** upperColumn);
993
994  // Copy constructor
995  CbcFixVariable ( const CbcFixVariable & rhs);
996   
997  // Assignment operator
998  CbcFixVariable & operator=( const CbcFixVariable & rhs);
999
1000  /// Clone
1001  virtual CbcConsequence * clone() const;
1002
1003  /// Destructor
1004  virtual ~CbcFixVariable ();
1005
1006  /** Apply to an LP solver.  Action depends on state
1007   */
1008  virtual void applyToSolver(OsiSolverInterface * solver, int state) const;
1009 
1010protected:
1011  /// Number of states
1012  int numberStates_;
1013  /// Values of integers for various states
1014  int * states_;
1015  /// Start of information for each state (setting new lower)
1016  int * startLower_;
1017  /// Start of information for each state (setting new upper)
1018  int * startUpper_;
1019  /// For each variable new bounds
1020  double * newBound_;
1021  /// Variable
1022  int * variable_;
1023};
1024/** Dummy branching object
1025
1026  This object specifies a one-way dummy branch.
1027  This is so one can carry on branching even when it looks feasible
1028*/
1029
1030class CbcDummyBranchingObject : public CbcBranchingObject {
1031
1032public:
1033
1034  /// Default constructor
1035  CbcDummyBranchingObject (CbcModel * model=NULL);
1036
1037  /// Copy constructor
1038  CbcDummyBranchingObject ( const CbcDummyBranchingObject &);
1039   
1040  /// Assignment operator
1041  CbcDummyBranchingObject & operator= (const CbcDummyBranchingObject& rhs);
1042
1043  /// Clone
1044  virtual CbcBranchingObject * clone() const;
1045
1046  /// Destructor
1047  virtual ~CbcDummyBranchingObject ();
1048 
1049  /** \brief Dummy branch
1050  */
1051  virtual double branch();
1052
1053  /** \brief Print something about branch - only if log level high
1054  */
1055  virtual void print();
1056
1057};
1058
1059
1060#endif
Note: See TracBrowser for help on using the repository browser.