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-2018 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_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 "blockmemshell/memory.h"
29 #include "scip/presol_stuffing.h"
30 #include "scip/pub_matrix.h"
31 #include "scip/pub_message.h"
32 #include "scip/pub_misc_sort.h"
33 #include "scip/pub_presol.h"
34 #include "scip/pub_var.h"
35 #include "scip/scip_general.h"
36 #include "scip/scip_mem.h"
37 #include "scip/scip_message.h"
38 #include "scip/scip_nlp.h"
39 #include "scip/scip_numerics.h"
40 #include "scip/scip_presol.h"
41 #include "scip/scip_pricer.h"
42 #include "scip/scip_prob.h"
43 #include "scip/scip_probing.h"
44 #include "scip/scip_var.h"
45 #include <string.h>
46 
47 #define PRESOL_NAME "stuffing"
48 #define PRESOL_DESC "fix redundant singleton continuous variables"
49 #define PRESOL_PRIORITY -100 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
50 #define PRESOL_MAXROUNDS 0 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
51 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
52 
53 /** type of fixing direction */
55 {
56  FIXATLB = -1, /**< fix variable at lower bound */
57  NOFIX = 0, /**< do not fix variable */
58  FIXATUB = 1 /**< fix variable at upper bound */
59 };
61 
62 /*
63  * Local methods
64  */
65 
66 /** try to fix singleton continuous variables */
67 static
69  SCIP* scip, /**< SCIP main data structure */
70  SCIP_MATRIX* matrix, /**< matrix containing the constraints */
71  FIXINGDIRECTION* varstofix, /**< array holding fixing information */
72  int* nfixings /**< number of possible fixings */
73  )
74 {
75  SCIP_Real* valpnt;
76  SCIP_Real* colratios;
77  SCIP_Real* colcoeffs;
78  SCIP_Bool* rowprocessed;
79  int* rowpnt;
80  int* rowend;
81  int* colindices;
82  int* dummy;
83  SCIP_Bool* swapped;
84  SCIP_Real upperconst;
85  SCIP_Real lowerconst;
86  SCIP_Real rhs;
87  SCIP_Bool tryfixing;
88  int idx;
89  int col;
90  int row;
91  int fillcnt;
92  int k;
93  int nrows;
94  int ncols;
95 
96  assert(scip != NULL);
97  assert(matrix != NULL);
98  assert(varstofix != NULL);
99  assert(nfixings != NULL);
100 
101  nrows = SCIPmatrixGetNRows(matrix);
102  ncols = SCIPmatrixGetNColumns(matrix);
103 
104  SCIP_CALL( SCIPallocBufferArray(scip, &colindices, ncols) );
105  SCIP_CALL( SCIPallocBufferArray(scip, &colratios, ncols) );
106  SCIP_CALL( SCIPallocBufferArray(scip, &colcoeffs, ncols) );
107  SCIP_CALL( SCIPallocBufferArray(scip, &dummy, ncols) );
108 
109  SCIP_CALL( SCIPallocBufferArray(scip, &swapped, ncols) );
110  BMSclearMemoryArray(swapped, ncols);
111 
112  SCIP_CALL( SCIPallocBufferArray(scip, &rowprocessed, nrows) );
113  BMSclearMemoryArray(rowprocessed, nrows);
114 
115  for( col = 0; col < ncols; col++ )
116  {
117  /* consider only rows with minimal one continuous singleton column */
118  if( SCIPmatrixGetColNNonzs(matrix, col) == 1
122  {
123  row = *(SCIPmatrixGetColIdxPtr(matrix, col));
124  if( rowprocessed[row] )
125  continue;
126 
127  rowprocessed[row] = TRUE;
128 
129  /* treat all >= rows from matrix, but internally we transform to <= relation */
130  if( SCIPmatrixIsRowRhsInfinity(matrix, row) )
131  {
132  fillcnt = 0;
133  tryfixing = TRUE;
134  upperconst = 0.0;
135  lowerconst = 0.0;
136  rhs = -SCIPmatrixGetRowLhs(matrix, row);
137 
138  rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
139  rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
140  valpnt = SCIPmatrixGetRowValPtr(matrix, row);
141 
142  for( ; (rowpnt < rowend); rowpnt++, valpnt++ )
143  {
144  SCIP_Real coef;
145  SCIP_VAR* var;
146  SCIP_Real lb;
147  SCIP_Real ub;
148 
149  coef = -(*valpnt);
150  idx = *rowpnt;
151  var = SCIPmatrixGetVar(matrix, idx);
152  lb = SCIPvarGetLbGlobal(var);
153  ub = SCIPvarGetUbGlobal(var);
154 
155  /* we need to check if this is a singleton continuous variable and
156  * all constraints containing this variable are present inside
157  * the mixed integer linear matrix
158  */
159  if( SCIPmatrixGetColNNonzs(matrix, idx) == 1
162  {
163  if( SCIPisLT(scip, SCIPvarGetObj(var), 0.0) && SCIPisGT(scip, coef, 0.0) )
164  {
165  /* case 1: obj < 0 and coef > 0 */
166  if( SCIPisInfinity(scip, -lb) )
167  {
168  tryfixing = FALSE;
169  break;
170  }
171 
172  upperconst += coef * lb;
173  lowerconst += coef * lb;
174  colratios[fillcnt] = SCIPvarGetObj(var) / coef;
175  colindices[fillcnt] = idx;
176  colcoeffs[fillcnt] = coef;
177  fillcnt++;
178  }
179  else if( SCIPisGT(scip, SCIPvarGetObj(var), 0.0) && SCIPisLT(scip, coef, 0.0) )
180  {
181  /* case 2: obj > 0 and coef < 0 */
182  if( SCIPisInfinity(scip, ub) )
183  {
184  tryfixing = FALSE;
185  break;
186  }
187 
188  /* multiply column by (-1) to become case 1.
189  * now bounds are swapped: ub := -lb, lb := -ub
190  */
191  swapped[idx] = TRUE;
192  upperconst += coef * ub;
193  lowerconst += coef * ub;
194  colratios[fillcnt] = SCIPvarGetObj(var) / coef;
195  colindices[fillcnt] = idx;
196  colcoeffs[fillcnt] = -coef;
197  fillcnt++;
198  }
199  else if( SCIPisGE(scip, SCIPvarGetObj(var), 0.0) && SCIPisGE(scip, coef, 0.0) )
200  {
201  /* case 3: obj >= 0 and coef >= 0 is handled by duality fixing.
202  * we only consider the lower bound for the constants
203  */
204  if( SCIPisInfinity(scip, -lb) )
205  {
206  /* maybe unbounded */
207  tryfixing = FALSE;
208  break;
209  }
210 
211  upperconst += coef * lb;
212  lowerconst += coef * lb;
213  }
214  else
215  {
216  /* case 4: obj <= 0 and coef <= 0 is also handled by duality fixing.
217  * we only consider the upper bound for the constants
218  */
219  assert(SCIPisLE(scip, SCIPvarGetObj(var), 0.0));
220  assert(SCIPisLE(scip, coef, 0.0));
221 
222  if( SCIPisInfinity(scip, ub) )
223  {
224  /* maybe unbounded */
225  tryfixing = FALSE;
226  break;
227  }
228 
229  upperconst += coef * ub;
230  lowerconst += coef * ub;
231  }
232  }
233  else
234  {
235  /* consider contribution of discrete variables, non-singleton
236  * continuous variables and variables with more than one lock
237  */
238  if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) )
239  {
240  tryfixing = FALSE;
241  break;
242  }
243 
244  if( coef > 0 )
245  {
246  upperconst += coef * ub;
247  lowerconst += coef * lb;
248  }
249  else
250  {
251  upperconst += coef * lb;
252  lowerconst += coef * ub;
253  }
254  }
255  }
256 
257  if( tryfixing )
258  {
259  SCIPsortRealRealIntInt(colratios, colcoeffs, colindices, dummy, fillcnt);
260 
261  /* verify which singleton continuous variable can be fixed */
262  for( k = 0; k < fillcnt; k++ )
263  {
264  SCIP_VAR* var;
265  SCIP_Real lb;
266  SCIP_Real ub;
267  SCIP_Real delta;
268 
269  idx = colindices[k];
270  var = SCIPmatrixGetVar(matrix, idx);
271  lb = SCIPvarGetLbGlobal(var);
272  ub = SCIPvarGetUbGlobal(var);
273 
274  /* stop fixing if variable bounds are not finite */
275  if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) )
276  break;
277 
278  assert(SCIPmatrixGetColNNonzs(matrix, idx) == 1);
279  assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS);
281  assert(colcoeffs[k] >= 0);
282 
283  /* calculate the change in the row activities if this variable changes
284  * its value from to its other bound
285  */
286  if( swapped[idx] )
287  delta = -(lb - ub) * colcoeffs[k];
288  else
289  delta = (ub - lb) * colcoeffs[k];
290 
291  assert(delta >= 0);
292 
293  if( SCIPisLE(scip, delta, rhs - upperconst) )
294  {
295  if( swapped[idx] )
296  varstofix[idx] = FIXATLB;
297  else
298  varstofix[idx] = FIXATUB;
299 
300  (*nfixings)++;
301  }
302  else if( SCIPisLE(scip, rhs, lowerconst) )
303  {
304  if( swapped[idx] )
305  varstofix[idx] = FIXATUB;
306  else
307  varstofix[idx] = FIXATLB;
308 
309  (*nfixings)++;
310  }
311 
312  upperconst += delta;
313  lowerconst += delta;
314  }
315  }
316  }
317  }
318  }
319 
320  SCIPfreeBufferArray(scip, &rowprocessed);
321  SCIPfreeBufferArray(scip, &swapped);
322  SCIPfreeBufferArray(scip, &dummy);
323  SCIPfreeBufferArray(scip, &colcoeffs);
324  SCIPfreeBufferArray(scip, &colratios);
325  SCIPfreeBufferArray(scip, &colindices);
326 
327  return SCIP_OKAY;
328 }
329 
330 /*
331  * Callback methods of presolver
332  */
333 
334 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
335 static
336 SCIP_DECL_PRESOLCOPY(presolCopyStuffing)
337 { /*lint --e{715}*/
338  assert(scip != NULL);
339  assert(presol != NULL);
340  assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
341 
342  /* call inclusion method of presolver */
344 
345  return SCIP_OKAY;
346 }
347 
348 /** execution method of presolver */
349 static
350 SCIP_DECL_PRESOLEXEC(presolExecStuffing)
351 { /*lint --e{715}*/
352  SCIP_MATRIX* matrix;
353  SCIP_Bool initialized;
354  SCIP_Bool complete;
355 
356  assert(result != NULL);
357  *result = SCIP_DIDNOTRUN;
358 
360  return SCIP_OKAY;
361 
363  return SCIP_OKAY;
364 
365  if( !SCIPallowDualReds(scip) )
366  return SCIP_OKAY;
367 
368  *result = SCIP_DIDNOTFIND;
369 
370  matrix = NULL;
371  SCIP_CALL( SCIPmatrixCreate(scip, &matrix, &initialized, &complete) );
372 
373  if( initialized )
374  {
375  FIXINGDIRECTION* varstofix;
376  int nfixings;
377  int ncols;
378 
379  nfixings = 0;
380  ncols = SCIPmatrixGetNColumns(matrix);
381 
382  SCIP_CALL( SCIPallocBufferArray(scip, &varstofix, ncols) );
383  BMSclearMemoryArray(varstofix, ncols);
384 
385  SCIP_CALL( singletonColumnStuffing(scip, matrix, varstofix, &nfixings) );
386 
387  if( nfixings > 0 )
388  {
389  int v;
390  int oldnfixedvars;
391 
392  oldnfixedvars = *nfixedvars;
393 
394  /* look for fixable variables */
395  for( v = ncols - 1; v >= 0; --v )
396  {
397  SCIP_Bool infeasible;
398  SCIP_Bool fixed;
399  SCIP_VAR* var;
400 
401  var = SCIPmatrixGetVar(matrix, v);
402 
403  if( varstofix[v] == FIXATLB )
404  {
405  SCIP_Real lb;
406 
409 
410  lb = SCIPvarGetLbGlobal(var);
411  assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS);
412 
413  /* avoid fixings to infinite values */
414  assert(!SCIPisInfinity(scip, -lb));
415 
416  SCIPdebugMsg(scip, "Fix variable %s at lower bound %.15g\n", SCIPvarGetName(var), lb);
417 
418  /* fix at lower bound */
419  SCIP_CALL( SCIPfixVar(scip, var, lb, &infeasible, &fixed) );
420  if( infeasible )
421  {
422  SCIPdebugMsg(scip, " -> infeasible fixing\n");
423  *result = SCIP_CUTOFF;
424 
425  break;
426  }
427  assert(fixed);
428  (*nfixedvars)++;
429  }
430  else if( varstofix[v] == FIXATUB )
431  {
432  SCIP_Real ub;
433 
436 
437  ub = SCIPvarGetUbGlobal(var);
438  assert(SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS);
439 
440  /* avoid fixings to infinite values */
441  assert(!SCIPisInfinity(scip, ub));
442 
443  SCIPdebugMsg(scip, "Fix variable %s at upper bound %.15g\n", SCIPvarGetName(var), ub);
444 
445  /* fix at upper bound */
446  SCIP_CALL( SCIPfixVar(scip, var, ub, &infeasible, &fixed) );
447  if( infeasible )
448  {
449  SCIPdebugMsg(scip, " -> infeasible fixing\n");
450  *result = SCIP_CUTOFF;
451 
452  break;
453  }
454  assert(fixed);
455 
456  (*nfixedvars)++;
457  }
458  }
459 
460  if( *result != SCIP_CUTOFF && *nfixedvars > oldnfixedvars )
461  *result = SCIP_SUCCESS;
462  }
463 
464  SCIPfreeBufferArray(scip, &varstofix);
465  }
466 
467  SCIPmatrixFree(scip, &matrix);
468 
469  return SCIP_OKAY;
470 }
471 
472 /*
473  * presolver specific interface methods
474  */
475 
476 /** creates the stuffing presolver and includes it in SCIP */
478  SCIP* scip /**< SCIP data structure */
479  )
480 {
481  SCIP_PRESOL* presol;
482 
483  /* include presolver */
485  PRESOL_TIMING, presolExecStuffing, NULL) );
486  SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyStuffing) );
487 
488  return SCIP_OKAY;
489 }
490 
491 /*lint --e{749}*/
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
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1407
#define NULL
Definition: def.h:239
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1479
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3176
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:412
SCIP_RETCODE SCIPincludePresolStuffing(SCIP *scip)
public methods for memory management
static SCIP_DECL_PRESOLEXEC(presolExecStuffing)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17343
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3233
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:864
fix singleton continuous variables
#define FALSE
Definition: def.h:65
public methods for presolving plugins
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip_pricer.c:418
#define TRUE
Definition: def.h:64
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
public methods for problem variables
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
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
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2224
static SCIP_DECL_PRESOLCOPY(presolCopyStuffing)
public methods for numerical tolerances
void SCIPsortRealRealIntInt(SCIP_Real *realarray1, SCIP_Real *realarray2, int *intarray1, int *intarray2, int len)
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1455
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17353
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_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define PRESOL_PRIORITY
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1443
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16729
SCIP_Bool SCIPisNLPEnabled(SCIP *scip)
Definition: scip_nlp.c:246
#define PRESOL_NAME
#define SCIP_CALL(x)
Definition: def.h:351
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:62
#define PRESOL_DESC
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:17191
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8168
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define PRESOL_MAXROUNDS
public methods for matrix
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:152
public methods for variable pricer plugins
static SCIP_RETCODE singletonColumnStuffing(SCIP *scip, SCIP_MATRIX *matrix, FIXINGDIRECTION *varstofix, int *nfixings)
public methods for nonlinear relaxations
methods for sorting joint arrays of various types
public methods for presolvers
general public methods
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
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:8478
public methods for message output
#define SCIP_Real
Definition: def.h:150
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:739
public methods for message handling
int SCIPmatrixGetColNDownlocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1395
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:16894
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:112
public methods for global and local (sub)problems
#define PRESOL_TIMING
enum Fixingdirection FIXINGDIRECTION
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1351
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1339
memory allocation routines