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