00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011 #include "CouenneExprSum.hpp"
00012 #include "CouenneExprGroup.hpp"
00013 #include "CouenneConfig.h"
00014 #include "CoinHelperFunctions.hpp"
00015 #include "CoinFinite.hpp"
00016
00017 using namespace Couenne;
00018
00020 static CouNumber scanBounds (int, int, int *, CouNumber *, CouNumber *, int *);
00021
00022
00025
00026 bool exprSum::impliedBound (int wind, CouNumber *l, CouNumber *u, t_chg_bounds *chg, enum auxSign sign) {
00027
00052
00053
00054 CouNumber
00055 a0 = 0.,
00056 wl = sign == expression::AUX_GEQ ? -COIN_DBL_MAX : l [wind],
00057 wu = sign == expression::AUX_LEQ ? COIN_DBL_MAX : u [wind];
00058
00059
00060
00061 if ((wl < -COUENNE_INFINITY) &&
00062 (wu > COUENNE_INFINITY))
00063 return false;
00064
00065 int
00066 nterms = nargs_,
00067 nlin = 0;
00068
00069 exprGroup *eg = NULL;
00070
00071 bool isExprGroup = (code () == COU_EXPRGROUP);
00072
00073 if (isExprGroup) {
00074
00075 eg = dynamic_cast <exprGroup *> (this);
00076
00077 a0 += eg -> getc0 ();
00078 nlin += eg -> lcoeff (). size ();
00079 }
00080
00081 nterms += nlin;
00082
00083
00084
00085
00086
00087 CouNumber *C1 = (CouNumber *) malloc (nterms * sizeof (CouNumber)),
00088 *C2 = (CouNumber *) malloc (nlin * sizeof (CouNumber));
00089 int *I1 = (int *) malloc (nterms * sizeof (int)),
00090 *I2 = (int *) malloc (nlin * sizeof (int));
00091
00092 int ipos, ineg = ipos = 0;
00093
00094 std::set <int> intSet;
00095
00096
00097
00098 for (int i = nargs_; i--;) {
00099
00100 int index = arglist_ [i] -> Index ();
00101
00102 if (index < 0)
00103 a0 += arglist_ [i] -> Value ();
00104 else {
00105 I1 [ipos] = index;
00106 C1 [ipos++] = 1.;
00107
00108
00109 if (arglist_ [i] -> isDefinedInteger ())
00110 intSet.insert (index);
00111 }
00112 }
00113
00114
00115
00116 if (isExprGroup) {
00117
00118 exprGroup::lincoeff &lcoe = eg -> lcoeff ();
00119
00120 for (register exprGroup::lincoeff::iterator el = lcoe.begin ();
00121 el != lcoe.end (); ++el) {
00122
00123 CouNumber coe = el -> second;
00124 int ind = el -> first -> Index ();
00125
00126 if (coe > 0.) {I1 [ipos] = ind; C1 [ipos++] = coe;}
00127 else if (coe < -0.) {I2 [ineg] = ind; C2 [ineg++] = coe;}
00128
00129 if (el -> first -> isDefinedInteger ())
00130 intSet.insert (ind);
00131 }
00132 }
00133
00134
00135
00136
00137
00138
00139
00140
00141
00142
00143
00144
00145 int infLo1 = -1, infLo2 = -1,
00146 infUp1 = -1, infUp2 = -1;
00147
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157 CouNumber
00158
00159 lower = a0 + scanBounds (ipos, -1, I1, C1, l, &infLo1)
00160 + scanBounds (ineg, +1, I2, C2, u, &infUp2),
00161
00162 upper = a0 + scanBounds (ipos, +1, I1, C1, u, &infUp1)
00163 + scanBounds (ineg, -1, I2, C2, l, &infLo2);
00164
00165
00166
00167
00168
00169
00170 bool tighter = false;
00171
00172
00173
00174 {
00175 CouNumber
00176 slackL = lower - wl,
00177 slackU = wu - upper;
00178
00179
00180
00181
00182
00183 if ((slackL > 0.) &&
00184 (infLo1 == -1) &&
00185 (infUp2 == -1)) {
00186
00187
00188 if ((sign != expression::AUX_LEQ) && (updateBound (-1, l + wind, lower))) {
00189 chg [wind].setLower(t_chg_bounds::CHANGED);
00190 tighter = true;
00191 if (intSet.find (wind)!= intSet.end ())
00192 l [wind] = ceil (l [wind] - COUENNE_EPS);
00193 }
00194
00195 if ((slackU > 0.) &&
00196 (infLo2 == -1) &&
00197 (infUp1 == -1)) {
00198
00199
00200 if ((sign != expression::AUX_GEQ) && (updateBound (+1, u + wind, upper))) {
00201 chg [wind].setUpper(t_chg_bounds::CHANGED);
00202 tighter = true;
00203 if (intSet.find (wind)!= intSet.end ())
00204 u [wind] = floor (u [wind] + COUENNE_EPS);
00205 }
00206
00207 free (I1); free (I2);
00208 free (C1); free (C2);
00209
00210 return false;
00211 }
00212 }
00213 else if ((slackU > 0.) &&
00214 (infLo2 == -1) &&
00215 (infUp1 == -1)) {
00216
00217
00218 if ((sign != expression::AUX_GEQ) && (updateBound (+1, u + wind, upper))) {
00219 tighter = true;
00220 chg [wind].setUpper(t_chg_bounds::CHANGED);
00221 if (intSet.find (wind)!= intSet.end ())
00222 u [wind] = floor (u [wind] + COUENNE_EPS);
00223 }
00224 }
00225 }
00226
00227
00228
00229
00230
00231
00232 int maxind = -1;
00233
00234 for (register int i=ipos; i--; I1++) if (*I1 > maxind) maxind = *I1;
00235 for (register int i=ineg; i--; I2++) if (*I2 > maxind) maxind = *I2;
00236
00237 I1 -= ipos;
00238 I2 -= ineg;
00239
00240 CouNumber *lc = (CouNumber *) malloc (++maxind * sizeof (CouNumber));
00241 CouNumber *uc = (CouNumber *) malloc (maxind * sizeof (CouNumber));
00242
00243 CoinCopyN (l, maxind, lc);
00244 CoinCopyN (u, maxind, uc);
00245
00246
00247
00248 if ((infLo1 == -1) && (infUp2 == -1) && (wu < COUENNE_INFINITY / 1e10)) {
00249
00250
00251
00252 for (register int i=ipos; i--;) {
00253 int ind = I1 [i];
00254 if ((tighter = (updateBound (+1, u + ind, (wu - lower) / C1 [i] + lc [ind]) || tighter))) {
00255 chg [ind].setUpper(t_chg_bounds::CHANGED);
00256 if (intSet.find (ind)!= intSet.end ())
00257 u [ind] = floor (u [ind] + COUENNE_EPS);
00258 }
00259 }
00260
00261
00262 for (register int i=ineg; i--;) {
00263 int ind = I2 [i];
00264 if ((tighter = (updateBound (-1, l + ind, (wu - lower) / C2 [i] + uc [ind]) || tighter))) {
00265 chg [ind].setLower(t_chg_bounds::CHANGED);
00266 if (intSet.find (ind)!= intSet.end ())
00267 l [ind] = ceil (l [ind] - COUENNE_EPS);
00268 }
00269 }
00270 } else
00271
00272 if ((infLo1 >= 0) && (infUp2 == -1)) {
00273 int ind = I1 [infLo1];
00274 if ((tighter = (updateBound (+1, u + ind, (wu - lower) / C1 [infLo1]) || tighter))) {
00275 chg [ind].setUpper(t_chg_bounds::CHANGED);
00276 if (intSet.find (ind)!= intSet.end ())
00277 u [ind] = floor (u [ind] + COUENNE_EPS);
00278 }
00279 }
00280 else
00281 if ((infLo1 == -1) && (infUp2 >= 0)) {
00282 int ind = I2 [infUp2];
00283 if ((tighter = (updateBound (-1, l + ind, (wu - lower) / C2 [infUp2]) || tighter))) {
00284 chg [ind].setLower(t_chg_bounds::CHANGED);
00285 if (intSet.find (ind)!= intSet.end ())
00286 l [ind] = ceil (l [ind] - COUENNE_EPS);
00287 }
00288 }
00289
00290
00291
00292 if ((infUp1 == -1) && (infLo2 == -1) && (wl > -COUENNE_INFINITY / 1e10)) {
00293
00294
00295 for (register int i=ipos; i--;) {
00296 int ind = I1 [i];
00297 if ((tighter = (updateBound (-1, l + ind, (wl - upper) / C1 [i] + uc [ind]) || tighter))) {
00298 chg [ind].setLower(t_chg_bounds::CHANGED);
00299 if (intSet.find (ind) != intSet.end ())
00300 l [ind] = ceil (l [ind] - COUENNE_EPS);
00301 }
00302 }
00303
00304 for (register int i=ineg; i--;) {
00305 int ind = I2 [i];
00306 if ((tighter = (updateBound (+1, u + ind, (wl - upper) / C2 [i] + lc [ind]) || tighter))) {
00307 chg [ind].setUpper(t_chg_bounds::CHANGED);
00308 if (intSet.find (ind) != intSet.end ())
00309 u [ind] = floor (u [ind] + COUENNE_EPS);
00310 }
00311 }
00312 } else
00313
00314 if ((infUp1 >= 0) && (infLo2 == -1)) {
00315 int ind = I1 [infUp1];
00316 if ((tighter = (updateBound (-1, l + ind, (wl - upper) / C1 [infUp1]) || tighter))) {
00317 chg [ind].setLower(t_chg_bounds::CHANGED);
00318 if (intSet.find (ind) != intSet.end ())
00319 l [ind] = ceil (l [ind] - COUENNE_EPS);
00320 }
00321 }
00322 else
00323 if ((infUp1 == -1) && (infLo2 >= 0)) {
00324 int ind = I2 [infLo2];
00325 if ((tighter = (updateBound (+1, u + ind, (wl - upper) / C2 [infLo2]) || tighter))) {
00326 chg [ind].setUpper(t_chg_bounds::CHANGED);
00327 if (intSet.find (ind) != intSet.end ())
00328 u [ind] = floor (u [ind] + COUENNE_EPS);
00329 }
00330 }
00331
00332
00333
00334 free (I1); free (I2);
00335 free (C1); free (C2);
00336 free (lc); free (uc);
00337
00338 return tighter;
00339 }
00340
00341
00343
00344 static CouNumber scanBounds (int num,
00345 int sign,
00346 int *indices,
00347 CouNumber *coeff,
00348 CouNumber *bounds,
00349 int *infnum) {
00350
00351 CouNumber bound = 0.;
00352
00353 for (register int i = num; i--;) {
00354
00355 CouNumber bd = bounds [indices [i]];
00356
00357
00358
00359 if (((sign > 0) ? bd : -bd) > COUENNE_INFINITY / 1e10) {
00360
00361 bounds [indices [i]] = (sign > 0) ? COIN_DBL_MAX : -COIN_DBL_MAX;
00362
00363
00364
00365 if (*infnum == -1) *infnum = i;
00366 else if (*infnum >= 0) *infnum = -2;
00367 }
00368 else bound += coeff [i] * bd;
00369 }
00370
00371 return bound;
00372 }