1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 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 */
83   	enum Fixingdirection
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   	};
89   	typedef enum Fixingdirection FIXINGDIRECTION;
90   	
91   	/** type of variable lock compensation */
92   	enum Lockcompensation
93   	{
94   	   COMPENSATE_DOWNLOCK = 0,
95   	   COMPENSATE_UPLOCK   = 1
96   	};
97   	typedef enum Lockcompensation LOCKCOMPENSATION;
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
106  	SCIP_RETCODE compensateVarLock(
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 &&
155  	         SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS &&
156  	         SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == SCIPmatrixGetColNUplocks(matrix, *rowpnt) &&
157  	         SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == SCIPmatrixGetColNDownlocks(matrix, *rowpnt)
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 &&
272  	         SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == SCIPmatrixGetColNUplocks(matrix, colidx) &&
273  	         SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == SCIPmatrixGetColNDownlocks(matrix, colidx) &&
274  	         SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
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",
476  	                  SCIPvarGetName(SCIPmatrixGetVar(matrix, col)),SCIPvarGetLbGlobal(SCIPmatrixGetVar(matrix, col)),
477  	                  SCIPvarGetUbGlobal(SCIPmatrixGetVar(matrix, col)), SCIPvarGetObj(SCIPmatrixGetVar(matrix, col)),
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",
494  	                  SCIPvarGetName(SCIPmatrixGetVar(matrix, col)),SCIPvarGetLbGlobal(SCIPmatrixGetVar(matrix, col)),
495  	                  SCIPvarGetUbGlobal(SCIPmatrixGetVar(matrix, col)), SCIPvarGetObj(SCIPmatrixGetVar(matrix, col)),
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 */
521  	   SCIP_CALL( SCIPincludePresolDualcomp(scip) );
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  	
539  	   if( (SCIPgetStage(scip) != SCIP_STAGE_PRESOLVING) || SCIPinProbing(scip) || SCIPisNLPEnabled(scip) )
540  	      return SCIP_OKAY;
541  	
542  	   if( SCIPisStopped(scip) || SCIPgetNActivePricers(scip) > 0 )
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  	
549  	   if( !SCIPallowStrongDualReds(scip) )
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 */
601  	         if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS &&
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 */
610  	         if( SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == 1 &&
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  	
773  	               if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
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  	
802  	               if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
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 */
846  	SCIP_RETCODE SCIPincludePresolDualcomp(
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 */
857  	   SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS,
858  	         PRESOL_TIMING, presolExecDualcomp, presoldata) );
859  	   SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyDualcomp) );
860  	   SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeDualcomp) );
861  	
862  	   SCIP_CALL( SCIPaddBoolParam(scip,
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  	}
869