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

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

try slightly different branching

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