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-2024 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_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
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 */
77static
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);
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) */
345static
346SCIP_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 */
359static
360SCIP_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);
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);
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}*/
#define NULL
Definition: def.h:267
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2172
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPincludePresolStuffing(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_Bool SCIPisNLPEnabled(SCIP *scip)
Definition: scip_nlp.c:74
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:140
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
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
Definition: presol.c:599
int SCIPgetNActivePricers(SCIP *scip)
Definition: scip_pricer.c:348
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3353
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8276
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3295
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition: scip_var.c:8629
void SCIPsortRealRealIntInt(SCIP_Real *realarray1, SCIP_Real *realarray2, int *intarray1, int *intarray2, int len)
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1580
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1708
int SCIPmatrixGetColNDownlocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1648
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1592
SCIP_Bool SCIPmatrixIsRowRhsInfinity(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1766
int SCIPmatrixGetColNUplocks(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1636
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1742
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1684
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
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1604
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:1072
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1660
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1696
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1732
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
Fixingdirection
enum Fixingdirection FIXINGDIRECTION
static SCIP_DECL_PRESOLEXEC(presolExecStuffing)
#define PRESOL_NAME
@ FIXATUB
@ FIXATLB
@ NOFIX
enum Fixingdirection FIXINGDIRECTION
static SCIP_DECL_PRESOLCOPY(presolCopyStuffing)
static SCIP_RETCODE singletonColumnStuffing(SCIP *scip, SCIP_MATRIX *matrix, FIXINGDIRECTION *varstofix, int *nfixings)
#define PRESOL_PRIORITY
#define PRESOL_MAXROUNDS
#define PRESOL_TIMING
#define PRESOL_DESC
fix singleton continuous variables
public methods for matrix
public methods for message output
methods for sorting joint arrays of various types
public methods for presolvers
public methods for problem variables
general public methods
public methods for memory management
public methods for message handling
public methods for nonlinear relaxation
public methods for numerical tolerances
public methods for presolving plugins
public methods for variable pricer plugins
public methods for global and local (sub)problems
public methods for the probing mode
public methods for SCIP variables
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SUCCESS
Definition: type_result.h:58
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_STAGE_PRESOLVING
Definition: type_set.h:49
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71
@ SCIP_LOCKTYPE_MODEL
Definition: type_var.h:97