1 /* $Id$
2 *
3 * Name: CouenneCutGenerator.cpp
4 * Author: Pietro Belotti
5 * Purpose: define a class of convexification procedures
6 *
7 * (C) Carnegie-Mellon University, 2006-09.
8 * This file is licensed under the Eclipse Public License (EPL)
9 */
10
11 #include "CglCutGenerator.hpp"
12
13 #include "CouenneCutGenerator.hpp"
14
15 #include "CouenneProblem.hpp"
16 #include "CouenneChooseStrong.hpp"
17 #include "CouenneChooseVariable.hpp"
18
19 #include "CbcTree.hpp"
20 #include "BonCbc.hpp"
21 #include "CouenneRecordBestSol.hpp"
22
23 using namespace Ipopt;
24 using namespace Couenne;
25
26 /// constructor
CouenneCutGenerator(Bonmin::OsiTMINLPInterface * nlp,Bonmin::BabSetupBase * base,CouenneProblem * problem,struct ASL * asl)27 CouenneCutGenerator::CouenneCutGenerator (Bonmin::OsiTMINLPInterface *nlp,
28 Bonmin::BabSetupBase *base,
29 CouenneProblem *problem,
30 struct ASL *asl):
31
32 CglCutGenerator (),
33
34 firstcall_ (true),
35 problem_ (problem),
36 nrootcuts_ (0),
37 ntotalcuts_ (0),
38 septime_ (0),
39 objValue_ (- DBL_MAX),
40 nlp_ (nlp),
41 BabPtr_ (NULL),
42 infeasNode_ (false),
43 jnlst_ (base ? base -> journalist () : NULL),
44 rootTime_ (-1.) {
45
46 if (base) {
47
48 base -> options () -> GetIntegerValue ("convexification_points", nSamples_, "couenne.");
49
50 std::string s;
51
52 base -> options () -> GetStringValue ("convexification_type", s, "couenne.");
53 if (s == "current-point-only") convtype_ = CURRENT_ONLY;
54 else if (s == "uniform-grid") convtype_ = UNIFORM_GRID;
55 else convtype_ = AROUND_CURPOINT;
56
57 base -> options () -> GetStringValue ("violated_cuts_only", s, "couenne.");
58 addviolated_ = (s == "yes");
59
60 base -> options () -> GetStringValue ("check_lp", s, "couenne.");
61 check_lp_ = (s == "yes");
62
63 base -> options () -> GetStringValue ("enable_lp_implied_bounds", s, "couenne.");
64 enable_lp_implied_bounds_ = (s == "yes");
65
66 } else {
67
68 nSamples_ = 4;
69 convtype_ = CURRENT_ONLY;
70 addviolated_ = true;
71 check_lp_ = false;
72 enable_lp_implied_bounds_ = false;
73 }
74
75 lastPrintLine = -1;
76
77 //if (asl) // deal with problems not originating from AMPL
78 //problem_ = new CouenneProblem (asl, base, jnlst_);
79 }
80
81
82 /// destructor
~CouenneCutGenerator()83 CouenneCutGenerator::~CouenneCutGenerator ()
84 {}//if (problem_) delete problem_;}
85
86
87 /// copy constructor
CouenneCutGenerator(const CouenneCutGenerator & src)88 CouenneCutGenerator::CouenneCutGenerator (const CouenneCutGenerator &src):
89
90 CglCutGenerator (src),
91
92 firstcall_ (src. firstcall_),
93 addviolated_ (src. addviolated_),
94 convtype_ (src. convtype_),
95 nSamples_ (src. nSamples_),
96 problem_ (src. problem_),// -> clone ()),
97 nrootcuts_ (src. nrootcuts_),
98 ntotalcuts_ (src. ntotalcuts_),
99 septime_ (src. septime_),
100 objValue_ (src. objValue_),
101 nlp_ (src. nlp_),
102 BabPtr_ (src. BabPtr_),
103 infeasNode_ (src. infeasNode_),
104 jnlst_ (src. jnlst_),
105 rootTime_ (src. rootTime_),
106 check_lp_ (src. check_lp_),
107 enable_lp_implied_bounds_ (src.enable_lp_implied_bounds_),
108 lastPrintLine(src.lastPrintLine)
109 {}
110
111
112 #define MAX_SLOPE 1e3
113
114 /// add half-space through two points (x1,y1) and (x2,y2)
addSegment(OsiCuts & cs,int wi,int xi,CouNumber x1,CouNumber y1,CouNumber x2,CouNumber y2,int sign) const115 int CouenneCutGenerator::addSegment (OsiCuts &cs, int wi, int xi,
116 CouNumber x1, CouNumber y1,
117 CouNumber x2, CouNumber y2, int sign) const {
118
119 if (fabs (x2-x1) < COUENNE_EPS) {
120 if (fabs (y2-y1) > MAX_SLOPE * COUENNE_EPS)
121 jnlst_->Printf(J_WARNING, J_CONVEXIFYING,
122 "warning, discontinuity of %e over an interval of %e\n", y2-y1, x2-x1);
123 //else return createCut (cs, y2, (int) 0, wi, 1.);
124 }
125
126 CouNumber dx = x2-x1, dy = y2-y1;
127
128 // return createCut (cs, y1 + oppslope * x1, sign, wi, 1., xi, oppslope);
129 return createCut (cs, y1*dx - dy*x1, (dx>0) ? sign : -sign, wi, dx, xi, -dy);
130 }
131
132
133 /// add tangent at (x,w) with given slope
addTangent(OsiCuts & cs,int wi,int xi,CouNumber x,CouNumber w,CouNumber slope,int sign) const134 int CouenneCutGenerator::addTangent (OsiCuts &cs, int wi, int xi,
135 CouNumber x, CouNumber w,
136 CouNumber slope, int sign) const
137 {return createCut (cs, w - slope * x, sign, wi, 1., xi, - slope);}
138
139
140 /// total number of variables (original + auxiliary) of the problem
getnvars() const141 int CouenneCutGenerator::getnvars () const
142 {return problem_ -> nVars ();}
143
144
145 /// Add list of options to be read from file
registerOptions(Ipopt::SmartPtr<Bonmin::RegisteredOptions> roptions)146 void CouenneCutGenerator::registerOptions (Ipopt::SmartPtr <Bonmin::RegisteredOptions> roptions) {
147
148 roptions -> SetRegisteringCategory ("Couenne options", Bonmin::RegisteredOptions::CouenneCategory);
149
150 roptions -> AddLowerBoundedIntegerOption
151 ("convexification_cuts",
152 "Specify the frequency (in terms of nodes) at which couenne ecp cuts are generated.",
153 -99,1,
154 "A frequency of 0 amounts to never solve the NLP relaxation.");
155
156 roptions -> AddStringOption2
157 ("check_lp",
158 "Check all LPs through an independent call to OsiClpSolverInterface::initialSolve()",
159 "no",
160 "no","",
161 "yes","");
162
163 roptions -> AddStringOption3
164 ("convexification_type",
165 "Determines in which point the linear over/under-estimator are generated",
166 "current-point-only",
167 "current-point-only","Only at current optimum of relaxation",
168 "uniform-grid","Points chosen in a uniform grid between the bounds of the problem",
169 "around-current-point","At points around current optimum of relaxation",
170 "For the lower envelopes of convex functions, this is the number of points where a supporting hyperplane is generated. "
171 "This only holds for the initial linearization, as all other linearizations only add at most one cut per expression."
172 );
173
174 roptions -> AddLowerBoundedIntegerOption
175 ("convexification_points",
176 "Specify the number of points at which to convexify when convexification type "
177 "is uniform-grid or around-current-point.",
178 0,4,
179 "");
180
181 roptions -> AddStringOption2
182 ("violated_cuts_only",
183 "Yes if only violated convexification cuts should be added",
184 "yes",
185 "no","",
186 "yes","");
187
188 roptions -> AddStringOption2
189 ("enable_lp_implied_bounds",
190 "Enable OsiSolverInterface::tightenBounds () -- warning: it has caused "
191 "some trouble to Couenne",
192 "no",
193 "no","",
194 "yes","");
195
196 roptions -> AddStringOption3
197 ("multilinear_separation",
198 "Separation for multilinear terms",
199 "tight",
200 "none", "No separation -- just use the four McCormick inequalities",
201 "simple", "Use one considering lower curve only",
202 "tight", "Use one considering both curves pi(x) = l_{k+1} and pi(x) = u_{k+1}",
203 "Type of separation for multilinear terms where the dependent variable is also bounded"
204 );
205 }
206
207 /*********************************************************************/
printLineInfo() const208 void CouenneCutGenerator::printLineInfo() const {
209
210 double cbcLb = BabPtr_->model().getBestPossibleObjValue();
211 double lpVal = BabPtr_->model().solver()->getObjValue();
212 int nbNodes = BabPtr_->model().getNodeCount();
213 int nbNodesRem = BabPtr_->model().tree()->size();
214 int depth = BabPtr_->model().currentDepth();
215 CouenneRecordBestSol *rs = problem_->getRecordBestSol();
216
217 if(rs->getHasSol()) {
218 double bestSolVal = rs->getVal();
219 printf("%10d %8d %6d %10.6f %10.6f %10.6f\n",
220 nbNodes, nbNodesRem, depth, cbcLb, lpVal, bestSolVal);
221 }
222 else {
223 printf("%10d %8d %6d %10.6f %10.6f ----------\n",
224 nbNodes, nbNodesRem, depth, cbcLb, lpVal);
225 }
226 problem_->doPrint_ = true;
227 if((depth < problem_->minDepthPrint_) ||
228 (nbNodes < problem_->minNodePrint_)) {
229 problem_->doPrint_ = false;
230 }
231 /***
232 if(depth > 200) {
233 printf("CouenneCutGenerator::printLineInfo(): exit on depth\n");
234 exit(1);
235 }
236 ***/
237 } /* printLineInfo */
238