1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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_dualcomp.c
17 * @ingroup DEFPLUGINS_PRESOL
18 * @brief dual compensation presolver
19 * @author Dieter Weninger
20 *
21 * This presolver looks for variables with
22 * i) objcoef >= 0 and exactly one downlock
23 * ii) objcoef <= 0 and exactly one uplock
24 * and fixes the variable in case i) at the lower bound and in case ii) at the
25 * upper bound if a combination of singleton continuous variables can compensate
26 * the downlock in case i) and the uplock in case ii).
27 */
28
29 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
30
31 #include "blockmemshell/memory.h"
32 #include "scip/presol_dualcomp.h"
33 #include "scip/pub_matrix.h"
34 #include "scip/pub_message.h"
35 #include "scip/pub_presol.h"
36 #include "scip/pub_var.h"
37 #include "scip/scip_general.h"
38 #include "scip/scip_mem.h"
39 #include "scip/scip_message.h"
40 #include "scip/scip_nlp.h"
41 #include "scip/scip_numerics.h"
42 #include "scip/scip_param.h"
43 #include "scip/scip_presol.h"
44 #include "scip/scip_pricer.h"
45 #include "scip/scip_prob.h"
46 #include "scip/scip_probing.h"
47 #include "scip/scip_var.h"
48 #include <string.h>
49
50 #define PRESOL_NAME "dualcomp"
51 #define PRESOL_DESC "compensate single up-/downlocks by singleton continuous variables"
52
53 /* we need singleton continuous variables for the lock compensation,
54 * thus it is presumably a good idea to call this presolver before stuffing, which
55 * fixes singleton continuous variables
56 */
57 #define PRESOL_PRIORITY -50 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers) */
58 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
59 #define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */
60
61 #define DEFAULT_COMP_ONLY_DIS_VARS FALSE /**< should only discrete variables be compensated? */
62
63 /*
64 * Data structures
65 */
66
67 /** control parameters */
68 struct SCIP_PresolData
69 {
70 SCIP_Bool componlydisvars; /**< flag indicating if only discrete variables should be compensated */
71 };
72
73 /** type of fixing direction */
74 enum Fixingdirection
75 {
76 FIXATLB = -1, /**< fix variable at lower bound */
77 NOFIX = 0, /**< do not fix variable */
78 FIXATUB = 1 /**< fix variable at upper bound */
79 };
80 typedef enum Fixingdirection FIXINGDIRECTION;
81
82 /** type of variable lock compensation */
83 enum Lockcompensation
84 {
85 COMPENSATE_DOWNLOCK = 0,
86 COMPENSATE_UPLOCK = 1
87 };
88 typedef enum Lockcompensation LOCKCOMPENSATION;
89
90 /*
91 * Local methods
92 */
93
94 /** try to compensate a variable with a single opposite lock
95 by using singleton continuous variables */
96 static
compensateVarLock(SCIP * scip,SCIP_MATRIX * matrix,int col,int row,SCIP_Real val,SCIP_Bool twosides,LOCKCOMPENSATION compensation,FIXINGDIRECTION * varstofix,int * nfixings)97 SCIP_RETCODE compensateVarLock(
98 SCIP* scip, /**< SCIP main data structure */
99 SCIP_MATRIX* matrix, /**< matrix containing the constraints */
100 int col, /**< variable fixing candidate */
101 int row, /**< row index with opposite lock */
102 SCIP_Real val, /**< value of fixing candidate in the opposite lock constraint */
103 SCIP_Bool twosides, /**< flag indicating that two sides are present */
104 LOCKCOMPENSATION compensation, /**< type of lock compensation */
105 FIXINGDIRECTION* varstofix, /**< array holding fixing information */
106 int* nfixings /**< number of possible fixings */
107 )
108 {
109 SCIP_Real* valpnt;
110 int* rowpnt;
111 int* rowend;
112 SCIP_VAR* var;
113 int colidx;
114 SCIP_Real coef;
115 SCIP_Real lhs;
116 SCIP_Real delta;
117 SCIP_Bool trytofix;
118 SCIP_Real lb;
119 SCIP_Real ub;
120 SCIP_Bool deltaisinf;
121 SCIP_Real ratio;
122 SCIP_Bool multrowbyminusone;
123 SCIP_Bool singleton;
124 SCIP_Real offset;
125
126 assert(scip != NULL);
127 assert(matrix != NULL);
128 assert(0 <= col && col < SCIPmatrixGetNColumns(matrix));
129 assert(0 <= row && row < SCIPmatrixGetNRows(matrix));
130 assert(compensation == COMPENSATE_DOWNLOCK || compensation == COMPENSATE_UPLOCK);
131 assert(varstofix != NULL);
132 assert(nfixings != NULL);
133
134 /* the variable for compensation should not be a compensation variable itself */
135 assert(!(SCIPmatrixGetColNNonzs(matrix,col) == 1 && SCIPvarGetType(SCIPmatrixGetVar(matrix,col)) == SCIP_VARTYPE_CONTINUOUS));
136
137 /* try lock compensation only if minimum one singleton continuous variable is present */
138 singleton = FALSE;
139 rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
140 rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
141 for( ; rowpnt < rowend; rowpnt++ )
142 {
143 var = SCIPmatrixGetVar(matrix, *rowpnt);
144
145 if( SCIPmatrixGetColNNonzs(matrix, *rowpnt) == 1 &&
146 SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS &&
147 SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == SCIPmatrixGetColNUplocks(matrix, *rowpnt) &&
148 SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == SCIPmatrixGetColNDownlocks(matrix, *rowpnt)
149 )
150 {
151 /* minimal one valid compensation variable is present in this row */
152 singleton = TRUE;
153 break;
154 }
155 }
156
157 /* return if no compensation variable is available */
158 if( !singleton )
159 return SCIP_OKAY;
160
161 /* we perform the following transformations afterwards:
162 *
163 * lhs <= a1 x1 + a2 x2 + ... an xn <= rhs
164 * with a1, a2, ..., an >= 0.
165 *
166 * for the downlock case we multiply the constraint in thought by (-1)
167 * if the corresponding coefficient is negative.
168 *
169 * we attribute the uplock case to the downlock case by multiplying
170 * in thought the corresponding column by (-1).
171 */
172 multrowbyminusone = FALSE;
173 if( compensation == COMPENSATE_DOWNLOCK )
174 {
175 if( SCIPisLT(scip,val,0.0) )
176 multrowbyminusone = TRUE;
177 }
178 else
179 {
180 assert(compensation == COMPENSATE_UPLOCK);
181
182 /* in the uplock case we multiply the column in thought by (-1) and
183 * thus we need to multiply the constraint by (-1) to get a positive coefficient
184 */
185 if( SCIPisGT(scip,val,0.0) )
186 multrowbyminusone = TRUE;
187 }
188
189 /* we need the objective coefficient and constraint coefficient ratio
190 * to later preserve optimality.
191 * further we need to consider multiplications of the constraint by (-1).
192 * for ranged rows and equalities we switch to the rhs.
193 */
194 lhs = SCIPmatrixGetRowLhs(matrix, row);
195 ratio = SCIPvarGetObj( SCIPmatrixGetVar(matrix,col) ) / val;
196 if( multrowbyminusone )
197 {
198 if( twosides )
199 lhs = -SCIPmatrixGetRowRhs(matrix, row);
200 else
201 lhs = -lhs;
202
203 ratio = -ratio;
204 }
205
206 offset = 0.0;
207 trytofix = TRUE;
208 delta = 0;
209 deltaisinf = FALSE;
210
211 rowpnt = SCIPmatrixGetRowIdxPtr(matrix, row);
212 rowend = rowpnt + SCIPmatrixGetRowNNonzs(matrix, row);
213 valpnt = SCIPmatrixGetRowValPtr(matrix, row);
214
215 for( ; rowpnt < rowend; rowpnt++, valpnt++ )
216 {
217 colidx = *rowpnt;
218 coef = *valpnt;
219 var = SCIPmatrixGetVar(matrix, colidx);
220 lb = SCIPvarGetLbGlobal(var);
221 ub = SCIPvarGetUbGlobal(var);
222
223 if( colidx == col )
224 {
225 /* this is the variable which we want to compensate */
226
227 if( compensation == COMPENSATE_DOWNLOCK )
228 {
229 if( SCIPisInfinity(scip, -lb) )
230 {
231 trytofix = FALSE;
232 break;
233 }
234 else
235 {
236 if( multrowbyminusone )
237 offset += (-coef) * lb;
238 else
239 offset += coef * lb;
240 }
241 }
242 else
243 {
244 if( SCIPisInfinity(scip, ub) )
245 {
246 trytofix = FALSE;
247 break;
248 }
249 else
250 {
251 /* for the uplock case we have opposed sign for the coefficient as
252 * in the downlock case.
253 * the multiplication of the column results in swapping the negative bounds.
254 */
255 if( multrowbyminusone )
256 offset += coef * (-ub);
257 else
258 offset += (-coef) * (-ub);
259 }
260 }
261 }
262 else if( SCIPmatrixGetColNNonzs(matrix, colidx) == 1 &&
263 SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == SCIPmatrixGetColNUplocks(matrix, colidx) &&
264 SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == SCIPmatrixGetColNDownlocks(matrix, colidx) &&
265 SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
266 {
267 /* this is singleton continuous variable and
268 * thus a valid compensation candidate
269 */
270
271 if( SCIPisLT(scip,coef,0.0) )
272 {
273 /* coef < 0 */
274
275 if( multrowbyminusone )
276 {
277 if( SCIPisInfinity(scip, -lb) )
278 {
279 trytofix = FALSE;
280 break;
281 }
282
283 /* we have a negative coefficient and the row is multiplied by (-1)
284 * thus actually we have a positive coefficient
285 */
286 offset += (-coef) * lb;
287
288 /* only consider singleton continuous variables with a better or the same
289 * obj/coef ratio for preserving optimality
290 */
291 if( SCIPisLE(scip,SCIPvarGetObj(SCIPmatrixGetVar(matrix, colidx))/(-coef), ratio) )
292 {
293 if( SCIPisInfinity(scip, ub) )
294 {
295 deltaisinf = TRUE;
296 break;
297 }
298
299 /* calculate the contribution to the compensation value */
300 delta += (-coef) * (ub - lb);
301 }
302 }
303 else
304 {
305 if( SCIPisInfinity(scip, ub) )
306 {
307 trytofix = FALSE;
308 break;
309 }
310
311 /* we have a negative coefficient and hence need to multiply the column by (-1).
312 * this means the bounds swap and change the sign
313 */
314 offset += (-coef) * (-ub);
315
316 /* only consider singleton continuous variables with a better or the same
317 * obj/coef ratio for preserving optimality
318 */
319 if( SCIPisLE(scip,SCIPvarGetObj(SCIPmatrixGetVar(matrix, colidx))/coef, ratio) )
320 {
321 if( SCIPisInfinity(scip, -lb) )
322 {
323 deltaisinf = TRUE;
324 break;
325 }
326
327 /* calculate the contribution to the compensation value */
328 delta += (-coef) * (ub - lb);
329 }
330 }
331 }
332 else
333 {
334 /* coef >= 0 */
335
336 if( multrowbyminusone )
337 {
338 /* we have a positive or zero coefficient and the row is multiplied by (-1) */
339 if( SCIPisInfinity(scip, ub) )
340 {
341 trytofix = FALSE;
342 break;
343 }
344
345 /* we have a positive or zero coefficient and multiply in thought the constraint
346 * by (-1) thus we have actually a negative coefficient and multiply the column by (-1).
347 * therefore the sign of the coefficient does not change but the bounds swap and change
348 * the sign.
349 */
350 offset += coef * (-ub);
351
352 /* we have a positive or zero coefficient and multiply in thought the constraint
353 * by (-1) which delivers the ratio.
354 * a further multiplication of the column does not change anything.
355 */
356 if( SCIPisLE(scip,SCIPvarGetObj(SCIPmatrixGetVar(matrix, colidx))/(-coef), ratio) )
357 {
358 if( SCIPisInfinity(scip, -lb) )
359 {
360 deltaisinf = TRUE;
361 break;
362 }
363
364 /* calculate the contribution to the compensation value */
365 delta += coef * (ub - lb);
366 }
367 }
368 else
369 {
370 if( SCIPisInfinity(scip, -lb) )
371 {
372 trytofix = FALSE;
373 break;
374 }
375
376 /* we have positive coefficient and do not need to multiply anything by (-1) */
377 offset += coef * lb;
378
379 if( SCIPisLE(scip,SCIPvarGetObj(SCIPmatrixGetVar(matrix, colidx))/coef, ratio) )
380 {
381 if( SCIPisInfinity(scip, ub) )
382 {
383 deltaisinf = TRUE;
384 break;
385 }
386
387 /* calculate the contribution to the compensation value */
388 delta += coef * (ub - lb);
389 }
390 }
391 }
392 }
393 else
394 {
395 /* remaining variables */
396
397 /* the reasons for the following signs are the same as for the singleton
398 * continuous variables
399 */
400 if( SCIPisLT(scip,coef,0.0) )
401 {
402 if( multrowbyminusone )
403 {
404 if( SCIPisInfinity(scip, -lb) )
405 {
406 trytofix = FALSE;
407 break;
408 }
409
410 offset += (-coef) * lb;
411 }
412 else
413 {
414 if( SCIPisInfinity(scip, ub) )
415 {
416 trytofix = FALSE;
417 break;
418 }
419
420 offset += (-coef) * (-ub);
421 }
422 }
423 else
424 {
425 if( multrowbyminusone )
426 {
427 if( SCIPisInfinity(scip, ub) )
428 {
429 trytofix = FALSE;
430 break;
431 }
432
433 offset += coef * (-ub);
434 }
435 else
436 {
437 if( SCIPisInfinity(scip, -lb) )
438 {
439 trytofix = FALSE;
440 break;
441 }
442
443 offset += coef * lb;
444 }
445 }
446 }
447 }
448
449 /* avoid fixings to infinite values or fixings of already fixed variables */
450 if( trytofix && varstofix[col] == NOFIX)
451 {
452 /* feasibility is secured if the compensation value delta
453 * is large enough to compensate the value lhs-offset
454 */
455 if( deltaisinf || SCIPisLE(scip, lhs-offset, delta) )
456 {
457 if( compensation == COMPENSATE_UPLOCK )
458 {
459 if( !SCIPisInfinity(scip,SCIPvarGetUbGlobal(SCIPmatrixGetVar(matrix, col))) )
460 {
461 varstofix[col] = FIXATUB;
462 (*nfixings)++;
463
464 #ifdef SCIP_MORE_DEBUG
465 SCIPmatrixPrintRow(scip, matrix, row);
466 SCIPdebugMsg(scip, "%s, bds=[%.2f,%.2f], obj=%.2f, nnonzs=%d, type=%s, fix=ub, %.1f <= %.1f\n",
467 SCIPvarGetName(SCIPmatrixGetVar(matrix, col)),SCIPvarGetLbGlobal(SCIPmatrixGetVar(matrix, col)),
468 SCIPvarGetUbGlobal(SCIPmatrixGetVar(matrix, col)), SCIPvarGetObj(SCIPmatrixGetVar(matrix, col)),
469 SCIPmatrixGetColNNonzs(matrix, col),
470 SCIPvarGetType(SCIPmatrixGetVar(matrix, col))==SCIP_VARTYPE_CONTINUOUS ? "con" : "dis",
471 lhs-offset, delta);
472 #endif
473 }
474 }
475 else
476 {
477 if( !SCIPisInfinity(scip,-SCIPvarGetLbGlobal(SCIPmatrixGetVar(matrix, col))) )
478 {
479 varstofix[col] = FIXATLB;
480 (*nfixings)++;
481
482 #ifdef SCIP_MORE_DEBUG
483 SCIPmatrixPrintRow(scip, matrix, row);
484 SCIPdebugMsg(scip, "%s, bds=[%.2f,%.2f], obj=%.2f, nnonzs=%d, type=%s, fix=lb, %.1f <= %.1f\n",
485 SCIPvarGetName(SCIPmatrixGetVar(matrix, col)),SCIPvarGetLbGlobal(SCIPmatrixGetVar(matrix, col)),
486 SCIPvarGetUbGlobal(SCIPmatrixGetVar(matrix, col)), SCIPvarGetObj(SCIPmatrixGetVar(matrix, col)),
487 SCIPmatrixGetColNNonzs(matrix, col),
488 SCIPvarGetType(SCIPmatrixGetVar(matrix, col))==SCIP_VARTYPE_CONTINUOUS ? "con" : "dis",
489 lhs-offset, delta);
490 #endif
491 }
492 }
493 }
494 }
495
496 return SCIP_OKAY;
497 }
498
499 /*
500 * Callback methods of presolver
501 */
502
503 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
504 static
SCIP_DECL_PRESOLCOPY(presolCopyDualcomp)505 SCIP_DECL_PRESOLCOPY(presolCopyDualcomp)
506 { /*lint --e{715}*/
507 assert(scip != NULL);
508 assert(presol != NULL);
509 assert(strcmp(SCIPpresolGetName(presol), PRESOL_NAME) == 0);
510
511 /* call inclusion method of presolver */
512 SCIP_CALL( SCIPincludePresolDualcomp(scip) );
513
514 return SCIP_OKAY;
515 }
516
517 /** execution method of presolver */
518 static
SCIP_DECL_PRESOLEXEC(presolExecDualcomp)519 SCIP_DECL_PRESOLEXEC(presolExecDualcomp)
520 { /*lint --e{715}*/
521 SCIP_PRESOLDATA* presoldata;
522 SCIP_MATRIX* matrix;
523 SCIP_Bool initialized;
524 SCIP_Bool complete;
525 SCIP_Bool infeasible;
526
527 assert(result != NULL);
528 *result = SCIP_DIDNOTRUN;
529
530 if( (SCIPgetStage(scip) != SCIP_STAGE_PRESOLVING) || SCIPinProbing(scip) || SCIPisNLPEnabled(scip) )
531 return SCIP_OKAY;
532
533 if( SCIPisStopped(scip) || SCIPgetNActivePricers(scip) > 0 )
534 return SCIP_OKAY;
535
536 /* don't run if no compensation variables are present */
537 if( SCIPgetNContVars(scip) == 0 )
538 return SCIP_OKAY;
539
540 if( !SCIPallowStrongDualReds(scip) )
541 return SCIP_OKAY;
542
543 *result = SCIP_DIDNOTFIND;
544
545 presoldata = SCIPpresolGetData(presol);
546 assert(presoldata != NULL);
547
548 matrix = NULL;
549
550 SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible,
551 naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
552
553 /* if infeasibility was detected during matrix creation, return here */
554 if( infeasible )
555 {
556 if( initialized )
557 SCIPmatrixFree(scip, &matrix);
558
559 *result = SCIP_CUTOFF;
560 return SCIP_OKAY;
561 }
562
563 /* we only work on pure MIPs currently */
564 if( initialized && complete )
565 {
566 int ncols;
567 int i;
568 SCIP_Real* valpnt;
569 int* colpnt;
570 int* colend;
571 int row;
572 SCIP_VAR* var;
573 SCIP_Bool inspect;
574 SCIP_Real val;
575 FIXINGDIRECTION* varstofix;
576 int nfixings;
577 SCIP_Real lhs;
578 SCIP_Real rhs;
579 SCIP_Bool twosides;
580
581 ncols = SCIPmatrixGetNColumns(matrix);
582 nfixings = 0;
583
584 SCIP_CALL( SCIPallocBufferArray(scip, &varstofix, ncols) );
585 BMSclearMemoryArray(varstofix, ncols);
586
587 for(i = 0; i < ncols; i++)
588 {
589 var = SCIPmatrixGetVar(matrix, i);
590
591 /* exclude compensation variables itself for compensation */
592 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS &&
593 SCIPmatrixGetColNNonzs(matrix, i) == 1 )
594 continue;
595
596 /* if requested exclude continuous variables for compensation */
597 if( presoldata->componlydisvars && SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
598 continue;
599
600 /* verifiy that this variable has one uplock and that the uplocks are consistent */
601 if( SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == 1 &&
602 SCIPmatrixGetColNUplocks(matrix, i) == 1 &&
603 SCIPisLE(scip, SCIPvarGetObj(var), 0.0) )
604 {
605 row = -1;
606 val = 0.0;
607 inspect = FALSE;
608 twosides = FALSE;
609 colpnt = SCIPmatrixGetColIdxPtr(matrix, i);
610 colend = colpnt + SCIPmatrixGetColNNonzs(matrix, i);
611 valpnt = SCIPmatrixGetColValPtr(matrix, i);
612
613 /* search row which causes the uplock */
614 for( ; (colpnt < colend); colpnt++, valpnt++ )
615 {
616 row = *colpnt;
617 val = *valpnt;
618 lhs = SCIPmatrixGetRowLhs(matrix, row);
619 rhs = SCIPmatrixGetRowRhs(matrix, row);
620
621 if( SCIPisEQ(scip, lhs, rhs) )
622 {
623 /* equation */
624 inspect = TRUE;
625 twosides = TRUE;
626 break;
627 }
628 else if( SCIPmatrixIsRowRhsInfinity(matrix, row) )
629 {
630 /* >= */
631 if( SCIPisLT(scip, val, 0.0) )
632 {
633 inspect = TRUE;
634 break;
635 }
636 }
637 else if( !SCIPisInfinity(scip, -lhs) && !SCIPisInfinity(scip, rhs) )
638 {
639 /* ranged row */
640 inspect = TRUE;
641 twosides = TRUE;
642 break;
643 }
644 }
645
646 assert(inspect);
647
648 if( inspect ) /*lint !e774*/
649 {
650 assert(row >= 0);
651 assert(!SCIPisZero(scip, val));
652
653 /* try to fix variable i at the upper bound */
654 SCIP_CALL( compensateVarLock(scip, matrix, i, row, val,
655 twosides, COMPENSATE_UPLOCK, varstofix, &nfixings) );
656 }
657 }
658 /* verifiy that this variable has one downlock and that the downlocks are consistent */
659 else if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == 1 &&
660 SCIPmatrixGetColNDownlocks(matrix, i) == 1 &&
661 SCIPisGE(scip, SCIPvarGetObj(var), 0.0) )
662 {
663 row = -1;
664 val = 0.0;
665 inspect = FALSE;
666 twosides = FALSE;
667 colpnt = SCIPmatrixGetColIdxPtr(matrix, i);
668 colend = colpnt + SCIPmatrixGetColNNonzs(matrix, i);
669 valpnt = SCIPmatrixGetColValPtr(matrix, i);
670
671 /* search row which causes the downlock */
672 for( ; (colpnt < colend); colpnt++, valpnt++ )
673 {
674 row = *colpnt;
675 val = *valpnt;
676 lhs = SCIPmatrixGetRowLhs(matrix, row);
677 rhs = SCIPmatrixGetRowRhs(matrix, row);
678
679 if( SCIPisEQ(scip, lhs, rhs) )
680 {
681 /* equation */
682 inspect = TRUE;
683 twosides = TRUE;
684 break;
685 }
686 else if( SCIPmatrixIsRowRhsInfinity(matrix, row) )
687 {
688 /* >= */
689 if( SCIPisGT(scip, val, 0.0) )
690 {
691 inspect = TRUE;
692 break;
693 }
694 }
695 else if( !SCIPisInfinity(scip, -lhs) && !SCIPisInfinity(scip, rhs) )
696 {
697 /* ranged row */
698 inspect = TRUE;
699 twosides = TRUE;
700 break;
701 }
702 }
703
704 assert(inspect);
705
706 if( inspect ) /*lint !e774*/
707 {
708 assert(row >= 0);
709 assert(!SCIPisZero(scip, val));
710
711 /* try to fix variable i at the lower bound */
712 SCIP_CALL( compensateVarLock(scip, matrix, i, row, val,
713 twosides, COMPENSATE_DOWNLOCK, varstofix, &nfixings) );
714 }
715 }
716 }
717
718 if( nfixings > 0 )
719 {
720 int v;
721 int oldnfixedvars;
722 int numupperboundfixings;
723 int numlowerboundfixings;
724 int numcontinuousfixings;
725 int numdiscretefixings;
726
727 oldnfixedvars = *nfixedvars;
728 numupperboundfixings = 0;
729 numlowerboundfixings = 0;
730 numcontinuousfixings = 0;
731 numdiscretefixings = 0;
732
733 /* look for fixable variables */
734 for( v = ncols - 1; v >= 0; --v )
735 {
736 SCIP_Bool fixed;
737
738 var = SCIPmatrixGetVar(matrix, v);
739
740 if( varstofix[v] == FIXATLB )
741 {
742 SCIP_Real lb;
743
744 lb = SCIPvarGetLbGlobal(var);
745
746 /* avoid fixings to infinite values */
747 assert(!SCIPisInfinity(scip, -lb));
748
749 SCIPdebugMsg(scip, "Fix variable %s at lower bound %.15g\n", SCIPvarGetName(var), lb);
750
751 /* fix at lower bound */
752 SCIP_CALL( SCIPfixVar(scip, var, lb, &infeasible, &fixed) );
753 if( infeasible )
754 {
755 SCIPdebugMsg(scip, " -> infeasible fixing\n");
756 *result = SCIP_CUTOFF;
757
758 break;
759 }
760 assert(fixed);
761 (*nfixedvars)++;
762 numlowerboundfixings++;
763
764 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
765 numcontinuousfixings++;
766 else
767 numdiscretefixings++;
768 }
769 else if( varstofix[v] == FIXATUB )
770 {
771 SCIP_Real ub;
772
773 ub = SCIPvarGetUbGlobal(var);
774
775 /* avoid fixings to infinite values */
776 assert(!SCIPisInfinity(scip, ub));
777
778 SCIPdebugMsg(scip, "Fix variable %s at upper bound %.15g\n", SCIPvarGetName(var), ub);
779
780 /* fix at upper bound */
781 SCIP_CALL( SCIPfixVar(scip, var, ub, &infeasible, &fixed) );
782 if( infeasible )
783 {
784 SCIPdebugMsg(scip, " -> infeasible fixing\n");
785 *result = SCIP_CUTOFF;
786
787 break;
788 }
789 assert(fixed);
790 (*nfixedvars)++;
791 numupperboundfixings++;
792
793 if( SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS )
794 numcontinuousfixings++;
795 else
796 numdiscretefixings++;
797 }
798 }
799
800 if( *result != SCIP_CUTOFF && *nfixedvars > oldnfixedvars )
801 *result = SCIP_SUCCESS;
802
803 SCIPdebugMsg(scip, "### lbfixes: %d, ubfixes: %d, con: %d, dis: %d\n",
804 numlowerboundfixings, numupperboundfixings,
805 numcontinuousfixings, numdiscretefixings);
806 }
807
808 SCIPfreeBufferArray(scip, &varstofix);
809 }
810
811 SCIPmatrixFree(scip, &matrix);
812
813 return SCIP_OKAY;
814 }
815
816 /*
817 * presolver specific interface methods
818 */
819
820 /** destructor of presolver to free user data (called when SCIP is exiting) */
821 static
SCIP_DECL_PRESOLFREE(presolFreeDualcomp)822 SCIP_DECL_PRESOLFREE(presolFreeDualcomp)
823 { /*lint --e{715}*/
824 SCIP_PRESOLDATA* presoldata;
825
826 /* free presolver data */
827 presoldata = SCIPpresolGetData(presol);
828 assert(presoldata != NULL);
829
830 SCIPfreeBlockMemory(scip, &presoldata);
831 SCIPpresolSetData(presol, NULL);
832
833 return SCIP_OKAY;
834 }
835
836 /** creates the dualcomp presolver and includes it in SCIP */
SCIPincludePresolDualcomp(SCIP * scip)837 SCIP_RETCODE SCIPincludePresolDualcomp(
838 SCIP* scip /**< SCIP data structure */
839 )
840 {
841 SCIP_PRESOLDATA* presoldata;
842 SCIP_PRESOL* presol;
843
844 /* create dualcomp presolver data */
845 SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
846
847 /* include presolver */
848 SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS,
849 PRESOL_TIMING, presolExecDualcomp, presoldata) );
850 SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyDualcomp) );
851 SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeDualcomp) );
852
853 SCIP_CALL( SCIPaddBoolParam(scip,
854 "presolving/dualcomp/componlydisvars",
855 "should only discrete variables be compensated?",
856 &presoldata->componlydisvars, FALSE, DEFAULT_COMP_ONLY_DIS_VARS, NULL, NULL) );
857
858 return SCIP_OKAY;
859 }
860