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