00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #include<iomanip>
00014
00015 #include <CoinError.hpp>
00016 #include <CoinHelperFunctions.hpp>
00017 #include <CoinFileIO.hpp>
00018 #include <OsiClpSolverInterface.hpp>
00019
00020 #include "BB_init.hpp"
00021 #include "BCP_tm.hpp"
00022 #include "BB_tm.hpp"
00023 #include "BB_cut.hpp"
00024 #include "BB_user_data.hpp"
00025
00026 #include "BCP_math.hpp"
00027
00028 using namespace std;
00029
00030
00031
00032 int main(int argc, char* argv[])
00033 {
00034 WindowsErrorPopupBlocker();
00035 BB_init bb_init;
00036 return bcp_main(argc, argv, &bb_init);
00037 }
00038
00039
00040 void
00041 BB_tm::readInput(const char* filename)
00042
00043
00044
00045 {
00046 int i;
00047
00048
00049
00050
00051
00052
00053 bool found_file = false;
00054 CoinFileInput* fi = NULL;
00055
00056 OsiClpSolverInterface solver;
00057
00058 if (!found_file) {
00059
00060 try {
00061 found_file = true;
00062 fi = CoinFileInput::create("bac.lp");
00063 }
00064 catch (CoinError& err) {
00065
00066 found_file = false;
00067 }
00068 if (found_file) {
00069 solver.readLp("bac.lp");
00070 printf("Problem read from file bac.lp\n");
00071 }
00072 }
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093 if (found_file) {
00094
00095 const int rownum = solver.getNumRows();
00096 const int colnum = solver.getNumCols();
00097 desc.rownum = rownum;
00098 desc.colnum = colnum;
00099
00100
00101
00102 desc.integer = new bool[colnum];
00103 for (i = 0; i < colnum; ++i) {
00104 desc.integer[i] = solver.isInteger(i);
00105 }
00106
00107
00108
00109 desc.clb = new double[colnum];
00110 CoinDisjointCopyN(solver.getColLower(), colnum, desc.clb);
00111
00112 desc.cub = new double[colnum];
00113 CoinDisjointCopyN(solver.getColUpper(), colnum, desc.cub);
00114
00115 desc.obj = new double[colnum];
00116 CoinDisjointCopyN(solver.getObjCoefficients(), colnum, desc.obj);
00117
00118 const CoinPackedMatrix* byRow = solver.getMatrixByRow();
00119
00120 int core_size = 10;
00121 int *core_ind = new int[core_size];
00122 desc.rlb_core = new double[core_size];
00123 desc.rub_core = new double[core_size];
00124
00125 int indexed_size = 6;
00126 int *indexed_ind = new int[indexed_size];
00127 desc.rlb_indexed = new double[indexed_size];
00128 desc.rub_indexed = new double[indexed_size];
00129
00130
00131 for (i=0; i<core_size; i++) {
00132 core_ind[i] = i;
00133 }
00134 for (i=core_size; i<rownum; i++) {
00135 indexed_ind[i-core_size] = i;
00136 }
00137
00138 cout << "readInput(): core size: " << core_size << " indexed size: "
00139 << indexed_size << endl;
00140
00141
00142
00143 const double* solver_rlb = solver.getRowLower();
00144 const double* solver_rub = solver.getRowUpper();
00145
00146 for (i=0; i<core_size; ++i) {
00147 desc.rlb_core[i] = solver_rlb[core_ind[i]];
00148 desc.rub_core[i] = solver_rub[core_ind[i]];
00149 }
00150
00151 for (i=0; i<indexed_size; ++i) {
00152 desc.rlb_indexed[i] = solver_rlb[indexed_ind[i]];
00153 desc.rub_indexed[i] = solver_rub[indexed_ind[i]];
00154 }
00155
00156
00157
00158
00159 desc.core = new CoinPackedMatrix(false, 0.0, 0.0);
00160 desc.core->submatrixOf(*byRow, core_size, core_ind);
00161
00162 desc.indexed = new CoinPackedMatrix(false, 0.0, 0.0);
00163 desc.indexed->submatrixOf(*byRow, indexed_size, indexed_ind);
00164
00165 delete[] core_ind;
00166 delete[] indexed_ind;
00167
00168 } else {
00169
00170 printf("Problem created in memory\n");
00171
00172 desc.colnum = 10;
00173 int colnum = desc.colnum;
00174 desc.rownum = 16;
00175
00176 desc.obj = new double[colnum];
00177 desc.clb = new double[colnum];
00178 desc.cub = new double[colnum];
00179 desc.integer = new bool[colnum];
00180
00181 for(i=0; i<colnum; i++) {
00182 desc.obj[i] = -1;
00183 desc.clb[i] = 0;
00184 desc.cub[i] = 1;
00185 desc.integer[i] = true;
00186 }
00187
00188 desc.core = new CoinPackedMatrix(false, 0.0, 0.0);
00189 desc.rlb_core = new double[10];
00190 desc.rub_core = new double[10];
00191
00192 double* cutcoef = new double[colnum];
00193 int *cutind = new int[colnum];
00194 int j, cutnz;
00195
00196
00197
00198 cutcoef[0] = 1;
00199 cutcoef[1] = 1;
00200 cutnz = 2;
00201
00202 for(i=0; i<10; i++) {
00203 desc.rlb_core[i] = 0;
00204 desc.rub_core[i] = 1;
00205 j = (i+1) % colnum;
00206 cutind[0] = i;
00207 cutind[1] = j;
00208 desc.core->appendRow(cutnz, cutind, cutcoef);
00209 }
00210 desc.rlb_core[0] = 1;
00211
00212 desc.indexed = new CoinPackedMatrix(false, 0.0, 0.0);
00213 desc.rlb_indexed = new double[6];
00214 desc.rub_indexed = new double[6];
00215
00216
00217
00218 for(i=0; i<6; i++) {
00219 desc.rlb_indexed[i] = -BCP_DBL_MAX;
00220 desc.rub_indexed[i] = 1;
00221 }
00222
00223 cutcoef[0] = 1;
00224 cutcoef[1] = 1;
00225 cutcoef[2] = 1;
00226 cutnz = 3;
00227
00228 cutind[1] = 1;
00229 cutind[2] = 3;
00230 cutind[0] = 9;
00231 desc.indexed->appendRow(cutnz, cutind, cutcoef);
00232 cutind[0] = 0;
00233 cutind[1] = 2;
00234 cutind[2] = 4;
00235 desc.indexed->appendRow(cutnz, cutind, cutcoef);
00236 cutind[0] = 0;
00237 cutind[1] = 3;
00238 cutind[2] = 7;
00239 desc.indexed->appendRow(cutnz, cutind, cutcoef);
00240 cutind[0] = 1;
00241 cutind[1] = 4;
00242 cutind[2] = 5;
00243 desc.indexed->appendRow(cutnz, cutind, cutcoef);
00244 cutind[0] = 5;
00245 cutind[1] = 6;
00246 cutind[2] = 7;
00247 desc.indexed->appendRow(cutnz, cutind, cutcoef);
00248 cutind[0] = 0;
00249 cutind[1] = 6;
00250 cutind[2] = 8;
00251 desc.indexed->appendRow(cutnz, cutind, cutcoef);
00252
00253 delete[] cutcoef;
00254 delete[] cutind;
00255 }
00256 }
00257
00258
00259 void
00260 BB_tm::pack_module_data(BCP_buffer& buf, BCP_process_t ptype)
00261 {
00262
00263
00264 switch (ptype) {
00265 case BCP_ProcessType_LP:
00266 {
00267
00268
00269 buf.pack(&desc);
00270 }
00271 break;
00272 default:
00273 abort();
00274 }
00275 }
00276
00277
00278 void
00279 BB_tm::initialize_core(BCP_vec<BCP_var_core*>& vars,
00280 BCP_vec<BCP_cut_core*>& cuts,
00281 BCP_lp_relax*& matrix)
00282
00283
00284
00285 {
00286 int i;
00287
00288 for (i=0; i<desc.colnum; ++i) {
00289 if (desc.integer[i]) {
00290 if (desc.clb[i] == 0.0 && desc.cub[i] == 1.0) {
00291 vars.push_back(new BCP_var_core(BCP_BinaryVar, desc.obj[i], 0, 1));
00292 }
00293 else {
00294 vars.push_back(new BCP_var_core(BCP_IntegerVar, desc.obj[i],
00295 desc.clb[i], desc.cub[i]));
00296 }
00297 }
00298 else {
00299 vars.push_back(new BCP_var_core(BCP_ContinuousVar, desc.obj[i],
00300 desc.clb[i], desc.cub[i]));
00301 }
00302 }
00303
00304 const int corerows = desc.core->getNumRows();
00305 for (i=0; i<corerows; ++i) {
00306 cuts.push_back(new BCP_cut_core(desc.rlb_core[i], desc.rub_core[i]));
00307 }
00308
00309 matrix = new BCP_lp_relax;
00310
00311 matrix->copyOf(*desc.core, desc.obj, desc.clb, desc.cub,
00312 desc.rlb_core, desc.rub_core);
00313 }
00314
00315
00316 void
00317 BB_tm::create_root(BCP_vec<BCP_var*>& added_vars,
00318 BCP_vec<BCP_cut*>& added_cuts,
00319 BCP_user_data*& user_data)
00320 {
00321
00322 #ifdef USER_DATA
00323 user_data = new MY_user_data(desc.colnum);
00324 #endif
00325 }
00326
00327
00328 void
00329 BB_tm::display_feasible_solution(const BCP_solution *soln)
00330 {
00331 int i;
00332 const BCP_solution_generic *gsol =
00333 dynamic_cast<const BCP_solution_generic*>(soln);
00334
00335
00336
00337 const int colnum = desc.colnum;
00338 double* sol = new double[colnum];
00339
00340 CoinFillN(sol, colnum, 0.0);
00341
00342 const int size = gsol->_vars.size();
00343 for (i=0; i<size; ++i) {
00344 sol[gsol->_vars[i]->bcpind()] = gsol->_values[i];
00345 }
00346
00347 cout << "Customized display of the feasible solution:" << endl << endl;
00348 cout.setf(ios::fixed);
00349 cout.precision(2);
00350
00351 for(i=0; i<colnum; i++) {
00352 cout << sol[i] << " ";
00353
00354 if(i % 10 == 9) {
00355 cout << endl;
00356 }
00357 }
00358 cout << endl;
00359
00360
00361 cout << "Default BCP display of the feasible solution:" << endl << endl;
00362 BCP_tm_user::display_feasible_solution(soln);
00363
00364 delete[] sol;
00365 }