00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014 #undef HEUR_SOL
00015
00016 #include <vector>
00017
00018 #include "OS_lp.hpp"
00019 #include "OS_cut.hpp"
00020 #include "OS_var.hpp"
00021 #include "OsiClpSolverInterface.hpp"
00022 #include "CglSimpleRounding.hpp"
00023 #include "CglKnapsackCover.hpp"
00024
00025 #include "BCP_math.hpp"
00026 #include "BCP_lp.hpp"
00027 #include "BCP_problem_core.hpp"
00028 #include "BCP_lp_param.hpp"
00029
00030 using namespace std;
00031
00032
00033 void
00034 OS_lp::unpack_module_data(BCP_buffer& buf)
00035 {
00036 buf.unpack( os_prob);
00037 EPS = os_prob->EPSILON;
00044
00045
00046 std::cout << "number of variables " << os_prob->osinstance->getVariableNumber() << std::endl;
00047
00048
00049
00050 }
00051
00052
00053
00054
00055 OsiSolverInterface * OS_lp::initialize_solver_interface(){
00056
00057 OsiClpSolverInterface * clp = new OsiClpSolverInterface;
00058 clp->messageHandler()->setLogLevel(0);
00059 return clp;
00060 }
00061
00062
00063 void OS_lp::initialize_new_search_tree_node(const BCP_vec<BCP_var*>& vars,
00064 const BCP_vec<BCP_cut*>& cuts,
00065 const BCP_vec<BCP_obj_status>& vstatus,
00066 const BCP_vec<BCP_obj_status>& cstatus,
00067 BCP_vec<int>& var_changed_pos,
00068 BCP_vec<double>& var_new_bd,
00069 BCP_vec<int>& cut_changed_pos,
00070 BCP_vec<double>& cut_new_bd)
00071
00072
00073
00074
00075 {
00076 in_strong = 0;
00077
00078
00079
00080 bool relSol = BCP_lp_user::get_param(BCP_lp_par::LpVerb_RelaxedSolution) ;
00081 std::cout << relSol << std::endl;
00082
00083
00084 if(relSol == true){
00085 BCP_lp_user::set_param( BCP_lp_par::LpVerb_RelaxedSolution, false);
00086 }else{
00087 BCP_lp_user::set_param( BCP_lp_par::LpVerb_RelaxedSolution, true);
00088 }
00089
00090
00091 relSol = BCP_lp_user::get_param(BCP_lp_par::LpVerb_RelaxedSolution) ;
00092 std::cout << relSol << std::endl;
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103 #ifdef USER_DATA
00104 MY_user_data *curr_ud = dynamic_cast<MY_user_data*> (get_user_data());
00105 curr_ud->is_processed = 1;
00106 #endif
00107
00108 }
00109
00110
00111 void OS_lp::modify_lp_parameters(OsiSolverInterface* lp, bool in_strong_branching){
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136
00137
00138
00139
00140 }
00141
00142
00143
00144
00145 BCP_solution* OS_lp::generate_heuristic_solution(const BCP_lp_result& lpres,
00146 const BCP_vec<BCP_var*>& vars,
00147 const BCP_vec<BCP_cut*>& cuts) {
00148
00149 return NULL;
00150 }
00151
00152
00153
00154 BCP_branching_decision OS_lp::select_branching_candidates(const BCP_lp_result& lpres,
00155 const BCP_vec<BCP_var*>& vars,
00156 const BCP_vec<BCP_cut*>& cuts,
00157 const BCP_lp_var_pool& local_var_pool,
00158 const BCP_lp_cut_pool& local_cut_pool,
00159 BCP_vec<BCP_lp_branching_object*>& cands,
00160 bool force_branch) {
00161
00162
00163
00164
00165
00166
00167
00168
00169
00170 std::cout << "INSIDE BRANCHING DECISION: TESTING VARIABLE TYPES " << std::endl;
00171 std::cout << "SIZE OF VARS = " << vars.size() << std::endl;
00172 std::cout << "SIZE OF LOCAL VAR POOL = " << local_var_pool.size() << std::endl;
00173 std::cout << "CANDS SIZE = " << cands.size() << std::endl;
00174
00175
00176 const double intTol = BCP_lp_user::get_param(BCP_lp_par::IntegerTolerance) ;
00177
00178 int num_vars = vars.size();
00179
00180
00181
00182
00183
00184
00185
00186
00187
00188
00189
00190
00191
00192
00193 if( local_cut_pool.size() > 0 ) {
00194
00195 cout << "select_branching_candidates() returns BCP_DoNotBranch" << endl;
00196
00197 return(BCP_DoNotBranch);
00198 }
00199 else {
00200
00201 int i;
00202 const double *x = lpres.x();
00203 BCP_vec<int> select_pos;
00204
00205 for(i = 0; i < num_vars; i++) {
00206
00207
00208
00209
00210
00211
00212 if( vars[ i]->var_type() < 2) {
00213 if((x[i] -floor( x[i]) > intTol) && (ceil( x[i]) - x[i] > intTol)) {
00214 select_pos.push_back(i);
00215
00216
00217
00218 append_branching_vars( lpres.x(), vars, select_pos, cands);
00219
00220 cout << "Branching on variable: " << i << " (" << x[i] << ") depth: " << current_level() << endl;
00221 break;
00222 }
00223 }
00224 }
00225
00226 if (cands.size() == 0 && local_var_pool.size() == 0) {
00227 throw BCP_fatal_error("select_banching_candidate() : No cut in pool but couldn't select branching variable.\n");
00228
00229 }
00230
00231 if (cands.size() == 0 && local_var_pool.size() > 0) {
00232
00233 return BCP_DoNotBranch;
00234 }
00235
00236 cout << "select_branching_candidates() returns BCP_DoBranch" << endl;
00237
00238 return BCP_DoBranch;
00239 }
00240
00241 }
00242
00243
00244
00245 void OS_lp::set_user_data_for_children(BCP_presolved_lp_brobj* best,
00246 const int selected)
00247
00248
00249
00250
00251
00252 {
00253 #ifdef USER_DATA
00254 BCP_lp_branching_object *cand = best->candidate();
00255 MY_user_data *curr_ud = dynamic_cast<MY_user_data*> (get_user_data());
00256 real_user_data *curr_rud = curr_ud->p_rud;
00257
00258 for(int i=0; i<cand->child_num; i++) {
00259 MY_user_data *ud = new MY_user_data(curr_rud->max_card_set_zero);
00260 real_user_data *rud = ud->p_rud;
00261
00262 rud->card_set_zero = curr_rud->card_set_zero;
00263
00264 for(int j=0; j<curr_rud->card_set_zero; j++) {
00265 rud->set_zero[j] = curr_rud->set_zero[j];
00266 }
00267
00268 int ind_br = (*(cand->forced_var_pos))[0];
00269
00270 if((*(cand->forced_var_bd))[2*i + 1] < EPS) {
00271 rud->set_zero[curr_rud->card_set_zero] = ind_br;
00272 (rud->card_set_zero)++;
00273 }
00274 best->user_data()[i] = ud;
00275 }
00276 #endif
00277 }
00278
00279
00280
00281
00282
00283
00284
00285
00286 void OS_lp::cuts_to_rows(const BCP_vec<BCP_var*>& vars,
00287 BCP_vec<BCP_cut*>& cuts,
00288 BCP_vec<BCP_row*>& rows,
00289
00290 const BCP_lp_result& lpres,
00291 BCP_object_origin origin, bool allow_multiple) {
00292
00293
00294
00295
00296 std::cout << "Execute cuts_to_rows" << std::endl;
00297 const int cutnum = cuts.size();
00298 for (int i=0; i<cutnum; ++i) {
00299 const OsiRowCut* bcut = dynamic_cast<const OS_cut*>(cuts[i]);
00300 if (bcut) {
00301
00302 rows.push_back(new BCP_row(bcut->row(), bcut->lb(), bcut->ub()));
00303 continue;
00304 }
00305 throw BCP_fatal_error("Unknown cut type in cuts_to_rows.\n");
00306 }
00307 }
00308
00309
00310
00311 void OS_lp::vars_to_cols(const BCP_vec<BCP_cut*>& cuts,
00312 BCP_vec<BCP_var*>& vars,
00313 BCP_vec<BCP_col*>& cols,
00314 const BCP_lp_result& lpres,
00315 BCP_object_origin origin, bool allow_multiple)
00316 {
00317
00318 std::cout << "EXECUTE vars_to_cols **************" << std::endl;
00319 static const CoinPackedVector emptyVector(false);
00320 const int numvars = vars.size();
00321 int i;
00322 for (i = 0; i < numvars; ++i) {
00323 const OS_var* v = dynamic_cast<const OS_var*>(vars[i]);
00324
00325
00326
00327
00328 BCP_col* col = new BCP_col(v->coinPackedVec, v->weight, 0.0, 1.0);
00329
00330
00331 cols.push_back( col);
00332
00333
00334 }
00335 }
00336
00337
00338
00339 void OS_lp::process_lp_result(const BCP_lp_result& lpres,
00340 const BCP_vec<BCP_var*>& vars,
00341 const BCP_vec<BCP_cut*>& cuts,
00342 const double old_lower_bound,
00343 double& true_lower_bound,
00344 BCP_solution*& sol,
00345 BCP_vec<BCP_cut*>& new_cuts,
00346 BCP_vec<BCP_row*>& new_rows,
00347 BCP_vec<BCP_var*>& new_vars,
00348 BCP_vec<BCP_col*>& new_cols){
00349
00350
00351 generated_cuts = false;
00352 generated_vars = false;
00353
00354
00355 #if 1
00356
00357 {
00358
00359 OsiClpSolverInterface* my_lp_solver;
00360
00361 my_lp_solver = dynamic_cast<OsiClpSolverInterface *>(getLpProblemPointer()->lp_solver);
00362
00363
00364
00365
00366 CglKnapsackCover knapCover;
00367
00368
00369 OsiSolverInterface::ApplyCutsReturnCode acRc;
00370 OsiCuts my_cuts;
00371
00372
00373 double epsilon = .1;
00374 int i, k;
00375
00376
00377
00378 knapCover.generateCuts(*my_lp_solver, my_cuts);
00379 const double *x = lpres.x();
00380
00381 CoinPackedVector pv;
00382 int *pvIndexes = NULL;
00383 double *pvElements = NULL;
00384 int numElem;
00385 double lhs = 0;
00386 OS_cut* cut;
00387 int ncuts = my_cuts.sizeRowCuts();
00388 const OsiRowCut **newRowCuts = new const OsiRowCut * [ncuts];
00389 std::cout << "sizeRowCuts() = " << ncuts << std::endl;
00390 for(i = 0; i < ncuts; i++) {
00391 newRowCuts[i] = &my_cuts.rowCut(i);
00392 cut = new OS_cut( *newRowCuts[i]);
00393
00394
00395 cout <<" sense = " << newRowCuts[i]->sense() << endl;
00396 pv = newRowCuts[i]->row();
00397 pvIndexes = pv.getIndices();
00398 pvElements = pv.getElements();
00399 numElem = pv.getNumElements();
00400
00401 lhs = 0;
00402 for(k = 0; k < numElem; k++){
00403 lhs += pvElements[ k]*x[ pvIndexes[k] ];
00404
00405 }
00406
00407 if( (newRowCuts[i]->sense() == 'L') && (lhs > newRowCuts[i]->rhs() +epsilon ) ){
00408 cout <<" lhs - rhs = " << lhs - newRowCuts[i]->rhs() << endl;
00409 std::cout << "PUSHING BACK KNAPSACK COVER ROUNDING CUT" << std::endl;
00410 algo_cuts.push_back( cut);
00411 }
00412 }
00413
00414 generated_cuts = (algo_cuts.size() > 0);
00415 for(i = 0; i < ncuts; i++){
00416
00417 }
00418 delete[] newRowCuts;
00419 }
00420
00421 #endif
00422
00423 #if 0
00424
00425 {
00426 int i;
00427 int num_vars = vars.size();
00428 const double *x = lpres.x();
00429 OsiRowCut* rcut = new OsiRowCut();
00430
00431 int *cutind = new int[ num_vars];
00432
00433 int cut_nz;
00434
00435
00436 double cutrhs = 503.77;
00437
00438
00439 double *cutcoef = new double[ num_vars];
00440 double lhs = 0;
00441 for(i=0; i < num_vars; i++) {
00442 cutcoef[ i] = 1;
00443 cutind[ i] = i;
00444 cut_nz = num_vars;
00445 lhs += x[ i];
00446 }
00447 std::cout << "The LHS IS EQUAL TO === " << lhs << std::endl;
00448
00449
00450 if(lhs > cutrhs + EPS) {
00451
00452
00453 rcut->setLb(-BCP_DBL_MAX);
00454 rcut->setUb( cutrhs);
00455 rcut->setRow( cut_nz, cutind, cutcoef);
00456 OS_cut* cut = new OS_cut( *rcut);
00457 algo_cuts.push_back( cut);
00458 std::cout << "WE ARE ADDING A CUT!!!!!!!! " << std::endl;
00459 }
00460 delete rcut;
00461 delete[] cutind;
00462 delete[] cutcoef;
00463 generated_cuts = (algo_cuts.size() > 0);
00464 }
00465
00466 #endif
00467
00468 #if 0
00469 {
00470 const double* pi = lpres.pi();
00471 int numNonz = 4;
00472 int varIdx = vars.size();
00473 int* ind = new int[ numNonz];
00474 double* val = new double[ numNonz];
00475 double objVal = -13.0;
00476 double reducedCost = 0.0;
00477 int i;
00478
00479 ind[ 0] = 0;
00480 ind[ 1] = 1;
00481 ind[ 2] = 2;
00482 ind[ 3] = 3;
00483
00484 val[ 0] = 1.0;
00485 val[ 1] = 1.0;
00486 val[ 2] = 1.0;
00487 val[ 3] = 1.0;
00488
00489 for(i = 0 ; i < numNonz; i++){
00490 reducedCost += -pi[ i]*val[ i];
00491 }
00492 reducedCost += objVal;
00493 std::cout << "REDUCED COST = ************** " << reducedCost << std::endl;
00494
00495 if(reducedCost < -.01 && vars.size() < 3) {
00496 std::cout << "CALL OS_var CONSTRUCTOR " << std::endl;
00497 algo_vars.push_back(new OS_var(varIdx, CoinPackedVector(numNonz, ind, val, true), objVal));
00498 std::cout << "DONE WITH CALL OS_var CONSTRUCTOR " << std::endl;
00499 }
00500
00501 delete[] val;
00502 delete[] ind;
00503
00504
00505 generated_vars = (algo_vars.size() > 0);
00506 }
00507
00508 #endif
00509
00510
00511
00512
00513
00514
00515 if( (generated_vars == false) && (generated_cuts == false) ){
00516 BCP_lp_user::process_lp_result(lpres, vars, cuts,
00517 old_lower_bound, true_lower_bound, sol, new_cuts,
00518 new_rows, new_vars, new_cols);
00519 return;
00520 }
00521
00522 int i;
00523
00524
00525 if (generated_cuts) {
00526 new_cuts.append( algo_cuts);
00527
00528
00529
00530 int cutnum = algo_cuts.size();
00531
00532 for (i = 0; i < cutnum; ++i) {
00533
00534
00535 const OsiRowCut* bcut = dynamic_cast<const OS_cut*>(algo_cuts[i]);
00536
00537 if (bcut) {
00538 new_rows.push_back(new BCP_row(bcut->row(), bcut->lb(), bcut->ub()));
00539
00540 }
00541 else{
00542 throw BCP_fatal_error("Unknown cut type in cuts_to_rows.\n");
00543 }
00544 }
00545
00546
00547
00548 algo_cuts.clear();
00549 }
00550
00551
00552
00553
00554 if (generated_vars) {
00555 new_vars.append( algo_vars);
00556
00557
00558
00559
00560
00561 static const CoinPackedVector emptyVector(false);
00562 const int numvars = algo_vars.size();
00563 for (i = 0; i < numvars; ++i) {
00564 const OS_var* v = dynamic_cast<const OS_var*>(algo_vars[i]);
00565
00566
00567
00568
00569 BCP_col* col = new BCP_col(v->coinPackedVec, v->weight, 0.0, 1.0);
00570
00571
00572 new_cols.push_back( col);
00573
00574
00575 }
00576
00577
00578 algo_vars.clear();
00579
00580 std::cout << "GENERATED VARS IS TRUE ************** " << std::endl;
00581 true_lower_bound = old_lower_bound;
00582 } else {
00583 std::cout << "GENERATED VARS IS FALSE ************** " << std::endl;
00584 true_lower_bound = lpres.objval();
00585 }
00586 std::cout << "TRUE LOWER BOUND ************** " << true_lower_bound << std::endl;
00587 }
00588
00589
00590
00591
00592
00593
00594 void OS_lp::display_lp_solution(const BCP_lp_result& lpres,
00595 const BCP_vec<BCP_var*>& vars,
00596 const BCP_vec<BCP_cut*>& cuts,
00597 const bool final_lp_solution){
00598
00599
00600 BCP_lp_user::display_lp_solution( lpres, vars, cuts,
00601 final_lp_solution);
00602 return;
00603
00604 bool relSol = false;
00605 unsigned int i;
00606 double ietol;
00607 ietol = BCP_lp_user::get_param(BCP_lp_par::IntegerTolerance) ;
00608 relSol = BCP_lp_user::get_param(BCP_lp_par::LpVerb_RelaxedSolution) ;
00609
00610 const double *x = lpres.x();
00611 if( relSol == true){
00612 for (i = 0; i < vars.size(); ++i) {
00613 if(x[ i] > ietol) std::cout << x[ i] << std::endl;
00614 }
00615 }
00616
00617
00618
00619 }
00620
00621
00622