source: branches/sandbox/Cbc/src/CbcBranchBase.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: 23.0 KB
Line 
1/* $Id: CbcBranchBase.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 CbcBranchBase_H
5#define CbcBranchBase_H
6
7#include <string>
8#include <vector>
9#include "OsiBranchingObject.hpp"
10class OsiSolverInterface;
11class OsiSolverBranch;
12
13class CbcModel;
14class CbcNode;
15class CbcNodeInfo;
16class CbcBranchingObject;
17class OsiChooseVariable;
18class CbcObjectUpdateData;
19
20//#############################################################################
21
22enum CbcRangeCompare {
23    CbcRangeSame,
24    CbcRangeDisjoint,
25    CbcRangeSubset,
26    CbcRangeSuperset,
27    CbcRangeOverlap
28};
29
30//#############################################################################
31
32/** Abstract base class for `objects'.
33    It now just has stuff that OsiObject does not have
34
35  The branching model used in Cbc is based on the idea of an <i>object</i>.
36  In the abstract, an object is something that has a feasible region, can be
37  evaluated for infeasibility, can be branched on (<i>i.e.</i>, there's some
38  constructive action to be taken to move toward feasibility), and allows
39  comparison of the effect of branching.
40
41  This class (CbcObject) is the base class for an object. To round out the
42  branching model, the class CbcBranchingObject describes how to perform a
43  branch, and the class CbcBranchDecision describes how to compare two
44  CbcBranchingObjects.
45
46  To create a new type of object you need to provide three methods:
47  #infeasibility(), #feasibleRegion(), and #createCbcBranch(), described below.
48
49  This base class is primarily virtual to allow for any form of structure.
50  Any form of discontinuity is allowed.
51
52  \todo The notion that all branches are binary (two arms) is wired into the
53        implementation of CbcObject, CbcBranchingObject, and
54        CbcBranchDecision. Changing this will require a moderate amount of
55        recoding.
56 */
57// This can be used if object wants to skip strong branching
58typedef struct {
59    CbcBranchingObject * possibleBranch; // what a branch would do
60    double upMovement; // cost going up (and initial away from feasible)
61    double downMovement; // cost going down
62    int numIntInfeasUp ; // without odd ones
63    int numObjInfeasUp ; // just odd ones
64    bool finishedUp; // true if solver finished
65    int numItersUp ; // number of iterations in solver
66    int numIntInfeasDown ; // without odd ones
67    int numObjInfeasDown ; // just odd ones
68    bool finishedDown; // true if solver finished
69    int numItersDown; // number of iterations in solver
70    int objectNumber; // Which object it is
71    int fix; // 0 if no fix, 1 if we can fix up, -1 if we can fix down
72} CbcStrongInfo;
73
74class CbcObject : public OsiObject {
75
76public:
77
78    // Default Constructor
79    CbcObject ();
80
81    // Useful constructor
82    CbcObject (CbcModel * model);
83
84    // Copy constructor
85    CbcObject ( const CbcObject &);
86
87    // Assignment operator
88    CbcObject & operator=( const CbcObject& rhs);
89
90    /// Clone
91    virtual CbcObject * clone() const = 0;
92
93    /// Destructor
94    virtual ~CbcObject ();
95
96    /** Infeasibility of the object
97
98        This is some measure of the infeasibility of the object. It should be
99        scaled to be in the range [0.0, 0.5], with 0.0 indicating the object
100        is satisfied.
101
102        The preferred branching direction is returned in preferredWay,
103
104        This is used to prepare for strong branching but should also think of
105        case when no strong branching
106
107        The object may also compute an estimate of cost of going "up" or "down".
108        This will probably be based on pseudo-cost ideas
109    */
110#ifdef CBC_NEW_STYLE_BRANCH
111    virtual double infeasibility(const OsiBranchingInformation * info,
112                                 int &preferredWay) const = 0;
113#else
114    virtual double infeasibility(const OsiBranchingInformation * /*info*/,
115                                 int &preferredWay) const {
116        return infeasibility(preferredWay);
117    }
118    virtual double infeasibility(int &/*preferredWay*/) const {
119        throw CoinError("Need code", "infeasibility", "CbcBranchBase");
120    }
121#endif
122
123    /** For the variable(s) referenced by the object,
124        look at the current solution and set bounds to match the solution.
125    */
126    virtual void feasibleRegion() = 0;
127    /// Dummy one for compatibility
128    virtual double feasibleRegion(OsiSolverInterface * solver, const OsiBranchingInformation * info) const;
129
130    /** For the variable(s) referenced by the object,
131        look at the current solution and set bounds to match the solution.
132        Returns measure of how much it had to move solution to make feasible
133    */
134    virtual double feasibleRegion(OsiSolverInterface * solver) const ;
135
136    /** Create a branching object and indicate which way to branch first.
137
138        The branching object has to know how to create branches (fix
139        variables, etc.)
140    */
141#ifdef CBC_NEW_STYLE_BRANCH
142    virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) = 0;
143#else
144    virtual CbcBranchingObject * createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) {
145        return createBranch(solver, info, way);
146    }
147    virtual CbcBranchingObject * createBranch(OsiSolverInterface * /*solver*/,
148            const OsiBranchingInformation * /*info*/, int /*way*/) {
149        throw CoinError("Need code", "createBranch", "CbcBranchBase");
150    }
151#endif
152    /** Create an Osibranching object and indicate which way to branch first.
153
154        The branching object has to know how to create branches (fix
155        variables, etc.)
156    */
157    virtual OsiBranchingObject * createOsiBranch(OsiSolverInterface * solver, const OsiBranchingInformation * info, int way) const;
158    /** Create an OsiSolverBranch object
159
160        This returns NULL if branch not represented by bound changes
161    */
162    virtual OsiSolverBranch * solverBranch() const;
163
164    /** \brief Given a valid solution (with reduced costs, etc.),
165        return a branching object which would give a new feasible
166        point in a good direction.
167
168        If the method cannot generate a feasible point (because there aren't
169        any, or because it isn't bright enough to find one), it should
170        return null.
171    */
172    virtual CbcBranchingObject * preferredNewFeasible() const {
173        return NULL;
174    }
175
176    /** \brief Given a valid solution (with reduced costs, etc.),
177        return a branching object which would give a new feasible
178        point in a bad direction.
179
180        If the method cannot generate a feasible point (because there aren't
181        any, or because it isn't bright enough to find one), it should
182        return null.
183    */
184    virtual CbcBranchingObject * notPreferredNewFeasible() const {
185        return NULL;
186    }
187
188    /** Reset variable bounds to their original values.
189
190      Bounds may be tightened, so it may be good to be able to set this info in object.
191     */
192    virtual void resetBounds(const OsiSolverInterface * ) {}
193
194    /** Returns floor and ceiling i.e. closest valid points
195    */
196    virtual void floorCeiling(double & floorValue, double & ceilingValue, double value,
197                              double tolerance) const;
198
199    /** Pass in information on branch just done and create CbcObjectUpdateData instance.
200        If object does not need data then backward pointer will be NULL.
201        Assumes can get information from solver */
202    virtual CbcObjectUpdateData createUpdateInformation(const OsiSolverInterface * solver,
203            const CbcNode * node,
204            const CbcBranchingObject * branchingObject);
205
206    /// Update object by CbcObjectUpdateData
207    virtual void updateInformation(const CbcObjectUpdateData & ) {}
208
209    /// Identifier (normally column number in matrix)
210    inline int id() const {
211        return id_;
212    }
213
214    /** Set identifier (normally column number in matrix)
215        but 1000000000 to 1100000000 means optional branching object
216        i.e. code would work without it */
217    inline void setId(int value) {
218        id_ = value;
219    }
220
221    /** Return true if optional branching object
222        i.e. code would work without it */
223    inline bool optionalObject() const {
224        return (id_ >= 1000000000 && id_ < 1100000000);
225    }
226
227    /// Get position in object_ list
228    inline int position() const {
229        return position_;
230    }
231
232    /// Set position in object_ list
233    inline void setPosition(int position) {
234        position_ = position;
235    }
236
237    /// update model
238    inline void setModel(CbcModel * model) {
239        model_ = model;
240    }
241
242    /// Return model
243    inline CbcModel * model() const {
244        return  model_;
245    }
246
247    /// If -1 down always chosen first, +1 up always, 0 normal
248    inline int preferredWay() const {
249        return preferredWay_;
250    }
251    /// Set -1 down always chosen first, +1 up always, 0 normal
252    inline void setPreferredWay(int value) {
253        preferredWay_ = value;
254    }
255    /// Redoes data when sequence numbers change
256    virtual void redoSequenceEtc(CbcModel * , int , const int * ) {}
257
258protected:
259    /// data
260
261    /// Model
262    CbcModel * model_;
263    /// Identifier (normally column number in matrix)
264    int id_;
265    /// Position in object list
266    int position_;
267    /// If -1 down always chosen first, +1 up always, 0 normal
268    int preferredWay_;
269
270};
271
272/** \brief Abstract branching object base class
273    Now just difference with OsiBranchingObject
274
275  In the abstract, an CbcBranchingObject contains instructions for how to
276  branch. We want an abstract class so that we can describe how to branch on
277  simple objects (<i>e.g.</i>, integers) and more exotic objects
278  (<i>e.g.</i>, cliques or hyperplanes).
279
280  The #branch() method is the crucial routine: it is expected to be able to
281  step through a set of branch arms, executing the actions required to create
282  each subproblem in turn. The base class is primarily virtual to allow for
283  a wide range of problem modifications.
284
285  See CbcObject for an overview of the three classes (CbcObject,
286  CbcBranchingObject, and CbcBranchDecision) which make up cbc's branching
287  model.
288*/
289
290class CbcBranchingObject : public OsiBranchingObject {
291
292public:
293
294    /// Default Constructor
295    CbcBranchingObject ();
296
297    /// Constructor
298    CbcBranchingObject (CbcModel * model, int variable, int way , double value);
299
300    /// Copy constructor
301    CbcBranchingObject ( const CbcBranchingObject &);
302
303    /// Assignment operator
304    CbcBranchingObject & operator=( const CbcBranchingObject& rhs);
305
306    /// Clone
307    virtual CbcBranchingObject * clone() const = 0;
308
309    /// Destructor
310    virtual ~CbcBranchingObject ();
311
312    /** Some branchingObjects may claim to be able to skip
313        strong branching.  If so they ahve to fill in CbcStrongInfo.
314        The object mention in incoming CbcStrongInfo must match.
315        Returns nonzero if skip is wanted */
316    virtual int fillStrongInfo( CbcStrongInfo & ) {
317        return 0;
318    }
319    /// Reset number of branches left to original
320    inline void resetNumberBranchesLeft() {
321        branchIndex_ = 0;
322    }
323    /// Set number of branches to do
324    inline void setNumberBranches(int value) {
325        branchIndex_ = 0;
326        numberBranches_ = value;
327    }
328
329    /** \brief Execute the actions required to branch, as specified by the
330           current state of the branching object, and advance the object's
331           state.  Mainly for diagnostics, whether it is true branch or
332           strong branching is also passed.
333           Returns change in guessed objective on next branch
334    */
335    virtual double branch() = 0;
336    /** \brief Execute the actions required to branch, as specified by the
337           current state of the branching object, and advance the object's
338           state.  Mainly for diagnostics, whether it is true branch or
339           strong branching is also passed.
340           Returns change in guessed objective on next branch
341    */
342    virtual double branch(OsiSolverInterface * ) {
343        return branch();
344    }
345    /** Update bounds in solver as in 'branch' and update given bounds.
346        branchState is -1 for 'down' +1 for 'up' */
347    virtual void fix(OsiSolverInterface * ,
348                     double * , double * ,
349                     int ) const {}
350
351    /** Reset every information so that the branching object appears to point to
352        the previous child. This method does not need to modify anything in any
353        solver. */
354    virtual void previousBranch() {
355        assert(branchIndex_ > 0);
356        branchIndex_--;
357        way_ = -way_;
358    }
359
360    using OsiBranchingObject::print ;
361    /** \brief Print something about branch - only if log level high
362    */
363    virtual void print() const {}
364
365    /** \brief Index identifying the associated CbcObject within its class.
366
367      The name is misleading, and typically the index will <i>not</i> refer
368      directly to a variable.
369      Rather, it identifies an CbcObject within the class of similar
370      CbcObjects
371
372      <i>E.g.</i>, for an CbcSimpleInteger, variable() is the index of the
373      integer variable in the set of integer variables (<i>not</i> the index of
374      the variable in the set of all variables).
375    */
376    inline int variable() const {
377        return variable_;
378    }
379
380    /** Get the state of the branching object
381
382      Returns a code indicating the active arm of the branching object.
383      The precise meaning is defined in the derived class.
384
385      \sa #way_
386    */
387    inline int way() const {
388        return way_;
389    }
390
391    /** Set the state of the branching object.
392
393      See #way()
394    */
395    inline void way(int way) {
396        way_ = way;
397    }
398
399    /// update model
400    inline void setModel(CbcModel * model) {
401        model_ = model;
402    }
403    /// Return model
404    inline CbcModel * model() const {
405        return  model_;
406    }
407
408    /// Return pointer back to object which created
409    inline CbcObject * object() const {
410        return  originalCbcObject_;
411    }
412    /// Set pointer back to object which created
413    inline void setOriginalObject(CbcObject * object) {
414        originalCbcObject_ = object;
415    }
416
417    // Methods used in heuristics
418
419    /** Return the type (an integer identifier) of \c this */
420    virtual int type() const = 0;
421
422    /** Compare the original object of \c this with the original object of \c
423        brObj. Assumes that there is an ordering of the original objects.
424        This method should be invoked only if \c this and brObj are of the same
425        type.
426        Return negative/0/positive depending on whether \c this is
427        smaller/same/larger than the argument.
428    */
429    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const {
430        const CbcBranchingObject* br = dynamic_cast<const CbcBranchingObject*>(brObj);
431        return variable() - br->variable();
432    }
433
434    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
435        same type and must have the same original object, but they may have
436        different feasible regions.
437        Return the appropriate CbcRangeCompare value (first argument being the
438        sub/superset if that's the case). In case of overlap (and if \c
439        replaceIfOverlap is true) replace the current branching object with one
440        whose feasible region is the overlap.
441     */
442    virtual CbcRangeCompare compareBranchingObject
443    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false) = 0;
444
445protected:
446
447    /// The model that owns this branching object
448    CbcModel * model_;
449    /// Pointer back to object which created
450    CbcObject * originalCbcObject_;
451
452    /// Branching variable (0 is first integer)
453    int variable_;
454    // was - Way to branch - -1 down (first), 1 up, -2 down (second), 2 up (second)
455    /** The state of the branching object.
456
457      Specifies the active arm of the branching object. Coded as -1 to take
458      the `down' arm, +1 for the `up' arm. `Down' and `up' are defined based on
459      the natural meaning (floor and ceiling, respectively) for a simple integer.
460      The precise meaning is defined in the derived class.
461    */
462    int way_;
463
464};
465
466
467/** Abstract branching decision base class
468
469  In the abstract, an CbcBranchDecision object is expected to be able to
470  compare two possible branching choices.
471
472  The #betterBranch() method is the crucial routine. It is expected to be able
473  to compare two \link CbcBranchingObject CbcBranchingObjects \endlink.
474
475  See CbcObject for an overview of the three classes (CbcObject,
476  CbcBranchingObject, and CbcBranchDecision) which make up cbc's branching
477  model.
478*/
479
480class CbcBranchDecision {
481public:
482    /// Default Constructor
483    CbcBranchDecision ();
484
485    // Copy constructor
486    CbcBranchDecision ( const CbcBranchDecision &);
487
488    /// Destructor
489    virtual ~CbcBranchDecision();
490
491/// Clone
492    virtual CbcBranchDecision * clone() const = 0;
493
494    /// Initialize <i>e.g.</i> before starting to choose a branch at a node
495    virtual void initialize(CbcModel * model) = 0;
496
497    /** \brief Compare two branching objects. Return nonzero if branching
498           using \p thisOne is better than branching using \p bestSoFar.
499
500      If \p bestSoFar is NULL, the routine should return a nonzero value.
501      This routine is used only after strong branching.
502      Either this or bestBranch is used depending which user wants.
503
504    */
505
506    virtual int
507    betterBranch (CbcBranchingObject * thisOne,
508                  CbcBranchingObject * bestSoFar,
509                  double changeUp, int numberInfeasibilitiesUp,
510                  double changeDown, int numberInfeasibilitiesDown) = 0 ;
511
512    /** \brief Compare N branching objects. Return index of best
513        and sets way of branching in chosen object.
514
515      Either this or betterBranch is used depending which user wants.
516    */
517
518    virtual int
519    bestBranch (CbcBranchingObject ** objects, int numberObjects, int numberUnsatisfied,
520                double * changeUp, int * numberInfeasibilitiesUp,
521                double * changeDown, int * numberInfeasibilitiesDown,
522                double objectiveValue) ;
523
524    /** Says whether this method can handle both methods -
525        1 better, 2 best, 3 both */
526    virtual int whichMethod() {
527        return 2;
528    }
529
530    /** Saves a clone of current branching object.  Can be used to update
531        information on object causing branch - after branch */
532    virtual void saveBranchingObject(OsiBranchingObject * ) {}
533    /** Pass in information on branch just done.
534        assumes object can get information from solver */
535    virtual void updateInformation(OsiSolverInterface * ,
536                                   const CbcNode * ) {}
537    /** Sets or gets best criterion so far */
538    virtual void setBestCriterion(double ) {}
539    virtual double getBestCriterion() const {
540        return 0.0;
541    }
542    /// Create C++ lines to get to current state
543    virtual void generateCpp( FILE * ) {}
544    /// Model
545    inline CbcModel * cbcModel() const {
546        return model_;
547    }
548    /* If chooseMethod_ id non-null then the rest is fairly pointless
549       as choosemethod_ will be doing all work
550    */
551    OsiChooseVariable * chooseMethod() const {
552        return chooseMethod_;
553    }
554    /// Set (clone) chooseMethod
555    void setChooseMethod(const OsiChooseVariable & method);
556
557protected:
558
559    // Clone of branching object
560    CbcBranchingObject * object_;
561    /// Pointer to model
562    CbcModel * model_;
563    /* If chooseMethod_ id non-null then the rest is fairly pointless
564       as choosemethod_ will be doing all work
565    */
566    OsiChooseVariable * chooseMethod_;
567private:
568    /// Assignment is illegal
569    CbcBranchDecision & operator=(const CbcBranchDecision& rhs);
570
571};
572/** Abstract base class for consequent bounds.
573    When a variable is branched on it normally interacts with other variables by
574    means of equations.  There are cases where we want to step outside LP and do something
575    more directly e.g. fix bounds.  This class is for that.
576
577    At present it need not be virtual as only instance is CbcFixVariable, but ...
578
579 */
580
581class CbcConsequence {
582
583public:
584
585    // Default Constructor
586    CbcConsequence ();
587
588    // Copy constructor
589    CbcConsequence ( const CbcConsequence & rhs);
590
591    // Assignment operator
592    CbcConsequence & operator=( const CbcConsequence & rhs);
593
594    /// Clone
595    virtual CbcConsequence * clone() const = 0;
596
597    /// Destructor
598    virtual ~CbcConsequence ();
599
600    /** Apply to an LP solver.  Action depends on state
601     */
602    virtual void applyToSolver(OsiSolverInterface * solver, int state) const = 0;
603
604protected:
605};
606/*  This stores data so an object can be updated
607 */
608class CbcObjectUpdateData {
609
610public:
611
612    /// Default Constructor
613    CbcObjectUpdateData ();
614
615    /// Useful constructor
616    CbcObjectUpdateData (CbcObject * object,
617                         int way,
618                         double change,
619                         int status,
620                         int intDecrease_,
621                         double branchingValue);
622
623    /// Copy constructor
624    CbcObjectUpdateData ( const CbcObjectUpdateData &);
625
626    /// Assignment operator
627    CbcObjectUpdateData & operator=( const CbcObjectUpdateData& rhs);
628
629    /// Destructor
630    virtual ~CbcObjectUpdateData ();
631
632
633public:
634    /// data
635
636    /// Object
637    CbcObject * object_;
638    /// Branch as defined by instance of CbcObject
639    int way_;
640    /// Object number
641    int objectNumber_;
642    /// Change in objective
643    double change_;
644    /// Status 0 Optimal, 1 infeasible, 2 unknown
645    int status_;
646    /// Decrease in number unsatisfied
647    int intDecrease_;
648    /// Branching value
649    double branchingValue_;
650    /// Objective value before branching
651    double originalObjective_;
652    /// Current cutoff
653    double cutoff_;
654
655};
656
657//##############################################################################
658
659/** Compare two ranges. The two bounds arrays are both of size two and
660    describe closed intervals. Return the appropriate CbcRangeCompare value
661    (first argument being the sub/superset if that's the case). In case of
662    overlap (and if \c replaceIfOverlap is true) replace the content of thisBd
663    with the intersection of the ranges.
664*/
665static inline CbcRangeCompare
666CbcCompareRanges(double* thisBd, const double* otherBd,
667                 const bool replaceIfOverlap)
668{
669    const double lbDiff = thisBd[0] - otherBd[0];
670    if (lbDiff < 0) { // lb of this < lb of other
671        if (thisBd[1] >= otherBd[1]) { // ub of this >= ub of other
672            return CbcRangeSuperset;
673        } else if (thisBd[1] < otherBd[0]) {
674            return CbcRangeDisjoint;
675        } else {
676            // overlap
677            if (replaceIfOverlap) {
678                thisBd[0] = otherBd[0];
679            }
680            return CbcRangeOverlap;
681        }
682    } else if (lbDiff > 0) { // lb of this > lb of other
683        if (thisBd[1] <= otherBd[1]) { // ub of this <= ub of other
684            return CbcRangeSubset;
685        } else if (thisBd[0] > otherBd[1]) {
686            return CbcRangeDisjoint;
687        } else {
688            // overlap
689            if (replaceIfOverlap) {
690                thisBd[1] = otherBd[1];
691            }
692            return CbcRangeOverlap;
693        }
694    } else { // lb of this == lb of other
695        if (thisBd[1] == otherBd[1]) {
696            return CbcRangeSame;
697        }
698        return thisBd[1] < otherBd[1] ? CbcRangeSubset : CbcRangeSuperset;
699    }
700
701    return CbcRangeSame; // fake return
702
703}
704
705//#############################################################################
706
707#endif
Note: See TracBrowser for help on using the repository browser.