source: branches/devel/Cbc/src/CbcBranchActual.hpp @ 439

Last change on this file since 439 was 439, checked in by forrest, 13 years ago

towards common use with other solvers

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