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