1 : // Copyright (C) 2000, 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 <iostream>
12 :
13 : #include "CoinHelperFunctions.hpp"
14 : #include "CoinPackedVector.hpp"
15 : #include "CoinPackedMatrix.hpp"
16 : #include "OsiRowCutDebugger.hpp"
17 : #include "CglOddHole.hpp"
18 : //#define CGL_DEBUG
19 : // We may want to sort cut
20 : typedef struct {double dj;double element; int sequence;}
21 : double_double_int_triple;
22 : class double_double_int_triple_compare {
23 : public:
24 0 : bool operator() (double_double_int_triple x , double_double_int_triple y) const
25 : {
26 0 : return ( x.dj < y.dj);
27 : }
28 : };
29 : //-------------------------------------------------------------------------------
30 : // Generate three cycle cuts
31 : //-------------------------------------------------------------------
32 : void CglOddHole::generateCuts(const OsiSolverInterface & si, OsiCuts & cs,
33 0 : const CglTreeInfo info) const
34 : {
35 : // Get basic problem information
36 0 : int nRows=si.getNumRows();
37 0 : int nCols=si.getNumCols();
38 :
39 0 : const CoinPackedMatrix * rowCopy = si.getMatrixByRow();
40 :
41 : // Could do cliques and extra OSL cliques
42 : // For moment just easy ones
43 :
44 : // If no information exists then get a list of suitable rows
45 : // If it does then suitable rows are subset of information
46 :
47 0 : CglOddHole temp;
48 0 : int * checkRow = new int[nRows];
49 : int i;
50 0 : if (!suitableRows_) {
51 0 : for (i=0;i<nRows;i++) {
52 0 : checkRow[i]=1;
53 : }
54 : } else {
55 : // initialize and extend rows to current size
56 0 : memset(checkRow,0,nRows*sizeof(int));
57 0 : memcpy(checkRow,suitableRows_,CoinMin(nRows,numberRows_)*sizeof(int));
58 : }
59 0 : temp.createRowList(si,checkRow);
60 : // now cut down further by only allowing rows with fractional solution
61 0 : double * solution = new double[nCols];
62 0 : memcpy(solution,si.getColSolution(),nCols*sizeof(double));
63 0 : const int * column = rowCopy->getIndices();
64 0 : const CoinBigIndex * rowStart = rowCopy->getVectorStarts();
65 0 : const int * rowLength = rowCopy->getVectorLengths();
66 0 : const double * collower = si.getColLower();
67 0 : const double * colupper = si.getColUpper();
68 0 : int * suitable = temp.suitableRows_;
69 :
70 : // At present I am using new and delete as easier to see arrays in debugger
71 0 : int * fixed = new int[nCols]; // mark fixed columns
72 :
73 0 : for (i=0;i<nCols;i++) {
74 0 : if (si.isBinary(i) ) {
75 0 : fixed[i]=0;
76 0 : if (colupper[i]-collower[i]<epsilon_) {
77 0 : solution[i]=0.0;
78 0 : fixed[i]=2;
79 0 : } else if (solution[i]<epsilon_) {
80 0 : solution[i]=0.0;
81 0 : fixed[i]=-1;
82 0 : } else if (solution[i]>onetol_) {
83 0 : solution[i]=1.0;
84 0 : fixed[i]=+1;
85 : }
86 : } else {
87 : //mark as fixed even if not (can not intersect any interesting rows)
88 0 : solution[i]=0.0;
89 0 : fixed[i]=3;
90 : }
91 : }
92 : // first do packed
93 0 : const double * rowlower = si.getRowLower();
94 0 : const double * rowupper = si.getRowUpper();
95 0 : for (i=0;i<nRows;i++) {
96 0 : if (suitable[i]) {
97 : int k;
98 0 : double sum=0.0;
99 0 : if (rowupper[i]>1.001) suitable[i]=-1;
100 0 : for (k=rowStart[i]; k<rowStart[i]+rowLength[i];k++) {
101 0 : int icol=column[k];
102 0 : if (!fixed[icol]) sum += solution[icol];
103 : }
104 0 : if (sum<0.9) suitable[i]=-1; //say no good
105 : }
106 : }
107 : #ifdef CGL_DEBUG
108 : const OsiRowCutDebugger * debugger = si.getRowCutDebugger();
109 : if (debugger&&!debugger->onOptimalPath(si))
110 : debugger = NULL;
111 : #else
112 0 : const OsiRowCutDebugger * debugger = NULL;
113 : #endif
114 : temp.generateCuts(debugger, *rowCopy,solution,
115 0 : si.getReducedCost(),cs,suitable,fixed,true);
116 : // now cover
117 : //if no >= then skip
118 0 : bool doCover=false;
119 0 : int nsuitable=0;
120 0 : for (i=0;i<nRows;i++) {
121 0 : suitable[i]=abs(suitable[i]);
122 0 : if (suitable[i]) {
123 : int k;
124 0 : double sum=0.0;
125 0 : if (rowlower[i]<0.999) sum=2.0;
126 0 : if (rowupper[i]>1.001) doCover=true;
127 0 : for (k=rowStart[i]; k<rowStart[i]+rowLength[i];k++) {
128 0 : int icol=column[k];
129 0 : if (!fixed[icol]) sum += solution[icol];
130 0 : if (fixed[icol]==1) sum=2.0; //don't use if any at 1
131 : }
132 0 : if (sum>1.1) {
133 0 : suitable[i]=-1; //say no good
134 : } else {
135 0 : nsuitable++;
136 : }
137 : }
138 : }
139 0 : if (doCover&&nsuitable)
140 : temp.generateCuts(debugger, *rowCopy,solution,si.getReducedCost(),
141 0 : cs,suitable,fixed,false);
142 0 : delete [] checkRow;
143 0 : delete [] solution;
144 0 : delete [] fixed;
145 :
146 0 : }
147 : void CglOddHole::generateCuts(const OsiRowCutDebugger * debugger,
148 : const CoinPackedMatrix & rowCopy,
149 : const double * solution,
150 : const double * dj, OsiCuts & cs,
151 : const int * suitableRow,
152 : const int * fixedColumn,
153 0 : bool packed)
154 : {
155 0 : CoinPackedMatrix columnCopy = rowCopy;
156 0 : columnCopy.reverseOrdering();
157 :
158 : // Get basic problem information
159 0 : int nRows=columnCopy.getNumRows();
160 0 : int nCols=columnCopy.getNumCols();
161 :
162 0 : const int * column = rowCopy.getIndices();
163 0 : const CoinBigIndex * rowStart = rowCopy.getVectorStarts();
164 0 : const int * rowLength = rowCopy.getVectorLengths();
165 :
166 0 : const int * row = columnCopy.getIndices();
167 0 : const CoinBigIndex * columnStart = columnCopy.getVectorStarts();
168 0 : const int * columnLength = columnCopy.getVectorLengths();
169 :
170 : // we need only look at suitable rows and variables with unsatisfied 0-1
171 : // lookup from true row to compressed matrix
172 0 : int * mrow = new int[nRows];
173 : // lookup from true column to compressed
174 0 : int * lookup = new int[nCols];
175 : // number of columns in compressed matrix
176 0 : int nSmall=0;
177 : int i;
178 : //do lookup from true sequence to compressed
179 0 : int n=0;
180 0 : for (i=0;i<nRows;i++) {
181 0 : if (suitableRow[i]>0) {
182 0 : mrow[i]=n++;
183 : } else {
184 0 : mrow[i]=-1;
185 : }
186 : }
187 0 : for (i=0;i<nCols;i++) {
188 0 : if (!fixedColumn[i]) {
189 0 : lookup[i]=nSmall++;
190 : } else {
191 0 : lookup[i]=-1;
192 : }
193 : }
194 0 : int nSmall2=2*nSmall;
195 : // we don't know how big matrix will be
196 : #define MAXELS 50000
197 0 : int maxels=MAXELS;
198 : //How do I do reallocs in C++?
199 : // 1.0 - value x(i) - value x(j) for each node pair (or reverse if cover)
200 0 : double * cost = (double *) malloc(maxels*sizeof(double));
201 : // arc i.e. j which can be reached from i
202 0 : int * to= (int *) malloc(maxels*sizeof(int));
203 : //original row for each arc
204 0 : int * rowfound=(int *) malloc(maxels*sizeof(int));
205 : // start of each column
206 0 : int * starts=new int[2*nSmall+1];
207 0 : starts[0]=0;
208 : // useful array for marking if already connected
209 0 : int * mark =new int[nSmall2];
210 0 : memset(mark,0,nSmall2*sizeof(int));
211 0 : n=0; //number of elements in matrix
212 0 : for (i=0;i<nCols;i++) {
213 0 : int icol=lookup[i];
214 0 : if (icol>=0) {
215 : // column in compressed matrix
216 : int k;
217 0 : double dd=1.0000001-solution[i];
218 0 : mark[icol]=1;
219 : // reallocate if matrix reached size limit
220 0 : if (n+nCols>maxels) {
221 0 : maxels*=2;
222 0 : cost=(double *) realloc(cost,maxels*sizeof(int));
223 0 : to=(int *) realloc(to,maxels*sizeof(int));
224 0 : rowfound=(int *) realloc(rowfound,maxels*sizeof(int));
225 : }
226 : // get all other connected variables
227 0 : for (k=columnStart[i];k<columnStart[i]+columnLength[i];k++) {
228 0 : int irow=row[k];
229 0 : int jrow=mrow[irow];
230 : // but only if row in compressed matrix
231 0 : if (jrow>=0) {
232 : int j;
233 0 : for (j=rowStart[irow];j<rowStart[irow]+rowLength[irow];j++) {
234 0 : int jcol=column[j];
235 0 : int kcol=lookup[jcol];
236 0 : if (kcol>=0&&!mark[kcol]) {
237 0 : cost[n]=dd-solution[jcol];
238 0 : to[n]=kcol;
239 0 : rowfound[n++]=irow;//original row
240 0 : mark[kcol]=1;
241 : }
242 : }
243 : }
244 : }
245 0 : starts[icol+1]=n;
246 : // zero out markers for next column
247 0 : mark[icol]=0;
248 0 : for (k=starts[icol];k<starts[icol+1];k++) {
249 0 : int ito=to[k];
250 0 : if (ito<0||ito>=nSmall) abort();
251 0 : mark[to[k]]=0;
252 : }
253 : }
254 : }
255 : //if cover then change sign - otherwise make sure positive
256 0 : if (packed) {
257 0 : for (i=0;i<n;i++) {
258 0 : if (cost[i]<1.0e-10) {
259 0 : cost[i]=1.0e-10;
260 : }
261 : }
262 : } else {
263 0 : for (i=0;i<n;i++) {
264 0 : cost[i]=-cost[i];
265 0 : if (cost[i]<1.0e-10) {
266 0 : cost[i]=1.0e-10;
267 : }
268 : }
269 : }
270 : // we are going to double size
271 :
272 0 : if (2*n>maxels) {
273 0 : maxels=2*n;
274 0 : cost=(double *) realloc(cost,maxels*sizeof(double));
275 0 : to=(int *) realloc(to,maxels*sizeof(int));
276 0 : rowfound=(int *) realloc(rowfound,maxels*sizeof(int));
277 : }
278 : /* copy and make bipartite*/
279 :
280 0 : for (i=0;i<nSmall;i++) {
281 0 : int k,j=i+nSmall;
282 0 : for (k=starts[i];k<starts[i+1];k++) {
283 0 : int ito=to[k];
284 0 : to[n]=ito;
285 0 : to[k]=ito+nSmall;
286 0 : cost[n]=cost[k];
287 0 : rowfound[n++]=rowfound[k];;
288 : }
289 0 : starts[j+1]=n;
290 : }
291 : //random numbers to winnow out duplicate cuts
292 0 : double * check = new double[nCols];
293 0 : CoinSeedRandom(13579);
294 0 : for (i=0;i<nCols;i++) {
295 0 : check[i]=CoinDrand48();
296 : }
297 :
298 : // Shortest path algorithm from Dijkstra - is there a better one?
299 :
300 : typedef struct {
301 : double cost; //cost to starting node
302 : int back; //previous node
303 : } Path;
304 : typedef struct {
305 : double cost; //cost to starting node
306 : int node; //node
307 : } Item;
308 0 : Item * stack = new Item [nSmall2];
309 0 : Path * path = new Path [nSmall2];
310 : // arrays below are used only if looks promising
311 : // allocate here
312 : // we don't know how many cuts will be generated
313 0 : int ncuts=0;
314 0 : int maxcuts=1000;
315 0 : double * hash = (double *) malloc(maxcuts*sizeof(double));
316 : // to clean (should not be needed)
317 0 : int * clean = new int[nSmall2];
318 0 : int * candidate = new int[CoinMax(nSmall2,nCols)];
319 0 : double * element = new double[nCols];
320 : // in case we want to sort
321 : double_double_int_triple * sortit =
322 0 : new double_double_int_triple [nCols];
323 0 : memset(mark,0,nSmall2*sizeof(int));
324 0 : int * countcol = new int[nCols];
325 0 : memset(countcol,0,nCols*sizeof(int));
326 0 : int bias = packed ? 0 : 1; //amount to add before halving
327 : // If nSmall large then should do a randomized subset
328 : // Improvement 1
329 : int icol;
330 0 : for (icol=0;icol<nSmall;icol++) {
331 : int j;
332 0 : int jcol=icol+nSmall;
333 0 : int istack=1;
334 0 : for (j=0;j<nSmall2;j++) {
335 0 : path[j].cost=1.0e70;
336 0 : path[j].back=nSmall2+1;
337 : }
338 0 : path[icol].cost=0.0;
339 0 : path[icol].back=-1;
340 0 : stack[0].cost=0.0;
341 0 : stack[0].node=icol;
342 0 : mark[icol]=1;
343 0 : while(istack) {
344 0 : Item thisItem=stack[--istack];
345 0 : double thisCost=thisItem.cost;
346 0 : int inode=thisItem.node;
347 : int k;
348 0 : mark[inode]=0; //say available for further work
349 : // See if sorting every so many would help (and which way)?
350 : // Improvement 2
351 0 : for (k=starts[inode];k<starts[inode+1];k++) {
352 0 : int jnode=to[k];
353 0 : if (!mark[jnode]&&thisCost+cost[k]<path[jnode].cost-1.0e-12) {
354 0 : path[jnode].cost=thisCost+cost[k];
355 0 : path[jnode].back=inode;
356 : // add to stack
357 0 : stack[istack].cost=path[jnode].cost;
358 0 : stack[istack++].node=jnode;
359 0 : mark[jnode]=1;
360 : #ifdef CGL_DEBUG
361 : assert (istack<=nSmall2);
362 : #endif
363 : }
364 : }
365 : }
366 0 : bool good=(path[jcol].cost<0.9999);
367 :
368 0 : if (good) { /* try */
369 : int ii;
370 0 : int nrow2=0;
371 0 : int nclean=0;
372 0 : double sum=0;
373 : #ifdef CGL_DEBUG
374 : printf("** %d ",jcol-nSmall);
375 : #endif
376 0 : ii=1;
377 0 : candidate[0]=jcol;
378 0 : while(jcol!=icol) {
379 : int jjcol;
380 0 : jcol=path[jcol].back;
381 0 : if (jcol>=nSmall) {
382 0 : jjcol=jcol-nSmall;
383 : } else {
384 0 : jjcol=jcol;
385 : }
386 : #ifdef CGL_DEBUG
387 : printf(" %d",jjcol);
388 : #endif
389 0 : if (mark[jjcol]) {
390 : // good=false;
391 : // probably means this is from another cycle (will have been found)
392 : // one of cycles must be zero cost
393 : // printf("variable already on chain!\n");
394 : } else {
395 0 : mark[jjcol]=1;
396 0 : clean[nclean++]=jjcol;
397 0 : candidate[ii++]=jcol;
398 : #ifdef CGL_DEBUG
399 : assert (ii<=nSmall2);
400 : #endif
401 : }
402 : }
403 : #ifdef CGL_DEBUG
404 : printf("\n");
405 : #endif
406 0 : for (j=0;j<nclean;j++) {
407 0 : int k=clean[j];
408 0 : mark[k]=0;
409 : }
410 0 : if (good) {
411 : int k;
412 0 : for (k=ii-1;k>0;k--) {
413 0 : int jk,kk=candidate[k];
414 0 : int ix=0;
415 0 : for (jk=starts[kk];jk<starts[kk+1];jk++) {
416 0 : int ito=to[jk];
417 0 : if (ito==candidate[k-1]) {
418 0 : ix=1;
419 : // back to original row
420 0 : mrow[nrow2++]=rowfound[jk];
421 0 : break;
422 : }
423 : }
424 0 : if (!ix) {
425 0 : good=false;
426 : }
427 : }
428 0 : if ((nrow2&1)!=1) {
429 0 : good=false;
430 : }
431 0 : if (good) {
432 0 : int nincut=0;
433 0 : for (k=0;k<nrow2;k++) {
434 0 : int j,irow=mrow[k];
435 0 : for (j=rowStart[irow];j<rowStart[irow]+rowLength[irow];j++) {
436 0 : int icol=column[j];
437 0 : if (!countcol[icol]) candidate[nincut++]=icol;
438 0 : countcol[icol]++;
439 : }
440 : }
441 : #ifdef CGL_DEBUG
442 : printf("true constraint %d",nrow2);
443 : #endif
444 0 : nrow2=nrow2>>1;
445 0 : double rhs=nrow2;
446 0 : if (!packed) rhs++; // +1 for cover
447 0 : ii=0;
448 0 : for (k=0;k<nincut;k++) {
449 0 : int jcol=candidate[k];
450 0 : if (countcol[jcol]) {
451 : #ifdef CGL_DEBUG
452 : printf(" %d %d",jcol,countcol[jcol]);
453 : #endif
454 0 : int ihalf=(countcol[jcol]+bias)>>1;
455 0 : if (ihalf) {
456 0 : element[ii]=ihalf;
457 0 : sum+=solution[jcol]*element[ii];
458 : /*printf("%d %g %g\n",jcol,element[ii],sumall[jcol]);*/
459 0 : candidate[ii++]=jcol;
460 : }
461 0 : countcol[jcol]=0;
462 : }
463 : }
464 : #ifdef CGL_DEBUG
465 : printf("\n");
466 : #endif
467 0 : OsiRowCut rc;
468 0 : double violation=0.0;
469 0 : if (packed) {
470 0 : violation = sum-rhs;
471 0 : rc.setLb(-DBL_MAX);
472 0 : rc.setUb(rhs);
473 : } else {
474 : // other way for cover
475 0 : violation = rhs-sum;
476 0 : rc.setUb(DBL_MAX);
477 0 : rc.setLb(rhs);
478 : }
479 0 : if (violation<minimumViolation_) {
480 : #ifdef CGL_DEBUG
481 : printf("why no cut\n");
482 : #endif
483 0 : good=false;
484 : } else {
485 0 : if (((double) ii) * minimumViolationPer_>violation||
486 : ii>maximumEntries_) {
487 : #ifdef CGL_DEBUG
488 : printf("why no cut\n");
489 : #endif
490 0 : if (packed) {
491 : // sort and see if we can get down to length
492 : // relax by taking out ones with solution 0.0
493 0 : nincut=ii;
494 0 : for (k=0;k<nincut;k++) {
495 0 : int jcol=candidate[k];
496 0 : double value = fabs(dj[jcol]);
497 0 : if (solution[jcol])
498 0 : value = -solution[jcol];
499 0 : sortit[k].dj=value;
500 0 : sortit[k].element=element[k];
501 0 : sortit[k].sequence=jcol;
502 : }
503 : // sort
504 0 : std::sort(sortit,sortit+nincut,double_double_int_triple_compare());
505 0 : nincut = min(nincut,maximumEntries_);
506 0 : sum=0.0;
507 0 : for (k=0;k<nincut;k++) {
508 0 : int jcol=sortit[k].sequence;
509 0 : candidate[k]=jcol;
510 0 : element[k]=sortit[k].element;
511 0 : sum+=solution[jcol]*element[k];
512 : }
513 0 : violation = sum-rhs;
514 0 : ii=nincut;
515 0 : if (violation<minimumViolation_) {
516 0 : good=false;
517 : }
518 : } else {
519 0 : good=false;
520 : }
521 : }
522 : }
523 0 : if (good) {
524 : //this assumes not many cuts
525 : int j;
526 : #if 0
527 : double value=0.0;
528 : for (j=0;j<ii;j++) {
529 : int icol=candidate[j];
530 : value += check[icol]*element[j];
531 : }
532 : #else
533 0 : CoinPackedVector candidatePv(ii,candidate,element);
534 0 : candidatePv.sortIncrIndex();
535 0 : double value = candidatePv.dotProduct(check);
536 : #endif
537 :
538 0 : for (j=0;j<ncuts;j++) {
539 0 : if (value==hash[j]) {
540 : //could check equality - quicker just to assume
541 0 : break;
542 : }
543 : }
544 0 : if (j==ncuts) {
545 : //new
546 0 : if (ncuts==maxcuts) {
547 0 : maxcuts *= 2;
548 0 : hash = (double *) realloc(hash,maxcuts*sizeof(double));
549 : }
550 0 : hash[ncuts++]=value;
551 0 : rc.setRow(ii,candidate,element);
552 : #ifdef CGL_DEBUG
553 : printf("sum %g rhs %g %d\n",sum,rhs,ii);
554 : if (debugger)
555 : assert(!debugger->invalidCut(rc));
556 : #endif
557 0 : cs.insert(rc);
558 0 : }
559 0 : }
560 : }
561 : /* end of adding cut */
562 : }
563 : }
564 : }
565 0 : delete [] countcol;
566 0 : delete [] element;
567 0 : delete [] candidate;
568 0 : delete [] sortit;
569 0 : delete [] clean;
570 0 : delete [] path;
571 0 : delete [] stack;
572 0 : free(hash);
573 0 : delete [] check;
574 0 : delete [] mark;
575 0 : delete [] starts;
576 0 : delete [] lookup;
577 0 : delete [] mrow;
578 0 : free(rowfound);
579 0 : free(to);
580 0 : free(cost);
581 0 : }
582 :
583 : // Create a list of rows which might yield cuts
584 : // The possible parameter is a list to cut down search
585 : void CglOddHole::createRowList( const OsiSolverInterface & si,
586 0 : const int * possible)
587 : {
588 : // Get basic problem information
589 0 : int nRows=si.getNumRows();
590 :
591 0 : const CoinPackedMatrix * rowCopy = si.getMatrixByRow();
592 :
593 0 : const int * column = rowCopy->getIndices();
594 0 : const CoinBigIndex * rowStart = rowCopy->getVectorStarts();
595 0 : const int * rowLength = rowCopy->getVectorLengths();
596 :
597 : int rowIndex;
598 0 : delete [] suitableRows_;
599 0 : numberRows_=nRows;
600 :
601 0 : const double * rowElements = rowCopy->getElements();
602 0 : const double * rowupper = si.getRowUpper();
603 0 : const double * rowlower = si.getRowLower();
604 0 : const double * collower = si.getColLower();
605 0 : const double * colupper = si.getColUpper();
606 :
607 0 : suitableRows_=new int[nRows];
608 0 : if (possible) {
609 0 : memcpy(suitableRows_,possible,nRows*sizeof(int));
610 : } else {
611 : int i;
612 0 : for (i=0;i<nRows;i++) {
613 0 : suitableRows_[i]=1;
614 : }
615 : }
616 0 : for (rowIndex=0; rowIndex<nRows; rowIndex++){
617 0 : double rhs1=rowupper[rowIndex];
618 0 : double rhs2=rowlower[rowIndex];
619 0 : if (suitableRows_[rowIndex]) {
620 : int i;
621 0 : bool goodRow=true;
622 0 : for (i=rowStart[rowIndex];
623 : i<rowStart[rowIndex]+rowLength[rowIndex];i++) {
624 0 : int thisCol=column[i];
625 0 : if (colupper[thisCol]-collower[thisCol]>epsilon_) {
626 : // could allow general integer variables but unlikely
627 0 : if (!si.isBinary(thisCol) ) {
628 0 : goodRow=false;
629 0 : break;
630 : }
631 0 : if (fabs(rowElements[i]-1.0)>epsilon_) {
632 0 : goodRow=false;
633 0 : break;
634 : }
635 : } else {
636 0 : rhs1 -= collower[thisCol]*rowElements[i];
637 0 : rhs2 -= collower[thisCol]*rowElements[i];
638 : }
639 : }
640 0 : if (fabs(rhs1-1.0)>epsilon_&&fabs(rhs2-1.0)>epsilon_) {
641 0 : goodRow=false;
642 : }
643 0 : if (goodRow) {
644 0 : suitableRows_[rowIndex]=1;
645 : } else {
646 0 : suitableRows_[rowIndex]=0;
647 : }
648 : }
649 : }
650 0 : }
651 : /// This version passes in a list - 1 marks possible
652 0 : void CglOddHole::createRowList(int numberRows, const int * whichRow)
653 : {
654 0 : suitableRows_=new int [numberRows];
655 0 : numberRows_=numberRows;
656 0 : memcpy(suitableRows_,whichRow,numberRows*sizeof(int));
657 0 : }
658 :
659 : // Create a list of extra row cliques which may not be in matrix
660 : // At present these are classical cliques
661 : void CglOddHole::createCliqueList(int numberCliques, const int * cliqueStart,
662 0 : const int * cliqueMember)
663 : {
664 0 : numberCliques_=numberCliques;
665 0 : startClique_=new int[numberCliques_+1];
666 0 : memcpy(startClique_,cliqueStart,(numberCliques_+1)*sizeof(int));
667 0 : int length=startClique_[numberCliques_];
668 0 : member_=new int[length];
669 0 : memcpy(member_,cliqueMember,length*sizeof(int));
670 0 : }
671 : // Returns how many rows might give three cycle cuts
672 0 : int CglOddHole::numberPossible()
673 : {
674 0 : int i,n=0;
675 0 : for (i=0;i<numberRows_;i++) {
676 0 : if (suitableRows_[i]) n++;
677 : }
678 0 : return n;
679 : }
680 :
681 :
682 : //-------------------------------------------------------------------
683 : // Default Constructor
684 : //-------------------------------------------------------------------
685 10 : CglOddHole::CglOddHole ()
686 : :
687 : CglCutGenerator(),
688 : epsilon_(1.0e-08),
689 10 : onetol_(1-epsilon_)
690 : {
691 : // null copy of suitable rows
692 10 : numberRows_=0;
693 10 : suitableRows_=NULL;
694 10 : startClique_=NULL;
695 10 : numberCliques_=0;
696 10 : member_=NULL;
697 10 : minimumViolation_=0.001;
698 10 : minimumViolationPer_=0.0003;
699 10 : maximumEntries_=100;
700 10 : }
701 :
702 : //-------------------------------------------------------------------
703 : // Copy constructor
704 : //-------------------------------------------------------------------
705 : CglOddHole::CglOddHole (
706 0 : const CglOddHole & source)
707 : :
708 : CglCutGenerator(source),
709 : epsilon_(source.epsilon_),
710 0 : onetol_(source.onetol_)
711 : {
712 : // copy list of suitable rows
713 0 : numberRows_=source.numberRows_;
714 0 : if (numberRows_) {
715 0 : suitableRows_=new int[numberRows_];
716 0 : memcpy(suitableRows_,source.suitableRows_,numberRows_*sizeof(int));
717 : } else {
718 0 : suitableRows_=NULL;
719 : }
720 : // copy list of cliques
721 0 : numberCliques_=source.numberCliques_;
722 0 : if (numberCliques_) {
723 0 : startClique_=new int[numberCliques_+1];
724 0 : memcpy(startClique_,source.startClique_,(numberCliques_+1)*sizeof(int));
725 0 : int length=startClique_[numberCliques_];
726 0 : member_=new int[length];
727 0 : memcpy(member_,source.member_,length*sizeof(int));
728 : } else {
729 0 : startClique_=NULL;
730 0 : member_=NULL;
731 : }
732 0 : minimumViolation_=source.minimumViolation_;
733 0 : minimumViolationPer_=source.minimumViolationPer_;
734 0 : maximumEntries_=source.maximumEntries_;
735 0 : }
736 :
737 : //-------------------------------------------------------------------
738 : // Clone
739 : //-------------------------------------------------------------------
740 : CglCutGenerator *
741 0 : CglOddHole::clone() const
742 : {
743 0 : return new CglOddHole(*this);
744 : }
745 :
746 : //-------------------------------------------------------------------
747 : // Destructor
748 : //-------------------------------------------------------------------
749 10 : CglOddHole::~CglOddHole ()
750 : {
751 : // free memory
752 10 : delete [] suitableRows_;
753 10 : delete [] startClique_;
754 10 : delete [] member_;
755 10 : }
756 :
757 : //----------------------------------------------------------------
758 : // Assignment operator
759 : //-------------------------------------------------------------------
760 : CglOddHole &
761 : CglOddHole::operator=(
762 0 : const CglOddHole& rhs)
763 : {
764 0 : if (this != &rhs) {
765 0 : CglCutGenerator::operator=(rhs);
766 0 : epsilon_=rhs.epsilon_;
767 0 : onetol_=rhs.onetol_;
768 0 : delete [] suitableRows_;
769 : // copy list of suitable rows
770 0 : numberRows_=rhs.numberRows_;
771 0 : suitableRows_=new int[numberRows_];
772 0 : memcpy(suitableRows_,rhs.suitableRows_,numberRows_*sizeof(int));
773 0 : delete [] startClique_;
774 0 : delete [] member_;
775 : // copy list of cliques
776 0 : numberCliques_=rhs.numberCliques_;
777 0 : if (numberCliques_) {
778 0 : startClique_=new int[numberCliques_+1];
779 0 : memcpy(startClique_,rhs.startClique_,(numberCliques_+1)*sizeof(int));
780 0 : int length=startClique_[numberCliques_];
781 0 : member_=new int[length];
782 0 : memcpy(member_,rhs.member_,length*sizeof(int));
783 : } else {
784 0 : startClique_=NULL;
785 0 : member_=NULL;
786 : }
787 0 : minimumViolation_=rhs.minimumViolation_;
788 0 : minimumViolationPer_=rhs.minimumViolationPer_;
789 0 : maximumEntries_=rhs.maximumEntries_;
790 : }
791 0 : return *this;
792 : }
793 : // Minimum violation
794 : double
795 0 : CglOddHole::getMinimumViolation() const
796 : {
797 0 : return minimumViolation_;
798 : }
799 : void
800 0 : CglOddHole::setMinimumViolation(double value)
801 : {
802 0 : if (value>1.0e-8&&value<=0.5)
803 0 : minimumViolation_=value;
804 0 : }
805 : // Minimum violation per entry
806 : double
807 0 : CglOddHole::getMinimumViolationPer() const
808 : {
809 0 : return minimumViolationPer_;
810 : }
811 : void
812 0 : CglOddHole::setMinimumViolationPer(double value)
813 : {
814 0 : if (value>1.0e-8&&value<=0.25)
815 0 : minimumViolationPer_=value;
816 0 : }
817 : // Maximum number of entries in a cut
818 : int
819 0 : CglOddHole::getMaximumEntries() const
820 : {
821 0 : return maximumEntries_;
822 : }
823 : void
824 0 : CglOddHole::setMaximumEntries(int value)
825 : {
826 0 : if (value>2)
827 0 : maximumEntries_=value;
828 0 : }
829 :
830 : // This can be used to refresh any inforamtion
831 : void
832 0 : CglOddHole::refreshSolver(OsiSolverInterface * solver)
833 : {
834 84 : }
|
