# SCIP

Solving Constraint Integer Programs

presol_tworowbnd.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
7 /* fuer Informationstechnik Berlin */
8 /* */
10 /* */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file presol_tworowbnd.c
17  * @brief do bound tightening by using two rows
18  * @author Dieter Weninger
19  *
20  * Perform bound tightening on two inequalities with some common variables.
21  *
22  * Let two constraints be given:
23  * \f{eqnarray*}{
24  * A_{iR} x_R + A_{iS} x_S \geq b_i\\
25  * A_{kR} x_R + A_{kT} x_T \geq b_k
26  * \f}
27  * with \f$N\f$ the set of variable indexes, \f$R \subseteq N\f$, \f$S \subseteq N\f$, \f$T \subseteq N\f$,
28  * \f$R \cap S = \emptyset\f$, \f$R \cap T = \emptyset\f$, \f$S \cap T = \emptyset\f$ and \f$i \not= k\f$.
29  *
30  * Solve the following two LPs
31  * \f{eqnarray*}{
32  * L = \min \{ A_{kR} x_R : A_{iR} x_R + A_{iS} x_S \geq b_i \}\\
33  * U = \max \{ A_{kR} x_R : A_{iR} x_R + A_{iS} x_S \geq b_i \}
34  * \f}
35  * and use \f$L\f$ and \f$U\f$ for getting bounds on \f$x_T\f$.
36  *
37  * If \f$L + \mbox{infimum}(A_{kT}x_T) \geq b_k\f$, then the second constraint above is redundant.
38  */
39
40 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
41
42 #include <stdio.h>
43 #include <assert.h>
44 #include <string.h>
45
46 #include "scip/pub_matrix.h"
47 #include "presol_tworowbnd.h"
48
49 #define PRESOL_NAME "tworowbnd"
50 #define PRESOL_DESC "do bound tigthening by using two rows"
51 #define PRESOL_PRIORITY -500000 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
52 #define PRESOL_MAXROUNDS 0 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
53 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
54
55 #define SUPPORT_THRESHOLD 0.5 /**< threshold for two constraints overlap */
56 #define FASTMODE_THRESHOLD 1000 /**< max number of baserows for switching to fast mode */
57
58 /* uncomment the following define to debug solving the small LPs */
59 /* #define DEBUG_WRITE_CHECK_LPS */
60
61 /** type of bound change */
63 {
67 };
68 typedef enum Bndchgtype BNDCHGTYPE;
69
70 /*
71  * Local methods
72  */
73
74 #ifdef DEBUG_WRITE_CHECK_LPS
75 /** write min and max LP to file */
76 static
77 void writeLPs(
78  SCIP* scip, /**< SCIP data structure */
79  SCIP_MATRIX* matrix, /**< constraint matrix object */
80  int otherrow, /**< other row index */
81  int numoverlap, /**< overlap-size */
82  int* overlapidx, /**< overlap column indexes */
83  int* othernonoverlapidx, /**< other row non overlap indexes */
84  SCIP_Real* coefbaseoverlap, /**< base row overlap coefficients */
85  SCIP_Real* coefotheroverlap, /**< other row overlap coefficients */
86  SCIP_Real* coefothernonoverlap,/**< other row non overlap coefficients */
87  SCIP_Real* lowerbds, /**< lower bounds */
88  SCIP_Real* upperbds /**< upper bounds */
89  )
90 {
91  FILE* filemax;
92  FILE* filemin;
93  SCIP_Real lhs;
94  int i;
95  int nothernonolap;
96
97  lhs = SCIPmatrixGetRowLhs(matrix, otherrow);
98
99  filemax = fopen("max.lp", "wt");
100  filemin = fopen("min.lp", "wt");
101  if( filemax != NULL && filemin != NULL )
102  {
103  fprintf(filemax, "max\n\t");
104  fprintf(filemin, "min\n\t");
105
106  for( i = 0; i < numoverlap; i++ )
107  {
108  if( coefbaseoverlap[i] > 0.0 )
109  {
110  fprintf(filemax, "+%.24f %s ", coefbaseoverlap[i], SCIPvarGetName(SCIPmatrixGetVar(matrix, overlapidx[i])));
111  fprintf(filemin, "+%.24f %s ", coefbaseoverlap[i], SCIPvarGetName(SCIPmatrixGetVar(matrix, overlapidx[i])));
112  }
113  else
114  {
115  fprintf(filemax, "%.24f %s ", coefbaseoverlap[i], SCIPvarGetName(SCIPmatrixGetVar(matrix, overlapidx[i])));
116  fprintf(filemin, "%.24f %s ", coefbaseoverlap[i], SCIPvarGetName(SCIPmatrixGetVar(matrix, overlapidx[i])));
117  }
118  }
119
120  fprintf(filemax, "\ns.t.\n\t");
121  fprintf(filemin, "\ns.t.\n\t");
122
123  for( i = 0; i < numoverlap; i++ )
124  {
125  if( coefotheroverlap[i] > 0.0 )
126  {
127  fprintf(filemax, "+%.24f %s ", coefotheroverlap[i], SCIPvarGetName(SCIPmatrixGetVar(matrix, overlapidx[i])));
128  fprintf(filemin, "+%.24f %s ", coefotheroverlap[i], SCIPvarGetName(SCIPmatrixGetVar(matrix, overlapidx[i])));
129  }
130  else
131  {
132  fprintf(filemax, "%.24f %s ", coefotheroverlap[i], SCIPvarGetName(SCIPmatrixGetVar(matrix, overlapidx[i])));
133  fprintf(filemin, "%.24f %s ", coefotheroverlap[i], SCIPvarGetName(SCIPmatrixGetVar(matrix, overlapidx[i])));
134  }
135  }
136
137  nothernonolap = SCIPmatrixGetRowNNonzs(matrix, otherrow) - numoverlap;
138
139  for( i = 0; i < nothernonolap; i++ )
140  {
141  if( coefothernonoverlap[i] > 0.0 )
142  {
143  fprintf(filemax, "+%.24f %s ", coefothernonoverlap[i], SCIPvarGetName(SCIPmatrixGetVar(matrix, othernonoverlapidx[i])));
144  fprintf(filemin, "+%.24f %s ", coefothernonoverlap[i], SCIPvarGetName(SCIPmatrixGetVar(matrix, othernonoverlapidx[i])));
145  }
146  else
147  {
148  fprintf(filemax, "%.24f %s ", coefothernonoverlap[i], SCIPvarGetName(SCIPmatrixGetVar(matrix, othernonoverlapidx[i])));
149  fprintf(filemin, "%.24f %s ", coefothernonoverlap[i], SCIPvarGetName(SCIPmatrixGetVar(matrix, othernonoverlapidx[i])));
150  }
151  }
152  fprintf(filemax, " >= %.24f\n", lhs);
153  fprintf(filemin, " >= %.24f\n", lhs);
154
155  fprintf(filemax, "bounds\n");
156  fprintf(filemin, "bounds\n");
157
158  for( i = 0; i < numoverlap; i++ )
159  {
160  if( !SCIPisInfinity(scip, -lowerbds[overlapidx[i]]) && !SCIPisInfinity(scip, upperbds[overlapidx[i]]) )
161  {
162  fprintf(filemax, "\t%.24f <= %s <= %.24f\n", lowerbds[overlapidx[i]],
163  SCIPvarGetName(SCIPmatrixGetVar(matrix, overlapidx[i])), upperbds[overlapidx[i]]);
164  fprintf(filemin, "\t%.24f <= %s <= %.24f\n", lowerbds[overlapidx[i]],
165  SCIPvarGetName(SCIPmatrixGetVar(matrix, overlapidx[i])), upperbds[overlapidx[i]]);
166  }
167  else if( !SCIPisInfinity(scip, -lowerbds[overlapidx[i]]) )
168  {
169  fprintf(filemax, "\t%.24f <= %s\n", lowerbds[overlapidx[i]], SCIPvarGetName(SCIPmatrixGetVar(matrix, overlapidx[i])));
170  fprintf(filemin, "\t%.24f <= %s\n", lowerbds[overlapidx[i]], SCIPvarGetName(SCIPmatrixGetVar(matrix, overlapidx[i])));
171  }
172  else if( !SCIPisInfinity(scip, upperbds[overlapidx[i]]) )
173  {
174  fprintf(filemax, "\t%s <= %.24f\n", SCIPvarGetName(SCIPmatrixGetVar(matrix, overlapidx[i])), upperbds[overlapidx[i]]);
175  fprintf(filemin, "\t%s <= %.24f\n", SCIPvarGetName(SCIPmatrixGetVar(matrix, overlapidx[i])), upperbds[overlapidx[i]]);
176  }
177  }
178
179  for( i = 0; i < nothernonolap; i++ )
180  {
181  if( !SCIPisInfinity(scip, -lowerbds[othernonoverlapidx[i]]) && !SCIPisInfinity(scip, upperbds[othernonoverlapidx[i]]) )
182  {
183  fprintf(filemax, "\t%.24f <= %s <= %.24f\n", lowerbds[othernonoverlapidx[i]],
184  SCIPvarGetName(SCIPmatrixGetVar(matrix, othernonoverlapidx[i])), upperbds[othernonoverlapidx[i]]);
185  fprintf(filemin, "\t%.24f <= %s <= %.24f\n", lowerbds[othernonoverlapidx[i]],
186  SCIPvarGetName(SCIPmatrixGetVar(matrix, othernonoverlapidx[i])), upperbds[othernonoverlapidx[i]]);
187  }
188  else if( !SCIPisInfinity(scip, -lowerbds[othernonoverlapidx[i]]) )
189  {
190  fprintf(filemax, "\t%.24f <= %s\n", lowerbds[othernonoverlapidx[i]],
191  SCIPvarGetName(SCIPmatrixGetVar(matrix, othernonoverlapidx[i])));
192  fprintf(filemin, "\t%.24f <= %s\n", lowerbds[othernonoverlapidx[i]],
193  SCIPvarGetName(SCIPmatrixGetVar(matrix, othernonoverlapidx[i])));
194  }
195  else if( !SCIPisInfinity(scip, upperbds[othernonoverlapidx[i]]) )
196  {
197  fprintf(filemax, "\t%s <= %.24f\n", SCIPvarGetName(SCIPmatrixGetVar(matrix, othernonoverlapidx[i])), upperbds[othernonoverlapidx[i]]);
198  fprintf(filemin, "\t%s <= %.24f\n", SCIPvarGetName(SCIPmatrixGetVar(matrix, othernonoverlapidx[i])), upperbds[othernonoverlapidx[i]]);
199  }
200  }
201
202
203  fprintf(filemax, "end\n");
204  fprintf(filemin, "end\n");
205
206  fclose(filemax);
207  fclose(filemin);
208  }
209  else
210  SCIPABORT();
211 }
212 #endif
213
214
215 /** solve two LPs with one row (single constraint) each
216  *
217  * a1x + a3y >= b1 (other row)
218  * a2x + a4z >= b2 (base row)
219  *
220  * minact = min{a2x : a1x + a3y >= b1}
221  * maxact = max{a2x : a1x + a3y >= b1}
222  */
223 static
225  SCIP* scip, /**< SCIP data structure */
226  SCIP_MATRIX* matrix, /**< constraint matrix object */
227  int baserow, /**< base row index */
228  int otherrow, /**< other row index */
229  int numoverlap, /**< overlap-size */
230  int* overlapidx, /**< overlap column indexes */
231  int* othernonoverlapidx, /**< other row non overlap indexes */
232  SCIP_Real* coefbaseoverlap, /**< base row overlap coefficients */
233  SCIP_Real* coefotheroverlap, /**< other row overlap coefficients */
234  SCIP_Real* coefothernonoverlap,/**< other row non overlap coefficients */
235  SCIP_Real* lowerbds, /**< lower bounds */
236  SCIP_Real* upperbds, /**< upper bounds */
237  SCIP_Real* tmplowerbds, /**< tmp lower bounds */
238  SCIP_Real* tmpupperbds, /**< tmp upper bounds */
239  SCIP_Real* minratios, /**< min LP ratios */
240  SCIP_Real* maxratios, /**< max LP ratios */
241  int* minsortedidx, /**< min LP sorted indexes */
242  int* maxsortedidx, /**< max LP sorted indexes */
243  SCIP_Real* minact, /**< calculated overlap minimal activity w.r.t. to the other row */
244  SCIP_Real* maxact /**< calculated overlap maximal activity w.r.t. to the other row */
245  )
246 {/*lint --e{715}*/
247  SCIP_Real val;
248  int nothernonoverlap;
249  SCIP_Real lhs;
250  SCIP_Real minlhs;
251  SCIP_Real maxlhs;
252  SCIP_Bool consred;
253  int nminratios;
254  int nmaxratios;
255  int i;
256
257  *minact = 0;
258  *maxact = 0;
259
260 #ifdef DEBUG_WRITE_CHECK_LPS
261  SCIPmatrixPrintRow(scip,matrix,baserow);
262  SCIPmatrixPrintRow(scip,matrix,otherrow);
263  writeLPs(scip, matrix, otherrow, numoverlap, overlapidx, othernonoverlapidx,
264  coefbaseoverlap, coefotheroverlap, coefothernonoverlap, lowerbds, upperbds);
265 #endif
266
267  lhs = SCIPmatrixGetRowLhs(matrix, otherrow);
268  assert(!SCIPisInfinity(scip, -lhs));
269
270  nothernonoverlap = SCIPmatrixGetRowNNonzs(matrix, otherrow) - numoverlap;
271  val = 0;
272  consred = FALSE;
273
274  /* compute maximal contribution of non-overlap part of the
275  single constraint to the activity.
276  maybe the single constraint is redundant */
277  for( i = 0; i < nothernonoverlap; i++ )
278  {
279  if( coefothernonoverlap[i] < 0.0 )
280  {
281  if( SCIPisInfinity(scip, -lowerbds[othernonoverlapidx[i]]) )
282  {
283  consred = TRUE;
284  break;
285  }
286  else
287  {
288  val += coefothernonoverlap[i] * lowerbds[othernonoverlapidx[i]];
289  }
290  }
291  else if( coefothernonoverlap[i] > 0.0 )
292  {
293  if( SCIPisInfinity(scip, upperbds[othernonoverlapidx[i]]) )
294  {
295  consred = TRUE;
296  break;
297  }
298  else
299  {
300  val += coefothernonoverlap[i] * upperbds[othernonoverlapidx[i]];
301  }
302  }
303  }
304
305  if( !consred )
306  {
307  SCIP_Real minlowerbnd;
308  minlowerbnd = SCIPinfinity(scip);
309
310  /* we want that every coefficient in the single constraint
311  has a negative sign and hence we need to multiply
312  some columns by -1 */
313  for( i = 0; i < numoverlap; i++ )
314  {
315  tmplowerbds[i] = lowerbds[overlapidx[i]];
316  tmpupperbds[i] = upperbds[overlapidx[i]];
317
318  if( coefotheroverlap[i] > 0.0 )
319  {
320  /* multiply column by -1 and swap bounds */
321  double tmp;
322  tmp = tmplowerbds[i];
323  tmplowerbds[i] = -tmpupperbds[i];
324  tmpupperbds[i] = -tmp;
325
326  coefotheroverlap[i] = -coefotheroverlap[i];
327  coefbaseoverlap[i] = -coefbaseoverlap[i];
328  }
329
330  if( tmplowerbds[i] < minlowerbnd )
331  {
332  if( SCIPisInfinity(scip, -tmplowerbds[i]) )
333  {
334  /* lower bounds have to be finite for later boundshift */
335  *minact = -SCIPinfinity(scip);
336  *maxact = SCIPinfinity(scip);
337  return;
338  }
339  minlowerbnd = tmplowerbds[i];
340  }
341  }
342
343  if( minlowerbnd < 0.0 )
344  {
345  SCIP_Real bndshift = -minlowerbnd;
346  if( bndshift > (SCIP_Real)SCIP_LONGINT_MAX )
347  {
348  /* shift value is too large */
349  *minact = -SCIPinfinity(scip);
350  *maxact = SCIPinfinity(scip);
351  return;
352  }
353  }
354
355  /* init left hand side values and consider non-overlapping contribution */
356  minlhs = lhs - val;
357  nminratios = 0;
358  maxlhs = lhs - val;
359  nmaxratios = 0;
360
361  if( minlowerbnd < 0.0 )
362  {
363  double bndshift = -minlowerbnd;
364  if( bndshift > (double)SCIP_LONGINT_MAX )
365  {
366  /* shift value is too large */
367  *minact = -SCIPinfinity(scip);
368  *maxact = SCIPinfinity(scip);
369  return;
370  }
371
372  /* shift polyhedra into the positive orthant */
373  for( i = 0; i < numoverlap; i++ )
374  {
375  minlhs += coefotheroverlap[i] * bndshift;
376  *minact -= coefbaseoverlap[i] * bndshift;
377
378  maxlhs += coefotheroverlap[i] * bndshift;
379  *maxact -= coefbaseoverlap[i] * bndshift;
380
381  tmplowerbds[i] += bndshift;
382  tmpupperbds[i] += bndshift;
383
384  assert(tmplowerbds[i] >= 0.0);
385  }
386  }
387
388  /*
389  * solve minimization LP
390  *
391  * we distinguish two column cases:
392  *
393  * a) b)
394  * min - min +
395  * s.t. - s.t. -
396  */
397
398  for( i = 0; i < numoverlap; i++ )
399  {
400  if( coefbaseoverlap[i] > 0.0 )
401  {
402  /* b): fix variable to its lower bound */
403  minlhs -= coefotheroverlap[i] * tmplowerbds[i];
404  *minact += coefbaseoverlap[i] * tmplowerbds[i];
405  }
406  else
407  {
408  /* a): save coefficient ratios for later sorting */
409  minratios[nminratios] = coefbaseoverlap[i] / coefotheroverlap[i];
410  minsortedidx[nminratios] = i;
411  nminratios++;
412
413  /* consider lower bounds for left hand side and obj value */
414  minlhs -= coefotheroverlap[i] * tmplowerbds[i];
415  *minact += coefbaseoverlap[i] * tmplowerbds[i];
416  }
417  }
418
419  /* sort the ratios for case a) */
420  if( nminratios > 1 )
421  SCIPsortRealInt(minratios, minsortedidx, nminratios);
422
423  /* pack every variable on the highest possible value as long as we are feasible */
424  for( i = nminratios-1; 0 <= i; i-- )
425  {
426  SCIP_Real tmpval;
427
428  /* consider contribution from lower bounds */
429  if( tmplowerbds[minsortedidx[i]] > 0 )
430  {
431  *minact -= coefbaseoverlap[minsortedidx[i]] * tmplowerbds[minsortedidx[i]];
432  minlhs += coefotheroverlap[minsortedidx[i]] * tmplowerbds[minsortedidx[i]];
433  }
434
435  /* calculate highest possible variable value */
436  tmpval = minlhs / coefotheroverlap[minsortedidx[i]];
437  if( tmpval < tmplowerbds[minsortedidx[i]] )
438  {
439  /* infeasible */
440  *minact = -SCIPinfinity(scip);
441  break;
442  }
443
444  /* if the upper bound is large enough we are ready
445  otherwise we set the variable to its upper bound and iterate */
446  if( tmpval <= tmpupperbds[minsortedidx[i]] )
447  {
448  *minact += coefbaseoverlap[minsortedidx[i]] * tmpval;
449  break;
450  }
451  else
452  {
453  *minact += coefbaseoverlap[minsortedidx[i]] * tmpupperbds[minsortedidx[i]];
454  minlhs -= coefotheroverlap[minsortedidx[i]] * tmpupperbds[minsortedidx[i]];
455  }
456  }
457
458
459  /*
460  * solve maximization LP
461  *
462  * we distinguish two column cases:
463  *
464  * c) d)
465  * max + max -
466  * s.t. - s.t. -
467  */
468  for( i = 0; i < numoverlap; i++ )
469  {
470  if( coefbaseoverlap[i] < 0.0 )
471  {
472  /* d): fix variable to its lower bound */
473  maxlhs -= coefotheroverlap[i] * tmplowerbds[i];
474  *maxact += coefbaseoverlap[i] * tmplowerbds[i];
475  }
476  else
477  {
478  /* c): save coefficient ratios for later sorting */
479  maxratios[nmaxratios] = coefbaseoverlap[i] / coefotheroverlap[i];
480  maxsortedidx[nmaxratios] = i;
481  nmaxratios++;
482
483  /* consider lower bounds for left hand side and obj value */
484  maxlhs -= coefotheroverlap[i] * tmplowerbds[i];
485  *maxact += coefbaseoverlap[i] * tmplowerbds[i];
486  }
487  }
488
489  /* sort the ratios for case a) */
490  if( nmaxratios > 1 )
491  SCIPsortRealInt(maxratios, maxsortedidx, nmaxratios);
492
493  /* pack every variable on the highest possible value as long as we are feasible */
494  for( i = 0; i < nmaxratios; i++ )
495  {
496  SCIP_Real tmpval;
497
498  /* consider contribution from lower bounds */
499  if( tmplowerbds[maxsortedidx[i]] > 0 )
500  {
501  *maxact -= coefbaseoverlap[maxsortedidx[i]] * tmplowerbds[maxsortedidx[i]];
502  maxlhs += coefotheroverlap[maxsortedidx[i]] * tmplowerbds[maxsortedidx[i]];
503  }
504
505  /* calculate highest possible variable value */
506  tmpval = maxlhs / coefotheroverlap[maxsortedidx[i]];
507  if( tmpval < tmplowerbds[maxsortedidx[i]] )
508  {
509  /* infeasible */
510  *maxact = SCIPinfinity(scip);
511  break;
512  }
513
514  /* if the upper bound is large enough we are ready
515  otherwise we set the variable to its upper bound and iterate */
516  if( tmpval <= tmpupperbds[maxsortedidx[i]] )
517  {
518  *maxact += coefbaseoverlap[maxsortedidx[i]] * tmpval;
519  break;
520  }
521  else
522  {
523  *maxact += coefbaseoverlap[maxsortedidx[i]] * tmpupperbds[maxsortedidx[i]];
524  maxlhs -= coefotheroverlap[maxsortedidx[i]] * tmpupperbds[maxsortedidx[i]];
525  }
526  }
527  }
528  else
529  {
530  /* single constraint is redundant.
531  we calculate the value of the objective function */
532
533  /* minimization LP */
534  for( i = 0; i < numoverlap; i++ )
535  {
536  if( coefbaseoverlap[i] > 0.0 )
537  {
538  if( !SCIPisInfinity(scip, -lowerbds[overlapidx[i]]) )
539  {
540  *minact += coefbaseoverlap[i] * lowerbds[overlapidx[i]];
541  }
542  else
543  {
544  *minact = -SCIPinfinity(scip);
545  break;
546  }
547  }
548  else if( coefbaseoverlap[i] < 0.0 )
549  {
550  if( !SCIPisInfinity(scip, upperbds[overlapidx[i]]) )
551  {
552  *minact += coefbaseoverlap[i] * upperbds[overlapidx[i]];
553  }
554  else
555  {
556  *minact = -SCIPinfinity(scip);
557  break;
558  }
559  }
560  }
561
562  /* maximization LP */
563  for( i = 0; i < numoverlap; i++ )
564  {
565  if( coefbaseoverlap[i] > 0.0 )
566  {
567  if( !SCIPisInfinity(scip, upperbds[overlapidx[i]]) )
568  {
569  *maxact += coefbaseoverlap[i] * upperbds[overlapidx[i]];
570  }
571  else
572  {
573  *maxact = SCIPinfinity(scip);
574  break;
575  }
576  }
577  else if( coefbaseoverlap[i] < 0.0 )
578  {
579  if( !SCIPisInfinity(scip, -lowerbds[overlapidx[i]]) )
580  {
581  *maxact += coefbaseoverlap[i] * lowerbds[overlapidx[i]];
582  }
583  else
584  {
585  *maxact = SCIPinfinity(scip);
586  break;
587  }
588  }
589  }
590  }
591
592 #ifdef DEBUG_WRITE_CHECK_LPS
593  {
594  SCIP_Real minsolve = 0.0;
595  SCIP* subscip;
596  SCIP_SOL* sol;
597  SCIP_STATUS status;
598  SCIP_VAR** vars;
599  int nvars;
600  int objnonzeros = 0;
601  SCIP_CALL_ABORT( SCIPcreate(&subscip) );
603  SCIP_CALL_ABORT( SCIPreadProb(subscip, "min.lp", NULL) );
604  SCIP_CALL_ABORT( SCIPsetIntParam(subscip,"presolving/maxrounds",0) );
605  vars = SCIPgetVars(subscip);
606  nvars = SCIPgetNVars(subscip);
607  for(i=0; i< nvars; i++)
608  {
609  if(SCIPvarGetObj(vars[i]) != 0.0)
610  objnonzeros++;
611  }
612  assert(numoverlap == objnonzeros);
613
614  SCIP_CALL_ABORT( SCIPsolve(subscip) );
615  status = SCIPgetStatus(subscip);
616  if(SCIP_STATUS_OPTIMAL == status)
617  {
618  sol = SCIPgetBestSol(subscip);
619  minsolve = SCIPgetSolOrigObj(subscip, sol);
620  assert(SCIPisEQ(scip,minsolve,*minact));
621  }
622  else
623  {
624  assert(SCIPisEQ(scip,-SCIPinfinity(scip),*minact));
625  }
626  SCIP_CALL_ABORT( SCIPfree(&subscip) );
627  }
628  {
629  SCIP_Real maxsolve = 0.0;
630  SCIP* subscip;
631  SCIP_SOL* sol;
632  SCIP_STATUS status;
633  SCIP_CALL_ABORT( SCIPcreate(&subscip) );
635  SCIP_CALL_ABORT( SCIPreadProb(subscip, "max.lp", NULL) );
636  SCIP_CALL_ABORT( SCIPsetIntParam(subscip,"presolving/maxrounds",0) );
637  SCIP_CALL_ABORT( SCIPsolve(subscip) );
638  status = SCIPgetStatus(subscip);
639  if(SCIP_STATUS_OPTIMAL == status)
640  {
641  sol = SCIPgetBestSol(subscip);
642  maxsolve = SCIPgetSolOrigObj(subscip, sol);
643  assert(SCIPisEQ(scip,maxsolve,*maxact));
644  }
645  else
646  {
647  assert(SCIPisEQ(scip,SCIPinfinity(scip),*maxact));
648  }
649  SCIP_CALL_ABORT( SCIPfree(&subscip) );
650  }
651 #endif
652 }/*lint !e438*/
653
654 /** calculate min activity */
655 static
657  SCIP* scip, /**< SCIP data structure */
658  int len, /**< length */
659  int* varidxs, /**< variables indexes */
660  SCIP_Real* coefs, /**< coefficients */
661  SCIP_Real* lowerbds, /**< lower bounds */
662  SCIP_Real* upperbds /**< upper bounds */
663  )
664 {
665  SCIP_Real infimum;
666  int i;
667
668  infimum = 0;
669
670  for( i = 0; i < len; i++ )
671  {
672  if( coefs[i] > 0.0 )
673  {
674  if( SCIPisInfinity(scip, -lowerbds[varidxs[i]]) )
675  {
676  infimum = -SCIPinfinity(scip);
677  break;
678  }
679  else
680  {
681  infimum += coefs[i] * lowerbds[varidxs[i]];
682  }
683  }
684  else
685  {
686  if( SCIPisInfinity(scip, upperbds[varidxs[i]]) )
687  {
688  infimum = -SCIPinfinity(scip);
689  break;
690  }
691  else
692  {
693  infimum += coefs[i] * upperbds[varidxs[i]];
694  }
695  }
696  }
697
698  return infimum;
699 }
700
701 /** calculate max activity */
702 static
704  SCIP* scip, /**< SCIP data structure */
705  int len, /**< length */
706  int* varidxs, /**< variable indexes */
707  SCIP_Real* coefs, /**< coefficients */
708  SCIP_Real* lowerbds, /**< lower bounds */
709  SCIP_Real* upperbds, /**< upper bounds */
710  int* infcnt /**< infinity counter */
711  )
712 {
713  SCIP_Real supremum;
714  int i;
715
716  *infcnt = 0;
717  supremum = 0;
718
719  for( i = 0; i < len; i++ )
720  {
721  if( coefs[i] < 0.0 )
722  {
723  if( SCIPisInfinity(scip, -lowerbds[varidxs[i]]) )
724  (*infcnt)++;
725  else
726  supremum += coefs[i] * lowerbds[varidxs[i]];
727  }
728  else
729  {
730  if( SCIPisInfinity(scip, upperbds[varidxs[i]]) )
731  (*infcnt)++;
732  else
733  supremum += coefs[i] * upperbds[varidxs[i]];
734  }
735  }
736
737  if(*infcnt > 0)
738  supremum = SCIPinfinity(scip);
739
740  return supremum;
741 }
742
743 /** get max activity without one column */
744 static
746  SCIP* scip, /**< SCIP data structure */
747  int len, /**< length */
748  int* varidxs, /**< variable indexes */
749  SCIP_Real* coefs, /**< coefficients */
750  SCIP_Real* lowerbds, /**< upper bounds */
751  SCIP_Real* upperbds, /**< lower bounds */
752  int idx /**< omitting index */
753  )
754 {
755  SCIP_Real supremum;
756  int i;
757
758  supremum = 0;
759
760  for( i = 0; i < len; i++ )
761  {
762  if( i == idx )
763  continue;
764
765  if( coefs[i] < 0.0 )
766  {
767  assert(!SCIPisInfinity(scip, -lowerbds[varidxs[i]]));
768  supremum += coefs[i] * lowerbds[varidxs[i]];
769  }
770  else
771  {
772  assert(!SCIPisInfinity(scip, upperbds[varidxs[i]]));
773  supremum += coefs[i] * upperbds[varidxs[i]];
774  }
775  }
776
777  return supremum;
778 }
779
780 /** apply bound tightening on two overlapping constraints */
781 static
783  SCIP* scip, /**< SCIP data structure */
784  SCIP_MATRIX* matrix, /**< constraint matrix object */
785  int baserow, /**< base row index */
786  int otherrow, /**< other row index */
787  int numoverlap, /**< overlap-size */
788  int* overlapidx, /**< overlap column indexes */
789  int* othernonoverlapidx, /**< other row non overlap indexes */
790  int* basenonoverlapidx, /**< base row non overlap indexes */
791  SCIP_Real* coefbaseoverlap, /**< base row overlap coefficients */
792  SCIP_Real* coefotheroverlap, /**< other row overlap coefficients */
793  SCIP_Real* coefbasenonoverlap, /**< base row non overlap coefficients */
794  SCIP_Real* coefothernonoverlap,/**< other row non overlap coefficients */
795  SCIP_Real* lowerbds, /**< lower bounds */
796  SCIP_Real* upperbds, /**< upper bounds */
797  SCIP_Real* tmplowerbds, /**< tmp lower bounds */
798  SCIP_Real* tmpupperbds, /**< tmp upper bounds */
799  SCIP_Real* minratios, /**< min LP ratios */
800  SCIP_Real* maxratios, /**< max LP ratios */
801  int* minsortedidx, /**< min LP sorted indexes */
802  int* maxsortedidx, /**< max LP sorted indexes */
803  int* ntightenbnds, /**< number of tightened bounds */
804  BNDCHGTYPE* tighten, /**< tightened bounds */
805  int* ndeletecons, /**< number of redundant constraints */
806  SCIP_Bool* deletecons /**< redundant constraints */
807  )
808 {
809  SCIP_Real maxactoverlap;
810  SCIP_Real minactoverlap;
811  SCIP_Real minactnonoverlap;
812  SCIP_Real maxactnonoverlap;
813  int len;
814  SCIP_Real lhs;
815  int i;
816
817  getActivities(scip, matrix, baserow, otherrow, numoverlap, overlapidx, othernonoverlapidx,
818  coefbaseoverlap, coefotheroverlap, coefothernonoverlap,
819  lowerbds, upperbds, tmplowerbds, tmpupperbds, minratios, maxratios,
820  minsortedidx, maxsortedidx, &minactoverlap, &maxactoverlap);
821
822  len = SCIPmatrixGetRowNNonzs(matrix, baserow) - numoverlap;
823  lhs = SCIPmatrixGetRowLhs(matrix, baserow);
824
825  if( !SCIPisInfinity(scip, -minactoverlap) )
826  {
827  /* detect redundant constraints */
828  minactnonoverlap = getMinActivity(scip, len, basenonoverlapidx, coefbasenonoverlap, lowerbds, upperbds);
829  if( !SCIPisInfinity(scip, -minactnonoverlap) )
830  {
831  if( SCIPisGE(scip, minactoverlap + minactnonoverlap, lhs) )
832  {
833  if( !deletecons[baserow] )
834  {
835  (*ndeletecons)++;
836  deletecons[baserow] = TRUE;
837  }
838  }
839  }
840  }
841
842  if( !SCIPisInfinity(scip, maxactoverlap) )
843  {
844  int infcnt;
845  SCIP_Real bnd;
846  SCIP_Real tmpsup;
847
848  /* bound tightening */
849  maxactnonoverlap = getMaxActivity(scip, len, basenonoverlapidx, coefbasenonoverlap, lowerbds, upperbds, &infcnt);
850  if( !SCIPisInfinity(scip, maxactnonoverlap) )
851  {
852  for( i = 0; i < len; i++ )
853  {
854  if( coefbasenonoverlap[i] < 0.0 )
855  {
856  /* get ub */
857  tmpsup = maxactnonoverlap - (coefbasenonoverlap[i] * lowerbds[basenonoverlapidx[i]]);
858  bnd = (lhs - (tmpsup + maxactoverlap)) / coefbasenonoverlap[i];
859  if( bnd < upperbds[basenonoverlapidx[i]] )
860  {
861  upperbds[basenonoverlapidx[i]] = bnd;
862  if( tighten[basenonoverlapidx[i]] != UPPERBOUND && tighten[basenonoverlapidx[i]] != BOTHBOUNDS )
863  {
864  (*ntightenbnds)++;
865  if( tighten[basenonoverlapidx[i]] == LOWERBOUND )
866  tighten[basenonoverlapidx[i]] = BOTHBOUNDS;
867  else
868  tighten[basenonoverlapidx[i]] = UPPERBOUND;
869  }
870  }
871  }
872  else
873  {
874  /* get lb */
875  tmpsup = maxactnonoverlap - (coefbasenonoverlap[i] * upperbds[basenonoverlapidx[i]]);
876  bnd = (lhs - (tmpsup + maxactoverlap)) / coefbasenonoverlap[i];
877  if( bnd > lowerbds[basenonoverlapidx[i]] )
878  {
879  lowerbds[basenonoverlapidx[i]] = bnd;
880  if( tighten[basenonoverlapidx[i]] != LOWERBOUND && tighten[basenonoverlapidx[i]] != BOTHBOUNDS )
881  {
882  (*ntightenbnds)++;
883  if( tighten[basenonoverlapidx[i]] == UPPERBOUND )
884  tighten[basenonoverlapidx[i]] = BOTHBOUNDS;
885  else
886  tighten[basenonoverlapidx[i]] = LOWERBOUND;
887  }
888  }
889  }
890  }
891  }
892  /* maximal activity in non-overlapping variables is +infinity */
893  else
894  {
895  /* we can only do bound tightening, if we have exactly one infinite contribution*/
896  if( infcnt == 1 )
897  {
898  for( i = 0; i < len; i++ )
899  {
900  if( coefbasenonoverlap[i] < 0.0 )
901  {
902  if( SCIPisInfinity(scip, -lowerbds[basenonoverlapidx[i]]) )
903  {
904  /* get ub */
905  tmpsup = getMaxResActivity(scip, len, basenonoverlapidx, coefbasenonoverlap, lowerbds, upperbds, i);
906  assert(!SCIPisInfinity(scip, tmpsup));
907  bnd = (lhs - (tmpsup + maxactoverlap)) / coefbasenonoverlap[i];
908  if( bnd < upperbds[basenonoverlapidx[i]] )
909  {
910  upperbds[basenonoverlapidx[i]] = bnd;
911  if( tighten[basenonoverlapidx[i]] != UPPERBOUND && tighten[basenonoverlapidx[i]] != BOTHBOUNDS )
912  {
913  (*ntightenbnds)++;
914  if( tighten[basenonoverlapidx[i]] == LOWERBOUND )
915  tighten[basenonoverlapidx[i]] = BOTHBOUNDS;
916  else
917  tighten[basenonoverlapidx[i]] = UPPERBOUND;
918  }
919  }
920  }
921  }
922  else
923  {
924  if( infcnt == 1 && SCIPisInfinity(scip, upperbds[basenonoverlapidx[i]]) )
925  {
926  /* get lb */
927  tmpsup = getMaxResActivity(scip, len, basenonoverlapidx, coefbasenonoverlap, lowerbds, upperbds, i);
928  assert(!SCIPisInfinity(scip, tmpsup));
929  bnd = (lhs - (tmpsup + maxactoverlap)) / coefbasenonoverlap[i];
930  if( bnd > lowerbds[basenonoverlapidx[i]] )
931  {
932  lowerbds[basenonoverlapidx[i]] = bnd;
933  if( tighten[basenonoverlapidx[i]] != LOWERBOUND && tighten[basenonoverlapidx[i]] != BOTHBOUNDS )
934  {
935  (*ntightenbnds)++;
936  if( tighten[basenonoverlapidx[i]] == UPPERBOUND )
937  tighten[basenonoverlapidx[i]] = BOTHBOUNDS;
938  else
939  tighten[basenonoverlapidx[i]] = LOWERBOUND;
940  }
941  }
942  }
943  }
944  }
945  }
946  }
947  }
948 }
949
950 /** extract coefficients from matrix */
951 static
953  SCIP* scip, /**< SCIP data structure */
954  SCIP_MATRIX* matrix, /**< constraint matrix object */
955  int baserow, /**< base row index */
956  int otherrow, /**< other row index */
957  int numoverlap, /**< overlap-size */
958  int* olapidxbaseorder, /**< overlap column indexes in baserow order */
959  int* olapidxotherorder, /**< overlap column indexes in otherrow order */
960  int* othernonoverlapidx, /**< other row non overlap indexes */
961  int* basenonoverlapidx, /**< base row non overlap indexes */
962  SCIP_Real* coefbaseoverlap, /**< base row overlap coefficients */
963  SCIP_Real* coefotheroverlap, /**< other row overlap coefficients */
964  SCIP_Real* coefbasenonoverlap, /**< base row non overlap coefficients */
965  SCIP_Real* coefothernonoverlap /**< other row non overlap coefficients */
966  )
967 {
968  SCIP_Real* valpnt;
969  int* rowpnt;
970  int* rowend;
971  int baserowcnt;
972  int otherrowcnt;
973  int olapcnt;
974  int nonolapcnt;
975
976  /* get number of columns in the rows */
977  baserowcnt = SCIPmatrixGetRowNNonzs(matrix, baserow);
978  otherrowcnt = SCIPmatrixGetRowNNonzs(matrix, otherrow);
979  assert(baserowcnt != 0 && otherrowcnt != 0);
980
981 #if 1 /* @todo why do we need this? */
982  /* set end marker */
983  if( numoverlap < SCIPmatrixGetNColumns(matrix) )
984  {
985  olapidxbaseorder[numoverlap] = -1;
986  olapidxotherorder[numoverlap] = -1;
987  }
988 #endif
989
990  olapcnt = 0;
991  nonolapcnt = 0;
992
993  /* partition columns of base row into overlapping columns and non-overlapping columns (w.r.t. other row) and store
994  * the corresponding coefficients
995  */
996  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, baserow);
997  rowend = rowpnt + baserowcnt;
998  valpnt = SCIPmatrixGetRowValPtr(matrix, baserow);
999
1000  for( ; rowpnt < rowend; rowpnt++, valpnt++ )
1001  {
1002  if( olapidxbaseorder[olapcnt] == *rowpnt )
1003  {
1004  coefbaseoverlap[olapcnt] = *valpnt;
1005  olapcnt++;
1006  }
1007  else
1008  {
1009  basenonoverlapidx[nonolapcnt] = *rowpnt;
1010  coefbasenonoverlap[nonolapcnt] = *valpnt;
1011  nonolapcnt++;
1012  }
1013  }
1014
1015  assert(olapcnt+nonolapcnt == baserowcnt);
1016  assert(olapcnt == numoverlap);
1017  assert(nonolapcnt > 0);
1018
1019  olapcnt = 0;
1020  nonolapcnt = 0;
1021
1022  /* partition columns of other row into overlapping columns and non-overlapping columns (w.r.t. base row) and store
1023  * the corresponding coefficients
1024  */
1025  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, otherrow);
1026  rowend = rowpnt + otherrowcnt;
1027  valpnt = SCIPmatrixGetRowValPtr(matrix, otherrow);
1028
1029  for( ; rowpnt < rowend; rowpnt++, valpnt++ )
1030  {
1031  if( olapidxotherorder[olapcnt] == *rowpnt )
1032  {
1033  coefotheroverlap[olapcnt] = *valpnt;
1034  olapcnt++;
1035  }
1036  else
1037  {
1038  othernonoverlapidx[nonolapcnt] = *rowpnt;
1039  coefothernonoverlap[nonolapcnt] = *valpnt;
1040  nonolapcnt++;
1041  }
1042  }
1043
1044  assert(olapcnt+nonolapcnt == otherrowcnt);
1045  assert(olapcnt == numoverlap);
1046 }
1047
1048 /** calculate overlap-size */
1049 static
1051  SCIP* scip, /**< SCIP data structure */
1052  SCIP_MATRIX* matrix, /**< constraint matrix object */
1053  int baserow, /**< base row index */
1054  int otherrow, /**< other row index */
1055  int* countings, /**< overlap counting helper array */
1056  int* clearinfo, /**< reset helper array */
1057  int* numoverlap, /**< overlap-size */
1058  int* olapidxotherorder /**< overlap column indexes in otherrow order */
1059  )
1060 {
1061  int* rowpnt;
1062  int* rowend;
1063  int noverlap;
1064  int baserowcnt;
1065  int otherrowcnt;
1066  int nclear;
1067  int i;
1068
1069  noverlap = 0;
1070  nclear = 0;
1071
1072  baserowcnt = SCIPmatrixGetRowNNonzs(matrix, baserow);
1073  otherrowcnt = SCIPmatrixGetRowNNonzs(matrix, otherrow);
1074  if( baserowcnt == 0 || otherrowcnt == 0 )
1075  {
1076  *numoverlap = noverlap;
1077  return;
1078  }
1079
1080  /* set flags corresponding to baserow non-zeros */
1081  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, baserow);
1082  rowend = rowpnt + baserowcnt;
1083  for( ; rowpnt < rowend; rowpnt++ )
1084  {
1085  countings[*rowpnt] = 1;
1086  clearinfo[nclear] = *rowpnt;
1087  nclear++;
1088  }
1089
1090  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, otherrow);
1091  rowend = rowpnt + otherrowcnt;
1092  for( ; rowpnt < rowend; rowpnt++ )
1093  {
1094  if( countings[*rowpnt] == 1 )
1095  {
1096  /* collect overlapping indexes in otherrow order */
1097  olapidxotherorder[noverlap] = *rowpnt;
1098  noverlap++;
1099  }
1100  }
1101
1102  for( i = 0; i < nclear; i++ )
1103  countings[clearinfo[i]] = 0;
1104
1105  *numoverlap = noverlap;
1106 }
1107
1108 static
1110  SCIP* scip, /**< SCIP data structure */
1111  SCIP_MATRIX* matrix, /**< constraint matrix object */
1112  int baserow, /**< base row index */
1113  int otherrow, /**< other row index */
1114  int* countings, /**< overlap counting helper array */
1115  int* clearinfo, /**< reset helper array */
1116  int numoverlap, /**< just calculated overlap-size */
1117  int* olapidxbaseorder /**< overlap column indexes in baserow order */
1118  )
1119 {
1120  int* rowpnt;
1121  int* rowend;
1122  int noverlap;
1123  int baserowcnt;
1124  int otherrowcnt;
1125  int nclear;
1126  int i;
1127
1128  noverlap = 0;
1129  nclear = 0;
1130
1131  baserowcnt = SCIPmatrixGetRowNNonzs(matrix, baserow);
1132  otherrowcnt = SCIPmatrixGetRowNNonzs(matrix, otherrow);
1133
1134  /* set flags corresponding to otherrow non-zeros */
1135  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, otherrow);
1136  rowend = rowpnt + otherrowcnt;
1137  for( ; rowpnt < rowend; rowpnt++ )
1138  {
1139  countings[*rowpnt] = 1;
1140  clearinfo[nclear] = *rowpnt;
1141  nclear++;
1142  }
1143
1144  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, baserow);
1145  rowend = rowpnt + baserowcnt;
1146  for( ; rowpnt < rowend; rowpnt++ )
1147  {
1148  if( countings[*rowpnt] == 1 )
1149  {
1150  /* collect overlapping indexes in baserow order */
1151  olapidxbaseorder[noverlap] = *rowpnt;
1152  noverlap++;
1153  }
1154  }
1155
1156  for( i = 0; i < nclear; i++ )
1157  countings[clearinfo[i]] = 0;
1158
1159  assert(noverlap == numoverlap);
1160 }
1161
1162
1163 /** perform bound tightening on two rows with a specific support intersection */
1164 static
1166  SCIP* scip, /**< SCIP data structure */
1167  SCIP_MATRIX* matrix, /**< constraint matrix object */
1168  int nbaserows, /**< number of base rows */
1169  int* baserows, /**< base rows indexes */
1170  SCIP_Real* lowerbds, /**< lower bounds */
1171  SCIP_Real* upperbds, /**< upper bounds */
1172  int* ntightenbnds, /**< number of tightened bounds */
1173  BNDCHGTYPE* tighten, /**< bound tighten information */
1174  int* ndeletecons, /**< number of redundant constraints */
1175  SCIP_Bool* deletecons /**< redundant constraints */
1176  )
1177 {
1178  int* rowpnt;
1179  int* rowend;
1180  int rowcnt;
1181  int br;
1182  int col;
1183  int* colpnt;
1184  int* colend;
1185  int colcnt;
1186  int numoverlap;
1187  int* olapidxbaseorder;
1188  int* olapidxotherorder;
1189  SCIP_Real threshold;
1190  int rowcnt2;
1191  int nrows;
1192  int ncols;
1193  int* othernonoverlapidx;
1194  int* basenonoverlapidx;
1195  SCIP_Real* coefbaseoverlap;
1196  SCIP_Real* coefotheroverlap;
1197  SCIP_Real* coefbasenonoverlap;
1198  SCIP_Real* coefothernonoverlap;
1199  int* countings;
1200  int* clearinfo;
1201  SCIP_Real* tmplowerbds;
1202  SCIP_Real* tmpupperbds;
1203  SCIP_Real* minratios;
1204  SCIP_Real* maxratios;
1205  int* minsortedidx;
1206  int* maxsortedidx;
1207  SCIP_Bool usefastmode;
1208  int* ignorerowidx;
1209  SCIP_Bool* ignorerow;
1210  int ignorerowcnt;
1211  int i;
1212
1213  nrows = SCIPmatrixGetNRows(matrix);
1214  ncols = SCIPmatrixGetNColumns(matrix);
1215
1216  SCIP_CALL( SCIPallocBufferArray(scip, &olapidxbaseorder, ncols) );
1217  SCIP_CALL( SCIPallocBufferArray(scip, &olapidxotherorder, ncols) );
1218  SCIP_CALL( SCIPallocBufferArray(scip, &othernonoverlapidx, ncols) );
1219  SCIP_CALL( SCIPallocBufferArray(scip, &basenonoverlapidx, ncols) );
1220  SCIP_CALL( SCIPallocBufferArray(scip, &coefbaseoverlap, ncols) );
1221  SCIP_CALL( SCIPallocBufferArray(scip, &coefotheroverlap, ncols) );
1222  SCIP_CALL( SCIPallocBufferArray(scip, &coefbasenonoverlap, ncols) );
1223  SCIP_CALL( SCIPallocBufferArray(scip, &coefothernonoverlap, ncols) );
1224  SCIP_CALL( SCIPallocBufferArray(scip, &countings, ncols) );
1225  BMSclearMemoryArray(countings, ncols);
1226  SCIP_CALL( SCIPallocBufferArray(scip, &clearinfo, ncols) );
1227  SCIP_CALL( SCIPallocBufferArray(scip, &tmplowerbds, ncols) );
1228  SCIP_CALL( SCIPallocBufferArray(scip, &tmpupperbds, ncols) );
1229  SCIP_CALL( SCIPallocBufferArray(scip, &minratios, ncols) );
1230  SCIP_CALL( SCIPallocBufferArray(scip, &maxratios, ncols) );
1231  SCIP_CALL( SCIPallocBufferArray(scip, &minsortedidx, ncols) );
1232  SCIP_CALL( SCIPallocBufferArray(scip, &maxsortedidx, ncols) );
1233  SCIP_CALL( SCIPallocBufferArray(scip, &ignorerowidx, nrows) );
1234  SCIP_CALL( SCIPallocBufferArray(scip, &ignorerow, nrows) );
1235  BMSclearMemoryArray(ignorerow, nrows);
1236
1237  /* use fast mode if too many base rows are present */
1238  if( nbaserows > FASTMODE_THRESHOLD )
1239  usefastmode = TRUE;
1240  else
1241  usefastmode = FALSE;
1242
1243  for( br = 0; br < nbaserows; br++ )
1244  {
1245  ignorerowcnt = 0;
1246
1247  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, baserows[br]);
1248  rowcnt = SCIPmatrixGetRowNNonzs(matrix, baserows[br]);
1249  if( rowcnt == 0 )
1250  continue;
1251
1252  rowend = rowpnt + rowcnt;
1253
1254  for( ; (rowpnt < rowend); rowpnt++ )
1255  {
1256  col = *rowpnt;
1257  colpnt = SCIPmatrixGetColIdxPtr(matrix, col);
1258  colcnt = SCIPmatrixGetColNNonzs(matrix, col);
1259  colend = colpnt + colcnt;
1260  for( ; (colpnt < colend); colpnt++ )
1261  {
1262  if( *colpnt == baserows[br] || ignorerow[*colpnt] )
1263  continue;
1264
1265  /* we consider only >= constraints */
1266  if( !SCIPmatrixIsRowRhsInfinity(matrix, *colpnt) )
1267  continue;
1268
1269  /* determine overlap-size */
1270  getNumOverlap(scip, matrix, baserows[br], *colpnt,
1271  countings, clearinfo, &numoverlap, olapidxotherorder);
1272
1273  if( numoverlap == 0 )
1274  continue;
1275
1276  rowcnt2 = SCIPmatrixGetRowNNonzs(matrix, *colpnt);
1277  threshold = (SCIP_Real)numoverlap/(SCIP_Real)MIN(rowcnt, rowcnt2);
1278
1279  /* verify if overlap-size is ok */
1280  if( SUPPORT_THRESHOLD <= threshold && numoverlap < rowcnt )
1281  {
1282  getOverlapBaseOrdered(scip, matrix, baserows[br], *colpnt,
1283  countings, clearinfo, numoverlap, olapidxbaseorder);
1284
1285  getCoefficients(scip, matrix, baserows[br], *colpnt, numoverlap,
1286  olapidxbaseorder, olapidxotherorder, othernonoverlapidx, basenonoverlapidx,
1287  coefbaseoverlap, coefotheroverlap, coefbasenonoverlap, coefothernonoverlap);
1288
1289  applyTightening(scip, matrix, baserows[br], *colpnt, numoverlap, olapidxotherorder,
1290  othernonoverlapidx, basenonoverlapidx,
1291  coefbaseoverlap, coefotheroverlap, coefbasenonoverlap, coefothernonoverlap,
1292  lowerbds, upperbds, tmplowerbds, tmpupperbds, minratios, maxratios,
1293  minsortedidx, maxsortedidx, ntightenbnds, tighten, ndeletecons, deletecons);
1294  }
1295
1296  ignorerow[*colpnt] = TRUE;
1297  ignorerowidx[ignorerowcnt] = *colpnt;
1298  ignorerowcnt++;
1299
1300  if( usefastmode )
1301  break;
1302  }
1303
1304  if( usefastmode )
1305  break;
1306  }
1307
1308  for( i = 0; i < ignorerowcnt; i++ )
1309  ignorerow[ignorerowidx[i]] = FALSE;
1310  }
1311
1312  SCIPfreeBufferArray(scip, &ignorerow);
1313  SCIPfreeBufferArray(scip, &ignorerowidx);
1314  SCIPfreeBufferArray(scip, &maxsortedidx);
1315  SCIPfreeBufferArray(scip, &minsortedidx);
1316  SCIPfreeBufferArray(scip, &maxratios);
1317  SCIPfreeBufferArray(scip, &minratios);
1318  SCIPfreeBufferArray(scip, &tmpupperbds);
1319  SCIPfreeBufferArray(scip, &tmplowerbds);
1320  SCIPfreeBufferArray(scip, &clearinfo);
1321  SCIPfreeBufferArray(scip, &countings);
1322  SCIPfreeBufferArray(scip, &coefothernonoverlap);
1323  SCIPfreeBufferArray(scip, &coefbasenonoverlap);
1324  SCIPfreeBufferArray(scip, &coefotheroverlap);
1325  SCIPfreeBufferArray(scip, &coefbaseoverlap);
1326  SCIPfreeBufferArray(scip, &basenonoverlapidx);
1327  SCIPfreeBufferArray(scip, &othernonoverlapidx);
1328  SCIPfreeBufferArray(scip, &olapidxotherorder);
1329  SCIPfreeBufferArray(scip, &olapidxbaseorder);
1330
1331  return SCIP_OKAY;
1332 }
1333
1334 /** determine base rows */
1335 static
1337  SCIP* scip, /**< SCIP main data structure */
1338  SCIP_MATRIX* matrix, /**< constraint matrix */
1339  int* nbaserows, /**< number of present base rows */
1340  int* baserows /**< indexes of base rows */
1341  )
1342 {
1343  int nrows;
1344  int fill;
1345  int r;
1346
1347  assert(scip != NULL);
1348  assert(matrix != NULL);
1349  assert(nbaserows != NULL);
1350  assert(baserows != NULL);
1351
1352  nrows = SCIPmatrixGetNRows(matrix);
1353
1354  fill = 0;
1355  for( r = 0; r < nrows; r++ )
1356  {
1357  if( !SCIPmatrixIsRowRhsInfinity(matrix, r) )
1358  continue;
1359
1360  baserows[fill] = r;
1361  fill++;
1362  }
1363
1364  *nbaserows = fill;
1365
1366  return SCIP_OKAY;
1367 }
1368
1369 /** get bounds of variables */
1370 static
1372  SCIP* scip, /**< SCIP main data structure */
1373  SCIP_MATRIX* matrix, /**< constraint matrix */
1374  SCIP_Real* lowerbds, /**< lower bounds */
1375  SCIP_Real* upperbds /**< upper bounds */
1376  )
1377 {
1378  int c;
1379  int ncols;
1380
1381  assert(scip != NULL);
1382  assert(matrix != NULL);
1383  assert(lowerbds != NULL);
1384  assert(upperbds != NULL);
1385
1386  ncols = SCIPmatrixGetNColumns(matrix);
1387
1388  for( c = 0; c < ncols; c++ )
1389  {
1390  SCIP_VAR* var;
1391  var = SCIPmatrixGetVar(matrix, c);
1392  lowerbds[c] = SCIPvarGetLbGlobal(var);
1393  upperbds[c] = SCIPvarGetUbGlobal(var);
1394  }
1395 }
1396
1397 /*
1398  * Callback methods of presolver
1399  */
1400
1401 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1402 static
1403 SCIP_DECL_PRESOLCOPY(presolCopyTworowbnd)
1404 { /*lint --e{715}*/
1405  assert(scip != NULL);
1406  assert(presol != NULL);
1407  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
1408
1409  /* call inclusion method of presolver */
1411
1412  return SCIP_OKAY;
1413 }
1414
1415 /** execution method of presolver */
1416 static
1417 SCIP_DECL_PRESOLEXEC(presolExecTworowbnd)
1418 { /*lint --e{715}*/
1419  SCIP_MATRIX* matrix;
1420  SCIP_Bool initialized;
1421  SCIP_Bool complete;
1422
1423  assert(result != NULL);
1424  *result = SCIP_DIDNOTRUN;
1425
1427  return SCIP_OKAY;
1428
1430  return SCIP_OKAY;
1431
1432  *result = SCIP_DIDNOTFIND;
1433
1434  matrix = NULL;
1435  SCIP_CALL( SCIPmatrixCreate(scip, &matrix, &initialized, &complete) );
1436
1437  if( initialized && complete )
1438  {
1439  int* baserows;
1440  int nbaserows;
1441  int ntightenbnds;
1442  BNDCHGTYPE* tighten;
1443  int ndeletecons;
1444  SCIP_Bool* deletecons;
1445  int ncols;
1446  int nrows;
1447  SCIP_Real* lowerbds;
1448  SCIP_Real* upperbds;
1449
1450  ncols = SCIPmatrixGetNColumns(matrix);
1451  nrows = SCIPmatrixGetNRows(matrix);
1452
1453  ntightenbnds = 0;
1454  ndeletecons = 0;
1455
1456  SCIP_CALL( SCIPallocBufferArray(scip, &baserows, nrows) );
1457
1458  SCIP_CALL( SCIPallocBufferArray(scip, &tighten, ncols) );
1459  BMSclearMemoryArray(tighten, ncols);
1460
1461  SCIP_CALL( SCIPallocBufferArray(scip, &lowerbds, ncols) );
1462  SCIP_CALL( SCIPallocBufferArray(scip, &upperbds, ncols) );
1463  getBounds(scip, matrix, lowerbds, upperbds);
1464
1465  SCIP_CALL( SCIPallocBufferArray(scip, &deletecons, nrows) );
1466  BMSclearMemoryArray(deletecons, nrows);
1467
1468  SCIP_CALL( getBaseRows(scip, matrix, &nbaserows, baserows) );
1469
1470  SCIP_CALL( calcTwoRowBnds(scip, matrix,
1471  nbaserows, baserows, lowerbds, upperbds,
1472  &ntightenbnds, tighten, &ndeletecons, deletecons) );
1473
1474  if( ntightenbnds > 0 )
1475  {
1476  int c;
1477  SCIP_VAR* var;
1478  SCIP_Bool infeas;
1479  SCIP_Bool tightened;
1480
1481  for( c = 0; c < ncols; c++ )
1482  {
1483  if( tighten[c] == LOWERBOUND )
1484  {
1485  var = SCIPmatrixGetVar(matrix, c);
1486  SCIP_CALL( SCIPtightenVarLb(scip, var, lowerbds[c], FALSE, &infeas, &tightened) );
1487  if( tightened )
1488  ++(*nchgbds);
1489  }
1490  else if( tighten[c] == UPPERBOUND )
1491  {
1492  var = SCIPmatrixGetVar(matrix, c);
1493  SCIP_CALL( SCIPtightenVarUb(scip, var, upperbds[c], FALSE, &infeas, &tightened) );
1494  if( tightened )
1495  ++(*nchgbds);
1496  }
1497  else if( tighten[c] == BOTHBOUNDS )
1498  {
1499  var = SCIPmatrixGetVar(matrix, c);
1500  SCIP_CALL( SCIPtightenVarLb(scip, var, lowerbds[c], FALSE, &infeas, &tightened) );
1501  if( tightened )
1502  ++(*nchgbds);
1503  SCIP_CALL( SCIPtightenVarUb(scip, var, upperbds[c], FALSE, &infeas, &tightened) );
1504  if( tightened )
1505  ++(*nchgbds);
1506  }
1507  }
1508  }
1509
1510  if( ndeletecons > 0 )
1511  {
1512  int r;
1513  for( r = 0; r < nrows; r++ )
1514  {
1515  if( deletecons[r] )
1516  {
1517  SCIP_CONS* cons;
1518  cons = SCIPmatrixGetCons(matrix, r);
1519  SCIP_CALL( SCIPdelCons(scip, cons) );
1520
1521  (*ndelconss)++;
1522  }
1523  }
1524  }
1525
1526  SCIPfreeBufferArray(scip, &deletecons);
1527  SCIPfreeBufferArray(scip, &upperbds);
1528  SCIPfreeBufferArray(scip, &lowerbds);
1529  SCIPfreeBufferArray(scip, &tighten);
1530  SCIPfreeBufferArray(scip, &baserows);
1531  }
1532
1533  SCIPmatrixFree(scip, &matrix);
1534
1535  return SCIP_OKAY;
1536 }
1537
1538 /*
1539  * presolver specific interface methods
1540  */
1541
1542 /** creates the tworowbnd presolver and includes it in SCIP */
1544  SCIP* scip /**< SCIP data structure */
1545  )
1546 {
1547  SCIP_PRESOL* presol;
1548
1549  /* include presolver */
1551  PRESOL_TIMING, presolExecTworowbnd, NULL) );
1552  SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyTworowbnd) );
1553
1554  return SCIP_OKAY;
1555 }
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
Definition: scip.c:6854
void SCIPmatrixPrintRow(SCIP *scip, SCIP_MATRIX *matrix, int row)
Definition: matrix.c:845
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1325
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22118
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1397
enum Bndchgtype BNDCHGTYPE
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:814
static void getActivities(SCIP *scip, SCIP_MATRIX *matrix, int baserow, int otherrow, int numoverlap, int *overlapidx, int *othernonoverlapidx, SCIP_Real *coefbaseoverlap, SCIP_Real *coefotheroverlap, SCIP_Real *coefothernonoverlap, SCIP_Real *lowerbds, SCIP_Real *upperbds, SCIP_Real *tmplowerbds, SCIP_Real *tmpupperbds, SCIP_Real *minratios, SCIP_Real *maxratios, int *minsortedidx, int *maxsortedidx, SCIP_Real *minact, SCIP_Real *maxact)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17166
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1525
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12481
static void getOverlapBaseOrdered(SCIP *scip, SCIP_MATRIX *matrix, int baserow, int otherrow, int *countings, int *clearinfo, int numoverlap, int *olapidxbaseorder)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45803
static SCIP_DECL_PRESOLEXEC(presolExecTworowbnd)
SCIP_RETCODE SCIPincludePresolTworowbnd(SCIP *scip)
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:782
static SCIP_Real getMaxResActivity(SCIP *scip, int len, int *varidxs, SCIP_Real *coefs, SCIP_Real *lowerbds, SCIP_Real *upperbds, int idx)
#define FALSE
Definition: def.h:64
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip.c:5655
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
static SCIP_RETCODE calcTwoRowBnds(SCIP *scip, SCIP_MATRIX *matrix, int nbaserows, int *baserows, SCIP_Real *lowerbds, SCIP_Real *upperbds, int *ntightenbnds, BNDCHGTYPE *tighten, int *ndeletecons, SCIP_Bool *deletecons)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip.c:22234
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45751
#define SCIP_LONGINT_MAX
Definition: def.h:121
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
static SCIP_DECL_PRESOLCOPY(presolCopyTworowbnd)
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip.c:696
SCIP_RETCODE SCIPmatrixCreate(SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool *initialized, SCIP_Bool *complete)
Definition: matrix.c:430
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1373
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17176
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1407
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip.c:15777
SCIP_RETCODE SCIPreadProb(SCIP *scip, const char *filename, const char *extension)
Definition: scip.c:9998
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip.c:921
Bndchgtype
static void getNumOverlap(SCIP *scip, SCIP_MATRIX *matrix, int baserow, int otherrow, int *countings, int *clearinfo, int *numoverlap, int *olapidxotherorder)
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1361
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
SCIP_Bool SCIPisNLPEnabled(SCIP *scip)
Definition: scip.c:30797
#define NULL
Definition: lpi_spx1.cpp:137
#define SCIP_CALL(x)
Definition: def.h:306
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1349
#define SUPPORT_THRESHOLD
#define PRESOL_MAXROUNDS
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
#define PRESOL_NAME
#define SCIP_Bool
Definition: def.h:61
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:57
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1245
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip.c:4625
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:553
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17014
#define FASTMODE_THRESHOLD
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip.c:38090
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
public methods for matrix
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35033
do bound tightening by using two rows
int SCIPgetNVars(SCIP *scip)
Definition: scip.c:11631
#define PRESOL_TIMING
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip.c:38931
SCIP_Bool SCIPmatrixIsRowRhsInfinity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1431
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip.c:6889
static void getCoefficients(SCIP *scip, SCIP_MATRIX *matrix, int baserow, int otherrow, int numoverlap, int *olapidxbaseorder, int *olapidxotherorder, int *othernonoverlapidx, int *basenonoverlapidx, SCIP_Real *coefbaseoverlap, SCIP_Real *coefotheroverlap, SCIP_Real *coefbasenonoverlap, SCIP_Real *coefothernonoverlap)
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip.c:11586
static SCIP_RETCODE getBaseRows(SCIP *scip, SCIP_MATRIX *matrix, int *nbaserows, int *baserows)
static void applyTightening(SCIP *scip, SCIP_MATRIX *matrix, int baserow, int otherrow, int numoverlap, int *overlapidx, int *othernonoverlapidx, int *basenonoverlapidx, SCIP_Real *coefbaseoverlap, SCIP_Real *coefotheroverlap, SCIP_Real *coefbasenonoverlap, SCIP_Real *coefothernonoverlap, SCIP_Real *lowerbds, SCIP_Real *upperbds, SCIP_Real *tmplowerbds, SCIP_Real *tmpupperbds, SCIP_Real *minratios, SCIP_Real *maxratios, int *minsortedidx, int *maxsortedidx, int *ntightenbnds, BNDCHGTYPE *tighten, int *ndeletecons, SCIP_Bool *deletecons)
#define SCIP_Real
Definition: def.h:135
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define MIN(x, y)
Definition: memory.c:75
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:85
#define SCIP_CALL_ABORT(x)
Definition: def.h:285
#define SCIPABORT()
Definition: def.h:278
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1269
#define PRESOL_PRIORITY
static void getBounds(SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real *lowerbds, SCIP_Real *upperbds)
static SCIP_Real getMaxActivity(SCIP *scip, int len, int *varidxs, SCIP_Real *coefs, SCIP_Real *lowerbds, SCIP_Real *upperbds, int *infcnt)
#define PRESOL_DESC
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip.c:774
static SCIP_Real getMinActivity(SCIP *scip, int len, int *varidxs, SCIP_Real *coefs, SCIP_Real *lowerbds, SCIP_Real *upperbds)
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1257