source: branches/sandbox/Cbc/src/CbcBranchActual.hpp @ 1286

Last change on this file since 1286 was 1286, checked in by EdwinStraver, 10 years ago

Changed formatting using AStyle -A4 -p

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 56.8 KB
Line 
1/* $Id: CbcBranchActual.hpp 1286 2009-11-09 23:33:07Z EdwinStraver $ */
2// Copyright (C) 2002, International Business Machines
3// Corporation and others.  All Rights Reserved.
4#ifndef CbcBranchActual_H
5#define CbcBranchActual_H
6
7#include "CbcBranchBase.hpp"
8#include "CoinPackedMatrix.hpp"
9class CbcIntegerBranchingObject;
10/// Define a clique class
11
12
13class CbcClique : public CbcObject {
14
15public:
16
17    // Default Constructor
18    CbcClique ();
19
20    /** Useful constructor (which are integer indices)
21        slack can denote a slack in set.
22        If type == NULL then as if 1
23    */
24    CbcClique (CbcModel * model, int cliqueType, int numberMembers,
25               const int * which, const char * type,
26               int identifier, int slack = -1);
27
28    // Copy constructor
29    CbcClique ( const CbcClique &);
30
31    /// Clone
32    virtual CbcObject * clone() const;
33
34    // Assignment operator
35    CbcClique & operator=( const CbcClique& rhs);
36
37    // Destructor
38    virtual ~CbcClique ();
39
40    /// Infeasibility - large is 0.5
41    virtual double infeasibility(const OsiBranchingInformation * info,
42                                 int &preferredWay) const;
43
44    using CbcObject::feasibleRegion ;
45    /// This looks at solution and sets bounds to contain solution
46    virtual void feasibleRegion();
47
48    /// Creates a branching object
49    virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) ;
50    /// Number of members
51    inline int numberMembers() const {
52        return numberMembers_;
53    }
54
55    /// Number of Non SOS members i.e. fixing to zero is strong
56    inline int numberNonSOSMembers() const {
57        return numberNonSOSMembers_;
58    }
59
60    /// Members (indices in range 0 ... numberIntegers_-1)
61    inline const int * members() const {
62        return members_;
63    }
64
65    /** Type of each member i.e. which way is strong 0=non SOS, 1 =SOS,
66        index is 0 ... numberMembers_-1 */
67    inline char type(int index) const {
68        if (type_) return type_[index];
69        else return 1;
70    }
71
72    /// Clique type - 0 <=, 1 ==
73    inline int cliqueType() const {
74        return cliqueType_;
75    }
76    /// Redoes data when sequence numbers change
77    virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns);
78
79protected:
80    /// data
81    /// Number of members
82    int numberMembers_;
83
84    /// Number of Non SOS members i.e. fixing to zero is strong
85    int numberNonSOSMembers_;
86
87    /// Members (indices in range 0 ... numberIntegers_-1)
88    int * members_;
89
90    /// Type of each member 0=SOS, 1 =clique
91    char * type_;
92
93    /// Clique type - 0 <=, 1 ==
94    int cliqueType_;
95
96    /// Which one is slack (if any) sequence within this set
97    int slack_;
98};
99
100/** Define Special Ordered Sets of type 1 and 2.  These do not have to be
101    integer - so do not appear in lists of integers.
102
103    which_ points directly to columns of matrix
104*/
105
106
107class CbcSOS : public CbcObject {
108
109public:
110
111    // Default Constructor
112    CbcSOS ();
113
114    /** Useful constructor - which are indices
115        and  weights are also given.  If null then 0,1,2..
116        type is SOS type
117    */
118    CbcSOS (CbcModel * model, int numberMembers,
119            const int * which, const double * weights, int identifier,
120            int type = 1);
121
122    // Copy constructor
123    CbcSOS ( const CbcSOS &);
124
125    /// Clone
126    virtual CbcObject * clone() const;
127
128    // Assignment operator
129    CbcSOS & operator=( const CbcSOS& rhs);
130
131    // Destructor
132    virtual ~CbcSOS ();
133
134    /// Infeasibility - large is 0.5
135    virtual double infeasibility(const OsiBranchingInformation * info,
136                                 int &preferredWay) const;
137
138    using CbcObject::feasibleRegion ;
139    /// This looks at solution and sets bounds to contain solution
140    virtual void feasibleRegion();
141
142    /// Creates a branching object
143    virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) ;
144
145
146
147    /** Pass in information on branch just done and create CbcObjectUpdateData instance.
148        If object does not need data then backward pointer will be NULL.
149        Assumes can get information from solver */
150    virtual CbcObjectUpdateData createUpdateInformation(const OsiSolverInterface * solver,
151            const CbcNode * node,
152            const CbcBranchingObject * branchingObject);
153    /// Update object by CbcObjectUpdateData
154    virtual void updateInformation(const CbcObjectUpdateData & data) ;
155    using CbcObject::solverBranch ;
156    /** Create an OsiSolverBranch object
157
158        This returns NULL if branch not represented by bound changes
159    */
160    virtual OsiSolverBranch * solverBranch() const;
161    /// Redoes data when sequence numbers change
162    virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns);
163
164    /// Construct an OsiSOS object
165    OsiSOS * osiObject(const OsiSolverInterface * solver) const;
166    /// Number of members
167    inline int numberMembers() const {
168        return numberMembers_;
169    }
170
171    /// Members (indices in range 0 ... numberColumns-1)
172    inline const int * members() const {
173        return members_;
174    }
175
176    /// SOS type
177    inline int sosType() const {
178        return sosType_;
179    }
180    /// Down number times
181    inline int numberTimesDown() const {
182        return numberTimesDown_;
183    }
184    /// Up number times
185    inline int numberTimesUp() const {
186        return numberTimesUp_;
187    }
188
189    /** Array of weights */
190    inline const double * weights() const {
191        return weights_;
192    }
193
194    /// Set number of members
195    inline void setNumberMembers(int n) {
196        numberMembers_ = n;
197    }
198
199    /// Members (indices in range 0 ... numberColumns-1)
200    inline int * mutableMembers() const {
201        return members_;
202    }
203
204    /** Array of weights */
205    inline double * mutableWeights() const {
206        return weights_;
207    }
208
209    /** \brief Return true if object can take part in normal heuristics
210    */
211    virtual bool canDoHeuristics() const {
212        return (sosType_ == 1 && integerValued_);
213    }
214    /// Set whether set is integer valued or not
215    inline void setIntegerValued(bool yesNo) {
216        integerValued_ = yesNo;
217    }
218private:
219    /// data
220
221    /// Members (indices in range 0 ... numberColumns-1)
222    int * members_;
223    /// Weights
224    double * weights_;
225    /// Current pseudo-shadow price estimate down
226    mutable double shadowEstimateDown_;
227    /// Current pseudo-shadow price estimate up
228    mutable double shadowEstimateUp_;
229    /// Down pseudo ratio
230    double downDynamicPseudoRatio_;
231    /// Up pseudo ratio
232    double upDynamicPseudoRatio_;
233    /// Number of times we have gone down
234    int numberTimesDown_;
235    /// Number of times we have gone up
236    int numberTimesUp_;
237    /// Number of members
238    int numberMembers_;
239    /// SOS type
240    int sosType_;
241    /// Whether integer valued
242    bool integerValued_;
243};
244
245/// Define a single integer class
246
247
248class CbcSimpleInteger : public CbcObject {
249
250public:
251
252    // Default Constructor
253    CbcSimpleInteger ();
254
255    // Useful constructor - passed model and index
256    CbcSimpleInteger (CbcModel * model,  int iColumn, double breakEven = 0.5);
257
258    // Useful constructor - passed model and Osi object
259    CbcSimpleInteger (CbcModel * model,  const OsiSimpleInteger * object);
260
261    // Copy constructor
262    CbcSimpleInteger ( const CbcSimpleInteger &);
263
264    /// Clone
265    virtual CbcObject * clone() const;
266
267    // Assignment operator
268    CbcSimpleInteger & operator=( const CbcSimpleInteger& rhs);
269
270    // Destructor
271    virtual ~CbcSimpleInteger ();
272    /// Construct an OsiSimpleInteger object
273    OsiSimpleInteger * osiObject() const;
274    /// Infeasibility - large is 0.5
275    virtual double infeasibility(const OsiBranchingInformation * info,
276                                 int &preferredWay) const;
277
278    using CbcObject::feasibleRegion ;
279    /** Set bounds to fix the variable at the current (integer) value.
280
281      Given an integer value, set the lower and upper bounds to fix the
282      variable. Returns amount it had to move variable.
283    */
284    virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
285
286    /** Create a branching object and indicate which way to branch first.
287
288        The branching object has to know how to create branches (fix
289        variables, etc.)
290    */
291    virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) ;
292    /// Fills in a created branching object
293    void fillCreateBranch(CbcIntegerBranchingObject * branching, const OsiBranchingInformation * info, int way) ;
294
295    using CbcObject::solverBranch ;
296    /** Create an OsiSolverBranch object
297
298        This returns NULL if branch not represented by bound changes
299    */
300    virtual OsiSolverBranch * solverBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
301
302    /** Set bounds to fix the variable at the current (integer) value.
303
304      Given an integer value, set the lower and upper bounds to fix the
305      variable. The algorithm takes a bit of care in order to compensate for
306      minor numerical inaccuracy.
307    */
308    virtual void feasibleRegion();
309
310    /** Column number if single column object -1 otherwise,
311        so returns >= 0
312        Used by heuristics
313    */
314    virtual int columnNumber() const;
315    /// Set column number
316    inline void setColumnNumber(int value) {
317        columnNumber_ = value;
318    }
319
320    /** Reset variable bounds to their original values.
321
322      Bounds may be tightened, so it may be good to be able to set this info in object.
323     */
324    virtual void resetBounds(const OsiSolverInterface * solver) ;
325    /**  Change column numbers after preprocessing
326     */
327    virtual void resetSequenceEtc(int numberColumns, const int * originalColumns) ;
328    /// Original bounds
329    inline double originalLowerBound() const {
330        return originalLower_;
331    }
332    inline void setOriginalLowerBound(double value) {
333        originalLower_ = value;
334    }
335    inline double originalUpperBound() const {
336        return originalUpper_;
337    }
338    inline void setOriginalUpperBound(double value) {
339        originalUpper_ = value;
340    }
341    /// Breakeven e.g 0.7 -> >= 0.7 go up first
342    inline double breakEven() const {
343        return breakEven_;
344    }
345    /// Set breakeven e.g 0.7 -> >= 0.7 go up first
346    inline void setBreakEven(double value) {
347        breakEven_ = value;
348    }
349
350
351protected:
352    /// data
353
354    /// Original lower bound
355    double originalLower_;
356    /// Original upper bound
357    double originalUpper_;
358    /// Breakeven i.e. >= this preferred is up
359    double breakEven_;
360    /// Column number in model
361    int columnNumber_;
362    /// If -1 down always chosen first, +1 up always, 0 normal
363    int preferredWay_;
364};
365/** Define an n-way class for variables.
366    Only valid value is one at UB others at LB
367    Normally 0-1
368*/
369
370
371class CbcNWay : public CbcObject {
372
373public:
374
375    // Default Constructor
376    CbcNWay ();
377
378    /** Useful constructor (which are matrix indices)
379    */
380    CbcNWay (CbcModel * model, int numberMembers,
381             const int * which, int identifier);
382
383    // Copy constructor
384    CbcNWay ( const CbcNWay &);
385
386    /// Clone
387    virtual CbcObject * clone() const;
388
389    /// Assignment operator
390    CbcNWay & operator=( const CbcNWay& rhs);
391
392    /// Destructor
393    virtual ~CbcNWay ();
394
395    /// Set up a consequence for a single member
396    void setConsequence(int iColumn, const CbcConsequence & consequence);
397
398    /// Applies a consequence for a single member
399    void applyConsequence(int iSequence, int state) const;
400
401    /// Infeasibility - large is 0.5 (and 0.5 will give this)
402    virtual double infeasibility(const OsiBranchingInformation * info,
403                                 int &preferredWay) const;
404
405    using CbcObject::feasibleRegion ;
406    /// This looks at solution and sets bounds to contain solution
407    virtual void feasibleRegion();
408
409    /// Creates a branching object
410    virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) ;
411
412    /// Number of members
413    inline int numberMembers() const {
414        return numberMembers_;
415    }
416
417    /// Members (indices in range 0 ... numberColumns-1)
418    inline const int * members() const {
419        return members_;
420    }
421    /// Redoes data when sequence numbers change
422    virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns);
423
424protected:
425    /// data
426    /// Number of members
427    int numberMembers_;
428
429    /// Members (indices in range 0 ... numberColumns-1)
430    int * members_;
431    /// Consequences (normally NULL)
432    CbcConsequence ** consequence_;
433};
434
435/** Simple branching object for an integer variable
436
437  This object can specify a two-way branch on an integer variable. For each
438  arm of the branch, the upper and lower bounds on the variable can be
439  independently specified.
440
441  Variable_ holds the index of the integer variable in the integerVariable_
442  array of the model.
443*/
444
445class CbcIntegerBranchingObject : public CbcBranchingObject {
446
447public:
448
449    /// Default constructor
450    CbcIntegerBranchingObject ();
451
452    /** Create a standard floor/ceiling branch object
453
454      Specifies a simple two-way branch. Let \p value = x*. One arm of the
455      branch will be lb <= x <= floor(x*), the other ceil(x*) <= x <= ub.
456      Specify way = -1 to set the object state to perform the down arm first,
457      way = 1 for the up arm.
458    */
459    CbcIntegerBranchingObject (CbcModel *model, int variable,
460                               int way , double value) ;
461
462    /** Create a degenerate branch object
463
464      Specifies a `one-way branch'. Calling branch() for this object will
465      always result in lowerValue <= x <= upperValue. Used to fix a variable
466      when lowerValue = upperValue.
467    */
468
469    CbcIntegerBranchingObject (CbcModel *model, int variable, int way,
470                               double lowerValue, double upperValue) ;
471
472    /// Copy constructor
473    CbcIntegerBranchingObject ( const CbcIntegerBranchingObject &);
474
475    /// Assignment operator
476    CbcIntegerBranchingObject & operator= (const CbcIntegerBranchingObject& rhs);
477
478    /// Clone
479    virtual CbcBranchingObject * clone() const;
480
481    /// Destructor
482    virtual ~CbcIntegerBranchingObject ();
483
484    /// Does part of constructor
485    void fillPart ( int variable, int way , double value) ;
486    using CbcBranchingObject::branch ;
487    /** \brief Sets the bounds for the variable according to the current arm
488           of the branch and advances the object state to the next arm.
489           Returns change in guessed objective on next branch
490    */
491    virtual double branch();
492    /** Update bounds in solver as in 'branch' and update given bounds.
493        branchState is -1 for 'down' +1 for 'up' */
494    virtual void fix(OsiSolverInterface * solver,
495                     double * lower, double * upper,
496                     int branchState) const ;
497
498#if 0
499    // No need to override. Default works fine.
500    /** Reset every information so that the branching object appears to point to
501        the previous child. This method does not need to modify anything in any
502        solver. */
503    virtual void previousBranch();
504#endif
505
506    using CbcBranchingObject::print ;
507    /** \brief Print something about branch - only if log level high
508    */
509    virtual void print();
510
511    /// Lower and upper bounds for down branch
512    inline const double * downBounds() const {
513        return down_;
514    }
515    /// Lower and upper bounds for up branch
516    inline const double * upBounds() const {
517        return up_;
518    }
519    /// Set lower and upper bounds for down branch
520    inline void setDownBounds(const double bounds[2]) {
521        memcpy(down_, bounds, 2*sizeof(double));
522    }
523    /// Set lower and upper bounds for up branch
524    inline void setUpBounds(const double bounds[2]) {
525        memcpy(up_, bounds, 2*sizeof(double));
526    }
527#ifdef FUNNY_BRANCHING
528    /** Which variable (top bit if upper bound changing,
529        next bit if on down branch */
530    inline const int * variables() const {
531        return variables_;
532    }
533    // New bound
534    inline const double * newBounds() const {
535        return newBounds_;
536    }
537    /// Number of bound changes
538    inline int numberExtraChangedBounds() const {
539        return numberExtraChangedBounds_;
540    }
541    /// Just apply extra bounds to one variable - COIN_DBL_MAX ignore
542    int applyExtraBounds(int iColumn, double lower, double upper, int way) ;
543    /// Deactivate bounds for branching
544    void deactivate();
545    /// Are active bounds for branching
546    inline bool active() const {
547        return (down_[1] != -COIN_DBL_MAX);
548    }
549#endif
550
551    /** Return the type (an integer identifier) of \c this */
552    virtual int type() const {
553        return 100;
554    }
555
556    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
557        same type and must have the same original object, but they may have
558        different feasible regions.
559        Return the appropriate CbcRangeCompare value (first argument being the
560        sub/superset if that's the case). In case of overlap (and if \c
561        replaceIfOverlap is true) replace the current branching object with one
562        whose feasible region is the overlap.
563     */
564    virtual CbcRangeCompare compareBranchingObject
565    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
566
567protected:
568    /// Lower [0] and upper [1] bounds for the down arm (way_ = -1)
569    double down_[2];
570    /// Lower [0] and upper [1] bounds for the up arm (way_ = 1)
571    double up_[2];
572#ifdef FUNNY_BRANCHING
573    /** Which variable (top bit if upper bound changing)
574        next bit if changing on down branch only */
575    int * variables_;
576    // New bound
577    double * newBounds_;
578    /// Number of Extra bound changes
579    int numberExtraChangedBounds_;
580#endif
581};
582
583
584/// Define a single integer class but with pseudo costs
585
586
587class CbcSimpleIntegerPseudoCost : public CbcSimpleInteger {
588
589public:
590
591    // Default Constructor
592    CbcSimpleIntegerPseudoCost ();
593
594    // Useful constructor - passed model index
595    CbcSimpleIntegerPseudoCost (CbcModel * model, int iColumn, double breakEven = 0.5);
596
597    // Useful constructor - passed and model index and pseudo costs
598    CbcSimpleIntegerPseudoCost (CbcModel * model, int iColumn,
599                                double downPseudoCost, double upPseudoCost);
600    // Useful constructor - passed and model index and pseudo costs
601    CbcSimpleIntegerPseudoCost (CbcModel * model, int dummy, int iColumn,
602                                double downPseudoCost, double upPseudoCost);
603
604    // Copy constructor
605    CbcSimpleIntegerPseudoCost ( const CbcSimpleIntegerPseudoCost &);
606
607    /// Clone
608    virtual CbcObject * clone() const;
609
610    // Assignment operator
611    CbcSimpleIntegerPseudoCost & operator=( const CbcSimpleIntegerPseudoCost& rhs);
612
613    // Destructor
614    virtual ~CbcSimpleIntegerPseudoCost ();
615
616    /// Infeasibility - large is 0.5
617    virtual double infeasibility(const OsiBranchingInformation * info,
618                                 int &preferredWay) const;
619
620    /// Creates a branching object
621    virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) ;
622
623    /// Down pseudo cost
624    inline double downPseudoCost() const {
625        return downPseudoCost_;
626    }
627    /// Set down pseudo cost
628    inline void setDownPseudoCost(double value) {
629        downPseudoCost_ = value;
630    }
631
632    /// Up pseudo cost
633    inline double upPseudoCost() const {
634        return upPseudoCost_;
635    }
636    /// Set up pseudo cost
637    inline void setUpPseudoCost(double value) {
638        upPseudoCost_ = value;
639    }
640
641    /// Up down separator
642    inline double upDownSeparator() const {
643        return upDownSeparator_;
644    }
645    /// Set up down separator
646    inline void setUpDownSeparator(double value) {
647        upDownSeparator_ = value;
648    }
649
650    /// Return "up" estimate
651    virtual double upEstimate() const;
652    /// Return "down" estimate (default 1.0e-5)
653    virtual double downEstimate() const;
654
655    /// method - see below for details
656    inline int method() const {
657        return method_;
658    }
659    /// Set method
660    inline void setMethod(int value) {
661        method_ = value;
662    }
663
664protected:
665    /// data
666
667    /// Down pseudo cost
668    double downPseudoCost_;
669    /// Up pseudo cost
670    double upPseudoCost_;
671    /** Up/down separator
672        If >0.0 then do first branch up if value-floor(value)
673        >= this value
674    */
675    double upDownSeparator_;
676    /** Method -
677        0 - normal - return min (up,down)
678        1 - if before any solution return CoinMax(up,down)
679        2 - if before branched solution return CoinMax(up,down)
680        3 - always return CoinMax(up,down)
681    */
682    int method_;
683};
684
685
686/** Simple branching object for an integer variable with pseudo costs
687
688  This object can specify a two-way branch on an integer variable. For each
689  arm of the branch, the upper and lower bounds on the variable can be
690  independently specified.
691
692  Variable_ holds the index of the integer variable in the integerVariable_
693  array of the model.
694*/
695
696class CbcIntegerPseudoCostBranchingObject : public CbcIntegerBranchingObject {
697
698public:
699
700    /// Default constructor
701    CbcIntegerPseudoCostBranchingObject ();
702
703    /** Create a standard floor/ceiling branch object
704
705      Specifies a simple two-way branch. Let \p value = x*. One arm of the
706      branch will be is lb <= x <= floor(x*), the other ceil(x*) <= x <= ub.
707      Specify way = -1 to set the object state to perform the down arm first,
708      way = 1 for the up arm.
709    */
710    CbcIntegerPseudoCostBranchingObject (CbcModel *model, int variable,
711                                         int way , double value) ;
712
713    /** Create a degenerate branch object
714
715      Specifies a `one-way branch'. Calling branch() for this object will
716      always result in lowerValue <= x <= upperValue. Used to fix a variable
717      when lowerValue = upperValue.
718    */
719
720    CbcIntegerPseudoCostBranchingObject (CbcModel *model, int variable, int way,
721                                         double lowerValue, double upperValue) ;
722
723    /// Copy constructor
724    CbcIntegerPseudoCostBranchingObject ( const CbcIntegerPseudoCostBranchingObject &);
725
726    /// Assignment operator
727    CbcIntegerPseudoCostBranchingObject & operator= (const CbcIntegerPseudoCostBranchingObject& rhs);
728
729    /// Clone
730    virtual CbcBranchingObject * clone() const;
731
732    /// Destructor
733    virtual ~CbcIntegerPseudoCostBranchingObject ();
734
735    using CbcBranchingObject::branch ;
736    /** \brief Sets the bounds for the variable according to the current arm
737           of the branch and advances the object state to the next arm.
738           This version also changes guessed objective value
739    */
740    virtual double branch();
741
742    /// Change in guessed
743    inline double changeInGuessed() const {
744        return changeInGuessed_;
745    }
746    /// Set change in guessed
747    inline void setChangeInGuessed(double value) {
748        changeInGuessed_ = value;
749    }
750
751    /** Return the type (an integer identifier) of \c this */
752    virtual int type() const {
753        return 101;
754    }
755
756    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
757        same type and must have the same original object, but they may have
758        different feasible regions.
759        Return the appropriate CbcRangeCompare value (first argument being the
760        sub/superset if that's the case). In case of overlap (and if \c
761        replaceIfOverlap is true) replace the current branching object with one
762        whose feasible region is the overlap.
763     */
764    virtual CbcRangeCompare compareBranchingObject
765    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
766
767protected:
768    /// Change in guessed objective value for next branch
769    double changeInGuessed_;
770};
771
772
773/** Branching object for unordered cliques
774
775    Intended for cliques which are long enough to make it worthwhile
776    but <= 64 members.  There will also be ones for long cliques.
777
778    Variable_ is the clique id number (redundant, as the object also holds a
779    pointer to the clique.
780 */
781class CbcCliqueBranchingObject : public CbcBranchingObject {
782
783public:
784
785    // Default Constructor
786    CbcCliqueBranchingObject ();
787
788    // Useful constructor
789    CbcCliqueBranchingObject (CbcModel * model,  const CbcClique * clique,
790                              int way,
791                              int numberOnDownSide, const int * down,
792                              int numberOnUpSide, const int * up);
793
794    // Copy constructor
795    CbcCliqueBranchingObject ( const CbcCliqueBranchingObject &);
796
797    // Assignment operator
798    CbcCliqueBranchingObject & operator=( const CbcCliqueBranchingObject& rhs);
799
800    /// Clone
801    virtual CbcBranchingObject * clone() const;
802
803    // Destructor
804    virtual ~CbcCliqueBranchingObject ();
805
806    using CbcBranchingObject::branch ;
807    /// Does next branch and updates state
808    virtual double branch();
809
810#if 0
811    // No need to override. Default works fine.
812    /** Reset every information so that the branching object appears to point to
813        the previous child. This method does not need to modify anything in any
814        solver. */
815    virtual void previousBranch();
816#endif
817
818    using CbcBranchingObject::print ;
819    /** \brief Print something about branch - only if log level high
820    */
821    virtual void print();
822
823    /** Return the type (an integer identifier) of \c this */
824    virtual int type() const {
825        return 102;
826    }
827
828    /** Compare the original object of \c this with the original object of \c
829        brObj. Assumes that there is an ordering of the original objects.
830        This method should be invoked only if \c this and brObj are of the same
831        type.
832        Return negative/0/positive depending on whether \c this is
833        smaller/same/larger than the argument.
834    */
835    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
836
837    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
838        same type and must have the same original object, but they may have
839        different feasible regions.
840        Return the appropriate CbcRangeCompare value (first argument being the
841        sub/superset if that's the case). In case of overlap (and if \c
842        replaceIfOverlap is true) replace the current branching object with one
843        whose feasible region is the overlap.
844     */
845    virtual CbcRangeCompare compareBranchingObject
846    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
847
848private:
849    /// data
850    const CbcClique * clique_;
851    /// downMask - bit set to fix to weak bounds, not set to leave unfixed
852    unsigned int downMask_[2];
853    /// upMask - bit set to fix to weak bounds, not set to leave unfixed
854    unsigned int upMask_[2];
855};
856
857
858/** Unordered Clique Branching Object class.
859    These are for cliques which are > 64 members
860    Variable is number of clique.
861 */
862class CbcLongCliqueBranchingObject : public CbcBranchingObject {
863
864public:
865
866    // Default Constructor
867    CbcLongCliqueBranchingObject ();
868
869    // Useful constructor
870    CbcLongCliqueBranchingObject (CbcModel * model,  const CbcClique * clique,
871                                  int way,
872                                  int numberOnDownSide, const int * down,
873                                  int numberOnUpSide, const int * up);
874
875    // Copy constructor
876    CbcLongCliqueBranchingObject ( const CbcLongCliqueBranchingObject &);
877
878    // Assignment operator
879    CbcLongCliqueBranchingObject & operator=( const CbcLongCliqueBranchingObject& rhs);
880
881    /// Clone
882    virtual CbcBranchingObject * clone() const;
883
884    // Destructor
885    virtual ~CbcLongCliqueBranchingObject ();
886
887    using CbcBranchingObject::branch ;
888    /// Does next branch and updates state
889    virtual double branch();
890
891#if 0
892    // No need to override. Default works fine.
893    /** Reset every information so that the branching object appears to point to
894        the previous child. This method does not need to modify anything in any
895        solver. */
896    virtual void previousBranch();
897#endif
898
899    using CbcBranchingObject::print ;
900    /** \brief Print something about branch - only if log level high
901    */
902    virtual void print();
903
904    /** Return the type (an integer identifier) of \c this */
905    virtual int type() const {
906        return 103;
907    }
908
909    /** Compare the original object of \c this with the original object of \c
910        brObj. Assumes that there is an ordering of the original objects.
911        This method should be invoked only if \c this and brObj are of the same
912        type.
913        Return negative/0/positive depending on whether \c this is
914        smaller/same/larger than the argument.
915    */
916    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
917
918    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
919        same type and must have the same original object, but they may have
920        different feasible regions.
921        Return the appropriate CbcRangeCompare value (first argument being the
922        sub/superset if that's the case). In case of overlap (and if \c
923        replaceIfOverlap is true) replace the current branching object with one
924        whose feasible region is the overlap.
925     */
926    virtual CbcRangeCompare compareBranchingObject
927    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
928
929private:
930    /// data
931    const CbcClique * clique_;
932    /// downMask - bit set to fix to weak bounds, not set to leave unfixed
933    unsigned int * downMask_;
934    /// upMask - bit set to fix to weak bounds, not set to leave unfixed
935    unsigned int * upMask_;
936};
937
938/** Branching object for Special ordered sets
939
940    Variable_ is the set id number (redundant, as the object also holds a
941    pointer to the set.
942 */
943class CbcSOSBranchingObject : public CbcBranchingObject {
944
945public:
946
947    // Default Constructor
948    CbcSOSBranchingObject ();
949
950    // Useful constructor
951    CbcSOSBranchingObject (CbcModel * model,  const CbcSOS * clique,
952                           int way,
953                           double separator);
954
955    // Copy constructor
956    CbcSOSBranchingObject ( const CbcSOSBranchingObject &);
957
958    // Assignment operator
959    CbcSOSBranchingObject & operator=( const CbcSOSBranchingObject& rhs);
960
961    /// Clone
962    virtual CbcBranchingObject * clone() const;
963
964    // Destructor
965    virtual ~CbcSOSBranchingObject ();
966
967    using CbcBranchingObject::branch ;
968    /// Does next branch and updates state
969    virtual double branch();
970    /** Update bounds in solver as in 'branch' and update given bounds.
971        branchState is -1 for 'down' +1 for 'up' */
972    virtual void fix(OsiSolverInterface * solver,
973                     double * lower, double * upper,
974                     int branchState) const ;
975
976    /** Reset every information so that the branching object appears to point to
977        the previous child. This method does not need to modify anything in any
978        solver. */
979    virtual void previousBranch() {
980        CbcBranchingObject::previousBranch();
981        computeNonzeroRange();
982    }
983
984    using CbcBranchingObject::print ;
985    /** \brief Print something about branch - only if log level high
986    */
987    virtual void print();
988
989    /** Return the type (an integer identifier) of \c this */
990    virtual int type() const {
991        return 104;
992    }
993
994    /** Compare the original object of \c this with the original object of \c
995        brObj. Assumes that there is an ordering of the original objects.
996        This method should be invoked only if \c this and brObj are of the same
997        type.
998        Return negative/0/positive depending on whether \c this is
999        smaller/same/larger than the argument.
1000    */
1001    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
1002
1003    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
1004        same type and must have the same original object, but they may have
1005        different feasible regions.
1006        Return the appropriate CbcRangeCompare value (first argument being the
1007        sub/superset if that's the case). In case of overlap (and if \c
1008        replaceIfOverlap is true) replace the current branching object with one
1009        whose feasible region is the overlap.
1010     */
1011    virtual CbcRangeCompare compareBranchingObject
1012    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
1013
1014    /** Fill out the \c firstNonzero_ and \c lastNonzero_ data members */
1015    void computeNonzeroRange();
1016
1017private:
1018    /// data
1019    const CbcSOS * set_;
1020    /// separator
1021    double separator_;
1022    /** The following two members describe the range in the members_ of the
1023        original object that whose upper bound is not fixed to 0. This is not
1024        necessary for Cbc to function correctly, this is there for heuristics so
1025        that separate branching decisions on the same object can be pooled into
1026        one branching object. */
1027    int firstNonzero_;
1028    int lastNonzero_;
1029};
1030
1031/** N way branching Object class.
1032    Variable is number of set.
1033 */
1034class CbcNWayBranchingObject : public CbcBranchingObject {
1035
1036public:
1037
1038    // Default Constructor
1039    CbcNWayBranchingObject ();
1040
1041    /** Useful constructor - order had matrix indices
1042        way_ -1 corresponds to setting first, +1 to second, +3 etc.
1043        this is so -1 and +1 have similarity to normal
1044    */
1045    CbcNWayBranchingObject (CbcModel * model,  const CbcNWay * nway,
1046                            int numberBranches, const int * order);
1047
1048    // Copy constructor
1049    CbcNWayBranchingObject ( const CbcNWayBranchingObject &);
1050
1051    // Assignment operator
1052    CbcNWayBranchingObject & operator=( const CbcNWayBranchingObject& rhs);
1053
1054    /// Clone
1055    virtual CbcBranchingObject * clone() const;
1056
1057    // Destructor
1058    virtual ~CbcNWayBranchingObject ();
1059
1060    using CbcBranchingObject::branch ;
1061    /// Does next branch and updates state
1062    virtual double branch();
1063
1064#if 0
1065    // FIXME: what do we need to do here?
1066    /** Reset every information so that the branching object appears to point to
1067        the previous child. This method does not need to modify anything in any
1068        solver. */
1069    virtual void previousBranch();
1070#endif
1071
1072    using CbcBranchingObject::print ;
1073    /** \brief Print something about branch - only if log level high
1074    */
1075    virtual void print();
1076    /** The number of branch arms created for this branching object
1077    */
1078    virtual int numberBranches() const {
1079        return numberInSet_;
1080    }
1081    /// Is this a two way object (-1 down, +1 up)
1082    virtual bool twoWay() const {
1083        return false;
1084    }
1085
1086    /** Return the type (an integer identifier) of \c this */
1087    virtual int type() const {
1088        return 105;
1089    }
1090
1091    /** Compare the original object of \c this with the original object of \c
1092        brObj. Assumes that there is an ordering of the original objects.
1093        This method should be invoked only if \c this and brObj are of the same
1094        type.
1095        Return negative/0/positive depending on whether \c this is
1096        smaller/same/larger than the argument.
1097    */
1098    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
1099
1100    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
1101        same type and must have the same original object, but they may have
1102        different feasible regions.
1103        Return the appropriate CbcRangeCompare value (first argument being the
1104        sub/superset if that's the case). In case of overlap (and if \c
1105        replaceIfOverlap is true) replace the current branching object with one
1106        whose feasible region is the overlap.
1107     */
1108    virtual CbcRangeCompare compareBranchingObject
1109    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
1110
1111private:
1112    /// order of branching - points back to CbcNWay
1113    int * order_;
1114    /// Points back to object
1115    const CbcNWay * object_;
1116    /// Number in set
1117    int numberInSet_;
1118};
1119
1120/** Branching decision default class
1121
1122  This class implements a simple default algorithm
1123  (betterBranch()) for choosing a branching variable.
1124*/
1125
1126class CbcBranchDefaultDecision : public CbcBranchDecision {
1127public:
1128    // Default Constructor
1129    CbcBranchDefaultDecision ();
1130
1131    // Copy constructor
1132    CbcBranchDefaultDecision ( const CbcBranchDefaultDecision &);
1133
1134    virtual ~CbcBranchDefaultDecision();
1135
1136    /// Clone
1137    virtual CbcBranchDecision * clone() const;
1138
1139    /// Initialize, <i>e.g.</i> before the start of branch selection at a node
1140    virtual void initialize(CbcModel * model);
1141
1142    /** \brief Compare two branching objects. Return nonzero if \p thisOne is
1143           better than \p bestSoFar.
1144
1145      The routine compares branches using the values supplied in \p numInfUp and
1146      \p numInfDn until a solution is found by search, after which it uses the
1147      values supplied in \p changeUp and \p changeDn. The best branching object
1148      seen so far and the associated parameter values are remembered in the
1149      \c CbcBranchDefaultDecision object. The nonzero return value is +1 if the
1150      up branch is preferred, -1 if the down branch is preferred.
1151
1152      As the names imply, the assumption is that the values supplied for
1153      \p numInfUp and \p numInfDn will be the number of infeasibilities reported
1154      by the branching object, and \p changeUp and \p changeDn will be the
1155      estimated change in objective. Other measures can be used if desired.
1156
1157      Because an \c CbcBranchDefaultDecision object remembers the current best
1158      branching candidate (#bestObject_) as well as the values used in the
1159      comparison, the parameter \p bestSoFar is redundant, hence unused.
1160    */
1161    virtual int betterBranch(CbcBranchingObject * thisOne,
1162                             CbcBranchingObject * bestSoFar,
1163                             double changeUp, int numInfUp,
1164                             double changeDn, int numInfDn);
1165    /** Sets or gets best criterion so far */
1166    virtual void setBestCriterion(double value);
1167    virtual double getBestCriterion() const;
1168
1169    /** \brief Compare N branching objects. Return index of best
1170        and sets way of branching in chosen object.
1171
1172      This routine is used only after strong branching.
1173    */
1174
1175    virtual int
1176    bestBranch (CbcBranchingObject ** objects, int numberObjects, int numberUnsatisfied,
1177                double * changeUp, int * numberInfeasibilitiesUp,
1178                double * changeDown, int * numberInfeasibilitiesDown,
1179                double objectiveValue) ;
1180private:
1181
1182    /// Illegal Assignment operator
1183    CbcBranchDefaultDecision & operator=(const CbcBranchDefaultDecision& rhs);
1184
1185    /// data
1186
1187    /// "best" so far
1188    double bestCriterion_;
1189
1190    /// Change up for best
1191    double bestChangeUp_;
1192
1193    /// Number of infeasibilities for up
1194    int bestNumberUp_;
1195
1196    /// Change down for best
1197    double bestChangeDown_;
1198
1199    /// Pointer to best branching object
1200    CbcBranchingObject * bestObject_;
1201
1202    /// Number of infeasibilities for down
1203    int bestNumberDown_;
1204
1205};
1206
1207/** Define a follow on class.
1208    The idea of this is that in air-crew scheduling problems crew may fly in on flight A
1209    and out on flight B or on some other flight.  A useful branch is one which on one side
1210    fixes all which go out on flight B to 0, while the other branch fixes all those that do NOT
1211    go out on flight B to 0.
1212
1213    This branching rule should be in addition to normal rules and have a high priority.
1214*/
1215
1216
1217
1218class CbcFollowOn : public CbcObject {
1219
1220public:
1221
1222    // Default Constructor
1223    CbcFollowOn ();
1224
1225    /** Useful constructor
1226    */
1227    CbcFollowOn (CbcModel * model);
1228
1229    // Copy constructor
1230    CbcFollowOn ( const CbcFollowOn &);
1231
1232    /// Clone
1233    virtual CbcObject * clone() const;
1234
1235    // Assignment operator
1236    CbcFollowOn & operator=( const CbcFollowOn& rhs);
1237
1238    // Destructor
1239    ~CbcFollowOn ();
1240
1241    /// Infeasibility - large is 0.5
1242    virtual double infeasibility(const OsiBranchingInformation * info,
1243                                 int &preferredWay) const;
1244
1245    using CbcObject::feasibleRegion ;
1246    /// This looks at solution and sets bounds to contain solution
1247    virtual void feasibleRegion();
1248
1249    /// Creates a branching object
1250    virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) ;
1251    /// As some computation is needed in more than one place - returns row
1252    virtual int gutsOfFollowOn(int & otherRow, int & preferredWay) const;
1253
1254protected:
1255    /// data
1256    /// Matrix
1257    CoinPackedMatrix matrix_;
1258    /// Matrix by row
1259    CoinPackedMatrix matrixByRow_;
1260    /// Possible rhs (if 0 then not possible)
1261    int * rhs_;
1262};
1263/** General Branching Object class.
1264    Each way fixes some variables to lower bound
1265 */
1266class CbcFixingBranchingObject : public CbcBranchingObject {
1267
1268public:
1269
1270    // Default Constructor
1271    CbcFixingBranchingObject ();
1272
1273    // Useful constructor
1274    CbcFixingBranchingObject (CbcModel * model,
1275                              int way,
1276                              int numberOnDownSide, const int * down,
1277                              int numberOnUpSide, const int * up);
1278
1279    // Copy constructor
1280    CbcFixingBranchingObject ( const CbcFixingBranchingObject &);
1281
1282    // Assignment operator
1283    CbcFixingBranchingObject & operator=( const CbcFixingBranchingObject& rhs);
1284
1285    /// Clone
1286    virtual CbcBranchingObject * clone() const;
1287
1288    // Destructor
1289    virtual ~CbcFixingBranchingObject ();
1290
1291    using CbcBranchingObject::branch ;
1292    /// Does next branch and updates state
1293    virtual double branch();
1294
1295#if 0
1296    // No need to override. Default works fine.
1297    /** Reset every information so that the branching object appears to point to
1298        the previous child. This method does not need to modify anything in any
1299        solver. */
1300    virtual void previousBranch();
1301#endif
1302
1303    using CbcBranchingObject::print ;
1304    /** \brief Print something about branch - only if log level high
1305    */
1306    virtual void print();
1307
1308    /** Return the type (an integer identifier) of \c this */
1309    virtual int type() const {
1310        return 106;
1311    }
1312
1313    /** Compare the original object of \c this with the original object of \c
1314        brObj. Assumes that there is an ordering of the original objects.
1315        This method should be invoked only if \c this and brObj are of the same
1316        type.
1317        Return negative/0/positive depending on whether \c this is
1318        smaller/same/larger than the argument.
1319    */
1320    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
1321
1322    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
1323        same type and must have the same original object, but they may have
1324        different feasible regions.
1325        Return the appropriate CbcRangeCompare value (first argument being the
1326        sub/superset if that's the case). In case of overlap (and if \c
1327        replaceIfOverlap is true) replace the current branching object with one
1328        whose feasible region is the overlap.
1329     */
1330    virtual CbcRangeCompare compareBranchingObject
1331    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
1332
1333private:
1334    /// data
1335    /// Number on down list
1336    int numberDown_;
1337    /// Number on up list
1338    int numberUp_;
1339    /// downList - variables to fix to lb on down branch
1340    int * downList_;
1341    /// upList - variables to fix to lb on up branch
1342    int * upList_;
1343};
1344/** Class for consequent bounds.
1345    When a variable is branched on it normally interacts with other variables by
1346    means of equations.  There are cases where we want to step outside LP and do something
1347    more directly e.g. fix bounds.  This class is for that.
1348
1349    A state of -9999 means at LB, +9999 means at UB,
1350    others mean if fixed to that value.
1351
1352 */
1353
1354class CbcFixVariable : public CbcConsequence {
1355
1356public:
1357
1358    // Default Constructor
1359    CbcFixVariable ();
1360
1361    // One useful Constructor
1362    CbcFixVariable (int numberStates, const int * states, const int * numberNewLower, const int ** newLowerValue,
1363                    const int ** lowerColumn,
1364                    const int * numberNewUpper, const int ** newUpperValue,
1365                    const int ** upperColumn);
1366
1367    // Copy constructor
1368    CbcFixVariable ( const CbcFixVariable & rhs);
1369
1370    // Assignment operator
1371    CbcFixVariable & operator=( const CbcFixVariable & rhs);
1372
1373    /// Clone
1374    virtual CbcConsequence * clone() const;
1375
1376    /// Destructor
1377    virtual ~CbcFixVariable ();
1378
1379    /** Apply to an LP solver.  Action depends on state
1380     */
1381    virtual void applyToSolver(OsiSolverInterface * solver, int state) const;
1382
1383protected:
1384    /// Number of states
1385    int numberStates_;
1386    /// Values of integers for various states
1387    int * states_;
1388    /// Start of information for each state (setting new lower)
1389    int * startLower_;
1390    /// Start of information for each state (setting new upper)
1391    int * startUpper_;
1392    /// For each variable new bounds
1393    double * newBound_;
1394    /// Variable
1395    int * variable_;
1396};
1397/** Dummy branching object
1398
1399  This object specifies a one-way dummy branch.
1400  This is so one can carry on branching even when it looks feasible
1401*/
1402
1403class CbcDummyBranchingObject : public CbcBranchingObject {
1404
1405public:
1406
1407    /// Default constructor
1408    CbcDummyBranchingObject (CbcModel * model = NULL);
1409
1410    /// Copy constructor
1411    CbcDummyBranchingObject ( const CbcDummyBranchingObject &);
1412
1413    /// Assignment operator
1414    CbcDummyBranchingObject & operator= (const CbcDummyBranchingObject& rhs);
1415
1416    /// Clone
1417    virtual CbcBranchingObject * clone() const;
1418
1419    /// Destructor
1420    virtual ~CbcDummyBranchingObject ();
1421
1422    using CbcBranchingObject::branch ;
1423    /** \brief Dummy branch
1424    */
1425    virtual double branch();
1426
1427#if 0
1428    // No need to override. Default works fine.
1429    /** Reset every information so that the branching object appears to point to
1430        the previous child. This method does not need to modify anything in any
1431        solver. */
1432    virtual void previousBranch();
1433#endif
1434
1435    using CbcBranchingObject::print ;
1436    /** \brief Print something about branch - only if log level high
1437    */
1438    virtual void print();
1439
1440    /** Return the type (an integer identifier) of \c this */
1441    virtual int type() const {
1442        return 107;
1443    }
1444
1445    /** Compare the original object of \c this with the original object of \c
1446        brObj. Assumes that there is an ordering of the original objects.
1447        This method should be invoked only if \c this and brObj are of the same
1448        type.
1449        Return negative/0/positive depending on whether \c this is
1450        smaller/same/larger than the argument.
1451    */
1452    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
1453
1454    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
1455        same type and must have the same original object, but they may have
1456        different feasible regions.
1457        Return the appropriate CbcRangeCompare value (first argument being the
1458        sub/superset if that's the case). In case of overlap (and if \c
1459        replaceIfOverlap is true) replace the current branching object with one
1460        whose feasible region is the overlap.
1461     */
1462    virtual CbcRangeCompare compareBranchingObject
1463    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
1464
1465};
1466
1467/** Define a catch all class.
1468    This will create a list of subproblems
1469*/
1470
1471
1472class CbcGeneral : public CbcObject {
1473
1474public:
1475
1476    // Default Constructor
1477    CbcGeneral ();
1478
1479    /** Useful constructor
1480        Just needs to point to model.
1481    */
1482    CbcGeneral (CbcModel * model);
1483
1484    // Copy constructor
1485    CbcGeneral ( const CbcGeneral &);
1486
1487    /// Clone
1488    virtual CbcObject * clone() const = 0;
1489
1490    // Assignment operator
1491    CbcGeneral & operator=( const CbcGeneral& rhs);
1492
1493    // Destructor
1494    ~CbcGeneral ();
1495
1496    /// Infeasibility - large is 0.5
1497    virtual double infeasibility(const OsiBranchingInformation * info,
1498                                 int &preferredWay) const;
1499
1500    using CbcObject::feasibleRegion ;
1501    /// This looks at solution and sets bounds to contain solution
1502    virtual void feasibleRegion() = 0;
1503
1504    /// Creates a branching object
1505    virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) ;
1506
1507    /// Redoes data when sequence numbers change
1508    virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns) = 0;
1509
1510protected:
1511    /// data
1512};
1513#ifdef COIN_HAS_CLP
1514
1515/** Define a catch all class.
1516    This will create a list of subproblems using partial evaluation
1517*/
1518#include "ClpSimplex.hpp"
1519#include "ClpNode.hpp"
1520
1521class CbcGeneralDepth : public CbcGeneral {
1522
1523public:
1524
1525    // Default Constructor
1526    CbcGeneralDepth ();
1527
1528    /** Useful constructor
1529        Just needs to point to model.
1530        Initial version does evaluation to depth N
1531        This is stored in CbcModel but may be
1532        better here
1533    */
1534    CbcGeneralDepth (CbcModel * model, int maximumDepth);
1535
1536    // Copy constructor
1537    CbcGeneralDepth ( const CbcGeneralDepth &);
1538
1539    /// Clone
1540    virtual CbcObject * clone() const;
1541
1542    // Assignment operator
1543    CbcGeneralDepth & operator=( const CbcGeneralDepth& rhs);
1544
1545    // Destructor
1546    ~CbcGeneralDepth ();
1547
1548    /// Infeasibility - large is 0.5
1549    virtual double infeasibility(const OsiBranchingInformation * info,
1550                                 int &preferredWay) const;
1551
1552    using CbcObject::feasibleRegion ;
1553    /// This looks at solution and sets bounds to contain solution
1554    virtual void feasibleRegion();
1555
1556    /// Creates a branching object
1557    virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) ;
1558    /// Return maximum number of nodes
1559    inline int maximumNodes() const {
1560        return maximumNodes_;
1561    }
1562    /// Get maximum depth
1563    inline int maximumDepth() const {
1564        return maximumDepth_;
1565    }
1566    /// Set maximum depth
1567    inline void setMaximumDepth(int value) {
1568        maximumDepth_ = value;
1569    }
1570    /// Get which solution
1571    inline int whichSolution() const {
1572        return whichSolution_;
1573    }
1574    /// Get ClpNode info
1575    inline ClpNode * nodeInfo(int which) {
1576        return nodeInfo_->nodeInfo_[which];
1577    }
1578
1579    /// Redoes data when sequence numbers change
1580    virtual void redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns);
1581
1582protected:
1583    /// data
1584    /// Maximum depth
1585    int maximumDepth_;
1586    /// Maximum nodes
1587    int maximumNodes_;
1588    /// Which node has solution (or -1)
1589    mutable int whichSolution_;
1590    /// Number of valid nodes (including whichSolution_)
1591    mutable int numberNodes_;
1592    /// For solving nodes
1593    mutable ClpNodeStuff * nodeInfo_;
1594};
1595
1596/** Defines a general subproblem
1597    Basis will be made more compact later
1598*/
1599class CoinWarmStartDiff;
1600class CbcSubProblem {
1601
1602public:
1603
1604    /// Default constructor
1605    CbcSubProblem ();
1606
1607    /// Constructor from model
1608    CbcSubProblem (const OsiSolverInterface * solver,
1609                   const double * lowerBefore,
1610                   const double * upperBefore,
1611                   const unsigned char * status,
1612                   int depth);
1613
1614    /// Copy constructor
1615    CbcSubProblem ( const CbcSubProblem &);
1616
1617    /// Assignment operator
1618    CbcSubProblem & operator= (const CbcSubProblem& rhs);
1619
1620    /// Destructor
1621    virtual ~CbcSubProblem ();
1622
1623    /// Apply subproblem (1=bounds, 2=basis, 3=both)
1624    void apply(OsiSolverInterface * model, int what = 3) const;
1625
1626public:
1627    /// Value of objective
1628    double objectiveValue_;
1629    /// Sum of infeasibilities
1630    double sumInfeasibilities_;
1631    /** Which variable (top bit if upper bound changing)
1632        next bit if changing on down branch only */
1633    int * variables_;
1634    /// New bound
1635    double * newBounds_;
1636    /// Status
1637    mutable CoinWarmStartBasis * status_;
1638    /// Depth
1639    int depth_;
1640    /// Number of Extra bound changes
1641    int numberChangedBounds_;
1642    /// Number of infeasibilities
1643    int numberInfeasibilities_;
1644};
1645
1646/** Branching object for general objects
1647
1648 */
1649class CbcNode;
1650class CbcGeneralBranchingObject : public CbcBranchingObject {
1651
1652public:
1653
1654    // Default Constructor
1655    CbcGeneralBranchingObject ();
1656
1657    // Useful constructor
1658    CbcGeneralBranchingObject (CbcModel * model);
1659
1660    // Copy constructor
1661    CbcGeneralBranchingObject ( const CbcGeneralBranchingObject &);
1662
1663    // Assignment operator
1664    CbcGeneralBranchingObject & operator=( const CbcGeneralBranchingObject& rhs);
1665
1666    /// Clone
1667    virtual CbcBranchingObject * clone() const;
1668
1669    // Destructor
1670    virtual ~CbcGeneralBranchingObject ();
1671
1672    using CbcBranchingObject::branch ;
1673    /// Does next branch and updates state
1674    virtual double branch();
1675    /** Double checks in case node can change its mind!
1676        Can change objective etc */
1677    virtual void checkIsCutoff(double cutoff);
1678
1679    using CbcBranchingObject::print ;
1680    /** \brief Print something about branch - only if log level high
1681    */
1682    virtual void print();
1683    /// Fill in current objective etc
1684    void state(double & objectiveValue, double & sumInfeasibilities,
1685               int & numberUnsatisfied, int which) const;
1686    /// Set CbcNode
1687    inline void setNode(CbcNode * node) {
1688        node_ = node;
1689    }
1690    /** Return the type (an integer identifier) of \c this */
1691    virtual int type() const {
1692        return 108;
1693    }
1694
1695    /** Compare the original object of \c this with the original object of \c
1696        brObj. Assumes that there is an ordering of the original objects.
1697        This method should be invoked only if \c this and brObj are of the same
1698        type.
1699        Return negative/0/positive depending on whether \c this is
1700        smaller/same/larger than the argument.
1701    */
1702    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
1703
1704    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
1705        same type and must have the same original object, but they may have
1706        different feasible regions.
1707        Return the appropriate CbcRangeCompare value (first argument being the
1708        sub/superset if that's the case). In case of overlap (and if \c
1709        replaceIfOverlap is true) replace the current branching object with one
1710        whose feasible region is the overlap.
1711     */
1712    virtual CbcRangeCompare compareBranchingObject
1713    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
1714    /// Number of subproblems
1715    inline int numberSubProblems() const {
1716        return numberSubProblems_;
1717    }
1718    /// Decrement number left and return number
1719    inline int decrementNumberLeft() {
1720        numberSubLeft_--;
1721        return numberSubLeft_;
1722    }
1723    /// Which node we want to use
1724    inline int whichNode() const {
1725        return whichNode_;
1726    }
1727    /// Set which node we want to use
1728    inline void setWhichNode(int value) {
1729        whichNode_ = value;
1730    }
1731    // Sub problem
1732    const CbcSubProblem * subProblem(int which) const {
1733        return subProblems_ + which;
1734    }
1735
1736public:
1737    /// data
1738    // Sub problems
1739    CbcSubProblem * subProblems_;
1740    /// Node
1741    CbcNode * node_;
1742    /// Number of subproblems
1743    int numberSubProblems_;
1744    /// Number of subproblems left
1745    int numberSubLeft_;
1746    /// Which node we want to use (-1 for default)
1747    int whichNode_;
1748    /// Number of rows
1749    int numberRows_;
1750};
1751
1752/** Branching object for general objects - just one
1753
1754 */
1755class CbcOneGeneralBranchingObject : public CbcBranchingObject {
1756
1757public:
1758
1759    // Default Constructor
1760    CbcOneGeneralBranchingObject ();
1761
1762    // Useful constructor
1763    CbcOneGeneralBranchingObject (CbcModel * model,
1764                                  CbcGeneralBranchingObject * object,
1765                                  int whichOne);
1766
1767    // Copy constructor
1768    CbcOneGeneralBranchingObject ( const CbcOneGeneralBranchingObject &);
1769
1770    // Assignment operator
1771    CbcOneGeneralBranchingObject & operator=( const CbcOneGeneralBranchingObject& rhs);
1772
1773    /// Clone
1774    virtual CbcBranchingObject * clone() const;
1775
1776    // Destructor
1777    virtual ~CbcOneGeneralBranchingObject ();
1778
1779    using CbcBranchingObject::branch ;
1780    /// Does next branch and updates state
1781    virtual double branch();
1782    /** Double checks in case node can change its mind!
1783        Can change objective etc */
1784    virtual void checkIsCutoff(double cutoff);
1785
1786    using CbcBranchingObject::print ;
1787    /** \brief Print something about branch - only if log level high
1788    */
1789    virtual void print();
1790    /** Return the type (an integer identifier) of \c this */
1791    virtual int type() const {
1792        return 110;
1793    }
1794
1795    /** Compare the original object of \c this with the original object of \c
1796        brObj. Assumes that there is an ordering of the original objects.
1797        This method should be invoked only if \c this and brObj are of the same
1798        type.
1799        Return negative/0/positive depending on whether \c this is
1800        smaller/same/larger than the argument.
1801    */
1802    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
1803
1804    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
1805        same type and must have the same original object, but they may have
1806        different feasible regions.
1807        Return the appropriate CbcRangeCompare value (first argument being the
1808        sub/superset if that's the case). In case of overlap (and if \c
1809        replaceIfOverlap is true) replace the current branching object with one
1810        whose feasible region is the overlap.
1811     */
1812    virtual CbcRangeCompare compareBranchingObject
1813    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
1814
1815public:
1816    /// data
1817    /// Object
1818    CbcGeneralBranchingObject * object_;
1819    /// Which one
1820    int whichOne_;
1821};
1822#endif
1823#endif
Note: See TracBrowser for help on using the repository browser.