1 : // Copyright (C) 2004, International Business Machines
2 : // Corporation and others. All Rights Reserved.
3 : #if defined(_MSC_VER)
4 : // Turn off compiler warning about long names
5 : # pragma warning(disable:4786)
6 : #endif
7 : #include <cstdlib>
8 : #include <cstdio>
9 : #include <cmath>
10 : #include <cfloat>
11 : #include <cassert>
12 : #include <iostream>
13 : //#define PRINT_DEBUG
14 : //#define CGL_DEBUG
15 : #include "CoinHelperFunctions.hpp"
16 : #include "CoinPackedMatrix.hpp"
17 : #include "CoinFinite.hpp"
18 : #include "OsiRowCutDebugger.hpp"
19 : #include "CglDuplicateRow.hpp"
20 : #include "CglStored.hpp"
21 : //-------------------------------------------------------------------
22 : // Generate duplicate row column cuts
23 : //-------------------------------------------------------------------
24 : void CglDuplicateRow::generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
25 0 : const CglTreeInfo info) const
26 : {
27 : #ifdef CGL_DEBUG
28 : const OsiRowCutDebugger * debugger = si.getRowCutDebugger();
29 : if (debugger&&debugger->onOptimalPath(si)) {
30 : printf("On optimal path\n");
31 : }
32 : #endif
33 : // Don't do in tree ?
34 0 : if (info.inTree) {
35 : // but do any stored cuts
36 0 : if (storedCuts_)
37 0 : storedCuts_->generateCuts(si,cs,info);
38 0 : return;
39 : }
40 0 : int numberColumns = matrix_.getNumCols();
41 0 : CoinPackedVector ubs;
42 :
43 : // Column copy
44 0 : const double * element = matrix_.getElements();
45 0 : const int * row = matrix_.getIndices();
46 0 : const CoinBigIndex * columnStart = matrix_.getVectorStarts();
47 0 : const int * columnLength = matrix_.getVectorLengths();
48 : // Row copy
49 0 : const double * elementByRow = matrixByRow_.getElements();
50 0 : const int * column = matrixByRow_.getIndices();
51 0 : const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
52 0 : const int * rowLength = matrixByRow_.getVectorLengths();
53 0 : const double * columnLower = si.getColLower();
54 0 : const double * columnUpper = si.getColUpper();
55 0 : int nFree=0;
56 0 : int nOut=0;
57 0 : int nFixed=0;
58 : int i;
59 0 : int numberRows=matrix_.getNumRows();
60 0 : const double * rowLower = si.getRowLower();
61 0 : const double * rowUpper = si.getRowUpper();
62 0 : int * effectiveRhs = CoinCopyOfArray(rhs_,numberRows);
63 0 : int * effectiveLower = CoinCopyOfArray(lower_,numberRows);
64 : // mark bad rows - also used for domination
65 0 : for (i=0;i<numberRows;i++) {
66 0 : duplicate_[i]=-1;
67 : int j;
68 0 : for (j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
69 0 : if (elementByRow[j]!=1.0) {
70 0 : duplicate_[i]=-3;
71 0 : rhs_[i]=-1000000;
72 0 : break;
73 : }
74 : }
75 : }
76 0 : double * colUpper2 = CoinCopyOfArray(columnUpper,numberColumns);
77 0 : if (!info.pass&&(mode_&2)!=0) {
78 : // First look at duplicate or dominated columns
79 0 : double * random = new double[numberRows];
80 0 : double * sort = new double[numberColumns+1];
81 0 : for (i=0;i<numberRows;i++) {
82 0 : if (rowLower[i]<-1.0e20||rowUpper[i]>1.0e20)
83 0 : random[i]=0.0;
84 : else
85 0 : random[i] = CoinDrand48();
86 : }
87 0 : int * which = new int[numberColumns];
88 0 : int nPossible=0;
89 0 : for ( i=0;i<numberColumns;i++) {
90 0 : if (si.isBinary(i)) {
91 0 : double value = 0.0;
92 0 : for (int jj=columnStart[i];jj<columnStart[i]+columnLength[i];jj++) {
93 0 : int iRow = row[jj];
94 0 : value += element[jj]*random[iRow];
95 : }
96 0 : sort[nPossible]=value;
97 0 : which[nPossible++]=i;
98 : }
99 : }
100 0 : sort[nPossible]=COIN_DBL_MAX;
101 0 : CoinSort_2(sort,sort+nPossible,which);
102 0 : int last=maximumDominated_-1;
103 0 : double lastValue=-1.0;
104 0 : const double *objective = si.getObjCoefficients() ;
105 0 : double direction = si.getObjSense();
106 : // arrays for checking
107 0 : double * elementEqualJ = new double [2*numberRows];
108 0 : CoinZeroN(elementEqualJ,numberRows); // for memory checkers
109 0 : double * elementGeJ = elementEqualJ + numberRows;
110 0 : CoinZeroN(elementGeJ,numberRows);
111 0 : int * rowEqualJ = new int[2*numberRows];
112 0 : CoinZeroN(rowEqualJ,numberRows); // for memory checkers
113 0 : int * rowGeJ = rowEqualJ + numberRows;
114 0 : char * mark = new char[numberRows];
115 0 : CoinZeroN(mark,numberRows);
116 0 : for (i=0;i<nPossible+1;i++) {
117 0 : if (sort[i]>lastValue) {
118 0 : if (i-last<=maximumDominated_) {
119 : // look to see if dominated
120 0 : for (int j=last;j<i;j++) {
121 0 : int jColumn = which[j];
122 : // skip if already fixed
123 0 : if (!colUpper2[jColumn])
124 0 : continue;
125 0 : int nGeJ=0;
126 0 : int nEqualJ=0;
127 : int jj;
128 0 : for (jj=columnStart[jColumn];jj<columnStart[jColumn]+columnLength[jColumn];jj++) {
129 0 : int iRow = row[jj];
130 0 : if (random[iRow]) {
131 0 : elementEqualJ[nEqualJ]=element[jj];
132 0 : rowEqualJ[nEqualJ++]=iRow;
133 : } else {
134 : // swap sign so all rows look like G
135 0 : elementGeJ[iRow]=(rowUpper[iRow]>1.0e20) ? element[jj] : -element[jj];
136 0 : rowGeJ[nGeJ++]=iRow;
137 : }
138 : }
139 0 : double objValueJ = objective[jColumn]*direction;
140 0 : for (int k=j+1;k<i;k++) {
141 0 : int kColumn = which[k];
142 : // skip if already fixed
143 0 : if (!colUpper2[kColumn])
144 0 : continue;
145 0 : int nEqualK=0;
146 : // -2 no good, -1 J dominates K, 0 unknown or equal, 1 K dominates J
147 0 : int dominate=0;
148 : // mark
149 : int kk;
150 0 : for (kk=0;kk<nGeJ;kk++)
151 0 : mark[rowGeJ[kk]]=1;
152 0 : for (kk=columnStart[kColumn];kk<columnStart[kColumn]+columnLength[kColumn];kk++) {
153 0 : int iRow = row[kk];
154 0 : if (random[iRow]) {
155 0 : if (iRow!=rowEqualJ[nEqualK]||
156 : element[kk]!=elementEqualJ[nEqualK]) {
157 0 : dominate=-2;
158 0 : break;
159 : } else {
160 0 : nEqualK++;
161 : }
162 : } else {
163 : // swap sign so all rows look like G
164 0 : double valueK = (rowUpper[iRow]>1.0e20) ? element[kk] : -element[kk];
165 0 : double valueJ = elementGeJ[iRow];
166 0 : mark[iRow]=0;
167 0 : if (valueJ==valueK) {
168 : // equal
169 0 : } else if (valueJ>valueK) {
170 : // J would dominate K
171 0 : if (dominate==1) {
172 : // no good
173 0 : dominate=-2;
174 0 : break;
175 : } else {
176 0 : dominate=-1;
177 : }
178 : } else {
179 : // K would dominate J
180 0 : if (dominate==-1) {
181 : // no good
182 0 : dominate=-2;
183 0 : break;
184 : } else {
185 0 : dominate=1;
186 : }
187 : }
188 : }
189 : }
190 0 : kk=0;
191 0 : if (dominate!=-2) {
192 : // unmark and check
193 0 : for (;kk<nGeJ;kk++) {
194 0 : int iRow = rowGeJ[kk];
195 0 : if (mark[iRow]) {
196 0 : double valueK = 0.0;
197 0 : double valueJ = elementGeJ[iRow];
198 0 : if (valueJ>valueK) {
199 : // J would dominate K
200 0 : if (dominate==1) {
201 : // no good
202 0 : dominate=-2;
203 0 : break;
204 : } else {
205 0 : dominate=-1;
206 : }
207 : } else {
208 : // K would dominate J
209 0 : if (dominate==-1) {
210 : // no good
211 0 : dominate=-2;
212 0 : break;
213 : } else {
214 0 : dominate=1;
215 : }
216 : }
217 : }
218 0 : mark[iRow]=0;
219 : }
220 : }
221 : // just unmark rest
222 0 : for (;kk<nGeJ;kk++)
223 0 : mark[rowGeJ[kk]]=0;
224 0 : if (nEqualK==nEqualJ&&dominate!=-2) {
225 0 : double objValueK = objective[kColumn]*direction;
226 0 : if (objValueJ==objValueK) {
227 0 : if (dominate<=0) {
228 : // say J dominates
229 0 : assert (colUpper2[kColumn]);
230 0 : dominate=-1;
231 : } else {
232 : // say K dominates
233 0 : assert (colUpper2[jColumn]);
234 0 : dominate=1;
235 : }
236 0 : } else if (objValueJ<objValueK&&dominate<=0) {
237 : // say J dominates
238 0 : assert (colUpper2[kColumn]);
239 0 : dominate=-1;
240 0 : } else if (objValueJ>objValueK&&dominate==1) {
241 : // say K dominates
242 0 : assert (colUpper2[jColumn]);
243 0 : dominate=1;
244 : } else {
245 0 : dominate=0;
246 : }
247 0 : if (dominate) {
248 : // see if both can be 1
249 0 : bool canFix=false;
250 0 : for (int jj=0;jj<nEqualJ;jj++) {
251 0 : double value = 2.0*elementEqualJ[jj];
252 0 : int iRow = rowEqualJ[jj];
253 0 : if (duplicate_[iRow]==-1&&rowUpper[iRow]<1.999999) {
254 0 : canFix=true;
255 : } else {
256 0 : double minSum=0.0;
257 0 : double maxSum=0.0;
258 0 : for (int j=rowStart[iRow];j<rowStart[iRow]+rowLength[iRow];j++) {
259 0 : int iColumn = column[j];
260 0 : if (iColumn!=jColumn&&iColumn!=kColumn) {
261 0 : double elValue = elementByRow[j];
262 0 : double lo = columnLower[iColumn];
263 0 : double up = colUpper2[iColumn];
264 0 : if (elValue>0.0) {
265 0 : minSum += lo*elValue;
266 0 : maxSum += up*elValue;
267 : } else {
268 0 : maxSum += lo*elValue;
269 0 : minSum += up*elValue;
270 : }
271 : }
272 : }
273 0 : if (minSum+value>rowUpper[iRow]+1.0e-5)
274 0 : canFix=true;
275 0 : else if (maxSum+value<rowLower[iRow]-1.0e-5)
276 0 : canFix=true;
277 : }
278 0 : if (canFix)
279 0 : break;
280 : }
281 0 : if (canFix) {
282 0 : int iColumn = (dominate>0) ? jColumn : kColumn;
283 0 : nFixed++;
284 0 : assert (!columnLower[iColumn]);
285 0 : colUpper2[iColumn]=0.0;
286 0 : ubs.insert(iColumn,0.0);
287 0 : if (iColumn==jColumn)
288 0 : break; // no need to carry on on jColumn
289 : } else {
290 0 : int iDominated = (dominate>0) ? jColumn : kColumn;
291 0 : int iDominating = (dominate<0) ? jColumn : kColumn;
292 0 : double els[]={1.0,-1.0};
293 : int inds[2];
294 0 : inds[0]=iDominating;
295 0 : inds[1]=iDominated;
296 0 : if (!storedCuts_)
297 0 : storedCuts_ = new CglStored();
298 0 : storedCuts_->addCut(0.0,COIN_DBL_MAX,2,inds,els);
299 : }
300 : }
301 : }
302 : }
303 0 : for (jj=0;jj<nGeJ;jj++) {
304 0 : int iRow = rowGeJ[jj];
305 0 : elementGeJ[iRow]=0.0;
306 : }
307 : }
308 : }
309 0 : last=i;
310 0 : lastValue = sort[i];
311 : }
312 : }
313 0 : delete [] mark;
314 0 : delete [] elementEqualJ;
315 0 : delete [] rowEqualJ;
316 0 : delete [] random;
317 0 : delete [] sort;
318 0 : delete [] which;
319 : #ifdef COIN_DEVELOP
320 : int numberCuts = storedCuts_ ? storedCuts_->sizeRowCuts() : 0;
321 : if (nFixed||numberCuts)
322 : printf("** %d fixed and %d cuts from domination\n",nFixed,numberCuts);
323 : #endif
324 : }
325 0 : bool infeasible=false;
326 : // if we were just doing columns - mark all as bad
327 0 : if ((mode_&1)==0) {
328 0 : for (i=0;i<numberRows;i++) {
329 0 : duplicate_[i]=-3;
330 0 : rhs_[i]=-1000000;
331 : }
332 : }
333 0 : for ( i=0;i<numberColumns;i++) {
334 0 : if (columnLower[i]) {
335 0 : double value = columnLower[i];
336 0 : for (int jj=columnStart[i];jj<columnStart[i]+columnLength[i];jj++) {
337 0 : int iRow = row[jj];
338 0 : nOut += (int) (element[jj]*value);
339 0 : effectiveRhs[iRow] -= (int) (element[jj]*value);
340 0 : effectiveLower[iRow] -= (int) (element[jj]*value);
341 : }
342 : }
343 : }
344 0 : for ( i=0;i<numberColumns;i++) {
345 0 : if (columnLower[i]!=colUpper2[i]) {
346 0 : bool fixed=false;
347 0 : for (int jj=columnStart[i];jj<columnStart[i]+columnLength[i];jj++) {
348 0 : int iRow = row[jj];
349 0 : if (rhs_[iRow]>=0&&element[jj]>effectiveRhs[iRow])
350 0 : fixed=true;
351 : }
352 0 : if (fixed) {
353 0 : nFixed++;
354 0 : colUpper2[i]=columnLower[i];
355 0 : ubs.insert(i,columnLower[i]);
356 : } else {
357 0 : nFree++;
358 : }
359 : }
360 : }
361 : // See if anything odd
362 0 : char * check = new char[numberColumns];
363 0 : memset(check,0,numberColumns);
364 0 : int * which2 = new int[numberColumns];
365 0 : for (i=0;i<numberRows;i++) {
366 0 : if (duplicate_[i]==-1) {
367 0 : if (effectiveRhs[i]>0)
368 0 : duplicate_[i]=-1;
369 0 : else if (effectiveRhs[i]==0)
370 0 : duplicate_[i]=-2;
371 : else
372 0 : duplicate_[i]=-3;
373 : } else {
374 0 : effectiveRhs[i]=-1000;
375 : }
376 : }
377 0 : for (i=0;i<numberRows;i++) {
378 : // initially just one
379 0 : if (effectiveRhs[i]==1&&duplicate_[i]==-1) {
380 0 : int nn=0;
381 : int j,k;
382 0 : for (j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
383 0 : int iColumn = column[j];
384 0 : if (columnLower[iColumn]!=colUpper2[iColumn]) {
385 : #ifndef NDEBUG
386 0 : assert (elementByRow[j]==1.0);
387 : #endif
388 0 : check[iColumn]=1;
389 0 : which2[nn++]=iColumn;
390 : }
391 : }
392 0 : for ( k=i+1;k<numberRows;k++) {
393 0 : if (effectiveRhs[k]==1&&duplicate_[i]==-1) {
394 0 : int nn2=0;
395 0 : int nnsame=0;
396 0 : for ( j=rowStart[k];j<rowStart[k]+rowLength[k];j++) {
397 0 : int iColumn = column[j];
398 0 : if (columnLower[iColumn]!=colUpper2[iColumn]) {
399 : #ifndef NDEBUG
400 0 : assert (elementByRow[j]==1.0);
401 : #endif
402 0 : nn2++;
403 0 : if (check[iColumn])
404 0 : nnsame++;
405 : }
406 : }
407 0 : if (nnsame==nn2) {
408 0 : if (nn2<nn&&effectiveLower[k]==rhs_[k]&&rhs_[i]==rhs_[k]) {
409 0 : if (logLevel_)
410 : printf("row %d strict subset of row %d, fix some in row %d\n",
411 0 : k,i,i);
412 : // treat i as duplicate
413 0 : duplicate_[i]=k;
414 : // zero out check so we can see what is extra
415 0 : for ( j=rowStart[k];j<rowStart[k]+rowLength[k];j++) {
416 0 : int iColumn = column[j];
417 0 : check[iColumn]=0;
418 : }
419 : // now redo and fix
420 0 : nn=0;
421 0 : for (j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
422 0 : int iColumn = column[j];
423 0 : if (columnLower[iColumn]!=colUpper2[iColumn]) {
424 0 : if (check[iColumn]) {
425 : // fix
426 0 : colUpper2[iColumn]=columnLower[iColumn];
427 0 : nFixed++;
428 0 : ubs.insert(iColumn,columnLower[iColumn]);
429 0 : check[iColumn]=0;
430 : } else {
431 0 : check[iColumn]=1;
432 0 : which2[nn++]=iColumn;
433 : }
434 : }
435 : }
436 0 : } else if (nn2==nn&&effectiveLower[i]==rhs_[i]&&effectiveLower[k]==rhs_[k]) {
437 0 : if (logLevel_)
438 : printf("row %d identical to row %d\n",
439 0 : k,i);
440 0 : duplicate_[k]=i;
441 0 : } else if (nn2>=nn&&effectiveLower[i]==rhs_[i]&&effectiveLower[k]==rhs_[k]) {
442 0 : abort();
443 : }
444 0 : } else if (nnsame==nn&&nn2>nn&&effectiveLower[i]==rhs_[i]&&rhs_[i]<=rhs_[k]) {
445 0 : if (logLevel_)
446 : printf("row %d strict superset of row %d, fix some in row %d\n",
447 0 : k,i,k);
448 : // treat k as duplicate
449 0 : duplicate_[k]=i;
450 : // set check for k
451 0 : for ( j=rowStart[k];j<rowStart[k]+rowLength[k];j++) {
452 0 : int iColumn = column[j];
453 0 : if (columnLower[iColumn]!=colUpper2[iColumn])
454 0 : check[iColumn]=1;
455 : }
456 : // zero out check so we can see what is extra
457 0 : for ( j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
458 0 : int iColumn = column[j];
459 0 : check[iColumn]=0;
460 : }
461 : // fix
462 0 : for (j=rowStart[k];j<rowStart[k]+rowLength[k];j++) {
463 0 : int iColumn = column[j];
464 0 : if (check[iColumn]) {
465 : // fix
466 0 : colUpper2[iColumn]=columnLower[iColumn];
467 0 : nFixed++;
468 0 : ubs.insert(iColumn,columnLower[iColumn]);
469 0 : check[iColumn]=0;
470 : }
471 : }
472 : // redo
473 0 : nn=0;
474 0 : for (j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
475 0 : int iColumn = column[j];
476 0 : if (columnLower[iColumn]!=colUpper2[iColumn]) {
477 0 : check[iColumn]=1;
478 0 : which2[nn++]=iColumn;
479 : }
480 : }
481 : } else {
482 : // may be redundant
483 0 : if (nnsame==nn2) {
484 : // k redundant ?
485 0 : if (nn2<nn&&effectiveLower[k]<=0&&rhs_[i]<=rhs_[k]) {
486 0 : if (logLevel_)
487 : printf("row %d slack subset of row %d, drop row %d\n",
488 0 : k,i,k);
489 : // treat k as duplicate
490 0 : duplicate_[k]=i;
491 : }
492 0 : } else if (nnsame==nn) {
493 : // i redundant ?
494 0 : if (nn2>nn&&effectiveLower[i]<=0&&rhs_[k]<=rhs_[i]) {
495 0 : if (logLevel_)
496 : printf("row %d slack subset of row %d, drop row %d\n",
497 0 : i,k,i);
498 : // treat i as duplicate
499 0 : duplicate_[i]=k;
500 : }
501 : }
502 : }
503 : }
504 : }
505 0 : for (k=0;k<nn;k++)
506 0 : check[which2[k]]=0;
507 :
508 : }
509 : }
510 0 : delete [] check;
511 0 : delete [] which2;
512 0 : delete [] colUpper2;
513 0 : int nRow=0;
514 0 : sizeDynamic_=1;
515 0 : for (i=0;i<numberRows;i++) {
516 0 : if (duplicate_[i]!=-3) {
517 0 : if (duplicate_[i]==-1) {
518 0 : nRow++;
519 0 : int k=effectiveRhs[i];
520 0 : while (k) {
521 0 : if (sizeDynamic_<1000000000)
522 0 : sizeDynamic_ = sizeDynamic_<<1;
523 0 : k = k >>1;
524 : }
525 : }
526 : } else {
527 0 : duplicate_[i]=-1;
528 : }
529 : }
530 0 : delete [] effectiveRhs;
531 0 : delete [] effectiveLower;
532 0 : if (logLevel_)
533 : printf("%d free (but %d fixed this time), %d out of rhs, DP size %d, %d rows\n",
534 0 : nFree,nFixed,nOut,sizeDynamic_,nRow);
535 0 : if (nFixed) {
536 0 : OsiColCut cc;
537 0 : cc.setUbs(ubs);
538 0 : cc.setEffectiveness(100.0);
539 0 : cs.insert(cc);
540 : }
541 0 : if (infeasible) {
542 : // generate infeasible cut and return
543 0 : OsiRowCut rc;
544 0 : rc.setLb(DBL_MAX);
545 0 : rc.setUb(0.0);
546 0 : cs.insert(rc);
547 0 : }
548 : }
549 : //-------------------------------------------------------------------
550 : // Default Constructor
551 : //-------------------------------------------------------------------
552 12 : CglDuplicateRow::CglDuplicateRow ()
553 : :
554 : CglCutGenerator(),
555 : rhs_(NULL),
556 : duplicate_(NULL),
557 : lower_(NULL),
558 : storedCuts_(NULL),
559 : maximumDominated_(1000),
560 : maximumRhs_(1),
561 : sizeDynamic_(COIN_INT_MAX),
562 : mode_(3),
563 12 : logLevel_(0)
564 : {
565 12 : }
566 : // Useful constructor
567 0 : CglDuplicateRow::CglDuplicateRow(OsiSolverInterface * solver)
568 : : CglCutGenerator(),
569 : rhs_(NULL),
570 : duplicate_(NULL),
571 : lower_(NULL),
572 : storedCuts_(NULL),
573 : maximumDominated_(1000),
574 : maximumRhs_(1),
575 : sizeDynamic_(COIN_INT_MAX),
576 : mode_(3),
577 0 : logLevel_(0)
578 : {
579 0 : refreshSolver(solver);
580 0 : }
581 :
582 : //-------------------------------------------------------------------
583 : // Copy constructor
584 : //-------------------------------------------------------------------
585 0 : CglDuplicateRow::CglDuplicateRow ( const CglDuplicateRow & rhs)
586 : :
587 : CglCutGenerator(rhs),
588 : matrix_(rhs.matrix_),
589 : matrixByRow_(rhs.matrixByRow_),
590 : storedCuts_(NULL),
591 : maximumDominated_(rhs.maximumDominated_),
592 : maximumRhs_(rhs.maximumRhs_),
593 : sizeDynamic_(rhs.sizeDynamic_),
594 : mode_(rhs.mode_),
595 0 : logLevel_(rhs.logLevel_)
596 : {
597 0 : int numberRows=matrix_.getNumRows();
598 0 : rhs_ = CoinCopyOfArray(rhs.rhs_,numberRows);
599 0 : duplicate_ = CoinCopyOfArray(rhs.duplicate_,numberRows);
600 0 : lower_ = CoinCopyOfArray(rhs.lower_,numberRows);
601 0 : if (rhs.storedCuts_)
602 0 : storedCuts_ = new CglStored(*rhs.storedCuts_);
603 0 : }
604 :
605 : //-------------------------------------------------------------------
606 : // Clone
607 : //-------------------------------------------------------------------
608 : CglCutGenerator *
609 0 : CglDuplicateRow::clone() const
610 : {
611 0 : return new CglDuplicateRow(*this);
612 : }
613 :
614 : //-------------------------------------------------------------------
615 : // Destructor
616 : //-------------------------------------------------------------------
617 12 : CglDuplicateRow::~CglDuplicateRow ()
618 : {
619 : // free memory
620 12 : delete [] rhs_;
621 12 : delete [] duplicate_;
622 12 : delete [] lower_;
623 12 : delete storedCuts_;
624 12 : }
625 :
626 : //----------------------------------------------------------------
627 : // Assignment operator
628 : //-------------------------------------------------------------------
629 : CglDuplicateRow &
630 : CglDuplicateRow::operator=(
631 0 : const CglDuplicateRow& rhs)
632 : {
633 0 : if (this != &rhs) {
634 0 : CglCutGenerator::operator=(rhs);
635 0 : delete [] rhs_;
636 0 : delete [] duplicate_;
637 0 : delete [] lower_;
638 0 : delete storedCuts_;
639 0 : storedCuts_ = NULL;
640 0 : matrix_=rhs.matrix_;
641 0 : matrixByRow_=rhs.matrixByRow_;
642 0 : maximumDominated_ = rhs.maximumDominated_;
643 0 : maximumRhs_=rhs.maximumRhs_;
644 0 : sizeDynamic_ = rhs.sizeDynamic_;
645 0 : mode_ = rhs.mode_;
646 0 : logLevel_ = rhs.logLevel_;
647 0 : int numberRows=matrix_.getNumRows();
648 0 : rhs_ = CoinCopyOfArray(rhs.rhs_,numberRows);
649 0 : duplicate_ = CoinCopyOfArray(rhs.duplicate_,numberRows);
650 0 : lower_ = CoinCopyOfArray(rhs.lower_,numberRows);
651 0 : if (rhs.storedCuts_)
652 0 : storedCuts_ = new CglStored(*rhs.storedCuts_);
653 : }
654 0 : return *this;
655 : }
656 :
657 : /// This can be used to refresh any inforamtion
658 : void
659 0 : CglDuplicateRow::refreshSolver(OsiSolverInterface * solver)
660 : {
661 0 : delete [] rhs_;
662 0 : delete [] duplicate_;
663 0 : delete [] lower_;
664 0 : matrix_ = *solver->getMatrixByCol();
665 0 : matrix_.removeGaps();
666 0 : matrix_.orderMatrix();
667 0 : matrixByRow_ = *solver->getMatrixByRow();
668 0 : int numberRows=matrix_.getNumRows();
669 0 : rhs_ = new int[numberRows];
670 0 : duplicate_ = new int[numberRows];
671 0 : lower_ = new int[numberRows];
672 0 : const double * rowLower = solver->getRowLower();
673 0 : const double * rowUpper = solver->getRowUpper();
674 : // Row copy
675 0 : const double * elementByRow = matrixByRow_.getElements();
676 0 : const int * column = matrixByRow_.getIndices();
677 0 : const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
678 0 : const int * rowLength = matrixByRow_.getVectorLengths();
679 : int iRow;
680 0 : int numberGood=0;
681 0 : int markBad = -(solver->getNumCols()+1);
682 0 : for (iRow=0;iRow<numberRows;iRow++) {
683 0 : rhs_[iRow]=markBad;
684 0 : lower_[iRow]=markBad;
685 0 : duplicate_[iRow]=-1;
686 0 : if (rowUpper[iRow]<100) {
687 0 : int iRhs= (int) floor(rowUpper[iRow]);
688 : // check elements
689 0 : bool good=true;
690 0 : for (int j=rowStart[iRow];j<rowStart[iRow]+rowLength[iRow];j++) {
691 0 : int iColumn = column[j];
692 0 : if (!solver->isInteger(iColumn))
693 0 : good=false;
694 0 : double value = elementByRow[j];
695 0 : if (floor(value)!=value||value<1.0) {
696 0 : good=false;
697 : }
698 : }
699 0 : if (good) {
700 0 : lower_[iRow] = (int) CoinMax(0.0,ceil(rowLower[iRow]));
701 0 : if (iRhs>=lower_[iRow]) {
702 0 : rhs_[iRow]=iRhs;
703 0 : numberGood++;
704 : } else {
705 : // infeasible ?
706 0 : lower_[iRow]=markBad;
707 0 : rhs_[iRow]=markBad;
708 : }
709 : } else {
710 0 : lower_[iRow]=markBad;
711 0 : rhs_[iRow]=markBad;
712 : }
713 : }
714 : }
715 0 : }
716 : /** Fix variables and find duplicate/dominated rows for the model of the
717 : solver interface, si.
718 :
719 : This is a very simple minded idea but I (JJF) am using it in a project so thought
720 : I might as well add it. It should really be called before first solve and I may
721 : modify CBC to allow for that.
722 :
723 : This is designed for problems with few rows and many integer variables where the rhs
724 : are <= or == and all coefficients and rhs are small integers.
725 :
726 : If effective rhs is K then we can fix all variables with coefficients > K to their lower bounds
727 : (effective rhs just means original with variables with nonzero lower bounds subtracted out).
728 :
729 : If one row is a subset of another and the effective rhs are same we can fix some variables
730 : and then the two rows are identical.
731 :
732 : This version does deletions and fixings and may return stored cuts for
733 : dominated columns
734 : */
735 : CglStored *
736 0 : CglDuplicateRow::outDuplicates( OsiSolverInterface * solver)
737 : {
738 :
739 0 : CglTreeInfo info;
740 0 : info.level = 0;
741 0 : info.pass = 0;
742 0 : int numberRows = solver->getNumRows();
743 0 : info.formulation_rows = numberRows;
744 0 : info.inTree = false;
745 0 : info.strengthenRow= NULL;
746 0 : info.pass = 0;
747 0 : OsiCuts cs;
748 0 : generateCuts(*solver,cs,info);
749 : // Get rid of duplicate rows
750 0 : int * which = new int[numberRows];
751 0 : int numberDrop=0;
752 0 : for (int iRow=0;iRow<numberRows;iRow++) {
753 0 : if (duplicate_[iRow]==-2||duplicate_[iRow]>=0)
754 0 : which[numberDrop++]=iRow;
755 : }
756 0 : if (numberDrop) {
757 0 : solver->deleteRows(numberDrop,which);
758 : }
759 0 : delete [] which;
760 : // see if we have any column cuts
761 0 : int numberColumnCuts = cs.sizeColCuts() ;
762 0 : const double * columnLower = solver->getColLower();
763 0 : const double * columnUpper = solver->getColUpper();
764 0 : for (int k = 0;k<numberColumnCuts;k++) {
765 0 : OsiColCut * thisCut = cs.colCutPtr(k) ;
766 0 : const CoinPackedVector & lbs = thisCut->lbs() ;
767 0 : const CoinPackedVector & ubs = thisCut->ubs() ;
768 : int j ;
769 : int n ;
770 : const int * which ;
771 : const double * values ;
772 0 : n = lbs.getNumElements() ;
773 0 : which = lbs.getIndices() ;
774 0 : values = lbs.getElements() ;
775 0 : for (j = 0;j<n;j++) {
776 0 : int iColumn = which[j] ;
777 0 : if (values[j]>columnLower[iColumn])
778 0 : solver->setColLower(iColumn,values[j]) ;
779 : }
780 0 : n = ubs.getNumElements() ;
781 0 : which = ubs.getIndices() ;
782 0 : values = ubs.getElements() ;
783 0 : for (j = 0;j<n;j++) {
784 0 : int iColumn = which[j] ;
785 0 : if (values[j]<columnUpper[iColumn])
786 0 : solver->setColUpper(iColumn,values[j]) ;
787 : }
788 : }
789 0 : return storedCuts_;
790 : }
791 : // Create C++ lines to get to current state
792 : std::string
793 0 : CglDuplicateRow::generateCpp( FILE * fp)
794 : {
795 0 : CglDuplicateRow other;
796 0 : fprintf(fp,"0#include \"CglDuplicateRow.hpp\"\n");
797 0 : fprintf(fp,"3 CglDuplicateRow duplicateRow;\n");
798 0 : if (logLevel_!=other.logLevel_)
799 0 : fprintf(fp,"3 duplicateRow.setLogLevel(%d);\n",logLevel_);
800 : else
801 0 : fprintf(fp,"4 duplicateRow.setLogLevel(%d);\n",logLevel_);
802 0 : if (maximumRhs_!=other.maximumRhs_)
803 0 : fprintf(fp,"3 duplicateRow.setMaximumRhs(%d);\n",maximumRhs_);
804 : else
805 0 : fprintf(fp,"4 duplicateRow.setMaximumRhs(%d);\n",maximumRhs_);
806 0 : if (maximumDominated_!=other.maximumDominated_)
807 0 : fprintf(fp,"3 duplicateRow.setMaximumDominated(%d);\n",maximumDominated_);
808 : else
809 0 : fprintf(fp,"4 duplicateRow.setMaximumDominated(%d);\n",maximumDominated_);
810 0 : if (mode_!=other.mode_)
811 0 : fprintf(fp,"3 duplicateRow.setMode(%d);\n",mode_);
812 : else
813 0 : fprintf(fp,"4 duplicateRow.setMode(%d);\n",mode_);
814 0 : if (getAggressiveness()!=other.getAggressiveness())
815 0 : fprintf(fp,"3 duplicateRow.setAggressiveness(%d);\n",getAggressiveness());
816 : else
817 0 : fprintf(fp,"4 duplicateRow.setAggressiveness(%d);\n",getAggressiveness());
818 0 : return "duplicateRow";
819 88 : }
|
