source: stable/0.3/Couenne/src/branch/CouenneObject.hpp @ 581

Last change on this file since 581 was 581, checked in by pbelotti, 9 years ago

intInfeasibility() checks lower/upper bounds to avoid non-null infeasibility upon out-of-bounds values, which triggers infeasibility in Couenne but not in Cbc, and this in turn makes the BB loop

  • Property svn:keywords set to Id
File size: 6.9 KB
Line 
1/* $Id: CouenneObject.hpp 581 2011-05-22 11:37:33Z pbelotti $
2 *
3 * Name:    CouenneObject.hpp
4 * Authors: Pierre Bonami, IBM Corp.
5 *          Pietro Belotti, Carnegie Mellon University
6 * Purpose: Object for auxiliary variables
7 *
8 * (C) Carnegie-Mellon University, 2006-11.
9 * This file is licensed under the Common Public License (CPL)
10 */
11
12#ifndef COUENNEOBJECT_HPP
13#define COUENNEOBJECT_HPP
14
15#include "BonBabSetupBase.hpp"
16#include "CoinFinite.hpp"
17
18#include "exprVar.hpp"
19#include "CouenneJournalist.hpp"
20#include "OsiBranchingObject.hpp"
21
22#define AGGR_MUL 2
23#define THRES_ZERO_SYMM 0.8
24
25const CouNumber closeToBounds = .05;
26
27/// Define what kind of branching (two- or three-way) and where to
28/// start from: left, (center,) or right. The last is to help
29/// diversify branching through randomization, which may help when the
30/// same variable is branched upon in several points of the BB tree.
31
32enum {TWO_LEFT,                 TWO_RIGHT,   TWO_RAND,
33      THREE_LEFT, THREE_CENTER, THREE_RIGHT, THREE_RAND, BRANCH_NONE};
34
35class funtriplet;
36class CouenneProblem;
37class CouenneCutGenerator;
38
39CouNumber minMaxDelta (funtriplet *ft, CouNumber lb, CouNumber ub);
40CouNumber maxHeight   (funtriplet *ft, CouNumber lb, CouNumber ub);
41
42
43/// OsiObject for auxiliary variables $w=f(x)$.
44///
45/// Associated with a multi-variate function $f(x)$ and a related
46/// infeasibility $|w-f(x)|$, creates branches to help restoring
47/// feasibility
48
49class CouenneObject: public OsiObject {
50
51public:
52
53  /// type of up/down estimate to return for pseudocosts
54  enum pseudocostMult {INFEASIBILITY, 
55                       INTERVAL_LP, INTERVAL_LP_REV,
56                       INTERVAL_BR, INTERVAL_BR_REV,
57                       PROJECTDIST};
58
59  /// type of object (for branching variable selection)
60  enum branch_obj {EXPR_OBJ, VAR_OBJ, VT_OBJ};
61
62  /// strategy names
63  enum brSelStrat {NO_STRATEGY, NO_BRANCH, MID_INTERVAL, MIN_AREA, BALANCED, LP_CENTRAL, LP_CLAMPED};
64
65  /// empty constructor (for unused objects)
66  CouenneObject ();
67
68  /// Constructor with information for branching point selection strategy
69  CouenneObject (CouenneCutGenerator *cutgen,
70                 CouenneProblem *p, 
71                 exprVar *ref, Bonmin::BabSetupBase *base, JnlstPtr jnlst);
72
73  /// Constructor with lesser information, used for infeasibility only
74  CouenneObject (exprVar *ref, Bonmin::BabSetupBase *base, JnlstPtr jnlst);
75
76  /// Destructor
77  ~CouenneObject () {}
78
79  /// Copy constructor
80  CouenneObject (const CouenneObject &src);
81
82  /// Cloning method
83  virtual CouenneObject * clone () const
84  {return new CouenneObject (*this);}
85
86  /// set object parameters by reading from command line
87  void setParameters (Bonmin::BabSetupBase *base);
88
89  /// compute infeasibility of this variable, |w - f(x)| (where w is
90  /// the auxiliary variable defined as w = f(x)
91  virtual double infeasibility (const OsiBranchingInformation *info, int &way) const;
92
93  /// compute infeasibility of this variable, |w - f(x)|, where w is
94  /// the auxiliary variable defined as w = f(x)
95  virtual double checkInfeasibility (const OsiBranchingInformation * info) const;
96
97  /// fix (one of the) arguments of reference auxiliary variable
98  virtual double feasibleRegion (OsiSolverInterface*, const OsiBranchingInformation*) const;
99
100  /// create CouenneBranchingObject or CouenneThreeWayBranchObj based
101  /// on this object
102  virtual OsiBranchingObject *createBranch (OsiSolverInterface*, 
103                                            const OsiBranchingInformation*, int) const;
104
105  /// return reference auxiliary variable
106  exprVar *Reference () const
107  {return reference_;}
108
109  /// return branching point selection strategy
110  enum brSelStrat Strategy ()  const
111  {return strategy_;}
112
113  /// pick branching point based on current strategy
114  CouNumber getBrPoint (funtriplet *ft, CouNumber x0, CouNumber l, CouNumber u) const;
115
116  /// returns a point "inside enough" a given interval, or x if it
117  /// already is
118  CouNumber midInterval (CouNumber x, CouNumber l, CouNumber u) const;
119
120  /// Return "down" estimate (for non-convex, distance old <--> new LP point)
121  virtual double downEstimate () const
122  {//if (jnlst_ -> ProduceOutput (J_MATRIX, J_BRANCHING)) {
123    //printf ("DOWN EST = %g for ", downEstimate_);
124    //reference_ -> print ();
125    //printf ("\n");
126    //}
127  return downEstimate_;}
128
129  /// Return "up" estimate (for non-convex, distance old <--> new LP point)
130  virtual double upEstimate () const
131  {//if (jnlst_ -> ProduceOutput (J_MATRIX, J_BRANCHING)) {
132    //printf ("UP EST = %g for ", upEstimate_);
133    //reference_ -> print ();
134    //printf ("\n");
135    //}
136  return upEstimate_;}
137
138  /// set up/down estimate (0 for down, 1 for up). This happens in
139  /// CouenneChooseStrong, where a new LP point is available and we
140  /// can measure distance from old LP point. This is the denominator
141  /// we use in pseudocost
142  void setEstimate (double est, int direction)
143  {(direction ? upEstimate_ : downEstimate_) = est;}
144
145  /// set up/down estimates based on branching information
146  void setEstimates (const OsiBranchingInformation *info,
147                     CouNumber *infeasibility,
148                     CouNumber *brpt) const;
149
150  /// are we on the bad or good side of the expression?
151  virtual bool isCuttable () const {
152    return (reference_ -> Image ()) ? 
153      ((!(reference_ -> isInteger ())) &&
154       reference_ -> Image () -> isCuttable (problem_, reference_ -> Index ())) :
155      (!(reference_ -> isInteger ()));
156  }
157
158  /// integer infeasibility: min {value - floor(value), ceil(value) - value}
159  virtual double intInfeasibility (double value, double lb, double ub) const;
160
161  /// Defines safe interval percentage for using LP point as a branching point
162  CouNumber lp_clamp () const
163  {return lp_clamp_;}
164
165  // Column number if single column object, -1 otherwise.
166  virtual int columnNumber () const
167  {//printf ("calling columnNumber(), returning %d\n",
168   //((reference_) ? reference_ -> Index () : -1));
169    return ((reference_) ? reference_ -> Index () : -1);}
170
171protected:
172
173  /// pointer to cut generator (not necessary, can be NULL)
174  CouenneCutGenerator *cutGen_;
175
176  /// pointer to Couenne problem
177  CouenneProblem *problem_;
178
179  /// The (auxiliary) variable this branching object refers to. If the
180  /// expression is w=f(x,y), this is w, as opposed to
181  /// CouenneBranchingObject, where it would be either x or y.
182  exprVar *reference_;
183
184  /// Branching point selection strategy
185  enum brSelStrat strategy_;
186
187  /// SmartPointer to the Journalist
188  JnlstPtr jnlst_;
189
190  /// Combination parameter for the mid-point branching point
191  /// selection strategy
192  CouNumber alpha_;
193
194  /// Defines safe interval percentage for using LP point as a branching point
195  CouNumber lp_clamp_;
196
197  /// feasibility tolerance (equal to that of CouenneProblem)
198  CouNumber feas_tolerance_;
199
200  /// shall we do Feasibility based Bound Tightening (FBBT) at branching?
201  bool doFBBT_;
202
203  /// shall we add convexification cuts at branching?
204  bool doConvCuts_;
205
206  /// down estimate (to be used in pseudocost)
207  mutable double downEstimate_;
208
209  /// up estimate (to be used in pseudocost)
210  mutable double upEstimate_;
211
212  /// multiplier type for pseudocost
213  enum pseudocostMult pseudoMultType_;
214};
215
216#endif
Note: See TracBrowser for help on using the repository browser.