00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #include <vector>
00014
00015 #include "BB_lp.hpp"
00016 #include "BB_cut.hpp"
00017 #include "OsiClpSolverInterface.hpp"
00018
00019 #include "BCP_math.hpp"
00020 #include "BCP_lp.hpp"
00021 #include "BCP_problem_core.hpp"
00022
00023 using namespace std;
00024
00025
00026 void
00027 BB_lp::unpack_module_data(BCP_buffer& buf)
00028 {
00029 buf.unpack(p_desc);
00030 EPS = p_desc->EPSILON;
00031 }
00032
00033
00034 OsiSolverInterface *
00035 BB_lp::initialize_solver_interface()
00036
00037
00038
00039 {
00040 OsiClpSolverInterface * clp = new OsiClpSolverInterface;
00041 clp->messageHandler()->setLogLevel(0);
00042
00043
00044 clp->getModelPtr()->messageHandler()->setLogLevel(0);
00045
00046
00047 clp->setHintParam(OsiDoDualInResolve, true, OsiHintTry);
00048
00049 return clp;
00050 }
00051
00052
00053 void
00054 BB_lp::initialize_new_search_tree_node(const BCP_vec<BCP_var*>& vars,
00055 const BCP_vec<BCP_cut*>& cuts,
00056 const BCP_vec<BCP_obj_status>& vstatus,
00057 const BCP_vec<BCP_obj_status>& cstatus,
00058 BCP_vec<int>& var_changed_pos,
00059 BCP_vec<double>& var_new_bd,
00060 BCP_vec<int>& cut_changed_pos,
00061 BCP_vec<double>& cut_new_bd)
00062
00063
00064
00065
00066 {
00067 in_strong = 0;
00068
00069 #ifdef USER_DATA
00070 MY_user_data *curr_ud = dynamic_cast<MY_user_data*> (get_user_data());
00071 curr_ud->is_processed = 1;
00072 #endif
00073
00074 }
00075
00076
00077 void
00078 BB_lp::modify_lp_parameters(OsiSolverInterface* lp, const int changeType,
00079 bool in_strong_branching)
00080
00081
00082
00083 {
00084 if (in_strong_branching) {
00085 in_strong = 1;
00086 lp->setIntParam(OsiMaxNumIterationHotStart, 50);
00087 }
00088
00089
00090 lp->writeLp("lpnode", "lp");
00091 cout << "LP node written in file lpnode.lp" << endl;
00092
00093
00094
00095
00096
00097 }
00098
00099
00100 BCP_solution*
00101 BB_lp::test_feasibility(const BCP_lp_result& lp_result,
00102 const BCP_vec<BCP_var*>& vars,
00103 const BCP_vec<BCP_cut*>& cuts)
00104
00105
00106
00107
00108
00109 {
00110
00111
00112 if (in_strong) {
00113 return(0);
00114 }
00115
00116
00117
00118
00119 if(getLpProblemPointer()->lp_solver->isAbandoned() ||
00120 getLpProblemPointer()->lp_solver->isProvenPrimalInfeasible() ||
00121 getLpProblemPointer()->lp_solver->isDualObjectiveLimitReached() ||
00122 getLpProblemPointer()->lp_solver->isIterationLimitReached()) {
00123 return(0);
00124 }
00125
00126 int i, j, k, cn = p_desc->colnum;;
00127 const double *x = lp_result.x();
00128 double *check_lhs = new double[p_desc->indexed->getNumRows()];
00129
00130
00131
00132 violated_cuts.clear();
00133 p_desc->indexed->times(lp_result.x(), check_lhs);
00134 for (i=0; i<p_desc->indexed->getNumRows(); ++i) {
00135 if ((check_lhs[i] < p_desc->rlb_indexed[i] - EPS) ||
00136 (check_lhs[i] > p_desc->rub_indexed[i] + EPS))
00137 violated_cuts.push_back(i);
00138 }
00139
00140 delete[] check_lhs;
00141
00142 OsiRowCut* rcut = new OsiRowCut();
00143 int *cutind = new int[cn], cut_nz;
00144 double* cutcoef = new double[cn], cutrhs = 1;
00145
00146
00147
00148 for(i=0; i<cn; i++) {
00149 j = (i+1) % cn;
00150 k = (i+2) % cn;
00151
00152 cutcoef[0] = 1;
00153 cutcoef[1] = 1;
00154 cutcoef[2] = 1;
00155 cut_nz = 3;
00156
00157 if(x[i] + x[j] + x[k] > 1 + EPS) {
00158
00159
00160
00161 cutind[0] = i;
00162 cutind[1] = j;
00163 cutind[2] = k;
00164
00165 rcut->setLb(-BCP_DBL_MAX);
00166 rcut->setUb(cutrhs);
00167 rcut->setRow(cut_nz, cutind, cutcoef);
00168
00169 BB_cut* cut = new BB_cut(*rcut);
00170 algo_cuts.push_back(cut);
00171
00172 }
00173 }
00174
00175 delete rcut;
00176 delete[] cutind;
00177 delete[] cutcoef;
00178
00179
00180
00181 return (violated_cuts.empty() + algo_cuts.empty() == 2 ?
00182 BCP_lp_user::test_feasibility(lp_result, vars, cuts) : 0);
00183 }
00184
00185
00186 void
00187 BB_lp::logical_fixing(const BCP_lp_result& lpres,
00188 const BCP_vec<BCP_var*>& vars,
00189 const BCP_vec<BCP_cut*>& cuts,
00190 const BCP_vec<BCP_obj_status>& var_status,
00191 const BCP_vec<BCP_obj_status>& cut_status,
00192 const int var_bound_changes_since_logical_fixing,
00193 BCP_vec<int>& changed_pos, BCP_vec<double>& new_bd)
00194
00195
00196
00197 {
00198 }
00199
00200
00201 void
00202 BB_lp::generate_cuts_in_lp(const BCP_lp_result& lpres,
00203 const BCP_vec<BCP_var*>& vars,
00204 const BCP_vec<BCP_cut*>& cuts,
00205 BCP_vec<BCP_cut*>& new_cuts,
00206 BCP_vec<BCP_row*>& new_rows)
00207
00208
00209
00210
00211
00212 {
00213 int i;
00214
00215 for (i=violated_cuts.size()-1; i>=0; --i) {
00216 const int ind = violated_cuts[i];
00217 new_cuts.push_back(new BB_indexed_cut(ind, p_desc->rlb_indexed[ind],
00218 p_desc->rub_indexed[ind]));
00219 }
00220 cout << "generate_cuts_in_lp(): found " << new_cuts.size()
00221 << " indexed cuts" << endl;
00222
00223 for(i=algo_cuts.size()-1; i>=0; --i) {
00224 new_cuts.push_back(algo_cuts[i]);
00225 }
00226 cout << "generate_cuts_in_lp(): found " << algo_cuts.size()
00227 << " algorithmic cuts" << endl;
00228
00229 algo_cuts.clear();
00230 }
00231
00232
00233 BCP_solution*
00234 BB_lp::generate_heuristic_solution(const BCP_lp_result& lpres,
00235 const BCP_vec<BCP_var*>& vars,
00236 const BCP_vec<BCP_cut*>& cuts)
00237 {
00238 #ifdef HEUR_SOL
00239
00240
00241
00242 int i, j, k, cn = p_desc->colnum;
00243 const double *x = lpres.x();
00244 double *rounded_x = new double[cn];
00245
00246 for(i=0; i<cn; i++) {
00247 if(x[i] > 0.5 + EPS) {
00248 rounded_x[i] = 1;
00249 }
00250 else {
00251 rounded_x[i] = 0;
00252 }
00253 }
00254
00255
00256
00257 int nb_rows_core = p_desc->core->getNumRows();
00258 int nb_rows_indexed = p_desc->indexed->getNumRows();
00259 int max_core_indexed;
00260
00261 if(nb_rows_indexed > nb_rows_core) {
00262 max_core_indexed = nb_rows_indexed;
00263 }
00264 else {
00265 max_core_indexed = nb_rows_core;
00266 }
00267
00268 double *check_lhs = new double[max_core_indexed];
00269
00270
00271
00272 p_desc->core->times(rounded_x, check_lhs);
00273
00274 for (i=0; i<nb_rows_core; ++i) {
00275 if ((check_lhs[i] < p_desc->rlb_core[i] - EPS) ||
00276 (check_lhs[i] > p_desc->rub_core[i] + EPS)) {
00277
00278 delete[] check_lhs;
00279 delete[] rounded_x;
00280 cout << "generate_heuristic_solution() returns nothing.\n"
00281 << endl;
00282 return(0);
00283 }
00284 }
00285
00286
00287
00288 p_desc->indexed->times(rounded_x, check_lhs);
00289 for (i=0; i<nb_rows_indexed; ++i) {
00290 if ((check_lhs[i] < p_desc->rlb_indexed[i] - EPS) ||
00291 (check_lhs[i] > p_desc->rub_indexed[i] + EPS)) {
00292
00293 delete[] check_lhs;
00294 delete[] rounded_x;
00295 cout << "generate_heuristic_solution() returns nothing.\n"
00296 << endl;
00297 return(0);
00298 }
00299 }
00300
00301 delete[] check_lhs;
00302
00303
00304
00305 for(i=0; i<cn; i++) {
00306 j = (i+1) % cn;
00307 k = (i+2) % cn;
00308
00309 if(x[i] + x[j] + x[k] > 1 + EPS) {
00310
00311 delete[] rounded_x;
00312 cout << "generate_heuristic_solution() returns nothing.\n"
00313 << endl;
00314 return(0);
00315 }
00316 }
00317
00318
00319
00320 BCP_solution_generic *heur_sol = new BCP_solution_generic();
00321 heur_sol->_delete_vars = false;
00322
00323
00324 BCP_vec<BCP_var_core *> core_vars = getLpProblemPointer()->core->vars;
00325 int ind;
00326
00327 for(i=0; i<cn; i++) {
00328 ind = core_vars[i]->bcpind();
00329 if(rounded_x[ind] > EPS) {
00330 heur_sol->add_entry(core_vars[i], rounded_x[ind]);
00331 }
00332 }
00333
00334 delete[] rounded_x;
00335 cout << "generate_heuristic_solution() returns a solution.\n"
00336 << endl;
00337 return(heur_sol);
00338
00339 #else
00340
00341
00342
00343 return(0);
00344 #endif
00345 }
00346
00347
00348 void
00349 BB_lp::cuts_to_rows(const BCP_vec<BCP_var*>& vars,
00350 BCP_vec<BCP_cut*>& cuts,
00351 BCP_vec<BCP_row*>& rows,
00352
00353 const BCP_lp_result& lpres,
00354 BCP_object_origin origin, bool allow_multiple)
00355
00356
00357
00358
00359
00360 {
00361 const int cutnum = cuts.size();
00362 for (int i=0; i<cutnum; ++i) {
00363 const BB_indexed_cut *icut =
00364 dynamic_cast<const BB_indexed_cut*>(cuts[i]);
00365 if (icut) {
00366 const int ind = icut->index();
00367 rows.push_back(new BCP_row(p_desc->indexed->getVector(ind),
00368 p_desc->rlb_indexed[ind],
00369 p_desc->rub_indexed[ind]));
00370 continue;
00371 }
00372
00373 const OsiRowCut* bcut = dynamic_cast<const BB_cut*>(cuts[i]);
00374 if (bcut) {
00375 rows.push_back(new BCP_row(bcut->row(), bcut->lb(), bcut->ub()));
00376 continue;
00377 }
00378
00379 throw BCP_fatal_error("Unknown cut type in cuts_to_rows.\n");
00380 }
00381 }
00382
00383
00384 BCP_branching_decision
00385 BB_lp::select_branching_candidates(const BCP_lp_result& lpres,
00386 const BCP_vec<BCP_var*>& vars,
00387 const BCP_vec<BCP_cut*>& cuts,
00388 const BCP_lp_var_pool& local_var_pool,
00389 const BCP_lp_cut_pool& local_cut_pool,
00390 BCP_vec<BCP_lp_branching_object*>& cands,
00391 bool force_branch)
00392 {
00393 #ifdef CUSTOM_BRANCH
00394
00395
00396
00397
00398
00399
00400
00401
00402
00403
00404
00405
00406
00407 if(local_cut_pool.size() > 0) {
00408
00409 cout << "select_branching_candidates() returns BCP_DoNotBranch"
00410 << endl;
00411
00412 return(BCP_DoNotBranch);
00413 }
00414 else {
00415
00416
00417
00418 int i;
00419 const double *x = lpres.x();
00420 BCP_vec<int> select_pos;
00421
00422 for(i=0; i<p_desc->colnum; i++) {
00423
00424 if((x[i] > EPS) && (x[i] < 1-EPS)) {
00425 select_pos.push_back(i);
00426
00427
00428
00429 append_branching_vars(lpres.x(), vars, select_pos, cands);
00430
00431 cout << "Branching on variable: " << i << " (" << x[i]
00432 << ") depth: " << current_level() << endl;
00433 break;
00434 }
00435 }
00436
00437 if (cands.size() == 0) {
00438 throw BCP_fatal_error("select_banching_candidate() : No cut in pool but couldn't select branching variable.\n");
00439 }
00440
00441
00442 cout << "select_branching_candidates() returns BCP_DoBranch" << endl;
00443
00444 return BCP_DoBranch;
00445 }
00446
00447 #else
00448 return(BCP_lp_user::select_branching_candidates(lpres, vars, cuts,
00449 local_var_pool,
00450 local_cut_pool, cands,
00451 force_branch));
00452 #endif
00453 }
00454
00455
00456 void
00457 BB_lp::set_user_data_for_children(BCP_presolved_lp_brobj* best,
00458 const int selected)
00459
00460
00461
00462
00463
00464 {
00465 #ifdef USER_DATA
00466 BCP_lp_branching_object *cand = best->candidate();
00467 MY_user_data *curr_ud = dynamic_cast<MY_user_data*> (get_user_data());
00468 real_user_data *curr_rud = curr_ud->p_rud;
00469
00470 for(int i=0; i<cand->child_num; i++) {
00471 MY_user_data *ud = new MY_user_data(curr_rud->max_card_set_zero);
00472 real_user_data *rud = ud->p_rud;
00473
00474 rud->card_set_zero = curr_rud->card_set_zero;
00475
00476 for(int j=0; j<curr_rud->card_set_zero; j++) {
00477 rud->set_zero[j] = curr_rud->set_zero[j];
00478 }
00479
00480 int ind_br = (*(cand->forced_var_pos))[0];
00481
00482 if((*(cand->forced_var_bd))[2*i + 1] < EPS) {
00483 rud->set_zero[curr_rud->card_set_zero] = ind_br;
00484 (rud->card_set_zero)++;
00485 }
00486 best->user_data()[i] = ud;
00487 }
00488 #endif
00489 }
00490
00491
00492
00493
00494