source: trunk/include/CbcBranchActual.hpp @ 59

Last change on this file since 59 was 59, checked in by forrest, 17 years ago

minor stuff for SOS

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 21.6 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) const;
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) const;
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) const;
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  /// Original bounds
240  inline double originalLowerBound() const
241  { return originalLower_;};
242  inline void setOriginalLowerBound(double value)
243  { originalLower_=value;};
244  inline double originalUpperBound() const
245  { return originalUpper_;};
246  inline void setOriginalUpperBound(double value)
247  { originalUpper_=value;};
248  /// Breakeven e.g 0.7 -> >= 0.7 go up first
249  inline double breakEven() const
250  { return breakEven_;};
251  /// Set breakeven e.g 0.7 -> >= 0.7 go up first
252  inline void setBreakEven(double value)
253  { breakEven_=value;};
254
255
256protected:
257  /// data
258
259  /// Sequence
260  int sequence_;
261  /// Column number in model
262  int columnNumber_;
263  /// Original lower bound
264  double originalLower_;
265  /// Original upper bound
266  double originalUpper_;
267  /// Breakeven i.e. >= this preferred is up
268  double breakEven_;
269};
270
271
272/** Simple branching object for an integer variable
273
274  This object can specify a two-way branch on an integer variable. For each
275  arm of the branch, the upper and lower bounds on the variable can be
276  independently specified.
277 
278  Variable_ holds the index of the integer variable in the integerVariable_
279  array of the model.
280*/
281
282class CbcIntegerBranchingObject : public CbcBranchingObject {
283
284public:
285
286  /// Default constructor
287  CbcIntegerBranchingObject ();
288
289  /** Create a standard floor/ceiling branch object
290
291    Specifies a simple two-way branch. Let \p value = x*. One arm of the
292    branch will be is lb <= x <= floor(x*), the other ceil(x*) <= x <= ub.
293    Specify way = -1 to set the object state to perform the down arm first,
294    way = 1 for the up arm.
295  */
296  CbcIntegerBranchingObject (CbcModel *model, int variable,
297                             int way , double value) ;
298 
299  /** Create a degenerate branch object
300
301    Specifies a `one-way branch'. Calling branch() for this object will
302    always result in lowerValue <= x <= upperValue. Used to fix a variable
303    when lowerValue = upperValue.
304  */
305
306  CbcIntegerBranchingObject (CbcModel *model, int variable, int way,
307                             double lowerValue, double upperValue) ;
308 
309  /// Copy constructor
310  CbcIntegerBranchingObject ( const CbcIntegerBranchingObject &);
311   
312  /// Assignment operator
313  CbcIntegerBranchingObject & operator= (const CbcIntegerBranchingObject& rhs);
314
315  /// Clone
316  virtual CbcBranchingObject * clone() const;
317
318  /// Destructor
319  virtual ~CbcIntegerBranchingObject ();
320 
321  /** \brief Sets the bounds for the variable according to the current arm
322             of the branch and advances the object state to the next arm.
323             Returns change in guessed objective on next branch
324  */
325  virtual double branch(bool normalBranch=false);
326
327  /** \brief Print something about branch - only if log level high
328  */
329  virtual void print(bool normalBranch);
330
331protected:
332  /// Lower [0] and upper [1] bounds for the down arm (way_ = -1)
333  double down_[2];
334  /// Lower [0] and upper [1] bounds for the up arm (way_ = 1)
335  double up_[2];
336};
337
338
339/// Define a single integer class but with pseudo costs
340
341
342class CbcSimpleIntegerPseudoCost : public CbcSimpleInteger {
343
344public:
345
346  // Default Constructor
347  CbcSimpleIntegerPseudoCost ();
348
349  // Useful constructor - passed integer index and model index
350  CbcSimpleIntegerPseudoCost (CbcModel * model, int sequence, int iColumn, double breakEven=0.5);
351 
352  // Useful constructor - passed integer index and model index and pseudo costs
353  CbcSimpleIntegerPseudoCost (CbcModel * model, int sequence, int iColumn, 
354                              double downPseudoCost, double upPseudoCost);
355 
356  // Copy constructor
357  CbcSimpleIntegerPseudoCost ( const CbcSimpleIntegerPseudoCost &);
358   
359  /// Clone
360  virtual CbcObject * clone() const;
361
362  // Assignment operator
363  CbcSimpleIntegerPseudoCost & operator=( const CbcSimpleIntegerPseudoCost& rhs);
364
365  // Destructor
366  ~CbcSimpleIntegerPseudoCost ();
367 
368  /// Infeasibility - large is 0.5
369  virtual double infeasibility(int & preferredWay) const;
370
371  /// Creates a branching object
372  virtual CbcBranchingObject * createBranch(int way) const;
373
374  /// Down pseudo cost
375  inline double downPseudoCost() const
376  { return downPseudoCost_;};
377  /// Set down pseudo cost
378  inline void setDownPseudoCost(double value)
379  { downPseudoCost_=value;};
380
381  /// Up pseudo cost
382  inline double upPseudoCost() const
383  { return upPseudoCost_;};
384  /// Set up pseudo cost
385  inline void setUpPseudoCost(double value)
386  { upPseudoCost_=value;};
387
388  /// Return "up" estimate
389  virtual double upEstimate() const;
390  /// Return "down" estimate (default 1.0e-5)
391  virtual double downEstimate() const;
392 
393  /// method - see below for details
394  inline int method() const
395  { return method_;};
396  /// Set method
397  inline void setMethod(int value)
398  { method_=value;};
399
400protected:
401  /// data
402
403  /// Down pseudo cost
404  double downPseudoCost_;
405  /// Up pseudo cost
406  double upPseudoCost_;
407  /** Method -
408      0 - normal - return min (up,down)
409      1 - if before any solution return max(up,down)
410      2 - if before branched solution return max(up,down)
411      3 - always return max(up,down)
412  */
413  int method_;
414};
415
416
417/** Simple branching object for an integer variable with pseudo costs
418
419  This object can specify a two-way branch on an integer variable. For each
420  arm of the branch, the upper and lower bounds on the variable can be
421  independently specified.
422 
423  Variable_ holds the index of the integer variable in the integerVariable_
424  array of the model.
425*/
426
427class CbcIntegerPseudoCostBranchingObject : public CbcIntegerBranchingObject {
428
429public:
430
431  /// Default constructor
432  CbcIntegerPseudoCostBranchingObject ();
433
434  /** Create a standard floor/ceiling branch object
435
436    Specifies a simple two-way branch. Let \p value = x*. One arm of the
437    branch will be is lb <= x <= floor(x*), the other ceil(x*) <= x <= ub.
438    Specify way = -1 to set the object state to perform the down arm first,
439    way = 1 for the up arm.
440  */
441  CbcIntegerPseudoCostBranchingObject (CbcModel *model, int variable,
442                             int way , double value) ;
443 
444  /** Create a degenerate branch object
445
446    Specifies a `one-way branch'. Calling branch() for this object will
447    always result in lowerValue <= x <= upperValue. Used to fix a variable
448    when lowerValue = upperValue.
449  */
450
451  CbcIntegerPseudoCostBranchingObject (CbcModel *model, int variable, int way,
452                             double lowerValue, double upperValue) ;
453 
454  /// Copy constructor
455  CbcIntegerPseudoCostBranchingObject ( const CbcIntegerPseudoCostBranchingObject &);
456   
457  /// Assignment operator
458  CbcIntegerPseudoCostBranchingObject & operator= (const CbcIntegerPseudoCostBranchingObject& rhs);
459
460  /// Clone
461  virtual CbcBranchingObject * clone() const;
462
463  /// Destructor
464  virtual ~CbcIntegerPseudoCostBranchingObject ();
465 
466  /** \brief Sets the bounds for the variable according to the current arm
467             of the branch and advances the object state to the next arm.
468             This version also changes guessed objective value
469  */
470  virtual double branch(bool normalBranch=false);
471
472  /// Change in guessed
473  inline double changeInGuessed() const
474  { return changeInGuessed_;};
475  /// Set change in guessed
476  inline void setChangeInGuessed(double value)
477  { changeInGuessed_=value;};
478protected:
479  /// Change in guessed objective value for next branch
480  double changeInGuessed_;
481};
482
483
484/** Branching object for unordered cliques
485
486    Intended for cliques which are long enough to make it worthwhile
487    but <= 64 members.  There will also be ones for long cliques.
488
489    Variable_ is the clique id number (redundant, as the object also holds a
490    pointer to the clique.
491 */
492class CbcCliqueBranchingObject : public CbcBranchingObject {
493
494public:
495
496  // Default Constructor
497  CbcCliqueBranchingObject ();
498
499  // Useful constructor
500  CbcCliqueBranchingObject (CbcModel * model,  const CbcClique * clique,
501                            int way,
502                            int numberOnDownSide, const int * down,
503                            int numberOnUpSide, const int * up);
504 
505  // Copy constructor
506  CbcCliqueBranchingObject ( const CbcCliqueBranchingObject &);
507   
508  // Assignment operator
509  CbcCliqueBranchingObject & operator=( const CbcCliqueBranchingObject& rhs);
510
511  /// Clone
512  virtual CbcBranchingObject * clone() const;
513
514  // Destructor
515  virtual ~CbcCliqueBranchingObject ();
516 
517  /// Does next branch and updates state
518  virtual double branch(bool normalBranch=false);
519
520  /** \brief Print something about branch - only if log level high
521  */
522  virtual void print(bool normalBranch);
523private:
524  /// data
525  const CbcClique * clique_;
526  /// downMask - bit set to fix to weak bounds, not set to leave unfixed
527  unsigned int downMask_[2];
528  /// upMask - bit set to fix to weak bounds, not set to leave unfixed
529  unsigned int upMask_[2];
530};
531
532
533/** Unordered Clique Branching Object class.
534    These are for cliques which are > 64 members
535    Variable is number of clique.
536 */
537class CbcLongCliqueBranchingObject : public CbcBranchingObject {
538
539public:
540
541  // Default Constructor
542  CbcLongCliqueBranchingObject ();
543
544  // Useful constructor
545  CbcLongCliqueBranchingObject (CbcModel * model,  const CbcClique * clique,
546                                 int way,
547                            int numberOnDownSide, const int * down,
548                            int numberOnUpSide, const int * up);
549 
550  // Copy constructor
551  CbcLongCliqueBranchingObject ( const CbcLongCliqueBranchingObject &);
552   
553  // Assignment operator
554  CbcLongCliqueBranchingObject & operator=( const CbcLongCliqueBranchingObject& rhs);
555
556  /// Clone
557  virtual CbcBranchingObject * clone() const;
558
559  // Destructor
560  virtual ~CbcLongCliqueBranchingObject ();
561 
562  /// Does next branch and updates state
563  virtual double branch(bool normalBranch=false);
564
565  /** \brief Print something about branch - only if log level high
566  */
567  virtual void print(bool normalBranch);
568private:
569  /// data
570  const CbcClique * clique_;
571  /// downMask - bit set to fix to weak bounds, not set to leave unfixed
572  unsigned int * downMask_;
573  /// upMask - bit set to fix to weak bounds, not set to leave unfixed
574  unsigned int * upMask_;
575};
576
577/** Branching object for Special ordered sets
578
579    Variable_ is the set id number (redundant, as the object also holds a
580    pointer to the set.
581 */
582class CbcSOSBranchingObject : public CbcBranchingObject {
583
584public:
585
586  // Default Constructor
587  CbcSOSBranchingObject ();
588
589  // Useful constructor
590  CbcSOSBranchingObject (CbcModel * model,  const CbcSOS * clique,
591                            int way,
592                         double separator);
593 
594  // Copy constructor
595  CbcSOSBranchingObject ( const CbcSOSBranchingObject &);
596   
597  // Assignment operator
598  CbcSOSBranchingObject & operator=( const CbcSOSBranchingObject& rhs);
599
600  /// Clone
601  virtual CbcBranchingObject * clone() const;
602
603  // Destructor
604  virtual ~CbcSOSBranchingObject ();
605 
606  /// Does next branch and updates state
607  virtual double branch(bool normalBranch=false);
608
609  /** \brief Print something about branch - only if log level high
610  */
611  virtual void print(bool normalBranch);
612private:
613  /// data
614  const CbcSOS * set_;
615  /// separator
616  double separator_;
617};
618
619/** Branching decision default class
620
621  This class implements a simple default algorithm
622  (betterBranch()) for choosing a branching variable.
623*/
624
625class CbcBranchDefaultDecision : public CbcBranchDecision {
626public:
627  // Default Constructor
628  CbcBranchDefaultDecision ();
629
630  // Copy constructor
631  CbcBranchDefaultDecision ( const CbcBranchDefaultDecision &);
632
633  virtual ~CbcBranchDefaultDecision();
634
635  /// Clone
636  virtual CbcBranchDecision * clone() const;
637
638  /// Initialize, <i>e.g.</i> before the start of branch selection at a node
639  virtual void initialize(CbcModel * model);
640
641  /** \brief Compare two branching objects. Return nonzero if \p thisOne is
642             better than \p bestSoFar.
643
644    The routine compares branches using the values supplied in \p numInfUp and
645    \p numInfDn until a solution is found by search, after which it uses the
646    values supplied in \p changeUp and \p changeDn. The best branching object
647    seen so far and the associated parameter values are remembered in the
648    \c CbcBranchDefaultDecision object. The nonzero return value is +1 if the
649    up branch is preferred, -1 if the down branch is preferred.
650
651    As the names imply, the assumption is that the values supplied for
652    \p numInfUp and \p numInfDn will be the number of infeasibilities reported
653    by the branching object, and \p changeUp and \p changeDn will be the
654    estimated change in objective. Other measures can be used if desired.
655
656    Because an \c CbcBranchDefaultDecision object remembers the current best
657    branching candidate (#bestObject_) as well as the values used in the
658    comparison, the parameter \p bestSoFar is redundant, hence unused.
659 */
660  virtual int betterBranch(CbcBranchingObject * thisOne,
661                            CbcBranchingObject * bestSoFar,
662                            double changeUp, int numInfUp,
663                            double changeDn, int numInfDn);
664
665private:
666 
667  /// Illegal Assignment operator
668  CbcBranchDefaultDecision & operator=(const CbcBranchDefaultDecision& rhs);
669
670  /// data
671
672  /// "best" so far
673  double bestCriterion_;
674
675  /// Change up for best
676  double bestChangeUp_;
677
678  /// Number of infeasibilities for up
679  int bestNumberUp_;
680
681  /// Change down for best
682  double bestChangeDown_;
683
684  /// Number of infeasibilities for down
685  int bestNumberDown_;
686
687  /// Pointer to best branching object
688  CbcBranchingObject * bestObject_;
689
690};
691
692/** Define a follow on class.
693    The idea of this is that in air-crew scheduling problems crew may fly in on flight A
694    and out on flight B or on some other flight.  A useful branch is one which on one side
695    fixes all which go out on flight B to 0, while the other branch fixes all those that do NOT
696    go out on flight B to 0.
697
698    This branching rule should be in addition to normal rules and have a high priority.
699*/
700
701
702
703class CbcFollowOn : public CbcObject {
704
705public:
706
707  // Default Constructor
708  CbcFollowOn ();
709
710  /** Useful constructor
711  */
712  CbcFollowOn (CbcModel * model);
713 
714  // Copy constructor
715  CbcFollowOn ( const CbcFollowOn &);
716   
717  /// Clone
718  virtual CbcObject * clone() const;
719
720  // Assignment operator
721  CbcFollowOn & operator=( const CbcFollowOn& rhs);
722
723  // Destructor
724  ~CbcFollowOn ();
725 
726  /// Infeasibility - large is 0.5
727  virtual double infeasibility(int & preferredWay) const;
728
729  /// This looks at solution and sets bounds to contain solution
730  virtual void feasibleRegion();
731  /// Creates a branching object
732  virtual CbcBranchingObject * createBranch(int way) const;
733  /// As some computation is needed in more than one place - returns row
734  virtual int gutsOfFollowOn(int & otherRow, int & preferredWay) const;
735
736protected:
737  /// data
738  /// Matrix
739  CoinPackedMatrix matrix_;
740  /// Matrix by row
741  CoinPackedMatrix matrixByRow_; 
742  /// Possible rhs (if 0 then not possible)
743  int * rhs_;
744};
745/** General Branching Object class.
746    Each way fixes some variables to lower bound
747 */
748class CbcFixingBranchingObject : public CbcBranchingObject {
749
750public:
751
752  // Default Constructor
753  CbcFixingBranchingObject ();
754
755  // Useful constructor
756  CbcFixingBranchingObject (CbcModel * model, 
757                            int way,
758                            int numberOnDownSide, const int * down,
759                            int numberOnUpSide, const int * up);
760 
761  // Copy constructor
762  CbcFixingBranchingObject ( const CbcFixingBranchingObject &);
763   
764  // Assignment operator
765  CbcFixingBranchingObject & operator=( const CbcFixingBranchingObject& rhs);
766
767  /// Clone
768  virtual CbcBranchingObject * clone() const;
769
770  // Destructor
771  virtual ~CbcFixingBranchingObject ();
772 
773  /// Does next branch and updates state
774  virtual double branch(bool normalBranch=false);
775
776  /** \brief Print something about branch - only if log level high
777  */
778  virtual void print(bool normalBranch);
779private:
780  /// data
781  /// Number on down list
782  int numberDown_;
783  /// Number on up list
784  int numberUp_;
785  /// downList - variables to fix to lb on down branch
786  int * downList_;
787  /// upList - variables to fix to lb on up branch
788  int * upList_;
789};
790#endif
Note: See TracBrowser for help on using the repository browser.