00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #include "CoinTime.hpp"
00013 #include "CouenneProblem.hpp"
00014
00015
00016
00017 #define VALID_ONLY_THRESHOLD 5
00018
00025
00026 int CouenneProblem::getIntegerCandidate (const double *xFrac, double *xInt,
00027 double *lb, double *ub) const {
00028 fillIntegerRank ();
00029
00030 if (numberInRank_.size () == 0)
00031 return 0;
00032
00033 CouNumber *store_optimum = optimum_;
00034 optimum_ = NULL;
00035
00036 int
00037 ncols = nVars (),
00038 retval = 0;
00039
00040 double
00041 *olb = new double [ncols], *oub = new double [ncols],
00042 *dualL = new double [nOrigVars_], *dualR = new double [nOrigVars_];
00043
00044
00045 CoinCopyN (Lb (), ncols, olb);
00046 CoinCopyN (Ub (), ncols, oub);
00047
00048
00049 CoinCopyN (xFrac, nOrigVars_, xInt);
00050
00051 domain_.push (nVars (), xInt, lb, ub);
00052
00053 CoinCopyN (lb, nVars (), Lb ());
00054 CoinCopyN (ub, nVars (), Ub ());
00055
00056 enum fixType *fixed = new enum fixType [nOrigVars_];
00057
00058 for (int i=0; i<nOrigVars_; i++)
00059 fixed [i] = (Var (i) -> isInteger () &&
00060 Var (i) -> Multiplicity () > 0) ?
00061 UNFIXED : CONTINUOUS;
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096
00097
00098
00099 const int infeasible = 1;
00100
00101 try {
00102
00103
00104
00105 int rank = 1;
00106
00107 if (jnlst_ -> ProduceOutput (Ipopt::J_MOREVECTOR, J_NLPHEURISTIC)) {
00108 printf ("= ===========================================\n");
00109 printf ("= BEGIN ===========================================\n");
00110 printf ("= ===========================================\n");
00111 for (int i=0; i<nOrigVars_; i++)
00112 if (variables_ [i] -> Multiplicity () > 0)
00113 printf ("#### %4d: %d %c %2d frac %20g [%20g,%20g]\n",
00114 i, fixed [i],
00115 variables_ [i] -> isInteger () ? 'I' : ' ',
00116 integerRank_ ? integerRank_ [i] : -1,
00117 xFrac [i], Lb (i), Ub (i));
00118 printf ("---\n");
00119 for (int i=nOrigVars_; i<nVars (); i++)
00120 if (variables_ [i] -> Multiplicity () > 0)
00121 printf ("#### %4d: %c frac %20g [%20g,%20g]\n",
00122 i, variables_ [i] -> isInteger () ? 'I' : ' ',
00123
00124 X (i), Lb (i), Ub (i));
00125 printf ("===================================================\n");
00126 printf ("===================================================\n");
00127 printf ("===================================================\n");
00128 }
00129
00130
00131 const int
00132 N_VARS_HUGE = 10000,
00133 N_VARS_LARGE = 1000,
00134 N_VARS_MEDIUM = 100,
00135 N_VARS_SMALL = 10,
00136 N_VARS_TINY = 5;
00137
00138 int
00139 ntrials = 0,
00140 nvars = nVars (),
00141 maxtrials =
00142 (nvars >= N_VARS_HUGE) ? 0 :
00143 (nvars >= N_VARS_LARGE) ? 1 :
00144 (nvars >= N_VARS_MEDIUM) ? 2 :
00145 (nvars >= N_VARS_SMALL) ? 4 :
00146 (nvars >= N_VARS_TINY) ? 8 : 16;
00147
00148 for (std::vector <int>::iterator rNum = numberInRank_.begin();
00149 ++rNum != numberInRank_.end(); rank++)
00150
00151 if (*rNum > 0) {
00152
00153 if (CoinCpuTime () > maxCpuTime_)
00154 break;
00155
00156
00157
00158
00159 for (int i=0; i<nOrigVars_; i++)
00160 if ((Var (i) -> Multiplicity () > 0) &&
00161 (Var (i) -> isInteger ()) &&
00162 (integerRank_ [i] == rank)) {
00163
00164 Lb (i) = CoinMax (Lb (i), floor (xFrac [i]));
00165 Ub (i) = CoinMin (Ub (i), ceil (xFrac [i]));
00166 }
00167
00168
00169 initAuxs ();
00170
00171 if (jnlst_ -> ProduceOutput (Ipopt::J_MOREVECTOR, J_NLPHEURISTIC)) {
00172 printf ("= RANK LEVEL = %d [%d] ==================================\n", rank, *rNum);
00173 for (int i=0; i<nOrigVars_; i++)
00174 if (Var (i) -> Multiplicity () > 0)
00175 printf ("#### %4d: %d %c %2d frac %20g -> int %20g [%20g,%20g]\n",
00176 i, fixed [i],
00177 variables_ [i] -> isInteger () ? 'I' : ' ',
00178 integerRank_ ? integerRank_ [i] : -1,
00179 xFrac [i], xInt [i], Lb (i), Ub (i));
00180 printf ("--------------------\n");
00181 for (int i=nOrigVars_; i<nVars (); i++)
00182 if (Var (i) -> Multiplicity () > 0)
00183 printf ("#### %4d: %c frac %20g [%20g,%20g]\n",
00184 i, variables_ [i] -> isInteger () ? 'I' : ' ',
00185
00186 X (i), Lb (i), Ub (i));
00187 printf ("=================================================\n");
00188 }
00189
00190
00191
00192 int remaining = *rNum;
00193
00194 do {
00195
00196 bool one_fixed = false;
00197
00198 for (int i=0; i<nOrigVars_; i++)
00199
00200 if ((Var (i) -> Multiplicity () > 0) &&
00201 (integerRank_ [i] == rank) &&
00202 (fixed [i] == UNFIXED) &&
00203 Var (i) -> isInteger ()) {
00204
00205 if (CoinCpuTime () > maxCpuTime_)
00206 break;
00207
00208
00209
00210 if (ceil (Lb (i) - COUENNE_EPS) + COUENNE_EPS >= floor (Ub (i) + COUENNE_EPS)) {
00211
00212 X (i) = xInt [i] = ceil (Lb (i) - COUENNE_EPS);
00213 fixed [i] = FIXED;
00214 one_fixed = true;
00215 --remaining;
00216 continue;
00217 }
00218
00219
00220 int result = testIntFix (i, xFrac [i], fixed, xInt,
00221 dualL, dualR, olb, oub, ntrials < maxtrials);
00222
00223 jnlst_ -> Printf (J_MOREVECTOR, J_NLPHEURISTIC,
00224 "testing %d [%g -> %g], res = %d\n", i, xFrac [i], xInt [i], result);
00225
00226 if (result > 0) {
00227 one_fixed = true;
00228 --remaining;
00229 } else if (result < 0)
00230 throw infeasible;
00231 }
00232
00233
00234
00235 if (!one_fixed) {
00236
00237 int index = 0;
00238
00239
00240 while ((index < nOrigVars_) &&
00241 (!(Var (index) -> isInteger ()) ||
00242 (integerRank_ [index] != rank) ||
00243 (fixed [index] != UNFIXED)))
00244 index++;
00245
00246 assert (index < nOrigVars_);
00247
00248 jnlst_ -> Printf (J_MOREVECTOR, J_NLPHEURISTIC,
00249 "none fixed, fix %d from %g [%g,%g] [L=%g, R=%g]",
00250 index, xFrac [index], Lb (index), Ub (index),
00251 dualL [index], dualR [index]);
00252
00253 Lb (index) = Ub (index) = X (index) = xInt [index] =
00254 ((dualL [index] < dualR [index] - COUENNE_EPS) ? floor (xFrac [index]) :
00255 (dualL [index] > dualR [index] + COUENNE_EPS) ? ceil (xFrac [index]) :
00256 ((CoinDrand48 () > xFrac [index] - floor (xFrac [index])) ?
00257 floor (xFrac [index]) : ceil (xFrac [index])));
00258
00259 jnlst_ -> Printf (J_MOREVECTOR, J_NLPHEURISTIC, " to %g\n", xInt [index]);
00260
00261 fixed [index] = FIXED;
00262
00263 --remaining;
00264 }
00265
00266 ntrials++;
00267
00268 if (jnlst_ -> ProduceOutput (Ipopt::J_MOREVECTOR, J_NLPHEURISTIC)) {
00269 printf ("--- remaining = %d --------------------------- \n", remaining);
00270 for (int i=0; i<nOrigVars_; i++)
00271 if (variables_ [i] -> Multiplicity () > 0)
00272 printf ("#### %4d: %d %c %2d frac %20g -> int %20g [%20g,%20g]\n",
00273 i, fixed [i],
00274 variables_ [i] -> isInteger () ? 'I' : ' ',
00275 integerRank_ ? integerRank_ [i] : -1,
00276 xFrac [i], xInt [i], Lb (i), Ub (i));
00277 printf ("---------------------------\n");
00278
00279 }
00280 } while (remaining > 0);
00281 }
00282
00283
00284 for (int i = nOrigVars_; i--;)
00285 if (Var (i) -> Multiplicity () > 0) {
00286
00287 if (fixed [i] == FIXED)
00288 lb [i] = ub [i] = X (i) = xInt [i];
00289
00290 else if (Lb (i) > Ub (i))
00291 xInt [i] = X (i) = lb [i] = ub [i] =
00292 (fixed [i] == CONTINUOUS) ?
00293 (0.5 * (Lb (i) + Ub (i))) :
00294 COUENNE_round (0.5 * (Lb (i) + Ub (i)));
00295
00296 else {
00297 lb [i] = Lb (i);
00298 ub [i] = Ub (i);
00299 if (xInt [i] < lb [i]) X (i) = xInt [i] = lb [i];
00300 else if (xInt [i] > ub [i]) X (i) = xInt [i] = ub [i];
00301 }
00302 }
00303
00304 restoreUnusedOriginals (xInt);
00305
00306
00307
00308 initAuxs ();
00309 int objind = Obj (0) -> Body () -> Index ();
00310
00311 if (X (objind) < getCutOff ()) {
00312
00313 const CouNumber *x = X ();
00314 CouNumber xp = x [objind];
00315
00316 if (checkNLP (x, xp, true)) {
00317 setCutOff (xp);
00318 jnlst_ -> Printf (J_DETAILED, J_NLPHEURISTIC,
00319 "new cutoff from getIntCand: %g\n", xp);
00320 }
00321 }
00322 }
00323
00324 catch (int i) {
00325
00326 if (i == infeasible)
00327 retval = -1;
00328 }
00329
00331
00332 if (jnlst_->ProduceOutput(Ipopt::J_MOREVECTOR, J_NLPHEURISTIC)) {
00333 if (retval >= 0) {
00334 printf ("- Done: retval %d ----------------------------------------------------------------\n",
00335 retval);
00336 for (int i=0; i<nOrigVars_; i++)
00337 if (variables_ [i] -> Multiplicity () > 0)
00338 printf ("#### %4d: %d %c frac %20g -> int %20g [%20g,%20g]\n",
00339 i, fixed [i], variables_ [i] -> isInteger () ? 'I' : ' ',
00340 xFrac [i], xInt [i], lb [i], ub [i]);
00341 } else printf ("no good point was found\n");
00342 }
00343
00344 delete [] fixed;
00345
00346 delete [] olb; delete [] oub;
00347 delete [] dualL; delete [] dualR;
00348
00349 domain_.pop ();
00350
00351 jnlst_ -> Printf (J_MOREVECTOR, J_NLPHEURISTIC, "Done with GetIntegerCandidate\n");
00352
00353 optimum_ = store_optimum;
00354
00355 return retval;
00356 }