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