Scippy

SCIP

Solving Constraint Integer Programs

presol_dualcomp.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 /* */
6 /* Copyright (C) 2002-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file presol_dualcomp.c
17  * @brief dual compensation presolver
18  * @author Dieter Weninger
19  *
20  * This presolver looks for variables with
21  * i) objcoef >= 0 and exactly one downlock
22  * ii) objcoef <= 0 and exactly one uplock
23  * and fixes the variable in case i) at the lower bound and in case ii) at the
24  * upper bound if a combination of singleton continuous variables can compensate
25  * the downlock in case i) and the uplock in case ii).
26  */
27 
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
29 
30 #include <stdio.h>
31 #include <assert.h>
32 #include <string.h>
33 
34 #include "scip/pub_matrix.h"
35 #include "presol_dualcomp.h"
36 
37 #define PRESOL_NAME "dualcomp"
38 #define PRESOL_DESC "compensate single up-/downlocks by singleton continuous variables"
39 
40 /* we need singleton continuous variables for the lock compensation,
41  * thus it is presumably a good idea to call this presolver before stuffing, which
42  * fixes singleton continuous variables
43  */
44 #define PRESOL_PRIORITY -50 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
45 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
46 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
47 
48 #define DEFAULT_COMP_ONLY_DIS_VARS FALSE /**< should only discrete variables be compensated? */
49 
50 /*
51  * Data structures
52  */
53 
54 /** control parameters */
55 struct SCIP_PresolData
56 {
57  SCIP_Bool componlydisvars; /**< flag indicating if only discrete variables should be compensated */
58 };
59 
60 /** type of fixing direction */
62 {
63  FIXATLB = -1, /**< fix variable at lower bound */
64  NOFIX = 0, /**< do not fix variable */
65  FIXATUB = 1 /**< fix variable at upper bound */
66 };
68 
69 /** type of variable lock compensation */
71 {
74 };
76 
77 /*
78  * Local methods
79  */
80 
81 /** try to compensate a variable with a single opposite lock
82  by using singleton continuous variables */
83 static
85  SCIP* scip, /**< SCIP main data structure */
86  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
87  int col, /**< variable fixing candidate */
88  int row, /**< row index with opposite lock */
89  SCIP_Real val, /**< value of fixing candidate in the opposite lock constraint */
90  SCIP_Bool twosides, /**< flag indicating that two sides are present */
91  LOCKCOMPENSATION compensation, /**< type of lock compensation */
92  FIXINGDIRECTION* varstofix, /**< array holding fixing information */
93  int* nfixings /**< number of possible fixings */
94  )
95 {
96  SCIP_Real* valpnt;
97  int* rowpnt;
98  int* rowend;
99  SCIP_VAR* var;
100  int colidx;
101  SCIP_Real coef;
102  SCIP_Real lhs;
103  SCIP_Real delta;
104  SCIP_Bool trytofix;
105  SCIP_Real lb;
106  SCIP_Real ub;
107  SCIP_Bool deltaisinf;
108  SCIP_Real ratio;
109  SCIP_Bool multrowbyminusone;
110  SCIP_Bool singleton;
111  SCIP_Real offset;
112 
113  assert(scip != NULL);
114  assert(matrix != NULL);
115  assert(0 <= col && col < SCIPmatrixGetNColumns(matrix));
116  assert(0 <= row && row < SCIPmatrixGetNRows(matrix));
117  assert(compensation == COMPENSATE_DOWNLOCK || compensation == COMPENSATE_UPLOCK);
118  assert(varstofix != NULL);
119  assert(nfixings != NULL);
120 
121  /* the variable for compensation should not be a compensation variable itself */
122  assert(!(SCIPmatrixGetColNNonzs(matrix,col) == 1 && SCIPvarGetType(SCIPmatrixGetVar(matrix,col)) == SCIP_VARTYPE_CONTINUOUS));
123 
124  /* try lock compensation only if minimum one singleton continuous variable is present */
125  singleton = FALSE;
126  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
127  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
128  for( ; rowpnt < rowend; rowpnt++ )
129  {
130  var = SCIPmatrixGetVar(matrix, *rowpnt);
131 
132  if( SCIPmatrixGetColNNonzs(matrix, *rowpnt) == 1 &&
134  SCIPvarGetNLocksUp(var) == SCIPmatrixGetColNUplocks(matrix, *rowpnt) &&
135  SCIPvarGetNLocksDown(var) == SCIPmatrixGetColNDownlocks(matrix, *rowpnt)
136  )
137  {
138  /* minimal one valid compensation variable is present in this row */
139  singleton = TRUE;
140  break;
141  }
142  }
143 
144  /* return if no compensation variable is available */
145  if( !singleton )
146  return SCIP_OKAY;
147 
148 
149  /* we perform the following transformations afterwards:
150  *
151  * lhs <= a1 x1 + a2 x2 + ... an xn <= rhs
152  * with a1, a2, ..., an >= 0.
153  *
154  * for the downlock case we multiply the constraint in thought by (-1)
155  * if the corresponding coefficient is negative.
156  *
157  * we attribute the uplock case to the downlock case by multiplying
158  * in thought the corresponding column by (-1).
159  */
160  multrowbyminusone = FALSE;
161  if( compensation == COMPENSATE_DOWNLOCK )
162  {
163  if( SCIPisLT(scip,val,0.0) )
164  multrowbyminusone = TRUE;
165  }
166  else
167  {
168  assert(compensation == COMPENSATE_UPLOCK);
169 
170  /* in the uplock case we multiply the column in thought by (-1) and
171  * thus we need to multiply the constraint by (-1) to get a positive coefficient
172  */
173  if( SCIPisGT(scip,val,0.0) )
174  multrowbyminusone = TRUE;
175  }
176 
177  /* we need the objective coefficient and constraint coefficient ratio
178  * to later preserve optimality.
179  * further we need to consider multiplications of the constraint by (-1).
180  * for ranged rows and equalities we switch to the rhs.
181  */
182  lhs = SCIPmatrixGetRowLhs(matrix, row);
183  ratio = SCIPvarGetObj( SCIPmatrixGetVar(matrix,col) ) / val;
184  if( multrowbyminusone )
185  {
186  if( twosides )
187  lhs = -SCIPmatrixGetRowRhs(matrix, row);
188  else
189  lhs = -lhs;
190 
191  ratio = -ratio;
192  }
193 
194  offset = 0.0;
195  trytofix = TRUE;
196  delta = 0;
197  deltaisinf = FALSE;
198 
199  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
200  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
201  valpnt = SCIPmatrixGetRowValPtr(matrix, row);
202 
203  for( ; rowpnt < rowend; rowpnt++, valpnt++ )
204  {
205  colidx = *rowpnt;
206  coef = *valpnt;
207  var = SCIPmatrixGetVar(matrix, colidx);
208  lb = SCIPvarGetLbGlobal(var);
209  ub = SCIPvarGetUbGlobal(var);
210 
211  if( colidx == col )
212  {
213  /* this is the variable which we want to compensate */
214 
215  if( compensation == COMPENSATE_DOWNLOCK )
216  {
217  if( SCIPisInfinity(scip, -lb) )
218  {
219  trytofix = FALSE;
220  break;
221  }
222  else
223  {
224  if( multrowbyminusone )
225  offset += (-coef) * lb;
226  else
227  offset += coef * lb;
228  }
229  }
230  else
231  {
232  if( SCIPisInfinity(scip, ub) )
233  {
234  trytofix = FALSE;
235  break;
236  }
237  else
238  {
239  /* for the uplock case we have opposed sign for the coefficient as
240  * in the downlock case.
241  * the multiplication of the column results in swapping the negative bounds.
242  */
243  if( multrowbyminusone )
244  offset += coef * (-ub);
245  else
246  offset += (-coef) * (-ub);
247  }
248  }
249  }
250  else if( SCIPmatrixGetColNNonzs(matrix, colidx) == 1 &&
251  SCIPvarGetNLocksUp(var) == SCIPmatrixGetColNUplocks(matrix, colidx) &&
252  SCIPvarGetNLocksDown(var) == SCIPmatrixGetColNDownlocks(matrix, colidx) &&
254  {
255  /* this is singleton continuous variable and
256  * thus a valid compensation candidate
257  */
258 
259  if( SCIPisLT(scip,coef,0.0) )
260  {
261  /* coef < 0 */
262 
263  if( multrowbyminusone )
264  {
265  if( SCIPisInfinity(scip, -lb) )
266  {
267  trytofix = FALSE;
268  break;
269  }
270 
271  /* we have a negative coefficient and the row is multiplied by (-1)
272  * thus actually we have a positive coefficient
273  */
274  offset += (-coef) * lb;
275 
276  /* only consider singleton continuous variables with a better or the same
277  * obj/coef ratio for preserving optimality
278  */
279  if( SCIPisLE(scip,SCIPvarGetObj(SCIPmatrixGetVar(matrix, colidx))/(-coef), ratio) )
280  {
281  if( SCIPisInfinity(scip, ub) )
282  {
283  deltaisinf = TRUE;
284  break;
285  }
286 
287  /* calculate the contribution to the compensation value */
288  delta += (-coef) * (ub - lb);
289  }
290  }
291  else
292  {
293  if( SCIPisInfinity(scip, ub) )
294  {
295  trytofix = FALSE;
296  break;
297  }
298 
299  /* we have a negative coefficient and hence need to multiply the column by (-1).
300  * this means the bounds swap and change the sign
301  */
302  offset += (-coef) * (-ub);
303 
304  /* only consider singleton continuous variables with a better or the same
305  * obj/coef ratio for preserving optimality
306  */
307  if( SCIPisLE(scip,SCIPvarGetObj(SCIPmatrixGetVar(matrix, colidx))/coef, ratio) )
308  {
309  if( SCIPisInfinity(scip, -lb) )
310  {
311  deltaisinf = TRUE;
312  break;
313  }
314 
315  /* calculate the contribution to the compensation value */
316  delta += (-coef) * (ub - lb);
317  }
318  }
319  }
320  else
321  {
322  /* coef >= 0 */
323 
324  if( multrowbyminusone )
325  {
326  /* we have a positive or zero coefficient and the row is multiplied by (-1) */
327  if( SCIPisInfinity(scip, ub) )
328  {
329  trytofix = FALSE;
330  break;
331  }
332 
333  /* we have a positive or zero coefficient and multiply in thought the constraint
334  * by (-1) thus we have actually a negative coefficient and multiply the column by (-1).
335  * therefore the sign of the coefficient does not change but the bounds swap and change
336  * the sign.
337  */
338  offset += coef * (-ub);
339 
340  /* we have a positive or zero coefficient and multiply in thought the constraint
341  * by (-1) which delivers the ratio.
342  * a further multiplication of the column does not change anything.
343  */
344  if( SCIPisLE(scip,SCIPvarGetObj(SCIPmatrixGetVar(matrix, colidx))/(-coef), ratio) )
345  {
346  if( SCIPisInfinity(scip, -lb) )
347  {
348  deltaisinf = TRUE;
349  break;
350  }
351 
352  /* calculate the contribution to the compensation value */
353  delta += coef * (ub - lb);
354  }
355  }
356  else
357  {
358  if( SCIPisInfinity(scip, -lb) )
359  {
360  trytofix = FALSE;
361  break;
362  }
363 
364  /* we have positive coefficient and do not need to multiply anything by (-1) */
365  offset += coef * lb;
366 
367  if( SCIPisLE(scip,SCIPvarGetObj(SCIPmatrixGetVar(matrix, colidx))/coef, ratio) )
368  {
369  if( SCIPisInfinity(scip, ub) )
370  {
371  deltaisinf = TRUE;
372  break;
373  }
374 
375  /* calculate the contribution to the compensation value */
376  delta += coef * (ub - lb);
377  }
378  }
379  }
380  }
381  else
382  {
383  /* remaining variables */
384 
385  /* the reasons for the following signs are the same as for the singleton
386  * continuous variables
387  */
388  if( SCIPisLT(scip,coef,0.0) )
389  {
390  if( multrowbyminusone )
391  {
392  if( SCIPisInfinity(scip, -lb) )
393  {
394  trytofix = FALSE;
395  break;
396  }
397 
398  offset += (-coef) * lb;
399  }
400  else
401  {
402  if( SCIPisInfinity(scip, ub) )
403  {
404  trytofix = FALSE;
405  break;
406  }
407 
408  offset += (-coef) * (-ub);
409  }
410  }
411  else
412  {
413  if( multrowbyminusone )
414  {
415  if( SCIPisInfinity(scip, ub) )
416  {
417  trytofix = FALSE;
418  break;
419  }
420 
421  offset += coef * (-ub);
422  }
423  else
424  {
425  if( SCIPisInfinity(scip, -lb) )
426  {
427  trytofix = FALSE;
428  break;
429  }
430 
431  offset += coef * lb;
432  }
433  }
434  }
435  }
436 
437  /* avoid fixings to infinite values or fixings of already fixed variables */
438  if( trytofix && varstofix[col] == NOFIX)
439  {
440  /* feasibility is secured if the compensation value delta
441  * is large enough to compensate the value lhs-offset
442  */
443  if( deltaisinf || SCIPisLE(scip, lhs-offset, delta) )
444  {
445  if( compensation == COMPENSATE_UPLOCK )
446  {
447  if( !SCIPisInfinity(scip,SCIPvarGetUbGlobal(SCIPmatrixGetVar(matrix, col))) )
448  {
449  varstofix[col] = FIXATUB;
450  (*nfixings)++;
451 
452 #ifdef SCIP_MORE_DEBUG
453  SCIPmatrixPrintRow(scip, matrix, row);
454  SCIPdebugMsg(scip, "%s, bds=[%.2f,%.2f], obj=%.2f, nnonzs=%d, type=%s, fix=ub, %.1f <= %.1f\n",
457  SCIPmatrixGetColNNonzs(matrix, col),
458  SCIPvarGetType(SCIPmatrixGetVar(matrix, col))==SCIP_VARTYPE_CONTINUOUS ? "con" : "dis",
459  lhs-offset, delta);
460 #endif
461  }
462  }
463  else
464  {
465  if( !SCIPisInfinity(scip,-SCIPvarGetLbGlobal(SCIPmatrixGetVar(matrix, col))) )
466  {
467  varstofix[col] = FIXATLB;
468  (*nfixings)++;
469 
470 #ifdef SCIP_MORE_DEBUG
471  SCIPmatrixPrintRow(scip, matrix, row);
472  SCIPdebugMsg(scip, "%s, bds=[%.2f,%.2f], obj=%.2f, nnonzs=%d, type=%s, fix=lb, %.1f <= %.1f\n",
475  SCIPmatrixGetColNNonzs(matrix, col),
476  SCIPvarGetType(SCIPmatrixGetVar(matrix, col))==SCIP_VARTYPE_CONTINUOUS ? "con" : "dis",
477  lhs-offset, delta);
478 #endif
479  }
480  }
481  }
482  }
483 
484  return SCIP_OKAY;
485 }
486 
487 /*
488  * Callback methods of presolver
489  */
490 
491 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
492 static
493 SCIP_DECL_PRESOLCOPY(presolCopyDualcomp)
494 { /*lint --e{715}*/
495  assert(scip != NULL);
496  assert(presol != NULL);
497  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
498 
499  /* call inclusion method of presolver */
501 
502  return SCIP_OKAY;
503 }
504 
505 /** execution method of presolver */
506 static
507 SCIP_DECL_PRESOLEXEC(presolExecDualcomp)
508 { /*lint --e{715}*/
509  SCIP_PRESOLDATA* presoldata;
510  SCIP_MATRIX* matrix;
511  SCIP_Bool initialized;
512  SCIP_Bool complete;
513 
514  assert(result != NULL);
515  *result = SCIP_DIDNOTRUN;
516 
518  return SCIP_OKAY;
519 
521  return SCIP_OKAY;
522 
523  /* don't run if no compensation variables are present */
524  if( SCIPgetNContVars(scip) == 0 )
525  return SCIP_OKAY;
526 
527  if( !SCIPallowDualReds(scip) )
528  return SCIP_OKAY;
529 
530  *result = SCIP_DIDNOTFIND;
531 
532  presoldata = SCIPpresolGetData(presol);
533  assert(presoldata != NULL);
534 
535  matrix = NULL;
536  SCIP_CALL( SCIPmatrixCreate(scip, &matrix, &initialized, &complete) );
537 
538  /* we only work on pure MIPs currently */
539  if( initialized && complete )
540  {
541  int ncols;
542  int i;
543  SCIP_Real* valpnt;
544  int* colpnt;
545  int* colend;
546  int row;
547  SCIP_VAR* var;
548  SCIP_Bool inspect;
549  SCIP_Real val;
550  FIXINGDIRECTION* varstofix;
551  int nfixings;
552  SCIP_Real lhs;
553  SCIP_Real rhs;
554  SCIP_Bool twosides;
555 
556  ncols = SCIPmatrixGetNColumns(matrix);
557  nfixings = 0;
558 
559  SCIP_CALL( SCIPallocBufferArray(scip, &varstofix, ncols) );
560  BMSclearMemoryArray(varstofix, ncols);
561 
562  for(i = 0; i < ncols; i++)
563  {
564  var = SCIPmatrixGetVar(matrix, i);
565 
566  /* exclude compensation variables itself for compensation */
568  SCIPmatrixGetColNNonzs(matrix, i) == 1 )
569  continue;
570 
571  /* if requested exclude continuous variables for compensation */
572  if( presoldata->componlydisvars && SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
573  continue;
574 
575  /* verifiy that this variable has one uplock and that the uplocks are consistent */
576  if( SCIPvarGetNLocksUp(var) == 1 &&
577  SCIPmatrixGetColNUplocks(matrix, i) == 1 &&
578  SCIPisLE(scip, SCIPvarGetObj(var), 0.0) )
579  {
580  row = -1;
581  val = 0.0;
582  inspect = FALSE;
583  twosides = FALSE;
584  colpnt = SCIPmatrixGetColIdxPtr(matrix, i);
585  colend = colpnt + SCIPmatrixGetColNNonzs(matrix, i);
586  valpnt = SCIPmatrixGetColValPtr(matrix, i);
587 
588  /* search row which causes the uplock */
589  for( ; (colpnt < colend); colpnt++, valpnt++ )
590  {
591  row = *colpnt;
592  val = *valpnt;
593  lhs = SCIPmatrixGetRowLhs(matrix, row);
594  rhs = SCIPmatrixGetRowRhs(matrix, row);
595 
596  if( SCIPisEQ(scip, lhs, rhs) )
597  {
598  /* equation */
599  inspect = TRUE;
600  twosides = TRUE;
601  break;
602  }
603  else if( SCIPmatrixIsRowRhsInfinity(matrix, row) )
604  {
605  /* >= */
606  if( SCIPisLT(scip, val, 0.0) )
607  {
608  inspect = TRUE;
609  break;
610  }
611  }
612  else if( !SCIPisInfinity(scip, -lhs) && !SCIPisInfinity(scip, rhs) )
613  {
614  /* ranged row */
615  inspect = TRUE;
616  twosides = TRUE;
617  break;
618  }
619  }
620 
621  assert(inspect);
622 
623  if( inspect ) /*lint !e774*/
624  {
625  assert(row >= 0);
626  assert(!SCIPisZero(scip, val));
627 
628  /* try to fix variable i at the upper bound */
629  SCIP_CALL( compensateVarLock(scip, matrix, i, row, val,
630  twosides, COMPENSATE_UPLOCK, varstofix, &nfixings) );
631  }
632  }
633  /* verifiy that this variable has one downlock and that the downlocks are consistent */
634  else if( SCIPvarGetNLocksDown(var) == 1 &&
635  SCIPmatrixGetColNDownlocks(matrix, i) == 1 &&
636  SCIPisGE(scip, SCIPvarGetObj(var), 0.0) )
637  {
638  row = -1;
639  val = 0.0;
640  inspect = FALSE;
641  twosides = FALSE;
642  colpnt = SCIPmatrixGetColIdxPtr(matrix, i);
643  colend = colpnt + SCIPmatrixGetColNNonzs(matrix, i);
644  valpnt = SCIPmatrixGetColValPtr(matrix, i);
645 
646  /* search row which causes the downlock */
647  for( ; (colpnt < colend); colpnt++, valpnt++ )
648  {
649  row = *colpnt;
650  val = *valpnt;
651  lhs = SCIPmatrixGetRowLhs(matrix, row);
652  rhs = SCIPmatrixGetRowRhs(matrix, row);
653 
654  if( SCIPisEQ(scip, lhs, rhs) )
655  {
656  /* equation */
657  inspect = TRUE;
658  twosides = TRUE;
659  break;
660  }
661  else if( SCIPmatrixIsRowRhsInfinity(matrix, row) )
662  {
663  /* >= */
664  if( SCIPisGT(scip, val, 0.0) )
665  {
666  inspect = TRUE;
667  break;
668  }
669  }
670  else if( !SCIPisInfinity(scip, -lhs) && !SCIPisInfinity(scip, rhs) )
671  {
672  /* ranged row */
673  inspect = TRUE;
674  twosides = TRUE;
675  break;
676  }
677  }
678 
679  assert(inspect);
680 
681  if( inspect ) /*lint !e774*/
682  {
683  assert(row >= 0);
684  assert(!SCIPisZero(scip, val));
685 
686  /* try to fix variable i at the lower bound */
687  SCIP_CALL( compensateVarLock(scip, matrix, i, row, val,
688  twosides, COMPENSATE_DOWNLOCK, varstofix, &nfixings) );
689  }
690  }
691  }
692 
693  if( nfixings > 0 )
694  {
695  int v;
696  int oldnfixedvars;
697  int numupperboundfixings;
698  int numlowerboundfixings;
699  int numcontinuousfixings;
700  int numdiscretefixings;
701 
702  oldnfixedvars = *nfixedvars;
703  numupperboundfixings = 0;
704  numlowerboundfixings = 0;
705  numcontinuousfixings = 0;
706  numdiscretefixings = 0;
707 
708  /* look for fixable variables */
709  for( v = ncols - 1; v >= 0; --v )
710  {
711  SCIP_Bool infeasible;
712  SCIP_Bool fixed;
713 
714  var = SCIPmatrixGetVar(matrix, v);
715 
716  if( varstofix[v] == FIXATLB )
717  {
718  SCIP_Real lb;
719 
720  lb = SCIPvarGetLbGlobal(var);
721 
722  /* avoid fixings to infinite values */
723  assert(!SCIPisInfinity(scip, -lb));
724 
725  SCIPdebugMsg(scip, "Fix variable %s at lower bound %.15g\n", SCIPvarGetName(var), lb);
726 
727  /* fix at lower bound */
728  SCIP_CALL( SCIPfixVar(scip, var, lb, &infeasible, &fixed) );
729  if( infeasible )
730  {
731  SCIPdebugMsg(scip, " -> infeasible fixing\n");
732  *result = SCIP_CUTOFF;
733 
734  break;
735  }
736  assert(fixed);
737  (*nfixedvars)++;
738  numlowerboundfixings++;
739 
741  numcontinuousfixings++;
742  else
743  numdiscretefixings++;
744  }
745  else if( varstofix[v] == FIXATUB )
746  {
747  SCIP_Real ub;
748 
749  ub = SCIPvarGetUbGlobal(var);
750 
751  /* avoid fixings to infinite values */
752  assert(!SCIPisInfinity(scip, ub));
753 
754  SCIPdebugMsg(scip, "Fix variable %s at upper bound %.15g\n", SCIPvarGetName(var), ub);
755 
756  /* fix at upper bound */
757  SCIP_CALL( SCIPfixVar(scip, var, ub, &infeasible, &fixed) );
758  if( infeasible )
759  {
760  SCIPdebugMsg(scip, " -> infeasible fixing\n");
761  *result = SCIP_CUTOFF;
762 
763  break;
764  }
765  assert(fixed);
766  (*nfixedvars)++;
767  numupperboundfixings++;
768 
770  numcontinuousfixings++;
771  else
772  numdiscretefixings++;
773  }
774  }
775 
776  if( *result != SCIP_CUTOFF && *nfixedvars > oldnfixedvars )
777  *result = SCIP_SUCCESS;
778 
779  SCIPdebugMsg(scip, "### lbfixes: %d, ubfixes: %d, con: %d, dis: %d\n",
780  numlowerboundfixings, numupperboundfixings,
781  numcontinuousfixings, numdiscretefixings);
782  }
783 
784  SCIPfreeBufferArray(scip, &varstofix);
785  }
786 
787  SCIPmatrixFree(scip, &matrix);
788 
789  return SCIP_OKAY;
790 }
791 
792 /*
793  * presolver specific interface methods
794  */
795 
796 /** destructor of presolver to free user data (called when SCIP is exiting) */
797 static
798 SCIP_DECL_PRESOLFREE(presolFreeDualcomp)
799 { /*lint --e{715}*/
800  SCIP_PRESOLDATA* presoldata;
801 
802  /* free presolver data */
803  presoldata = SCIPpresolGetData(presol);
804  assert(presoldata != NULL);
805 
806  SCIPfreeBlockMemory(scip, &presoldata);
807  SCIPpresolSetData(presol, NULL);
808 
809  return SCIP_OKAY;
810 }
811 
812 /** creates the dualcomp presolver and includes it in SCIP */
814  SCIP* scip /**< SCIP data structure */
815  )
816 {
817  SCIP_PRESOLDATA* presoldata;
818  SCIP_PRESOL* presol;
819 
820  /* create dualcomp presolver data */
821  SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
822 
823  /* include presolver */
825  PRESOL_TIMING, presolExecDualcomp, presoldata) );
826  SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyDualcomp) );
827  SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeDualcomp) );
828 
830  "presolving/dualcomp/componlydisvars",
831  "should only discrete variables be compensated?",
832  &presoldata->componlydisvars, FALSE, DEFAULT_COMP_ONLY_DIS_VARS, NULL, NULL) );
833 
834  return SCIP_OKAY;
835 }
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:6889
void SCIPmatrixPrintRow(SCIP *scip, SCIP_MATRIX *matrix, int row)
Definition: matrix.c:845
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:37
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1325
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1397
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip.c:6940
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:814
enum Fixingdirection FIXINGDIRECTION
dual compensation presolver
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17169
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46037
#define PRESOL_NAME
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:782
#define FALSE
Definition: def.h:64
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip.c:5690
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
static SCIP_DECL_PRESOLFREE(presolFreeDualcomp)
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:466
#define PRESOL_PRIORITY
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21973
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45985
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22003
static SCIP_DECL_PRESOLEXEC(presolExecDualcomp)
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21956
SCIP_RETCODE SCIPmatrixCreate(SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool *initialized, SCIP_Bool *complete)
Definition: matrix.c:430
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_RETCODE SCIPincludePresolDualcomp(SCIP *scip)
int SCIPgetNContVars(SCIP *scip)
Definition: scip.c:11860
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1373
static SCIP_RETCODE compensateVarLock(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Bool twosides, LOCKCOMPENSATION compensation, FIXINGDIRECTION *varstofix, int *nfixings)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17179
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1407
enum Fixingdirection FIXINGDIRECTION
Definition: presol_domcol.c:81
Fixingdirection
Definition: presol_domcol.c:75
SCIP_Real * SCIPmatrixGetColValPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1233
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45998
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:476
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1361
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16555
SCIP_Bool SCIPisNLPEnabled(SCIP *scip)
Definition: scip.c:30927
#define NULL
Definition: lpi_spx1.cpp:137
#define SCIP_CALL(x)
Definition: def.h:316
#define PRESOL_TIMING
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1349
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21991
#define SCIP_Bool
Definition: def.h:61
#define PRESOL_MAXROUNDS
int SCIPvarGetNLocksUp(SCIP_VAR *var)
Definition: var.c:3217
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1245
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:553
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17017
static SCIP_DECL_PRESOLCOPY(presolCopyDualcomp)
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip.c:25235
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:46061
#define DEFAULT_COMP_ONLY_DIS_VARS
public methods for matrix
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:35163
enum Lockcompensation LOCKCOMPENSATION
int SCIPvarGetNLocksDown(SCIP_VAR *var)
Definition: var.c:3162
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46024
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1419
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:6924
SCIP_Bool SCIPallowDualReds(SCIP *scip)
Definition: scip.c:25541
#define SCIP_Real
Definition: def.h:145
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
int SCIPmatrixGetColNDownlocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1313
#define PRESOL_DESC
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16720
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:46098
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46011
int SCIPmatrixGetColNUplocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1301
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:89
Lockcompensation
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1269
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4211
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1257