source: trunk/include/CbcBranchActual.hpp @ 129

Last change on this file since 129 was 129, checked in by forrest, 16 years ago

make createBranch non const

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 22.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
67protected:
68  /// data
69  /// Number of members
70  int numberMembers_;
71
72  /// Number of Non SOS members i.e. fixing to zero is strong
73  int numberNonSOSMembers_;
74
75  /// Members (indices in range 0 ... numberIntegers_-1)
76  int * members_;
77
78  /// Type of each member 0=SOS, 1 =clique
79  char * type_;
80
81  /// Clique type - 0 <=, 1 ==
82   int cliqueType_;
83
84  /// Which one is slack (if any) sequence within this set
85  int slack_;
86};
87
88/** Define Special Ordered Sets of type 1 and 2.  These do not have to be
89    integer - so do not appear in lists of integers.
90   
91    which_ points directly to columns of matrix
92*/
93
94
95class CbcSOS : public CbcObject {
96
97public:
98
99  // Default Constructor
100  CbcSOS ();
101
102  /** Useful constructor - which are indices
103      and  weights are also given.  If null then 0,1,2..
104      type is SOS type
105  */
106  CbcSOS (CbcModel * model, int numberMembers,
107           const int * which, const double * weights, int identifier,
108          int type=1);
109 
110  // Copy constructor
111  CbcSOS ( const CbcSOS &);
112   
113  /// Clone
114  virtual CbcObject * clone() const;
115
116  // Assignment operator
117  CbcSOS & operator=( const CbcSOS& rhs);
118
119  // Destructor
120  ~CbcSOS ();
121 
122  /// Infeasibility - large is 0.5
123  virtual double infeasibility(int & preferredWay) const;
124
125  /// This looks at solution and sets bounds to contain solution
126  virtual void feasibleRegion();
127  /// Creates a branching object
128  virtual CbcBranchingObject * createBranch(int way) ;
129
130  /// Number of members
131  inline int numberMembers() const
132  {return numberMembers_;};
133
134  /// Members (indices in range 0 ... numberColumns-1)
135  inline const int * members() const
136  {return members_;};
137
138  /// SOS type
139  inline int sosType() const
140  {return sosType_;};
141
142  /** Array of weights */
143  inline const double * weights() const
144  { return weights_;};
145
146private:
147  /// data
148
149  /// Members (indices in range 0 ... numberColumns-1)
150  int * members_;
151  /// Weights
152  double * weights_;
153
154  /// Number of members
155  int numberMembers_;
156  /// SOS type
157   int sosType_;
158};
159
160/// Define a single integer class
161
162
163class CbcSimpleInteger : public CbcObject {
164
165public:
166
167  // Default Constructor
168  CbcSimpleInteger ();
169
170  // Useful constructor - passed integer index and model index
171  CbcSimpleInteger (CbcModel * model, int sequence, int iColumn, double breakEven=0.5);
172 
173  // Copy constructor
174  CbcSimpleInteger ( const CbcSimpleInteger &);
175   
176  /// Clone
177  virtual CbcObject * clone() const;
178
179  // Assignment operator
180  CbcSimpleInteger & operator=( const CbcSimpleInteger& rhs);
181
182  // Destructor
183  ~CbcSimpleInteger ();
184 
185  /// Infeasibility - large is 0.5
186  virtual double infeasibility(int & preferredWay) const;
187
188  /** Set bounds to contain the current solution.
189
190    More precisely, for the variable associated with this object, take the
191    value given in the current solution, force it within the current bounds
192    if required, then set the bounds to fix the variable at the integer
193    nearest the solution value.
194  */
195  virtual void feasibleRegion();
196
197  /// Creates a branching object
198  virtual CbcBranchingObject * createBranch(int way) ;
199
200  /** \brief Given a valid solution (with reduced costs, etc.),
201      return a branching object which would give a new feasible
202      point in the good direction.
203
204    The preferred branching object will force the variable to be +/-1 from
205    its current value, depending on the reduced cost and objective sense.  If
206    movement in the direction which improves the objective is impossible due
207    to bounds on the variable, the branching object will move in the other
208    direction.  If no movement is possible, the method returns NULL.
209
210    Only the bounds on this variable are considered when determining if the new
211    point is feasible.
212  */
213  virtual CbcBranchingObject * preferredNewFeasible() const;
214 
215  /** \brief Given a valid solution (with reduced costs, etc.),
216      return a branching object which would give a new feasible
217      point in a bad direction.
218
219    As for preferredNewFeasible(), but the preferred branching object will
220    force movement in a direction that degrades the objective.
221  */
222  virtual CbcBranchingObject * notPreferredNewFeasible() const ;
223 
224  /** Reset original upper and lower bound values from the solver.
225 
226    Handy for updating bounds held in this object after bounds held in the
227    solver have been tightened.
228   */
229  virtual void resetBounds();
230 
231  /// Sequence number
232  inline int sequence() const
233  {return sequence_;};
234
235  /// Model column number
236  inline int modelSequence() const
237  {return columnNumber_;};
238 
239  /** Column number if single column object -1 otherwise,
240      so returns >= 0
241      Used by heuristics
242  */
243  virtual int columnNumber() const;
244
245  /// Original bounds
246  inline double originalLowerBound() const
247  { return originalLower_;};
248  inline void setOriginalLowerBound(double value)
249  { originalLower_=value;};
250  inline double originalUpperBound() const
251  { return originalUpper_;};
252  inline void setOriginalUpperBound(double value)
253  { originalUpper_=value;};
254  /// Breakeven e.g 0.7 -> >= 0.7 go up first
255  inline double breakEven() const
256  { return breakEven_;};
257  /// Set breakeven e.g 0.7 -> >= 0.7 go up first
258  inline void setBreakEven(double value)
259  { breakEven_=value;};
260
261
262protected:
263  /// data
264
265  /// Sequence
266  int sequence_;
267  /// Column number in model
268  int columnNumber_;
269  /// Original lower bound
270  double originalLower_;
271  /// Original upper bound
272  double originalUpper_;
273  /// Breakeven i.e. >= this preferred is up
274  double breakEven_;
275};
276
277
278/** Simple branching object for an integer variable
279
280  This object can specify a two-way branch on an integer variable. For each
281  arm of the branch, the upper and lower bounds on the variable can be
282  independently specified.
283 
284  Variable_ holds the index of the integer variable in the integerVariable_
285  array of the model.
286*/
287
288class CbcIntegerBranchingObject : public CbcBranchingObject {
289
290public:
291
292  /// Default constructor
293  CbcIntegerBranchingObject ();
294
295  /** Create a standard floor/ceiling branch object
296
297    Specifies a simple two-way branch. Let \p value = x*. One arm of the
298    branch will be is lb <= x <= floor(x*), the other ceil(x*) <= x <= ub.
299    Specify way = -1 to set the object state to perform the down arm first,
300    way = 1 for the up arm.
301  */
302  CbcIntegerBranchingObject (CbcModel *model, int variable,
303                             int way , double value) ;
304 
305  /** Create a degenerate branch object
306
307    Specifies a `one-way branch'. Calling branch() for this object will
308    always result in lowerValue <= x <= upperValue. Used to fix a variable
309    when lowerValue = upperValue.
310  */
311
312  CbcIntegerBranchingObject (CbcModel *model, int variable, int way,
313                             double lowerValue, double upperValue) ;
314 
315  /// Copy constructor
316  CbcIntegerBranchingObject ( const CbcIntegerBranchingObject &);
317   
318  /// Assignment operator
319  CbcIntegerBranchingObject & operator= (const CbcIntegerBranchingObject& rhs);
320
321  /// Clone
322  virtual CbcBranchingObject * clone() const;
323
324  /// Destructor
325  virtual ~CbcIntegerBranchingObject ();
326 
327  /** \brief Sets the bounds for the variable according to the current arm
328             of the branch and advances the object state to the next arm.
329             Returns change in guessed objective on next branch
330  */
331  virtual double branch(bool normalBranch=false);
332
333  /** \brief Print something about branch - only if log level high
334  */
335  virtual void print(bool normalBranch);
336
337protected:
338  /// Lower [0] and upper [1] bounds for the down arm (way_ = -1)
339  double down_[2];
340  /// Lower [0] and upper [1] bounds for the up arm (way_ = 1)
341  double up_[2];
342};
343
344
345/// Define a single integer class but with pseudo costs
346
347
348class CbcSimpleIntegerPseudoCost : public CbcSimpleInteger {
349
350public:
351
352  // Default Constructor
353  CbcSimpleIntegerPseudoCost ();
354
355  // Useful constructor - passed integer index and model index
356  CbcSimpleIntegerPseudoCost (CbcModel * model, int sequence, int iColumn, double breakEven=0.5);
357 
358  // Useful constructor - passed integer index and model index and pseudo costs
359  CbcSimpleIntegerPseudoCost (CbcModel * model, int sequence, int iColumn, 
360                              double downPseudoCost, double upPseudoCost);
361 
362  // Copy constructor
363  CbcSimpleIntegerPseudoCost ( const CbcSimpleIntegerPseudoCost &);
364   
365  /// Clone
366  virtual CbcObject * clone() const;
367
368  // Assignment operator
369  CbcSimpleIntegerPseudoCost & operator=( const CbcSimpleIntegerPseudoCost& rhs);
370
371  // Destructor
372  ~CbcSimpleIntegerPseudoCost ();
373 
374  /// Infeasibility - large is 0.5
375  virtual double infeasibility(int & preferredWay) const;
376
377  /// Creates a branching object
378  virtual CbcBranchingObject * createBranch(int way) ;
379
380  /// Down pseudo cost
381  inline double downPseudoCost() const
382  { return downPseudoCost_;};
383  /// Set down pseudo cost
384  inline void setDownPseudoCost(double value)
385  { downPseudoCost_=value;};
386
387  /// Up pseudo cost
388  inline double upPseudoCost() const
389  { return upPseudoCost_;};
390  /// Set up pseudo cost
391  inline void setUpPseudoCost(double value)
392  { upPseudoCost_=value;};
393
394  /// Return "up" estimate
395  virtual double upEstimate() const;
396  /// Return "down" estimate (default 1.0e-5)
397  virtual double downEstimate() const;
398 
399  /// method - see below for details
400  inline int method() const
401  { return method_;};
402  /// Set method
403  inline void setMethod(int value)
404  { method_=value;};
405
406protected:
407  /// data
408
409  /// Down pseudo cost
410  double downPseudoCost_;
411  /// Up pseudo cost
412  double upPseudoCost_;
413  /** Method -
414      0 - normal - return min (up,down)
415      1 - if before any solution return max(up,down)
416      2 - if before branched solution return max(up,down)
417      3 - always return max(up,down)
418  */
419  int method_;
420};
421
422
423/** Simple branching object for an integer variable with pseudo costs
424
425  This object can specify a two-way branch on an integer variable. For each
426  arm of the branch, the upper and lower bounds on the variable can be
427  independently specified.
428 
429  Variable_ holds the index of the integer variable in the integerVariable_
430  array of the model.
431*/
432
433class CbcIntegerPseudoCostBranchingObject : public CbcIntegerBranchingObject {
434
435public:
436
437  /// Default constructor
438  CbcIntegerPseudoCostBranchingObject ();
439
440  /** Create a standard floor/ceiling branch object
441
442    Specifies a simple two-way branch. Let \p value = x*. One arm of the
443    branch will be is lb <= x <= floor(x*), the other ceil(x*) <= x <= ub.
444    Specify way = -1 to set the object state to perform the down arm first,
445    way = 1 for the up arm.
446  */
447  CbcIntegerPseudoCostBranchingObject (CbcModel *model, int variable,
448                             int way , double value) ;
449 
450  /** Create a degenerate branch object
451
452    Specifies a `one-way branch'. Calling branch() for this object will
453    always result in lowerValue <= x <= upperValue. Used to fix a variable
454    when lowerValue = upperValue.
455  */
456
457  CbcIntegerPseudoCostBranchingObject (CbcModel *model, int variable, int way,
458                             double lowerValue, double upperValue) ;
459 
460  /// Copy constructor
461  CbcIntegerPseudoCostBranchingObject ( const CbcIntegerPseudoCostBranchingObject &);
462   
463  /// Assignment operator
464  CbcIntegerPseudoCostBranchingObject & operator= (const CbcIntegerPseudoCostBranchingObject& rhs);
465
466  /// Clone
467  virtual CbcBranchingObject * clone() const;
468
469  /// Destructor
470  virtual ~CbcIntegerPseudoCostBranchingObject ();
471 
472  /** \brief Sets the bounds for the variable according to the current arm
473             of the branch and advances the object state to the next arm.
474             This version also changes guessed objective value
475  */
476  virtual double branch(bool normalBranch=false);
477
478  /// Change in guessed
479  inline double changeInGuessed() const
480  { return changeInGuessed_;};
481  /// Set change in guessed
482  inline void setChangeInGuessed(double value)
483  { changeInGuessed_=value;};
484protected:
485  /// Change in guessed objective value for next branch
486  double changeInGuessed_;
487};
488
489
490/** Branching object for unordered cliques
491
492    Intended for cliques which are long enough to make it worthwhile
493    but <= 64 members.  There will also be ones for long cliques.
494
495    Variable_ is the clique id number (redundant, as the object also holds a
496    pointer to the clique.
497 */
498class CbcCliqueBranchingObject : public CbcBranchingObject {
499
500public:
501
502  // Default Constructor
503  CbcCliqueBranchingObject ();
504
505  // Useful constructor
506  CbcCliqueBranchingObject (CbcModel * model,  const CbcClique * clique,
507                            int way,
508                            int numberOnDownSide, const int * down,
509                            int numberOnUpSide, const int * up);
510 
511  // Copy constructor
512  CbcCliqueBranchingObject ( const CbcCliqueBranchingObject &);
513   
514  // Assignment operator
515  CbcCliqueBranchingObject & operator=( const CbcCliqueBranchingObject& rhs);
516
517  /// Clone
518  virtual CbcBranchingObject * clone() const;
519
520  // Destructor
521  virtual ~CbcCliqueBranchingObject ();
522 
523  /// Does next branch and updates state
524  virtual double branch(bool normalBranch=false);
525
526  /** \brief Print something about branch - only if log level high
527  */
528  virtual void print(bool normalBranch);
529private:
530  /// data
531  const CbcClique * clique_;
532  /// downMask - bit set to fix to weak bounds, not set to leave unfixed
533  unsigned int downMask_[2];
534  /// upMask - bit set to fix to weak bounds, not set to leave unfixed
535  unsigned int upMask_[2];
536};
537
538
539/** Unordered Clique Branching Object class.
540    These are for cliques which are > 64 members
541    Variable is number of clique.
542 */
543class CbcLongCliqueBranchingObject : public CbcBranchingObject {
544
545public:
546
547  // Default Constructor
548  CbcLongCliqueBranchingObject ();
549
550  // Useful constructor
551  CbcLongCliqueBranchingObject (CbcModel * model,  const CbcClique * clique,
552                                 int way,
553                            int numberOnDownSide, const int * down,
554                            int numberOnUpSide, const int * up);
555 
556  // Copy constructor
557  CbcLongCliqueBranchingObject ( const CbcLongCliqueBranchingObject &);
558   
559  // Assignment operator
560  CbcLongCliqueBranchingObject & operator=( const CbcLongCliqueBranchingObject& rhs);
561
562  /// Clone
563  virtual CbcBranchingObject * clone() const;
564
565  // Destructor
566  virtual ~CbcLongCliqueBranchingObject ();
567 
568  /// Does next branch and updates state
569  virtual double branch(bool normalBranch=false);
570
571  /** \brief Print something about branch - only if log level high
572  */
573  virtual void print(bool normalBranch);
574private:
575  /// data
576  const CbcClique * clique_;
577  /// downMask - bit set to fix to weak bounds, not set to leave unfixed
578  unsigned int * downMask_;
579  /// upMask - bit set to fix to weak bounds, not set to leave unfixed
580  unsigned int * upMask_;
581};
582
583/** Branching object for Special ordered sets
584
585    Variable_ is the set id number (redundant, as the object also holds a
586    pointer to the set.
587 */
588class CbcSOSBranchingObject : public CbcBranchingObject {
589
590public:
591
592  // Default Constructor
593  CbcSOSBranchingObject ();
594
595  // Useful constructor
596  CbcSOSBranchingObject (CbcModel * model,  const CbcSOS * clique,
597                            int way,
598                         double separator);
599 
600  // Copy constructor
601  CbcSOSBranchingObject ( const CbcSOSBranchingObject &);
602   
603  // Assignment operator
604  CbcSOSBranchingObject & operator=( const CbcSOSBranchingObject& rhs);
605
606  /// Clone
607  virtual CbcBranchingObject * clone() const;
608
609  // Destructor
610  virtual ~CbcSOSBranchingObject ();
611 
612  /// Does next branch and updates state
613  virtual double branch(bool normalBranch=false);
614
615  /** \brief Print something about branch - only if log level high
616  */
617  virtual void print(bool normalBranch);
618private:
619  /// data
620  const CbcSOS * set_;
621  /// separator
622  double separator_;
623};
624
625/** Branching decision default class
626
627  This class implements a simple default algorithm
628  (betterBranch()) for choosing a branching variable.
629*/
630
631class CbcBranchDefaultDecision : public CbcBranchDecision {
632public:
633  // Default Constructor
634  CbcBranchDefaultDecision ();
635
636  // Copy constructor
637  CbcBranchDefaultDecision ( const CbcBranchDefaultDecision &);
638
639  virtual ~CbcBranchDefaultDecision();
640
641  /// Clone
642  virtual CbcBranchDecision * clone() const;
643
644  /// Initialize, <i>e.g.</i> before the start of branch selection at a node
645  virtual void initialize(CbcModel * model);
646
647  /** \brief Compare two branching objects. Return nonzero if \p thisOne is
648             better than \p bestSoFar.
649
650    The routine compares branches using the values supplied in \p numInfUp and
651    \p numInfDn until a solution is found by search, after which it uses the
652    values supplied in \p changeUp and \p changeDn. The best branching object
653    seen so far and the associated parameter values are remembered in the
654    \c CbcBranchDefaultDecision object. The nonzero return value is +1 if the
655    up branch is preferred, -1 if the down branch is preferred.
656
657    As the names imply, the assumption is that the values supplied for
658    \p numInfUp and \p numInfDn will be the number of infeasibilities reported
659    by the branching object, and \p changeUp and \p changeDn will be the
660    estimated change in objective. Other measures can be used if desired.
661
662    Because an \c CbcBranchDefaultDecision object remembers the current best
663    branching candidate (#bestObject_) as well as the values used in the
664    comparison, the parameter \p bestSoFar is redundant, hence unused.
665 */
666  virtual int betterBranch(CbcBranchingObject * thisOne,
667                            CbcBranchingObject * bestSoFar,
668                            double changeUp, int numInfUp,
669                            double changeDn, int numInfDn);
670
671  /** \brief Compare N branching objects. Return index of best
672      and sets way of branching in chosen object.
673   
674    This routine is used only after strong branching.
675  */
676
677  virtual int
678  bestBranch (CbcBranchingObject ** objects, int numberObjects, int numberUnsatisfied,
679              double * changeUp, int * numberInfeasibilitiesUp,
680              double * changeDown, int * numberInfeasibilitiesDown,
681              double objectiveValue) ;
682private:
683 
684  /// Illegal Assignment operator
685  CbcBranchDefaultDecision & operator=(const CbcBranchDefaultDecision& rhs);
686
687  /// data
688
689  /// "best" so far
690  double bestCriterion_;
691
692  /// Change up for best
693  double bestChangeUp_;
694
695  /// Number of infeasibilities for up
696  int bestNumberUp_;
697
698  /// Change down for best
699  double bestChangeDown_;
700
701  /// Number of infeasibilities for down
702  int bestNumberDown_;
703
704  /// Pointer to best branching object
705  CbcBranchingObject * bestObject_;
706
707};
708
709/** Define a follow on class.
710    The idea of this is that in air-crew scheduling problems crew may fly in on flight A
711    and out on flight B or on some other flight.  A useful branch is one which on one side
712    fixes all which go out on flight B to 0, while the other branch fixes all those that do NOT
713    go out on flight B to 0.
714
715    This branching rule should be in addition to normal rules and have a high priority.
716*/
717
718
719
720class CbcFollowOn : public CbcObject {
721
722public:
723
724  // Default Constructor
725  CbcFollowOn ();
726
727  /** Useful constructor
728  */
729  CbcFollowOn (CbcModel * model);
730 
731  // Copy constructor
732  CbcFollowOn ( const CbcFollowOn &);
733   
734  /// Clone
735  virtual CbcObject * clone() const;
736
737  // Assignment operator
738  CbcFollowOn & operator=( const CbcFollowOn& rhs);
739
740  // Destructor
741  ~CbcFollowOn ();
742 
743  /// Infeasibility - large is 0.5
744  virtual double infeasibility(int & preferredWay) const;
745
746  /// This looks at solution and sets bounds to contain solution
747  virtual void feasibleRegion();
748  /// Creates a branching object
749  virtual CbcBranchingObject * createBranch(int way) ;
750  /// As some computation is needed in more than one place - returns row
751  virtual int gutsOfFollowOn(int & otherRow, int & preferredWay) const;
752
753protected:
754  /// data
755  /// Matrix
756  CoinPackedMatrix matrix_;
757  /// Matrix by row
758  CoinPackedMatrix matrixByRow_; 
759  /// Possible rhs (if 0 then not possible)
760  int * rhs_;
761};
762/** General Branching Object class.
763    Each way fixes some variables to lower bound
764 */
765class CbcFixingBranchingObject : public CbcBranchingObject {
766
767public:
768
769  // Default Constructor
770  CbcFixingBranchingObject ();
771
772  // Useful constructor
773  CbcFixingBranchingObject (CbcModel * model, 
774                            int way,
775                            int numberOnDownSide, const int * down,
776                            int numberOnUpSide, const int * up);
777 
778  // Copy constructor
779  CbcFixingBranchingObject ( const CbcFixingBranchingObject &);
780   
781  // Assignment operator
782  CbcFixingBranchingObject & operator=( const CbcFixingBranchingObject& rhs);
783
784  /// Clone
785  virtual CbcBranchingObject * clone() const;
786
787  // Destructor
788  virtual ~CbcFixingBranchingObject ();
789 
790  /// Does next branch and updates state
791  virtual double branch(bool normalBranch=false);
792
793  /** \brief Print something about branch - only if log level high
794  */
795  virtual void print(bool normalBranch);
796private:
797  /// data
798  /// Number on down list
799  int numberDown_;
800  /// Number on up list
801  int numberUp_;
802  /// downList - variables to fix to lb on down branch
803  int * downList_;
804  /// upList - variables to fix to lb on up branch
805  int * upList_;
806};
807#endif
Note: See TracBrowser for help on using the repository browser.