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