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

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

trunk from branches/devel

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