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

Last change on this file since 765 was 765, checked in by andreasw, 12 years ago

merging changes from Bug Squashing Party Aug 2007 to regular trunk

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