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