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

Last change on this file since 310 was 295, checked in by forrest, 14 years ago

for ampl

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