Scippy

SCIP

Solving Constraint Integer Programs

presol_stuffing.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-2016 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file presol_stuffing.c
17  * @brief fix singleton continuous variables
18  * @author Dieter Weninger
19  *
20  * Investigate singleton continuous variables if one can be fixed at a bound.
21  *
22  * @todo enhancement from singleton continuous variables to continuous
23  * variables with only one lock in a common row
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 
28 #include <stdio.h>
29 #include <assert.h>
30 #include <string.h>
31 
32 
33 #include "scip/pub_matrix.h"
34 #include "presol_stuffing.h"
35 
36 #define PRESOL_NAME "stuffing"
37 #define PRESOL_DESC "fix redundant singleton continuous variables"
38 #define PRESOL_PRIORITY -100 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
39 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
40 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
41 
42 /** type of fixing direction */
44 {
45  FIXATLB = -1, /**< fix variable at lower bound */
46  NOFIX = 0, /**< do not fix variable */
47  FIXATUB = 1 /**< fix variable at upper bound */
48 };
50 
51 /*
52  * Local methods
53  */
54 
55 /** try to fix singleton continuous variables */
56 static
58  SCIP* scip, /**< SCIP main data structure */
59  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
60  FIXINGDIRECTION* varstofix, /**< array holding fixing information */
61  int* nfixings /**< number of possible fixings */
62  )
63 {
64  SCIP_Real* valpnt;
65  SCIP_Real* colratios;
66  SCIP_Real* colcoeffs;
67  SCIP_Bool* rowprocessed;
68  int* rowpnt;
69  int* rowend;
70  int* colindices;
71  int* dummy;
72  SCIP_Bool* swapped;
73  SCIP_Real upperconst;
74  SCIP_Real lowerconst;
75  SCIP_Real rhs;
76  SCIP_Bool tryfixing;
77  int idx;
78  int col;
79  int row;
80  int fillcnt;
81  int k;
82  int nrows;
83  int ncols;
84 
85  assert(scip != NULL);
86  assert(matrix != NULL);
87  assert(varstofix != NULL);
88  assert(nfixings != NULL);
89 
90  nrows = SCIPmatrixGetNRows(matrix);
91  ncols = SCIPmatrixGetNColumns(matrix);
92 
93  SCIP_CALL( SCIPallocBufferArray(scip, &colindices, ncols) );
94  SCIP_CALL( SCIPallocBufferArray(scip, &colratios, ncols) );
95  SCIP_CALL( SCIPallocBufferArray(scip, &colcoeffs, ncols) );
96  SCIP_CALL( SCIPallocBufferArray(scip, &dummy, ncols) );
97 
98  SCIP_CALL( SCIPallocBufferArray(scip, &swapped, ncols) );
99  BMSclearMemoryArray(swapped, ncols);
100 
101  SCIP_CALL( SCIPallocBufferArray(scip, &rowprocessed, nrows) );
102  BMSclearMemoryArray(rowprocessed, nrows);
103 
104  for( col = 0; col < ncols; col++ )
105  {
106  /* consider only rows with minimal one continuous singleton column */
107  if( SCIPmatrixGetColNNonzs(matrix, col) == 1
109  && SCIPvarGetNLocksUp(SCIPmatrixGetVar(matrix, col)) == SCIPmatrixGetColNUplocks(matrix, col)
110  && SCIPvarGetNLocksDown(SCIPmatrixGetVar(matrix, col)) == SCIPmatrixGetColNDownlocks(matrix, col) )
111  {
112  row = *(SCIPmatrixGetColIdxPtr(matrix, col));
113  if( rowprocessed[row] )
114  continue;
115 
116  rowprocessed[row] = TRUE;
117 
118  /* treat all >= rows from matrix, but internally we transform to <= relation */
119  if( SCIPmatrixIsRowRhsInfinity(matrix, row) )
120  {
121  fillcnt = 0;
122  tryfixing = TRUE;
123  upperconst = 0.0;
124  lowerconst = 0.0;
125  rhs = -SCIPmatrixGetRowLhs(matrix, row);
126 
127  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
128  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
129  valpnt = SCIPmatrixGetRowValPtr(matrix, row);
130 
131  for( ; (rowpnt < rowend); rowpnt++, valpnt++ )
132  {
133  SCIP_Real coef;
134  SCIP_VAR* var;
135  SCIP_Real lb;
136  SCIP_Real ub;
137 
138  coef = -(*valpnt);
139  idx = *rowpnt;
140  var = SCIPmatrixGetVar(matrix, idx);
141  lb = SCIPvarGetLbGlobal(var);
142  ub = SCIPvarGetUbGlobal(var);
143 
144  /* we need to check if this is a singleton continuous variable and
145  * all constraints containing this variable are present inside
146  * the mixed integer linear matrix
147  */
148  if( SCIPmatrixGetColNNonzs(matrix, idx) == 1 &&
149  (SCIPvarGetNLocksUp(var) + SCIPvarGetNLocksDown(var)) == 1 &&
151  {
152  if( SCIPisLT(scip, SCIPvarGetObj(var), 0.0) && SCIPisGT(scip, coef, 0.0) )
153  {
154  /* case 1: obj < 0 and coef > 0 */
155  if( SCIPisInfinity(scip, -lb) )
156  {
157  tryfixing = FALSE;
158  break;
159  }
160 
161  upperconst += coef * lb;
162  lowerconst += coef * lb;
163  colratios[fillcnt] = SCIPvarGetObj(var) / coef;
164  colindices[fillcnt] = idx;
165  colcoeffs[fillcnt] = coef;
166  fillcnt++;
167  }
168  else if( SCIPisGT(scip, SCIPvarGetObj(var), 0.0) && SCIPisLT(scip, coef, 0.0) )
169  {
170  /* case 2: obj > 0 and coef < 0 */
171  if( SCIPisInfinity(scip, ub) )
172  {
173  tryfixing = FALSE;
174  break;
175  }
176 
177  /* multiply column by (-1) to become case 1.
178  * now bounds are swapped: ub := -lb, lb := -ub
179  */
180  swapped[idx] = TRUE;
181  upperconst += coef * ub;
182  lowerconst += coef * ub;
183  colratios[fillcnt] = SCIPvarGetObj(var) / coef;
184  colindices[fillcnt] = idx;
185  colcoeffs[fillcnt] = -coef;
186  fillcnt++;
187  }
188  else if( SCIPisGE(scip, SCIPvarGetObj(var), 0.0) && SCIPisGE(scip, coef, 0.0) )
189  {
190  /* case 3: obj >= 0 and coef >= 0 is handled by duality fixing.
191  * we only consider the lower bound for the constants
192  */
193  if( SCIPisInfinity(scip, -lb) )
194  {
195  /* maybe unbounded */
196  tryfixing = FALSE;
197  break;
198  }
199 
200  upperconst += coef * lb;
201  lowerconst += coef * lb;
202  }
203  else
204  {
205  /* case 4: obj <= 0 and coef <= 0 is also handled by duality fixing.
206  * we only consider the upper bound for the constants
207  */
208  assert(SCIPisLE(scip, SCIPvarGetObj(var), 0.0));
209  assert(SCIPisLE(scip, coef, 0.0));
210 
211  if( SCIPisInfinity(scip, ub) )
212  {
213  /* maybe unbounded */
214  tryfixing = FALSE;
215  break;
216  }
217 
218  upperconst += coef * ub;
219  lowerconst += coef * ub;
220  }
221  }
222  else
223  {
224  /* consider contribution of discrete variables, non-singleton
225  * continuous variables and variables with more than one lock
226  */
227  if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) )
228  {
229  tryfixing = FALSE;
230  break;
231  }
232 
233  if( coef > 0 )
234  {
235  upperconst += coef * ub;
236  lowerconst += coef * lb;
237  }
238  else
239  {
240  upperconst += coef * lb;
241  lowerconst += coef * ub;
242  }
243  }
244  }
245 
246  if( tryfixing )
247  {
248  SCIPsortRealRealIntInt(colratios, colcoeffs, colindices, dummy, fillcnt);
249 
250  /* verify which singleton continuous variable can be fixed */
251  for( k = 0; k < fillcnt; k++ )
252  {
253  SCIP_VAR* var;
254  SCIP_Real lb;
255  SCIP_Real ub;
256  SCIP_Real delta;
257 
258  idx = colindices[k];
259  var = SCIPmatrixGetVar(matrix, idx);
260  lb = SCIPvarGetLbGlobal(var);
261  ub = SCIPvarGetUbGlobal(var);
262 
263  /* stop fixing if variable bounds are not finite */
264  if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) )
265  break;
266 
267  assert(SCIPmatrixGetColNNonzs(matrix, idx) == 1);
268  assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS);
269  assert((SCIPvarGetNLocksUp(var) + SCIPvarGetNLocksDown(var)) == 1);
270  assert(colcoeffs[k] >= 0);
271 
272  /* calculate the change in the row activities if this variable changes
273  * its value from to its other bound
274  */
275  if( swapped[idx] )
276  delta = -(lb - ub) * colcoeffs[k];
277  else
278  delta = (ub - lb) * colcoeffs[k];
279 
280  assert(delta >= 0);
281 
282  if( SCIPisLE(scip, delta, rhs - upperconst) )
283  {
284  if( swapped[idx] )
285  varstofix[idx] = FIXATLB;
286  else
287  varstofix[idx] = FIXATUB;
288 
289  (*nfixings)++;
290  }
291  else if( SCIPisLE(scip, rhs, lowerconst) )
292  {
293  if( swapped[idx] )
294  varstofix[idx] = FIXATUB;
295  else
296  varstofix[idx] = FIXATLB;
297 
298  (*nfixings)++;
299  }
300 
301  upperconst += delta;
302  lowerconst += delta;
303  }
304  }
305  }
306  }
307  }
308 
309  SCIPfreeBufferArray(scip, &rowprocessed);
310  SCIPfreeBufferArray(scip, &swapped);
311  SCIPfreeBufferArray(scip, &dummy);
312  SCIPfreeBufferArray(scip, &colcoeffs);
313  SCIPfreeBufferArray(scip, &colratios);
314  SCIPfreeBufferArray(scip, &colindices);
315 
316  return SCIP_OKAY;
317 }
318 
319 /*
320  * Callback methods of presolver
321  */
322 
323 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
324 static
325 SCIP_DECL_PRESOLCOPY(presolCopyStuffing)
326 { /*lint --e{715}*/
327  assert(scip != NULL);
328  assert(presol != NULL);
329  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
330 
331  /* call inclusion method of presolver */
333 
334  return SCIP_OKAY;
335 }
336 
337 /** execution method of presolver */
338 static
339 SCIP_DECL_PRESOLEXEC(presolExecStuffing)
340 { /*lint --e{715}*/
341  SCIP_MATRIX* matrix;
342  SCIP_Bool initialized;
343  SCIP_Bool complete;
344 
345  assert(result != NULL);
346  *result = SCIP_DIDNOTRUN;
347 
349  return SCIP_OKAY;
350 
352  return SCIP_OKAY;
353 
354  if( !SCIPallowDualReds(scip) )
355  return SCIP_OKAY;
356 
357  *result = SCIP_DIDNOTFIND;
358 
359  matrix = NULL;
360  SCIP_CALL( SCIPmatrixCreate(scip, &matrix, &initialized, &complete) );
361 
362  if( initialized )
363  {
364  FIXINGDIRECTION* varstofix;
365  int nfixings;
366  int ncols;
367 
368  nfixings = 0;
369  ncols = SCIPmatrixGetNColumns(matrix);
370 
371  SCIP_CALL( SCIPallocBufferArray(scip, &varstofix, ncols) );
372  BMSclearMemoryArray(varstofix, ncols);
373 
374  SCIP_CALL( singletonColumnStuffing(scip, matrix, varstofix, &nfixings) );
375 
376  if( nfixings > 0 )
377  {
378  int v;
379  int oldnfixedvars;
380 
381  oldnfixedvars = *nfixedvars;
382 
383  /* look for fixable variables */
384  for( v = ncols - 1; v >= 0; --v )
385  {
386  SCIP_Bool infeasible;
387  SCIP_Bool fixed;
388  SCIP_VAR* var;
389 
390  var = SCIPmatrixGetVar(matrix, v);
391 
392  if( varstofix[v] == FIXATLB )
393  {
394  SCIP_Real lb;
395 
396  assert(SCIPvarGetNLocksUp(var) == SCIPmatrixGetColNUplocks(matrix, v) &&
398 
399  lb = SCIPvarGetLbGlobal(var);
400  assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS);
401 
402  /* avoid fixings to infinite values */
403  assert(!SCIPisInfinity(scip, -lb));
404 
405  SCIPdebugMessage("Fix variable %s at lower bound %.15g\n", SCIPvarGetName(var), lb);
406 
407  /* fix at lower bound */
408  SCIP_CALL( SCIPfixVar(scip, var, lb, &infeasible, &fixed) );
409  if( infeasible )
410  {
411  SCIPdebugMessage(" -> infeasible fixing\n");
412  *result = SCIP_CUTOFF;
413 
414  break;
415  }
416  assert(fixed);
417  (*nfixedvars)++;
418  }
419  else if( varstofix[v] == FIXATUB )
420  {
421  SCIP_Real ub;
422 
423  assert(SCIPvarGetNLocksUp(var) == SCIPmatrixGetColNUplocks(matrix, v) &&
425 
426  ub = SCIPvarGetUbGlobal(var);
427  assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS);
428 
429  /* avoid fixings to infinite values */
430  assert(!SCIPisInfinity(scip, ub));
431 
432  SCIPdebugMessage("Fix variable %s at upper bound %.15g\n", SCIPvarGetName(var), ub);
433 
434  /* fix at upper bound */
435  SCIP_CALL( SCIPfixVar(scip, var, ub, &infeasible, &fixed) );
436  if( infeasible )
437  {
438  SCIPdebugMessage(" -> infeasible fixing\n");
439  *result = SCIP_CUTOFF;
440 
441  break;
442  }
443  assert(fixed);
444 
445  (*nfixedvars)++;
446  }
447  }
448 
449  if( *result != SCIP_CUTOFF && *nfixedvars > oldnfixedvars )
450  *result = SCIP_SUCCESS;
451  }
452 
453  SCIPfreeBufferArray(scip, &varstofix);
454  }
455 
456  SCIPmatrixFree(scip, &matrix);
457 
458  return SCIP_OKAY;
459 }
460 
461 /*
462  * presolver specific interface methods
463  */
464 
465 /** creates the stuffing presolver and includes it in SCIP */
467  SCIP* scip /**< SCIP data structure */
468  )
469 {
470  SCIP_PRESOL* presol;
471 
472  /* include presolver */
474  PRESOL_TIMING, presolExecStuffing, NULL) );
475  SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyStuffing) );
476 
477  return SCIP_OKAY;
478 }
479 
480 /*lint --e{749}*/
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip.c:22777
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1325
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16443
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1397
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:41648
static SCIP_DECL_PRESOLEXEC(presolExecStuffing)
#define NULL
Definition: lpi_spx.cpp:130
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1125
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip.c:6226
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17067
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:553
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:782
fix singleton continuous variables
#define FALSE
Definition: def.h:56
#define TRUE
Definition: def.h:55
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define SCIP_CALL(x)
Definition: def.h:266
SCIP_Bool SCIPallowDualReds(SCIP *scip)
Definition: scip.c:23083
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip.c:5017
#define SCIPdebugMessage
Definition: pub_message.h:77
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:85
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:16905
int SCIPgetNContVars(SCIP *scip)
Definition: scip.c:10878
SCIP_RETCODE SCIPmatrixCreate(SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool *initialized, SCIP_Bool *complete)
Definition: matrix.c:430
SCIP_RETCODE SCIPincludePresolStuffing(SCIP *scip)
static SCIP_DECL_PRESOLCOPY(presolCopyStuffing)
void SCIPsortRealRealIntInt(SCIP_Real *realarray1, SCIP_Real *realarray2, int *intarray1, int *intarray2, int len)
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1373
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1407
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41585
enum Fixingdirection FIXINGDIRECTION
Definition: presol_domcol.c:77
Fixingdirection
Definition: presol_domcol.c:71
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41598
#define PRESOL_PRIORITY
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1361
#define PRESOL_NAME
int SCIPvarGetNLocksUp(SCIP_VAR *var)
Definition: var.c:3204
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1349
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip.c:32131
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41611
#define SCIP_Bool
Definition: def.h:53
#define PRESOL_DESC
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:801
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1245
SCIP_Bool SCIPisNLPEnabled(SCIP *scip)
Definition: scip.c:28369
#define PRESOL_MAXROUNDS
public methods for matrix
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:41624
static SCIP_RETCODE singletonColumnStuffing(SCIP *scip, SCIP_MATRIX *matrix, FIXINGDIRECTION *varstofix, int *nfixings)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16608
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:20585
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17057
SCIP_Bool SCIPmatrixIsRowRhsInfinity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1431
#define SCIP_Real
Definition: def.h:127
int SCIPmatrixGetColNDownlocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1313
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:20597
int SCIPmatrixGetColNUplocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1301
#define PRESOL_TIMING
enum Fixingdirection FIXINGDIRECTION
int SCIPvarGetNLocksDown(SCIP_VAR *var)
Definition: var.c:3149
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
Definition: scip.c:6191
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1269
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1257