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

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

many changes

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