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

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

for osi methods

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