Scippy

SCIP

Solving Constraint Integer Programs

prop_probing.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 prop_probing.c
26 * @ingroup DEFPLUGINS_PROP
27 * @brief probing propagator
28 * @author Tobias Achterberg
29 * @author Matthias Miltenberger
30 * @author Michael Winkler
31 */
32
33/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34
36#include "scip/prop_probing.h"
37#include "scip/pub_message.h"
38#include "scip/pub_misc.h"
39#include "scip/pub_misc_sort.h"
40#include "scip/pub_prop.h"
41#include "scip/pub_tree.h"
42#include "scip/pub_var.h"
43#include "scip/scip_branch.h"
44#include "scip/scip_general.h"
45#include "scip/scip_lp.h"
46#include "scip/scip_mem.h"
47#include "scip/scip_message.h"
48#include "scip/scip_numerics.h"
49#include "scip/scip_param.h"
50#include "scip/scip_prob.h"
51#include "scip/scip_probing.h"
52#include "scip/scip_prop.h"
55#include "scip/scip_timing.h"
56#include "scip/scip_tree.h"
57#include "scip/scip_var.h"
58#include <string.h>
59
60#define PROP_NAME "probing"
61#define PROP_DESC "probing propagator on binary variables"
62#define PROP_TIMING SCIP_PROPTIMING_AFTERLPLOOP
63#define PROP_PRIORITY -100000 /**< propagation priority */
64#define PROP_FREQ -1 /**< propagation frequency */
65#define PROP_DELAY TRUE /**< should propagation method be delayed, if other propagators found
66 * reductions? */
67#define PROP_PRESOL_PRIORITY -100000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers); combined with presolvers */
68#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */
69#define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no
70 * limit) */
71#define MAXDNOM 10000LL /**< maximal denominator for simple rational fixed values */
72
73
74/* @todo check for restricting the maximal number of implications that can be added by probing */
75
76/* sorting of probing variables, two different variants are implemeneted */
77/* #define VARIANT_B */
78
79
80/*
81 * Default parameter settings
82 */
83
84#define DEFAULT_MAXRUNS 1 /**< maximal number of runs, probing participates in (-1: no limit) */
85#define DEFAULT_PROPROUNDS -1 /**< maximal number of propagation rounds in probing subproblems */
86#define DEFAULT_MAXFIXINGS 25 /**< maximal number of fixings found, until probing is interrupted
87 * (0: don't interrupt) */
88#define DEFAULT_MAXUSELESS 1000 /**< maximal number of successive probings without fixings,
89 * until probing is aborted (0: don't abort) */
90#define DEFAULT_MAXTOTALUSELESS 50 /**< maximal number of successive probings without fixings, bound changes,
91 * and implications, until probing is aborted (0: don't abort) */
92#define DEFAULT_MAXSUMUSELESS 0 /**< maximal number of probings without fixings, until probing is aborted
93 * (0: don't abort) */
94#define DEFAULT_MAXDEPTH -1 /**< maximal depth until propagation is executed(-1: no limit) */
95#define DEFAULT_RANDSEED 59 /**< random initial seed */
96
97/*
98 * Data structures
99 */
100
101/** propagator data */
102struct SCIP_PropData
103{
104 SCIP_VAR** sortedvars; /**< problem variables sorted by number of rounding locks, used in presolving */
105 int* nprobed; /**< array of numbers how often we already probed on each variables */
106 int noldtotalvars; /**< number of total variables in problem */
107 int nsortedvars; /**< number of problem variables, used in presolving */
108 int nsortedbinvars; /**< number of binary problem variables, used in presolving */
109 int maxruns; /**< maximal number of runs, probing participates in (-1: no limit) */
110 int proprounds; /**< maximal number of propagation rounds in probing subproblems */
111 int maxfixings; /**< maximal number of fixings found, until probing is interrupted
112 * (0: don't interrupt) */
113 int maxuseless; /**< maximal number of successive probings without fixings,
114 * until probing is aborted (0: don't abort) */
115 int maxtotaluseless; /**< maximal number of successive probings without fixings, bound changes,
116 * and implications, until probing is aborted (0: don't abort) */
117 int maxsumuseless; /**< maximal number of probings without fixings, until probing is aborted
118 * (0: don't abort) */
119 int startidx; /**< starting variable index of next call, used in presolving */
120 int lastsortstartidx; /**< last starting variable index where the variables have been sorted, used in presolving */
121 int nfixings; /**< total number of fixings found in probing */
122 int naggregations; /**< total number of aggregations found in probing */
123 int nimplications; /**< total number of implications found in probing */
124 int nbdchgs; /**< total number of bound changes found in probing */
125 int nuseless; /**< current number of successive useless probings */
126 int ntotaluseless; /**< current number of successive totally useless probings */
127 int nsumuseless; /**< current number of useless probings */
128 int maxdepth; /**< maximal depth until propagation is executed */
129 SCIP_Longint lastnode; /**< last node where probing was applied, or -1 for presolving, and -2 for not applied yet */
130 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
131};
132
133
134/*
135 * Local methods
136 */
137/** initializes the propagator data */
138static
140 SCIP_PROPDATA* propdata /**< propagator data */
141 )
142{
143 assert(propdata != NULL);
144
145 propdata->sortedvars = NULL;
146 propdata->nprobed = NULL;
147 propdata->noldtotalvars = 0;
148 propdata->nsortedvars = 0;
149 propdata->nsortedbinvars = 0;
150 propdata->startidx = 0;
151 propdata->lastsortstartidx = -1;
152 propdata->nfixings = 0;
153 propdata->naggregations = 0;
154 propdata->nimplications = 0;
155 propdata->nbdchgs = 0;
156 propdata->nuseless = 0;
157 propdata->ntotaluseless = 0;
158 propdata->nsumuseless = 0;
159 propdata->lastnode = -2;
160 propdata->randnumgen = NULL;
161
162 return SCIP_OKAY;
163}
164
165/** frees the sorted vars array */
166static
168 SCIP* scip, /**< SCIP data structure */
169 SCIP_PROPDATA* propdata /**< propagator data */
170 )
171{
172 assert(propdata != NULL);
173
174 if( propdata->sortedvars != NULL )
175 {
176 int i;
177
178 /* release variables */
179 for( i = 0; i < propdata->nsortedvars; ++i )
180 {
181 SCIP_CALL( SCIPreleaseVar(scip, &propdata->sortedvars[i]) );
182 }
183 SCIPfreeMemoryArray(scip, &propdata->sortedvars);
184 propdata->nsortedvars = 0;
185 propdata->nsortedbinvars = 0;
186 }
187
188 SCIPfreeMemoryArrayNull(scip, &propdata->nprobed);
189 propdata->noldtotalvars = 0;
190
191 return SCIP_OKAY;
192}
193
194/** sorts the binary variables starting with the given index by rounding locks and implications */
195static
197 SCIP* scip, /**< SCIP data structure */
198 SCIP_PROPDATA* propdata, /**< propagator data */
199 SCIP_VAR** vars, /**< problem variables to be sorted */
200 int nvars, /**< number of problem variables to be sorted */
201 int firstidx /**< first index that should be subject to sorting */
202 )
203{
204 SCIP_VAR** sortedvars;
205 int nsortedvars;
206 SCIP_Real* scores;
207 int i;
208 int minnprobings;
209 SCIP_Real maxscore;
210 int nlocksdown;
211 int nlocksup;
212 int nimplzero;
213 int nimplone;
214 int nclqzero;
215 int nclqone;
216
217 assert(propdata != NULL);
218 assert(propdata->nprobed != NULL);
219
220 assert(vars != NULL || nvars == 0);
221
222 nsortedvars = nvars - firstidx;
223 if( nsortedvars <= 0 )
224 return SCIP_OKAY;
225
226 assert(vars != NULL);
227
228 sortedvars = &(vars[firstidx]);
229
230 SCIPdebugMsg(scip, "resorting probing variables %d to %d\n", firstidx, nvars-1);
231
232 /* sort the variables by number of rounding locks and implications */
233 SCIP_CALL( SCIPallocBufferArray(scip, &scores, nsortedvars) );
234
235 maxscore = -1.0;
236 minnprobings = INT_MAX;
237
238 /* determine maximal possible score and minimal number of probings over all variables */
239 for( i = 0; i < nvars; ++i )
240 {
241 SCIP_VAR* var;
242 SCIP_Real tmp;
243
244 var = vars[i];
245
246 assert(SCIPvarIsBinary(var));
247 assert(propdata->noldtotalvars > SCIPvarGetIndex(var));
248 assert(propdata->nprobed[SCIPvarGetIndex(var)] >= 0);
249
250 if( SCIPvarIsActive(var) )
251 {
254 nimplzero = SCIPvarGetNImpls(var, FALSE);
255 nimplone = SCIPvarGetNImpls(var, TRUE);
256 nclqzero = SCIPvarGetNCliques(var, FALSE);
257 nclqone = SCIPvarGetNCliques(var, TRUE);
258
259#ifndef VARIANT_B
260 tmp = -MAX(nlocksdown, nlocksup)
261 + 10.0 * MIN(nimplzero, nimplone)
262 + 100.0 * MIN(nclqzero, nclqone);
263#else
264 tmp = - ABS(nlocksdown - nlocksup)
265 + MIN(nlocksdown, nlocksup)
266 + 500.0 * nimplzero + 50.0 * nimplone
267 + 50000.0 * nclqzero + 5000.0 * nclqone;
268#endif
269
270 if( tmp > maxscore )
271 maxscore = tmp;
272 if( propdata->nprobed[SCIPvarGetIndex(var)] < minnprobings )
273 minnprobings = propdata->nprobed[SCIPvarGetIndex(var)];
274 }
275 }
276
277 /* correct number of probings on each variable by minimal number of probings */
278 if( minnprobings > 0 )
279 {
280 for( i = 0; i < nvars; ++i )
281 {
282 SCIP_VAR* var;
283
284 var = vars[i];
285
286 if( SCIPvarIsActive(var) )
287 propdata->nprobed[SCIPvarGetIndex(var)] -= minnprobings;
288 }
289 }
290
291 for( i = 0; i < nsortedvars; ++i )
292 {
293 SCIP_VAR* var;
294 var = sortedvars[i];
295
296 assert(SCIPvarIsBinary(var));
297
298 /* prefer variables that we did not already probe on */
299 if( SCIPvarIsActive(var) )
300 {
301 SCIP_Real randomoffset;
304 nimplzero = SCIPvarGetNImpls(var, FALSE);
305 nimplone = SCIPvarGetNImpls(var, TRUE);
306 nclqzero = SCIPvarGetNCliques(var, FALSE);
307 nclqone = SCIPvarGetNCliques(var, TRUE);
308
309 assert(propdata->noldtotalvars > SCIPvarGetIndex(var));
310 assert(propdata->nprobed[SCIPvarGetIndex(var)] >= 0);
311
312 /* use a random offset to break possible ties arbitrarily */
313 randomoffset = SCIPrandomGetReal(propdata->randnumgen, 0.0, 0.5);
314
315#ifndef VARIANT_B
316 scores[i] = -maxscore * propdata->nprobed[SCIPvarGetIndex(var)]
317 - MAX(nlocksdown, nlocksup)
318 + 10.0 * MIN(nimplzero, nimplone)
319 + 100.0 * MIN(nclqzero, nclqone) /*lint !e790*/
320 - randomoffset; /* to break ties randomly */
321#else
322 scores[i] = -maxscore * propdata->nprobed[SCIPvarGetIndex(var)]
323 - ABS(nlocksdown - nlocksup)
324 + MIN(nlocksdown, nlocksup)
325 + 500.0 * nimplzero + 50.0 * nimplone /*lint !e790*/
326 + 50000.0 * nclqzero + 5000.0 * nclqone /*lint !e790*/
327 - randomoffset; /* to break ties randomly */
328#endif
329 }
330 else
331 scores[i] = -SCIPinfinity(scip);
332 }
333
334 SCIPsortDownRealPtr(scores, (void**) sortedvars, nsortedvars);
335
336 SCIPfreeBufferArray(scip, &scores);
337
338 return SCIP_OKAY;
339}
340
341/** the main probing loop */
342static
344 SCIP* scip, /**< SCIP data structure */
345 SCIP_PROPDATA* propdata, /**< propagator data */
346 SCIP_VAR** vars, /**< problem variables */
347 int nvars, /**< number of problem variables */
348 int nbinvars, /**< number of binary variables */
349 int* startidx, /**< pointer to store starting variable index of next call */
350 int* nfixedvars, /**< pointer to store number of fixed variables */
351 int* naggrvars, /**< pointer to store number of aggregated variables */
352 int* nchgbds, /**< pointer to store number of changed bounds */
353 int oldnfixedvars, /**< number of previously fixed variables */
354 int oldnaggrvars, /**< number of previously aggregated variables */
355 SCIP_Bool* delay, /**< pointer to store whether propagator should be delayed */
356 SCIP_Bool* cutoff /**< pointer to store whether cutoff occured */
357 )
358{
359 SCIP_Real* zeroimpllbs;
360 SCIP_Real* zeroimplubs;
361 SCIP_Real* zeroproplbs;
362 SCIP_Real* zeropropubs;
363 SCIP_Real* oneimpllbs;
364 SCIP_Real* oneimplubs;
365 SCIP_Real* oneproplbs;
366 SCIP_Real* onepropubs;
367 int localnfixedvars;
368 int localnaggrvars;
369 int localnchgbds;
370 int localnimplications;
371 int maxfixings;
372 int maxuseless;
373 int maxtotaluseless;
374 int maxsumuseless;
375 int i;
376 int oldstartidx;
377 SCIP_Bool aborted;
378 SCIP_Bool looped;
379
380 assert(vars != NULL);
381 assert(nbinvars > 0);
382
383 maxfixings = (propdata->maxfixings > 0 ? propdata->maxfixings : INT_MAX);
384 maxuseless = (propdata->maxuseless > 0 ? propdata->maxuseless : INT_MAX);
385 maxtotaluseless = (propdata->maxtotaluseless > 0 ? propdata->maxtotaluseless : INT_MAX);
386 maxsumuseless = (propdata->maxsumuseless > 0 ? propdata->maxsumuseless : INT_MAX);
387 aborted = FALSE;
388 looped = FALSE;
389 oldstartidx = *startidx;
390 i = *startidx;
391
392 /* get temporary memory for storing probing results */
393 SCIP_CALL( SCIPallocBufferArray(scip, &zeroimpllbs, nvars) );
394 SCIP_CALL( SCIPallocBufferArray(scip, &zeroimplubs, nvars) );
395 SCIP_CALL( SCIPallocBufferArray(scip, &zeroproplbs, nvars) );
396 SCIP_CALL( SCIPallocBufferArray(scip, &zeropropubs, nvars) );
397 SCIP_CALL( SCIPallocBufferArray(scip, &oneimpllbs, nvars) );
398 SCIP_CALL( SCIPallocBufferArray(scip, &oneimplubs, nvars) );
399 SCIP_CALL( SCIPallocBufferArray(scip, &oneproplbs, nvars) );
400 SCIP_CALL( SCIPallocBufferArray(scip, &onepropubs, nvars) );
401
402 /* for each binary variable, probe fixing the variable to zero and one */
403 *delay = FALSE;
404 *cutoff = FALSE;
405 do
406 {
407 for( ; i < nbinvars && !(*cutoff); ++i )
408 {
409 SCIP_Bool localcutoff;
410 SCIP_Bool probingzero;
411 SCIP_Bool probingone;
412
413 /* check whether probing should be aborted */
414 if( propdata->nuseless >= maxuseless || propdata->ntotaluseless >= maxtotaluseless || propdata->nsumuseless >= maxsumuseless || SCIPisStopped(scip) )
415 {
417 " (%.1fs) probing: %d/%d (%.1f%%) - %d fixings, %d aggregations, %d implications, %d bound changes\n",
418 SCIPgetSolvingTime(scip), i+1, nbinvars, 100.0*(SCIP_Real)(i+1)/(SCIP_Real)nbinvars,
419 propdata->nfixings, propdata->naggregations, propdata->nimplications, propdata->nbdchgs);
420
421 aborted = TRUE;
422
423 if( propdata->nuseless >= maxuseless )
424 {
426 " (%.1fs) probing aborted: %d/%d successive useless probings\n", SCIPgetSolvingTime(scip),
427 propdata->nuseless, maxuseless);
428 }
429 else if( propdata->ntotaluseless >= maxtotaluseless )
430 {
432 " (%.1fs) probing aborted: %d/%d successive totally useless probings\n", SCIPgetSolvingTime(scip),
433 propdata->ntotaluseless, maxtotaluseless);
434 }
435 else if( propdata->nsumuseless >= maxsumuseless )
436 {
438 " (%.1fs) probing aborted: %d/%d useless probings in total\n", SCIPgetSolvingTime(scip),
439 propdata->nsumuseless, maxsumuseless);
440 }
441 else
442 {
443 assert(SCIPisStopped(scip));
445 " (%.1fs) probing aborted: solving stopped\n", SCIPgetSolvingTime(scip));
446 }
447 break;
448 }
449
450 /* check if we already fixed enough variables for this round, or probed on all variables */
451 if( *nfixedvars - oldnfixedvars + *naggrvars - oldnaggrvars >= maxfixings || (looped && oldstartidx == i) )
452 {
453 if( *nfixedvars - oldnfixedvars + *naggrvars - oldnaggrvars > 0 )
454 *delay = TRUE;
455 else
456 aborted = TRUE;
457 break;
458 }
459
460 /* display probing status */
461 if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING && (i+1) % 100 == 0 )
462 {
463 SCIP_VERBLEVEL verblevel;
464
465 verblevel = ((i+1) % 1000 == 0 ? SCIP_VERBLEVEL_HIGH : SCIP_VERBLEVEL_FULL);
466 SCIPverbMessage(scip, verblevel, NULL,
467 " (%.1fs) probing: %d/%d (%.1f%%) - %d fixings, %d aggregations, %d implications, %d bound changes\n",
468 SCIPgetSolvingTime(scip), i+1, nbinvars, 100.0*(SCIP_Real)(i+1)/(SCIP_Real)nbinvars,
469 propdata->nfixings, propdata->naggregations, propdata->nimplications, propdata->nbdchgs);
470 }
471
472 /* ignore variables, that were fixed, aggregated, or deleted in prior probings */
473 if( !SCIPvarIsActive(vars[i]) || SCIPvarIsDeleted(vars[i])
474 || SCIPvarGetLbLocal(vars[i]) > 0.5 || SCIPvarGetUbLocal(vars[i]) < 0.5 )
475 continue;
476
477 if( propdata->nuseless > 0 )
478 propdata->nsumuseless++;
479 else
480 propdata->nsumuseless = MAX(propdata->nsumuseless-1, 0);
481 propdata->nuseless++;
482 propdata->ntotaluseless++;
483
484 /* determine whether one probing should happen */
485 probingone = TRUE;
487 probingone = FALSE;
488
489 if( probingone )
490 {
491 /* apply probing for fixing the variable to one */
492 SCIP_CALL( SCIPapplyProbingVar(scip, vars, nvars, i, SCIP_BOUNDTYPE_LOWER, 1.0, propdata->proprounds,
493 oneimpllbs, oneimplubs, oneproplbs, onepropubs, &localcutoff) );
494
495 if( localcutoff )
496 {
497 SCIP_Bool fixed;
498
500 {
501 /* the variable can be fixed to FALSE */
502 SCIP_CALL( SCIPfixVar(scip, vars[i], 0.0, cutoff, &fixed) );
503 assert(fixed);
504 }
505 else
506 {
507 SCIP_CALL( SCIPtightenVarUb(scip, vars[i], 0.0, TRUE, cutoff, &fixed) );
508 }
509
510 if( fixed )
511 {
512 SCIPdebugMsg(scip, "fixed probing variable <%s> to 0.0, nlocks=(%d/%d)\n",
515 (*nfixedvars)++;
516 propdata->nfixings++;
517 propdata->nuseless = 0;
518 propdata->ntotaluseless = 0;
519 }
520 else if( *cutoff )
521 {
522 SCIPdebugMsg(scip, "tightening upper bound of probing variable <%s> to 0.0 led to a cutoff\n",
523 SCIPvarGetName(vars[i]));
524 }
525 continue; /* don't try downwards direction, because the variable is already fixed */
526 }
527
528 /* ignore variables, that were fixed, aggregated, or deleted in prior probings
529 * (propagators in one-probe might have found global fixings but did not trigger the localcutoff)
530 */
531 if( !SCIPvarIsActive(vars[i]) || SCIPvarIsDeleted(vars[i])
532 || SCIPvarGetLbLocal(vars[i]) > 0.5 || SCIPvarGetUbLocal(vars[i]) < 0.5 )
533 continue;
534 }
535
536 /* determine whether zero probing should happen */
537 probingzero = TRUE;
539 probingzero = FALSE;
540
541 if( probingzero )
542 {
543 /* apply probing for fixing the variable to zero */
544 SCIP_CALL( SCIPapplyProbingVar(scip, vars, nvars, i, SCIP_BOUNDTYPE_UPPER, 0.0, propdata->proprounds,
545 zeroimpllbs, zeroimplubs, zeroproplbs, zeropropubs, &localcutoff) );
546
547 if( localcutoff )
548 {
549 SCIP_Bool fixed;
550
552 {
553 /* the variable can be fixed to TRUE */
554 SCIP_CALL( SCIPfixVar(scip, vars[i], 1.0, cutoff, &fixed) );
555 }
556 else
557 {
558 SCIP_CALL( SCIPtightenVarLb(scip, vars[i], 1.0, TRUE, cutoff, &fixed) );
559 }
560
561 if( fixed )
562 {
563 SCIPdebugMsg(scip, "fixed probing variable <%s> to 1.0, nlocks=(%d/%d)\n",
566 (*nfixedvars)++;
567 propdata->nfixings++;
568 propdata->nuseless = 0;
569 propdata->ntotaluseless = 0;
570 }
571 else if( *cutoff )
572 {
573 SCIPdebugMsg(scip, "tightening lower bound of probing variable <%s> to 1.0 led to a cutoff\n",
574 SCIPvarGetName(vars[i]));
575 }
576 continue; /* don't analyze probing deductions, because the variable is already fixed */
577 }
578 }
579
580 /* not have to check deductions if only one probing direction has been checked */
581 if( !probingzero || !probingone )
582 continue;
583
584 assert(propdata->noldtotalvars > SCIPvarGetIndex(vars[i]));
585
586 /* count number of probings on each variable */
587 propdata->nprobed[SCIPvarGetIndex(vars[i])] += 1;
588
589 /* analyze probing deductions */
590 localnfixedvars = 0;
591 localnaggrvars = 0;
592 localnimplications = 0;
593 localnchgbds = 0;
594 SCIP_CALL( SCIPanalyzeDeductionsProbing(scip, vars[i], 0.0, 1.0,
595 nvars, vars, zeroimpllbs, zeroimplubs, zeroproplbs, zeropropubs, oneimpllbs, oneimplubs, oneproplbs, onepropubs,
596 &localnfixedvars, &localnaggrvars, &localnimplications, &localnchgbds, cutoff) );
597
598 *nfixedvars += localnfixedvars;
599 *naggrvars += localnaggrvars;
600 *nchgbds += localnchgbds;
601 propdata->nfixings += localnfixedvars;
602 propdata->naggregations += localnaggrvars;
603 propdata->nbdchgs += localnchgbds;
604 propdata->nimplications += localnimplications;
605
606 if( localnfixedvars > 0 || localnaggrvars > 0 )
607 {
608 SCIPdebugMsg(scip, "probing on <%s> led to %d fixed and %d aggregated variables\n", SCIPvarGetName(vars[i]),
609 localnfixedvars, localnaggrvars);
610 propdata->nuseless = 0;
611 propdata->ntotaluseless = 0;
612 }
613 if( localnimplications > 0 || localnchgbds > 0 )
614 propdata->ntotaluseless = 0;
615 }
616
617 looped = TRUE;
618
619 /* check if we reached the end of all binary variables but did not stop, so we start from the beginning */
620 if( i == nbinvars && !(*cutoff) && !(*delay) && !aborted )
621 {
623 " (%.1fs) probing cycle finished: starting next cycle\n", SCIPgetSolvingTime(scip));
624 i = 0;
625
627 {
628 SCIP_VAR** newvars;
629 int nnewvars;
630 int nnewbinvars;
631 int nnewintvars;
632 int nnewimplvars;
633 int lastidx;
634 int v;
635
636 assert(vars == propdata->sortedvars);
637 assert(nbinvars == propdata->nsortedbinvars);
638
639 /* release old variables and free memory */
640 for( v = propdata->nsortedvars - 1; v >= 0; --v )
641 {
642 SCIP_CALL( SCIPreleaseVar(scip, &propdata->sortedvars[v]) );
643 }
644 SCIPfreeMemoryArray(scip, &propdata->sortedvars);
645 propdata->nsortedvars = 0;
646 propdata->nsortedbinvars = 0;
647
648 /* get new variables */
649 nnewvars = SCIPgetNVars(scip);
650 newvars = SCIPgetVars(scip);
651 SCIP_CALL( SCIPduplicateMemoryArray(scip, &(propdata->sortedvars), newvars, nnewvars) ); /*lint !e666*/
652 propdata->nsortedvars = nnewvars;
653
654 nnewbinvars = SCIPgetNBinVars(scip);
655 nnewintvars = SCIPgetNIntVars(scip);
656 nnewimplvars = SCIPgetNImplVars(scip);
657
658 /* determine implicit binary variables */
659 lastidx = nnewbinvars + nnewintvars + nnewimplvars;
660 for( v = nnewbinvars; v < lastidx; ++v )
661 {
662 if( SCIPvarIsBinary(propdata->sortedvars[v]) )
663 {
664 SCIPswapPointers((void**) &(propdata->sortedvars[nnewbinvars]), (void**) &(propdata->sortedvars[v]));
665 ++nnewbinvars;
666 }
667 }
668 propdata->nsortedbinvars = nnewbinvars;
669
670 nbinvars = nnewbinvars;
671 vars = propdata->sortedvars;
672 nvars = propdata->nsortedvars;
673
674 SCIP_CALL( SCIPreallocBufferArray(scip, &zeroimpllbs, nvars) );
675 SCIP_CALL( SCIPreallocBufferArray(scip, &zeroimplubs, nvars) );
676 SCIP_CALL( SCIPreallocBufferArray(scip, &zeroproplbs, nvars) );
677 SCIP_CALL( SCIPreallocBufferArray(scip, &zeropropubs, nvars) );
678 SCIP_CALL( SCIPreallocBufferArray(scip, &oneimpllbs, nvars) );
679 SCIP_CALL( SCIPreallocBufferArray(scip, &oneimplubs, nvars) );
680 SCIP_CALL( SCIPreallocBufferArray(scip, &oneproplbs, nvars) );
681 SCIP_CALL( SCIPreallocBufferArray(scip, &onepropubs, nvars) );
682
683 /* correct oldstartidx which is used for early termination */
684 if( oldstartidx >= nbinvars )
685 oldstartidx = nbinvars - 1;
686
687 /* capture variables to make sure, the variables are not deleted */
688 for( v = propdata->nsortedvars - 1; v >= 0; --v )
689 {
690 SCIP_CALL( SCIPcaptureVar(scip, propdata->sortedvars[v]) );
691 }
692
693 if( nnewbinvars == 0 )
694 {
695 *startidx = 0;
696 propdata->lastsortstartidx = -1;
697 propdata->nuseless = 0;
698 propdata->ntotaluseless = 0;
699
700 goto TERMINATE;
701 }
702
703 /* resorting here might lead to probing a second time on the same variable */
704 SCIP_CALL( sortVariables(scip, propdata, propdata->sortedvars, propdata->nsortedbinvars, 0) );
705 propdata->lastsortstartidx = 0;
706 }
707 }
708 }
709 while( i == 0 && !(*cutoff) && !(*delay) && !aborted );
710
711 *startidx = i;
712
713 TERMINATE:
714 /* free temporary memory */
715 SCIPfreeBufferArray(scip, &onepropubs);
716 SCIPfreeBufferArray(scip, &oneproplbs);
717 SCIPfreeBufferArray(scip, &oneimplubs);
718 SCIPfreeBufferArray(scip, &oneimpllbs);
719 SCIPfreeBufferArray(scip, &zeropropubs);
720 SCIPfreeBufferArray(scip, &zeroproplbs);
721 SCIPfreeBufferArray(scip, &zeroimplubs);
722 SCIPfreeBufferArray(scip, &zeroimpllbs);
723
724 return SCIP_OKAY;
725}
726
727
728/*
729 * Callback methods of propagator
730 */
731
732/** copy method for constraint handler plugins (called when SCIP copies plugins) */
733static
734SCIP_DECL_PROPCOPY(propCopyProbing)
735{ /*lint --e{715}*/
736 assert(scip != NULL);
737 assert(prop != NULL);
738 assert(strcmp(SCIPpropGetName(prop), PROP_NAME) == 0);
739
740 /* call inclusion method for propagator */
742
743 return SCIP_OKAY;
744}
745
746
747/** destructor of propagator to free user data (called when SCIP is exiting) */
748static
749SCIP_DECL_PROPFREE(propFreeProbing)
750{ /*lint --e{715}*/
751 SCIP_PROPDATA* propdata;
752
753 /* free propagator data */
754 propdata = SCIPpropGetData(prop);
755 assert(propdata != NULL);
756 assert(propdata->sortedvars == NULL);
757 assert(propdata->nsortedvars == 0);
758 assert(propdata->nsortedbinvars == 0);
759
760 SCIPfreeBlockMemory(scip, &propdata);
761 SCIPpropSetData(prop, NULL);
762
763 return SCIP_OKAY;
764}
765
766
767/** initialization method of propagator (called after problem was transformed) */
768static
769SCIP_DECL_PROPINIT(propInitProbing)
770{ /*lint --e{715}*/
771 SCIP_PROPDATA* propdata;
772
773 propdata = SCIPpropGetData(prop);
774 assert(propdata != NULL);
775
776 SCIP_CALL( initPropdata(propdata) );
777
778 /* create random number generator */
779 SCIP_CALL( SCIPcreateRandom(scip, &propdata->randnumgen,
781
782 return SCIP_OKAY;
783}
784
785
786/** deinitialization method of propagator (called before transformed problem is freed) */
787static
788SCIP_DECL_PROPEXIT(propExitProbing)
789{ /*lint --e{715}*/
790 SCIP_PROPDATA* propdata;
791
792 propdata = SCIPpropGetData(prop);
793 assert(propdata != NULL);
794
795 SCIP_CALL( freeSortedvars(scip, propdata) );
796 assert(propdata->sortedvars == NULL);
797 assert(propdata->nsortedvars == 0);
798 assert(propdata->nsortedbinvars == 0);
799
800 /* free random number generator */
801 SCIPfreeRandom(scip, &propdata->randnumgen);
802
803 return SCIP_OKAY;
804}
805
806/** presolving initialization method of propagator (called when presolving is about to begin) */
807static
808SCIP_DECL_PROPINITPRE(propInitpreProbing)
809{ /*lint --e{715}*/
810 SCIP_PROPDATA* propdata;
811
812 propdata = SCIPpropGetData(prop);
813 assert(propdata != NULL);
814
815 propdata->lastnode = -2;
816
817 return SCIP_OKAY;
818}
819
820
821/** presolving deinitialization method of propagator (called after presolving has been finished) */
822static
823SCIP_DECL_PROPEXITPRE(propExitpreProbing)
824{ /*lint --e{715}*/
825 SCIP_PROPDATA* propdata;
826
827 propdata = SCIPpropGetData(prop);
828 assert(propdata != NULL);
829
830 /* delete the vars array, if the maximal number of runs are exceeded */
831 if( propdata->maxruns >= 0 && SCIPgetNRuns(scip) >= propdata->maxruns )
832 {
833 SCIP_CALL( freeSortedvars(scip, propdata) );
834 assert(propdata->sortedvars == NULL);
835 assert(propdata->nsortedvars == 0);
836 assert(propdata->nsortedbinvars == 0);
837 }
838
839 return SCIP_OKAY;
840}
841
842
843/** solving process initialization method of propagator (called when branch and bound process is about to begin) */
844static
845SCIP_DECL_PROPINITSOL(propInitsolProbing)
846{
847 /*lint --e{715}*/
848 SCIP_PROPDATA* propdata;
849
850 propdata = SCIPpropGetData(prop);
851 assert(propdata != NULL);
852
853 /* reset all propdata elements for stopping propagation earlier */
854 propdata->nuseless = 0;
855 propdata->ntotaluseless = 0;
856 propdata->nsumuseless = 0;
857
858 return SCIP_OKAY;
859}
860
861
862/** presolve method of propagator */
863static
864SCIP_DECL_PROPPRESOL(propPresolProbing)
865{ /*lint --e{715}*/
866 SCIP_PROPDATA* propdata;
867 int nvars;
868 int nbinvars;
869 int nintvars;
870 int nimplvars;
871 int oldnfixedvars;
872 int oldnaggrvars;
873 int oldnchgbds;
874 int oldnimplications;
875 int ntotalvars;
876 SCIP_Bool delay;
877 SCIP_Bool cutoff;
878
879 assert(result != NULL);
880
881 *result = SCIP_DIDNOTRUN;
882
883 nbinvars = SCIPgetNBinVars(scip);
884 nintvars = SCIPgetNIntVars(scip);
885 nimplvars = SCIPgetNImplVars(scip);
886
887 /* if we have no binary variable anymore, we stop probing */
888 if( nbinvars + nintvars + nimplvars == 0 )
889 return SCIP_OKAY;
890
891 /* get propagator data */
892 propdata = SCIPpropGetData(prop);
893 assert(propdata != NULL);
894
895 /* check, if probing should be applied in the current run */
896 if( propdata->maxruns >= 0 && SCIPgetNRuns(scip) > propdata->maxruns )
897 return SCIP_OKAY;
898
899 /* if no domains changed since the last call, we don't need to probe */
900 if( propdata->lastnode == -1 && nnewfixedvars == 0 && nnewaggrvars == 0 && nnewchgbds == 0 && nnewholes == 0 )
901 return SCIP_OKAY;
902
903 SCIPdebugMsg(scip, "executing probing (used %.1f sec)\n", SCIPpropGetTime(prop));
904
905 *result = SCIP_DIDNOTFIND;
906
907 /* allow some additional probings */
908 propdata->nuseless -= propdata->nuseless/10;
909 propdata->ntotaluseless -= propdata->ntotaluseless/10;
910
911 /* get variable data */
912 if( propdata->sortedvars == NULL )
913 {
914 SCIP_VAR** vars = SCIPgetVars(scip);
915 int lastidx;
916 int v;
917
918 assert(propdata->startidx == 0);
919
920 nvars = SCIPgetNVars(scip);
921
922 SCIP_CALL( SCIPduplicateMemoryArray(scip, &(propdata->sortedvars), vars, nvars) );
923 propdata->nsortedvars = nvars;
924
925 /* determine implicit binary variables */
926 lastidx = nbinvars + nintvars + nimplvars;
927 for( v = nbinvars; v < lastidx; ++v )
928 {
929 if( SCIPvarIsBinary(propdata->sortedvars[v]) )
930 {
931 SCIPswapPointers((void**) &(propdata->sortedvars[nbinvars]), (void**) &(propdata->sortedvars[v]));
932 ++nbinvars;
933 }
934 }
935 propdata->nsortedbinvars = nbinvars;
936
937 /* capture variables to make sure, the variables are not deleted */
938 for( v = propdata->nsortedvars - 1; v >= 0 ; --v )
939 {
940 SCIP_CALL( SCIPcaptureVar(scip, propdata->sortedvars[v]) );
941 }
942 }
943
944 if( propdata->nsortedbinvars == 0 )
945 return SCIP_OKAY;
946
947 /* number of total variables is not decreasing, and we can identify every variable by their index, so allocate
948 * enough space
949 */
950 ntotalvars = SCIPgetNTotalVars(scip);
951 if( propdata->noldtotalvars < ntotalvars )
952 {
953 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->nprobed, ntotalvars) );
954 BMSclearMemoryArray(&(propdata->nprobed[propdata->noldtotalvars]), ntotalvars - propdata->noldtotalvars); /*lint !e866*/
955 propdata->noldtotalvars = ntotalvars;
956 }
957
958 propdata->lastnode = -1;
959
960 /* sort the binary variables by number of rounding locks, if at least 100 variables were probed since last sort */
961 if( propdata->lastsortstartidx < 0 || propdata->startidx - propdata->lastsortstartidx >= 100 )
962 {
963 SCIP_CALL( sortVariables(scip, propdata, propdata->sortedvars, propdata->nsortedbinvars, propdata->startidx) );
964 propdata->lastsortstartidx = propdata->startidx;
965 }
966
967 oldnfixedvars = *nfixedvars;
968 oldnaggrvars = *naggrvars;
969 oldnchgbds = *nchgbds;
970 oldnimplications = propdata->nimplications;
971
972 /* start probing on variables */
973 SCIP_CALL( applyProbing(scip, propdata, propdata->sortedvars, propdata->nsortedvars, propdata->nsortedbinvars,
974 &(propdata->startidx), nfixedvars, naggrvars, nchgbds, oldnfixedvars, oldnaggrvars, &delay, &cutoff) );
975
976 /* adjust result code */
977 if( cutoff )
978 *result = SCIP_CUTOFF;
979 else
980 {
981 if( delay )
982 {
983 /* probing was interrupted because it reached the maximal fixings parameter, so we want to rerun it at the next call */
984 propdata->lastnode = -2;
985 }
986
987 if( *nfixedvars > oldnfixedvars || *naggrvars > oldnaggrvars || *nchgbds > oldnchgbds
988 || propdata->nimplications > oldnimplications )
989 *result = SCIP_SUCCESS;
990 }
991
992 return SCIP_OKAY;
993}
994
995
996/** execution method of propagator */
997static
998SCIP_DECL_PROPEXEC(propExecProbing)
999{ /*lint --e{715}*/
1000 SCIP_PROPDATA* propdata;
1001 SCIP_VAR** vars;
1002 SCIP_VAR** binvars;
1003 int nvars;
1004 int nbinvars;
1005 int i;
1006 int nfixedvars;
1007 int naggrvars;
1008 int nchgbds;
1009 int oldnfixedvars;
1010 int oldnaggrvars;
1011 int oldnchgbds;
1012 SCIPdebug( int oldnimplications; )
1013 int startidx;
1014 int ntotalvars;
1015 SCIP_Bool delay;
1016 SCIP_Bool cutoff;
1017
1018 assert(result != NULL);
1019
1020 *result = SCIP_DIDNOTRUN;
1021
1022 /* avoid recursive infinity loop */
1023 if( SCIPinProbing(scip) )
1024 return SCIP_OKAY;
1025
1026 /* only call propagation on branching candidates, if an optimal LP solution is at hand */
1028 return SCIP_OKAY;
1029
1030 /* get propagator data */
1031 propdata = SCIPpropGetData(prop);
1032 assert(propdata != NULL);
1033
1034 /* if already called stop */
1035 if( propdata->lastnode == SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) )
1036 return SCIP_OKAY;
1037
1038 /* if maximal depth for propagation is reached, stop */
1039 if( propdata->maxdepth >= 0 && propdata->maxdepth < SCIPgetDepth(scip) )
1040 return SCIP_OKAY;
1041
1042 propdata->lastnode = SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
1043
1044 /* get (number of) fractional variables that should be integral */
1045 /* todo check if integrating fractional implicit integer variables is beneficial for probing */
1046 SCIP_CALL( SCIPgetLPBranchCands(scip, &vars, NULL, NULL, &nvars, NULL, NULL) );
1047 nbinvars = 0;
1048
1049 /* alloc array for fractional binary variables */
1050 SCIP_CALL( SCIPallocBufferArray(scip, &binvars, nvars) );
1051
1052 /* copy binary variables to array binvars */
1053 for( i = 0; i < nvars; ++i )
1054 {
1055 SCIP_VAR* var;
1056 var = vars[i];
1057
1058 assert(var != NULL);
1059 if( SCIPvarIsBinary(var) )
1060 {
1061 assert(SCIPvarGetLbLocal(var) < 0.5);
1062 assert(SCIPvarGetUbLocal(var) > 0.5);
1063
1064 binvars[nbinvars] = var;
1065 ++nbinvars;
1066 }
1067 }
1068 SCIPdebugMsg(scip, "problem <%s> node %" SCIP_LONGINT_FORMAT " probing propagation found %d of %d possible probing candidates\n", SCIPgetProbName(scip), SCIPnodeGetNumber(SCIPgetCurrentNode(scip)), nbinvars, nvars);
1069
1070 if( nbinvars == 0 )
1071 {
1072 *result = SCIP_DIDNOTFIND;
1073 goto TERMINATE;
1074 }
1075
1076 /* number of total variables is not decreasing, and we can identify every variable by their index, so allocate
1077 * enough space
1078 */
1079 ntotalvars = SCIPgetNTotalVars(scip);
1080 if( propdata->noldtotalvars < ntotalvars )
1081 {
1082 SCIP_CALL( SCIPreallocMemoryArray(scip, &propdata->nprobed, ntotalvars) );
1083 BMSclearMemoryArray(&(propdata->nprobed[propdata->noldtotalvars]), ntotalvars - propdata->noldtotalvars); /*lint !e866*/
1084 propdata->noldtotalvars = ntotalvars;
1085 }
1086
1087 /* sort binary variables */
1088 SCIP_CALL( sortVariables(scip, propdata, binvars, nbinvars, 0) );
1089
1090 oldnfixedvars = 0;
1091 oldnaggrvars = 0;
1092 oldnchgbds = 0;
1093 nfixedvars = 0;
1094 naggrvars = 0;
1095 nchgbds = 0;
1096 startidx = 0;
1097 SCIPdebug( oldnimplications = propdata->nimplications; )
1098
1099 /* start probing on found variables */
1100 SCIP_CALL( applyProbing(scip, propdata, binvars, nbinvars, nbinvars, &startidx, &nfixedvars, &naggrvars, &nchgbds, oldnfixedvars, oldnaggrvars, &delay, &cutoff) );
1101 SCIPdebug( SCIPdebugMsg(scip, "probing propagation found %d fixings, %d aggregation, %d nchgbds, and %d implications\n",
1102 nfixedvars, naggrvars, nchgbds, (propdata->nimplications) - oldnimplications); )
1103
1104 if( delay )
1105 {
1106 /* probing was interrupted because it reached the maximal fixings parameter, so we want to rerun it at the next call */
1107 propdata->lastnode = -2;
1108 }
1109
1110 /* adjust result code */
1111 if( cutoff )
1112 *result = SCIP_CUTOFF;
1113 else if( nfixedvars > oldnfixedvars || naggrvars > oldnaggrvars || nchgbds > oldnchgbds )
1114 *result = SCIP_REDUCEDDOM;
1115
1116 TERMINATE:
1117 SCIPfreeBufferArray(scip, &binvars);
1118
1119 return SCIP_OKAY; /*lint !e438*/
1120}
1121
1122
1123/** propagation conflict resolving method of propagator */
1124static
1125SCIP_DECL_PROPRESPROP(propRespropProbing)
1126{ /*lint --e{715}*/
1127 *result = SCIP_DIDNOTRUN;
1128
1129 return SCIP_OKAY;
1130}
1131
1132
1133/*
1134 * propagator specific interface methods
1135 */
1136
1137/** creates the probing propagator and includes it in SCIP */
1139 SCIP* scip /**< SCIP data structure */
1140 )
1141{
1142 SCIP_PROPDATA* propdata;
1143 SCIP_PROP* prop;
1144
1145 /* create probing propagator data */
1146 SCIP_CALL( SCIPallocBlockMemory(scip, &propdata) );
1147 SCIP_CALL( initPropdata(propdata) );
1148
1149 /* include propagator */
1151 propExecProbing, propdata) );
1152
1153 assert(prop != NULL);
1154
1155 /* set optional callbacks via setter functions */
1156 SCIP_CALL( SCIPsetPropCopy(scip, prop, propCopyProbing) );
1157 SCIP_CALL( SCIPsetPropFree(scip, prop, propFreeProbing) );
1158 SCIP_CALL( SCIPsetPropInit(scip, prop, propInitProbing) );
1159 SCIP_CALL( SCIPsetPropExit(scip, prop, propExitProbing) );
1160 SCIP_CALL( SCIPsetPropInitsol(scip, prop, propInitsolProbing) );
1161 SCIP_CALL( SCIPsetPropInitpre(scip, prop, propInitpreProbing) );
1162 SCIP_CALL( SCIPsetPropExitpre(scip, prop, propExitpreProbing) );
1165 SCIP_CALL( SCIPsetPropResprop(scip, prop, propRespropProbing) );
1166
1167 /* add probing propagator parameters */
1169 "propagating/" PROP_NAME "/maxruns",
1170 "maximal number of runs, probing participates in (-1: no limit)",
1171 &propdata->maxruns, FALSE, DEFAULT_MAXRUNS, -1, INT_MAX, NULL, NULL) );
1173 "propagating/" PROP_NAME "/proprounds",
1174 "maximal number of propagation rounds in probing subproblems (-1: no limit, 0: auto)",
1175 &propdata->proprounds, TRUE, DEFAULT_PROPROUNDS, -1, INT_MAX, NULL, NULL) );
1177 "propagating/" PROP_NAME "/maxfixings",
1178 "maximal number of fixings found, until probing is interrupted (0: don't iterrupt)",
1179 &propdata->maxfixings, TRUE, DEFAULT_MAXFIXINGS, 0, INT_MAX, NULL, NULL) );
1181 "propagating/" PROP_NAME "/maxuseless",
1182 "maximal number of successive probings without fixings, until probing is aborted (0: don't abort)",
1183 &propdata->maxuseless, TRUE, DEFAULT_MAXUSELESS, 0, INT_MAX, NULL, NULL) );
1185 "propagating/" PROP_NAME "/maxtotaluseless",
1186 "maximal number of successive probings without fixings, bound changes, and implications, until probing is aborted (0: don't abort)",
1187 &propdata->maxtotaluseless, TRUE, DEFAULT_MAXTOTALUSELESS, 0, INT_MAX, NULL, NULL) );
1189 "propagating/" PROP_NAME "/maxsumuseless",
1190 "maximal number of probings without fixings, until probing is aborted (0: don't abort)",
1191 &propdata->maxsumuseless, TRUE, DEFAULT_MAXSUMUSELESS, 0, INT_MAX, NULL, NULL) );
1193 "propagating/" PROP_NAME "/maxdepth",
1194 "maximal depth until propagation is executed(-1: no limit)",
1195 &propdata->maxdepth, TRUE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) );
1196
1197 return SCIP_OKAY;
1198}
1199
1200
1201/** applies and evaluates probing of a single variable in the given direction and bound */
1203 SCIP* scip, /**< SCIP data structure */
1204 SCIP_VAR** vars, /**< problem variables */
1205 int nvars, /**< number of problem variables */
1206 int probingpos, /**< variable number to apply probing on */
1207 SCIP_BOUNDTYPE boundtype, /**< which bound should be changed */
1208 SCIP_Real bound, /**< which bound should be set */
1209 int maxproprounds, /**< maximal number of propagation rounds (-1: no limit, 0: parameter settings) */
1210 SCIP_Real* impllbs, /**< array to store lower bounds after applying implications and cliques */
1211 SCIP_Real* implubs, /**< array to store upper bounds after applying implications and cliques */
1212 SCIP_Real* proplbs, /**< array to store lower bounds after full propagation */
1213 SCIP_Real* propubs, /**< array to store upper bounds after full propagation */
1214 SCIP_Bool* cutoff /**< pointer to store whether the probing direction is infeasible */
1215 )
1216{
1217 assert(impllbs != NULL);
1218 assert(implubs != NULL);
1219 assert(proplbs != NULL);
1220 assert(propubs != NULL);
1221 assert(cutoff != NULL);
1222 assert(0 <= probingpos && probingpos < nvars);
1223 assert(SCIPisGE(scip, bound, SCIPvarGetLbLocal(vars[probingpos])));
1224 assert(SCIPisLE(scip, bound, SCIPvarGetUbLocal(vars[probingpos])));
1225
1226 SCIPdebugMsg(scip, "applying probing on variable <%s> %s %g (nlocks=%d/%d, impls=%d/%d, clqs=%d/%d)\n",
1227 SCIPvarGetName(vars[probingpos]), boundtype == SCIP_BOUNDTYPE_UPPER ? "<=" : ">=", bound,
1230 SCIPvarGetNImpls(vars[probingpos], FALSE), SCIPvarGetNImpls(vars[probingpos], TRUE),
1231 SCIPvarGetNCliques(vars[probingpos], FALSE), SCIPvarGetNCliques(vars[probingpos], TRUE));
1232
1233 /* in debug mode we assert above that this trivial infeasibility does not occur (for performance reasons), but in
1234 * optimized mode we return safely
1235 */
1236 if( SCIPisLT(scip, bound, SCIPvarGetLbLocal(vars[probingpos]))
1237 || SCIPisGT(scip, bound, SCIPvarGetUbLocal(vars[probingpos])) )
1238 {
1239 SCIPdebugMsg(scip, " -> trivial infeasibility detected\n");
1240 *cutoff = TRUE;
1241 return SCIP_OKAY;
1242 }
1243
1244 /* start probing mode */
1246
1247 /* enables collection of variable statistics during probing */
1249
1250 /* fix variable */
1251 if( boundtype == SCIP_BOUNDTYPE_UPPER )
1252 {
1253 SCIP_CALL( SCIPchgVarUbProbing(scip, vars[probingpos], bound) );
1254 }
1255 else
1256 {
1257 assert(boundtype == SCIP_BOUNDTYPE_LOWER);
1258 SCIP_CALL( SCIPchgVarLbProbing(scip, vars[probingpos], bound) );
1259 }
1260
1261 /* @todo it might pay off to catch the bounds-tightened event on all variables and then only get the implied and
1262 * propagated bounds on those variables which where really changed on propagation
1263 */
1264
1265 /* apply propagation of implication graph and clique table */
1267 if( !(*cutoff) )
1268 {
1269 int i;
1270
1271 for( i = 0; i < nvars; ++i )
1272 {
1273 impllbs[i] = SCIPvarGetLbLocal(vars[i]);
1274 implubs[i] = SCIPvarGetUbLocal(vars[i]);
1275 }
1276
1277 /* apply propagation */
1278 SCIP_CALL( SCIPpropagateProbing(scip, maxproprounds, cutoff, NULL) );
1279 }
1280 else
1281 {
1282 SCIPdebugMsg(scip, "propagating probing implications after <%s> to %g led to a cutoff\n",
1283 SCIPvarGetName(vars[probingpos]), bound);
1284 }
1285
1286 /* evaluate propagation */
1287 if( !(*cutoff) )
1288 {
1289 int i;
1290
1291 for( i = 0; i < nvars; ++i )
1292 {
1293 proplbs[i] = SCIPvarGetLbLocal(vars[i]);
1294 propubs[i] = SCIPvarGetUbLocal(vars[i]);
1295#if 0
1296#ifdef SCIP_DEBUG
1297 if( SCIPisGT(scip, proplbs[i], SCIPvarGetLbGlobal(vars[i])) )
1298 {
1299 SCIPdebugMsg(scip, " -> <%s>[%g,%g] >= %g\n", SCIPvarGetName(vars[i]),
1300 SCIPvarGetLbGlobal(vars[i]), SCIPvarGetUbGlobal(vars[i]), proplbs[i]);
1301 }
1302 if( SCIPisLT(scip, propubs[i], SCIPvarGetUbGlobal(vars[i])) )
1303 {
1304 SCIPdebugMsg(scip, " -> <%s>[%g,%g] <= %g\n", SCIPvarGetName(vars[i]),
1305 SCIPvarGetLbGlobal(vars[i]), SCIPvarGetUbGlobal(vars[i]), propubs[i]);
1306 }
1307#endif
1308#endif
1309 }
1310 }
1311
1312 /* exit probing mode */
1314
1315 return SCIP_OKAY;
1316}
1317
1318/** analyses boundchanges resulting from probing on a variable and performs deduced fixations, aggregations, and domain tightenings
1319 * Given a variable probingvar with domain [l,u] and bound tightening results from reducing the domain
1320 * once to [l,leftub] and once to [rightlb,u], the method computes and applies resulting variable fixations, aggregations,
1321 * implications, and bound changes. Variable probingvar does not need to be binary.
1322 * The whole domain of probingvar need to be covered by the left and right branches, i.e.,
1323 * we assume leftub >= rightlb for continuous variables or floor(leftub) >= ceil(rightlb)-1 for discrete variables.
1324 * Bounds after applying implications and cliques do not need to be provided, but if they are omitted and probingvar is a binary variable,
1325 * then already existing implications may be added.
1326 */
1328 SCIP* scip, /**< SCIP data structure */
1329 SCIP_VAR* probingvar, /**< the probing variable */
1330 SCIP_Real leftub, /**< upper bound of probing variable in left branch */
1331 SCIP_Real rightlb, /**< lower bound of probing variable in right branch */
1332 int nvars, /**< number of variables which bound changes should be analyzed */
1333 SCIP_VAR** vars, /**< variables which bound changes should be analyzed */
1334 SCIP_Real* leftimpllbs, /**< lower bounds after applying implications and cliques in left branch, or NULL */
1335 SCIP_Real* leftimplubs, /**< upper bounds after applying implications and cliques in left branch, or NULL */
1336 SCIP_Real* leftproplbs, /**< lower bounds after applying domain propagation in left branch */
1337 SCIP_Real* leftpropubs, /**< upper bounds after applying domain propagation in left branch */
1338 SCIP_Real* rightimpllbs, /**< lower bounds after applying implications and cliques in right branch, or NULL */
1339 SCIP_Real* rightimplubs, /**< upper bounds after applying implications and cliques in right branch, or NULL */
1340 SCIP_Real* rightproplbs, /**< lower bounds after applying domain propagation in right branch */
1341 SCIP_Real* rightpropubs, /**< upper bounds after applying domain propagation in right branch */
1342 int* nfixedvars, /**< pointer to counter which is increased by the number of deduced variable fixations */
1343 int* naggrvars, /**< pointer to counter which is increased by the number of deduced variable aggregations */
1344 int* nimplications, /**< pointer to counter which is increased by the number of deduced implications */
1345 int* nchgbds, /**< pointer to counter which is increased by the number of deduced bound tightenings */
1346 SCIP_Bool* cutoff /**< buffer to store whether a cutoff is detected */
1347 )
1348{
1349 SCIP_Bool fixedleft;
1350 SCIP_Bool fixedright;
1351 SCIP_Bool probingvarisbinary;
1352 SCIP_Bool probingvarisinteger;
1353 int j;
1354
1355 assert(scip != NULL);
1356 assert(probingvar != NULL);
1357 assert(SCIPisGE(scip, leftub, SCIPvarGetLbLocal(probingvar))); /* left branch should not be empty by default */
1358 assert(SCIPisLE(scip, rightlb, SCIPvarGetUbLocal(probingvar))); /* right branch should not be empty by default */
1359 assert(vars != NULL || nvars == 0);
1360 assert(leftproplbs != NULL);
1361 assert(leftpropubs != NULL);
1362 assert(rightproplbs != NULL);
1363 assert(rightpropubs != NULL);
1364 assert(nfixedvars != NULL);
1365 assert(naggrvars != NULL);
1366 assert(nimplications != NULL);
1367 assert(nchgbds != NULL);
1368 assert(cutoff != NULL);
1369
1370 /* @todo the asserts below could be relaxed by taking domain holes into account */
1371 if( SCIPvarGetType(probingvar) != SCIP_VARTYPE_CONTINUOUS )
1372 {
1373 /* adjust bounds to actually used ones */
1374 leftub = SCIPfloor(scip, leftub);
1375 rightlb = SCIPceil(scip, rightlb);
1376
1377 probingvarisinteger = TRUE;
1378 probingvarisbinary = SCIPvarIsBinary(probingvar);
1379 }
1380 else
1381 {
1382 /* assert dichotomy in case of continuous var: leftub >= rightlb */
1383 assert(SCIPisGE(scip, leftub, rightlb));
1384 probingvarisbinary = FALSE;
1385 probingvarisinteger = FALSE;
1386 }
1387
1388 /* check if probing variable was fixed in the branches */
1389 fixedleft = SCIPisEQ(scip, SCIPvarGetLbLocal(probingvar), leftub);
1390 fixedright = SCIPisEQ(scip, SCIPvarGetUbLocal(probingvar), rightlb);
1391
1392 *cutoff = FALSE;
1393
1394 for( j = 0; j < nvars && !*cutoff; ++j )
1395 {
1396 SCIP_VAR* var;
1397 SCIP_Bool varisinteger;
1398 SCIP_Real newlb;
1399 SCIP_Real newub;
1400
1401 assert(vars != NULL); /* for flexelint */
1402
1403 var = vars[j];
1404 assert(var != NULL);
1405
1406 /* @todo: add holes, and even add holes if x was the probing variable and it followed a better bound on x itself */
1407 /* @todo: check if we probed on an integer variable, that this maybe led to aggregation on two other variables, i.e
1408 * probing on x <= 1 and x >= 2 led to y = 1, z = 1 and y = 0, z = 0 resp., which means y = Z
1409 */
1410
1411 /* if probing variable is binary, then there is nothing we could deduce here (variable should be fixed in both branches)
1412 * if it is not binary, we want to see if we found bound tightenings, even though it seems quite unlikely */
1413 if( var == probingvar && probingvarisbinary )
1414 continue;
1415
1416 /* new bounds of the variable is the union of the propagated bounds of the left and right case */
1417 newlb = MIN(leftproplbs[j], rightproplbs[j]);
1418 newub = MAX(leftpropubs[j], rightpropubs[j]);
1419 varisinteger = (SCIPvarGetType(var) < SCIP_VARTYPE_CONTINUOUS);
1420
1421 /* check for fixed variables */
1422 if( SCIPisEQ(scip, newlb, newub) )
1423 {
1424 SCIP_Real fixval;
1425 SCIP_Bool fixed;
1426
1427 if( !varisinteger )
1428 {
1429 /* in both probings, variable j is deduced to the same value: fix variable to this value */
1430 fixval = SCIPselectSimpleValue(newlb - 0.9 * SCIPepsilon(scip), newub + 0.9 * SCIPepsilon(scip), MAXDNOM);
1431 }
1432 else
1433 {
1434 fixval = newlb;
1435 }
1436
1438 {
1439 SCIP_CALL( SCIPfixVar(scip, var, fixval, cutoff, &fixed) );
1440 }
1441 else
1442 {
1443 SCIP_CALL( SCIPtightenVarLb(scip, var, fixval, TRUE, cutoff, &fixed) );
1444 if( !*cutoff )
1445 {
1446 SCIP_Bool tightened;
1447
1448 SCIP_CALL( SCIPtightenVarUb(scip, var, fixval, TRUE, cutoff, &tightened) );
1449 fixed &= tightened;
1450 }
1451 }
1452
1453 if( fixed )
1454 {
1455 SCIPdebugMsg(scip, "fixed variable <%s> to %g due to probing on <%s> with nlocks=(%d/%d)\n",
1456 SCIPvarGetName(var), fixval,
1459 (*nfixedvars)++;
1460 }
1461 else if( *cutoff )
1462 {
1463 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible fixing of variable <%s> to %g\n",
1464 SCIPvarGetName(probingvar), SCIPvarGetName(var), fixval);
1465 }
1466
1467 continue;
1468 }
1469 else
1470 {
1471 /* check for bound tightenings */
1472 SCIP_Real oldlb;
1473 SCIP_Real oldub;
1474 SCIP_Bool tightened;
1475 SCIP_Bool tightenlb;
1476 SCIP_Bool tightenub;
1477 SCIP_Bool force;
1478
1479 oldlb = SCIPvarGetLbLocal(var);
1480 oldub = SCIPvarGetUbLocal(var);
1481
1482 if( varisinteger )
1483 {
1484 force = TRUE;
1485 tightenlb = (newlb > oldlb + 0.5);
1486 tightenub = (newub < oldub - 0.5);
1487 }
1488 else
1489 {
1490 force = TRUE;
1491 tightenlb = SCIPisLbBetter(scip, newlb, oldlb, oldub);
1492 tightenub = SCIPisUbBetter(scip, newub, oldlb, oldub);
1493 }
1494
1495 if( tightenlb )
1496 {
1497 /* in both probings, variable j is deduced to be at least newlb: tighten lower bound */
1498 SCIP_CALL( SCIPtightenVarLb(scip, var, newlb, force, cutoff, &tightened) );
1499 if( tightened )
1500 {
1501 SCIPdebugMsg(scip, "tightened lower bound of variable <%s>[%g,%g] to %g due to probing on <%s> with nlocks=(%d/%d)\n",
1502 SCIPvarGetName(var), oldlb, oldub, newlb,
1505 (*nchgbds)++;
1506 }
1507 else if( *cutoff )
1508 {
1509 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible new lower bound of variable <%s> to %g\n",
1510 SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb);
1511 }
1512 }
1513
1514 if( tightenub && !*cutoff )
1515 {
1516 /* in both probings, variable j is deduced to be at most newub: tighten upper bound */
1517 SCIP_CALL( SCIPtightenVarUb(scip, var, newub, force, cutoff, &tightened) );
1518 if( tightened )
1519 {
1520 SCIPdebugMsg(scip, "tightened upper bound of variable <%s>[%g,%g] to %g due to probing on <%s> with nlocks=(%d/%d)\n",
1521 SCIPvarGetName(var), oldlb, oldub, newub,
1524 (*nchgbds)++;
1525 }
1526 else if( *cutoff )
1527 {
1528 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible new lower bound of variable <%s> to %g\n",
1529 SCIPvarGetName(probingvar), SCIPvarGetName(var), newub);
1530 }
1531 }
1532 if( *cutoff )
1533 break;
1534 }
1535
1536 /* below we add aggregations and implications between probingvar and var,
1537 * we don't want this if both variables are the same
1538 */
1539 if( var == probingvar )
1540 continue;
1541
1542 /* check for aggregations and implications */
1543 if( fixedleft && fixedright &&
1544 SCIPisEQ(scip, leftproplbs[j], leftpropubs[j]) && SCIPisEQ(scip, rightproplbs[j], rightpropubs[j]) )
1545 {
1546 /* var is fixed whenever probingvar is fixed, i.e.,
1547 * var = leftproplbs[j] + (rightproplbs[j] - leftproplbs[j]) / (rightlb - leftub) * (probingvar - leftub)
1548 * -> both variables can be aggregated:
1549 * (rightlb - leftub) * (var - leftproplbs[j]) = (rightproplbs[j] - leftproplbs[j]) * (probingvar - leftub)
1550 * -> (rightlb - leftub) * var - (rightproplbs[j] - leftproplbs[j]) * probingvar = leftproplbs[j] * rightlb - rightproplbs[j] * leftub
1551 *
1552 * check for case where both variables are binary: leftub = 1, rightlb = 0
1553 * case leftproplbs[j] = 0, rightproplbs[j] = 1, i.e., var and probingvar are fixed to same value
1554 * -> aggregation is 1 * var - 1 * probingvar = 0 * 1 - 1 * 0 = 0 -> correct
1555 * case leftproplbs[j] = 1, rightproblbs[j] = 0, i.e., var and probingvar are fixed to opposite values
1556 * -> aggregation is 1 * var + 1 * probingvar = 1 * 1 - 0 * 0 = 0 -> correct
1557 */
1559 {
1560 SCIP_Bool aggregated;
1561 SCIP_Bool redundant;
1562
1563 SCIP_CALL( SCIPaggregateVars(scip, var, probingvar,
1564 rightlb - leftub, -(rightproplbs[j] - leftproplbs[j]), leftproplbs[j] * rightlb - rightproplbs[j] * leftub,
1565 cutoff, &redundant, &aggregated) );
1566
1567 if( aggregated )
1568 {
1569 SCIPdebugMsg(scip, "aggregated variables %g<%s> - %g<%s> == %g, nlocks=(%d/%d)\n",
1570 rightlb - leftub, SCIPvarGetName(var),
1571 rightproplbs[j] - leftproplbs[j], SCIPvarGetName(probingvar),
1572 leftproplbs[j] * rightlb - rightproplbs[j] * leftub,
1575 (*naggrvars)++;
1576 }
1577 if( *cutoff )
1578 {
1579 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible aggregation: %g<%s> - %g<%s> == %g\n",
1580 SCIPvarGetName(probingvar), rightlb - leftub, SCIPvarGetName(var),
1581 rightproplbs[j] - leftproplbs[j], SCIPvarGetName(probingvar),
1582 leftproplbs[j] * rightlb - rightproplbs[j] * leftub);
1583 }
1584 }
1585 else if( probingvarisinteger && SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0 )
1586 {
1587 /* if we are not in presolving, then we cannot do aggregations
1588 * but we can use variable bounds to code the same equality
1589 * var == ((leftproplbs[j] * rightlb - rightproplbs[j] * leftub) + (rightproplbs[j] - leftproplbs[j]) * probingvar) / (rightlb - leftub)
1590 */
1591 int nboundchanges;
1592
1593 assert(!SCIPisEQ(scip, leftub, rightlb));
1594
1595 SCIP_CALL( SCIPaddVarVlb(scip, var, probingvar, (rightproplbs[j] - leftproplbs[j]) / (rightlb - leftub), (leftproplbs[j] * rightlb - rightproplbs[j] * leftub) / (rightlb - leftub), cutoff, &nboundchanges) );
1596 (*nchgbds) += nboundchanges;
1597
1598 if( *cutoff )
1599 {
1600 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible vlb: %g<%s> - %g<%s> == %g\n",
1601 SCIPvarGetName(probingvar), rightlb - leftub, SCIPvarGetName(var),
1602 rightproplbs[j] - leftproplbs[j], SCIPvarGetName(probingvar),
1603 leftproplbs[j] * rightlb - rightproplbs[j] * leftub);
1604 }
1605 else
1606 {
1607 SCIP_CALL( SCIPaddVarVub(scip, var, probingvar, (rightproplbs[j] - leftproplbs[j]) / (rightlb - leftub), (leftproplbs[j] * rightlb - rightproplbs[j] * leftub) / (rightlb - leftub), cutoff, &nboundchanges) );
1608 (*nchgbds) += nboundchanges;
1609
1610 if( *cutoff )
1611 {
1612 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible vub: %g<%s> - %g<%s> == %g\n",
1613 SCIPvarGetName(probingvar), rightlb - leftub, SCIPvarGetName(var),
1614 rightproplbs[j] - leftproplbs[j], SCIPvarGetName(probingvar),
1615 leftproplbs[j] * rightlb - rightproplbs[j] * leftub);
1616 }
1617 }
1618 (*nimplications)++;
1619 }
1620 /* if probingvar is continuous and we are in solving stage, then we do nothing, but it's unlikely that we get
1621 * here (fixedleft && fixedright) with a continuous variable
1622 */
1623 }
1624 /* @todo: check if we can add variable lowerbounds/upperbounds on integer variables */
1625 /* can only add implications on binary variables which are globally valid */
1626 else if( probingvarisbinary && (SCIPgetStage(scip) != SCIP_STAGE_SOLVING || SCIPnodeGetDepth(SCIPgetCurrentNode(scip)) == 0) )
1627 {
1628 /* implications can be added only for binary variables */
1629 int nboundchanges;
1630
1631 /* since probing var is binary variable, probing should have fixed variable in both branches,
1632 * which is to 0.0 in the left branch and to 1.0 in the right branch */
1633 assert(fixedleft);
1634 assert(fixedright);
1635 assert(SCIPisZero(scip, leftub));
1636 assert(SCIPisEQ(scip, rightlb, 1.0));
1637
1638 if( SCIPisEQ(scip, newlb, leftpropubs[j]) && (leftimplubs == NULL || leftimplubs[j] > leftpropubs[j]) )
1639 {
1640 /* var is fixed to lower bound whenever probingvar is fixed to 0.0
1641 * and implication is not already known
1642 * -> insert implication: probingvar == 0 => var <= leftpropubs[j]
1643 */
1644 /*SCIPdebugMsg(scip, "found implication <%s> == 0 => <%s> == %g\n",
1645 SCIPvarGetName(probingvar), SCIPvarGetName(var), leftpropubs[j]);*/
1646 SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_UPPER, leftpropubs[j],
1647 cutoff, &nboundchanges) );
1648 (*nimplications)++;
1649 (*nchgbds) += nboundchanges;
1650
1651 if( *cutoff )
1652 {
1653 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> == %g\n",
1654 SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), leftpropubs[j]);
1655 }
1656 }
1657 else if( SCIPisEQ(scip, newub, leftproplbs[j]) && (leftimpllbs == NULL || leftimpllbs[j] < leftproplbs[j]) )
1658 {
1659 /* var is fixed to upper bound whenever probingvar is fixed to 0.0
1660 * and implication is not already known
1661 * -> insert implication: probingvar == 0 => var >= leftproplbs[j]
1662 */
1663 /*SCIPdebugMsg(scip, "found implication <%s> == 0 => <%s> == %g\n",
1664 SCIPvarGetName(probingvar), SCIPvarGetName(var), leftproplbs[j]);*/
1665 SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_LOWER, leftproplbs[j],
1666 cutoff, &nboundchanges) );
1667 (*nimplications)++;
1668 (*nchgbds) += nboundchanges;
1669
1670 if( *cutoff )
1671 {
1672 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> == %g\n",
1673 SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), leftproplbs[j]);
1674 }
1675 }
1676 /* we can do an else here, since the case where var is fixed for both fixings of probingvar had been handled as aggregation */
1677 else if( SCIPisEQ(scip, newlb, rightpropubs[j]) && (rightimplubs == NULL || rightimplubs[j] > rightpropubs[j]) )
1678 {
1679 /* var is fixed to lower bound whenever probingvar is fixed to 1.0
1680 * and implication is not already known
1681 * -> insert implication: probingvar == 1 => var <= rightpropubs[j]
1682 */
1683 /*SCIPdebugMsg(scip, "found implication <%s> == 1 => <%s> == %g\n",
1684 SCIPvarGetName(probingvar), SCIPvarGetName(var), rightpropubs[j]);*/
1685 SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_UPPER, rightpropubs[j],
1686 cutoff, &nboundchanges) );
1687 (*nimplications)++;
1688 (*nchgbds) += nboundchanges;
1689
1690 if( *cutoff )
1691 {
1692 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> == %g\n",
1693 SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), rightpropubs[j]);
1694 }
1695 }
1696 else if( SCIPisEQ(scip, newub, rightproplbs[j]) && (rightimpllbs == NULL || rightimpllbs[j] < rightproplbs[j]) )
1697 {
1698 /* var is fixed to upper bound whenever probingvar is fixed to 1.0
1699 * and implication is not already known
1700 * -> insert implication: probingvar == 1 => var >= leftproplbs[j]
1701 */
1702 /*SCIPdebugMsg(scip, "found implication <%s> == 1 => <%s> == %g\n",
1703 SCIPvarGetName(probingvar), SCIPvarGetName(var), rightproplbs[j]);*/
1704 SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_LOWER, rightproplbs[j],
1705 cutoff, &nboundchanges) );
1706 (*nimplications)++;
1707 (*nchgbds) += nboundchanges;
1708
1709 if( *cutoff )
1710 {
1711 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> == %g\n",
1712 SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), rightproplbs[j]);
1713 }
1714 }
1715 else if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
1716 {
1717 /* check for implications for lower or upper bounds (only store implications with bounds tightened at least by 0.5)
1718 * in case of binary variables, this should have been handled in the previous cases, since every boundchange also fixes the variable
1719 */
1720 if( leftpropubs[j] < newub - 0.5 && (leftimplubs == NULL || leftpropubs[j] < leftimplubs[j]) )
1721 {
1722 /* insert implication: probingvar == 0 => var <= leftpropubs[j] */
1723 /*SCIPdebugMsg(scip, "found implication <%s> == 0 => <%s>[%g,%g] <= %g\n",
1724 SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, leftpropubs[j]);*/
1725 SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_UPPER, leftpropubs[j],
1726 cutoff, &nboundchanges) );
1727 (*nimplications)++;
1728 (*nchgbds) += nboundchanges;
1729
1730 if( *cutoff )
1731 {
1732 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> <= %g\n",
1733 SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), leftpropubs[j]);
1734 }
1735 }
1736 if( leftproplbs[j] > newlb + 0.5 && (leftimpllbs == NULL || leftproplbs[j] > leftimpllbs[j]) && !*cutoff )
1737 {
1738 /* insert implication: probingvar == 0 => var >= leftproplbs[j] */
1739 /*SCIPdebugMsg(scip, "found implication <%s> == 0 => <%s>[%g,%g] >= %g\n",
1740 SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, leftproplbs[j]);*/
1741 SCIP_CALL( SCIPaddVarImplication(scip, probingvar, FALSE, var, SCIP_BOUNDTYPE_LOWER, leftproplbs[j],
1742 cutoff, &nboundchanges) );
1743 (*nimplications)++;
1744 (*nchgbds) += nboundchanges;
1745
1746 if( *cutoff )
1747 {
1748 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 0 => <%s> >= %g\n",
1749 SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), leftproplbs[j]);
1750 }
1751 }
1752 if( rightpropubs[j] < newub - 0.5 && (rightimplubs == NULL || rightpropubs[j] < rightimplubs[j]) && !*cutoff )
1753 {
1754 /* insert implication: probingvar == 1 => var <= rightpropubs[j] */
1755 /*SCIPdebugMsg(scip, "found implication <%s> == 1 => <%s>[%g,%g] <= %g\n",
1756 SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, rightpropubs[j]);*/
1757 SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_UPPER, rightpropubs[j],
1758 cutoff, &nboundchanges) );
1759 (*nimplications)++;
1760 (*nchgbds) += nboundchanges;
1761
1762 if( *cutoff )
1763 {
1764 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> <= %g\n",
1765 SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), rightpropubs[j]);
1766 }
1767 }
1768 if( rightproplbs[j] > newlb + 0.5 && (rightimpllbs == NULL || rightproplbs[j] > rightimpllbs[j]) && !*cutoff )
1769 {
1770 /* insert implication: probingvar == 1 => var >= rightproplbs[j] */
1771 /*SCIPdebugMsg(scip, "found implication <%s> == 1 => <%s>[%g,%g] >= %g\n",
1772 SCIPvarGetName(probingvar), SCIPvarGetName(var), newlb, newub, rightproplbs[j]);*/
1773 SCIP_CALL( SCIPaddVarImplication(scip, probingvar, TRUE, var, SCIP_BOUNDTYPE_LOWER, rightproplbs[j],
1774 cutoff, &nboundchanges) );
1775 (*nimplications)++;
1776 (*nchgbds) += nboundchanges;
1777
1778 if( *cutoff )
1779 {
1780 SCIPdebugMsg(scip, "analyzing probing deduction of <%s> led to an infeasible implication <%s> == 1 => <%s> <= %g\n",
1781 SCIPvarGetName(probingvar), SCIPvarGetName(probingvar), SCIPvarGetName(var), rightproplbs[j]);
1782 }
1783 }
1784 }
1785 }
1786 }
1787
1788 return SCIP_OKAY;
1789}
static long bound
#define NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define ABS(x)
Definition: def.h:235
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#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 SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2127
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1067
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
int SCIPgetNTotalVars(SCIP *scip)
Definition: scip_prob.c:2569
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_Real SCIPselectSimpleValue(SCIP_Real lb, SCIP_Real ub, SCIP_Longint maxdnom)
Definition: misc.c:9824
SCIP_RETCODE SCIPapplyProbingVar(SCIP *scip, SCIP_VAR **vars, int nvars, int probingpos, SCIP_BOUNDTYPE boundtype, SCIP_Real bound, int maxproprounds, SCIP_Real *impllbs, SCIP_Real *implubs, SCIP_Real *proplbs, SCIP_Real *propubs, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPanalyzeDeductionsProbing(SCIP *scip, SCIP_VAR *probingvar, SCIP_Real leftub, SCIP_Real rightlb, int nvars, SCIP_VAR **vars, SCIP_Real *leftimpllbs, SCIP_Real *leftimplubs, SCIP_Real *leftproplbs, SCIP_Real *leftpropubs, SCIP_Real *rightimpllbs, SCIP_Real *rightimplubs, SCIP_Real *rightproplbs, SCIP_Real *rightpropubs, int *nfixedvars, int *naggrvars, int *nimplications, int *nchgbds, SCIP_Bool *cutoff)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition: misc.c:10396
SCIP_RETCODE SCIPincludePropProbing(SCIP *scip)
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:395
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:168
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:81
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip_mem.h:70
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPduplicateMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:76
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:80
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7493
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7503
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:345
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:301
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:580
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:119
SCIP_RETCODE SCIPpropagateProbingImplications(SCIP *scip, SCIP_Bool *cutoff)
Definition: scip_probing.c:686
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:260
void SCIPpropSetData(SCIP_PROP *prop, SCIP_PROPDATA *propdata)
Definition: prop.c:799
SCIP_RETCODE SCIPsetPropInitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITSOL((*propinitsol)))
Definition: scip_prop.c:215
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:312
SCIP_PROPDATA * SCIPpropGetData(SCIP_PROP *prop)
Definition: prop.c:789
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_prop.c:279
SCIP_RETCODE SCIPsetPropExitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITPRE((*propexitpre)))
Definition: scip_prop.c:263
const char * SCIPpropGetName(SCIP_PROP *prop)
Definition: prop.c:941
SCIP_RETCODE SCIPsetPropExit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXIT((*propexit)))
Definition: scip_prop.c:199
SCIP_RETCODE SCIPsetPropInit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINIT((*propinit)))
Definition: scip_prop.c:183
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITPRE((*propinitpre)))
Definition: scip_prop.c:247
SCIP_Real SCIPpropGetTime(SCIP_PROP *prop)
Definition: prop.c:1056
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:167
SCIP_RETCODE SCIPsetPropCopy(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPCOPY((*propcopy)))
Definition: scip_prop.c:151
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip_prop.c:114
int SCIPgetNRuns(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
SCIP_Bool SCIPisUbBetter(SCIP *scip, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLbBetter(SCIP *scip, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5203
SCIP_Bool SCIPvarIsDeleted(SCIP_VAR *var)
Definition: var.c:17640
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17748
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17599
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18356
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3353
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
Definition: scip_var.c:8401
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5320
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
SCIP_RETCODE SCIPaddVarVub(SCIP *scip, SCIP_VAR *var, SCIP_VAR *vubvar, SCIP_Real vubcoef, SCIP_Real vubconstant, SCIP_Bool *infeasible, int *nbdchgs)
Definition: scip_var.c:6720
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17758
SCIP_RETCODE SCIPaddVarVlb(SCIP *scip, SCIP_VAR *var, SCIP_VAR *vlbvar, SCIP_Real vlbcoef, SCIP_Real vlbconstant, SCIP_Bool *infeasible, int *nbdchgs)
Definition: scip_var.c:6661
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_RETCODE SCIPaddVarImplication(SCIP *scip, SCIP_VAR *var, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype, SCIP_Real implbound, SCIP_Bool *infeasible, int *nbdchgs)
Definition: scip_var.c:6780
int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18430
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
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
void SCIPenableVarHistory(SCIP *scip)
Definition: scip_var.c:8741
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1214
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition: misc.c:10130
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
void SCIPsortDownRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
#define PROP_PRESOL_MAXROUNDS
Definition: prop_probing.c:69
#define PROP_PRESOLTIMING
Definition: prop_probing.c:68
#define PROP_DESC
Definition: prop_probing.c:61
static SCIP_DECL_PROPINIT(propInitProbing)
Definition: prop_probing.c:769
#define MAXDNOM
Definition: prop_probing.c:71
#define PROP_NAME
Definition: prop_probing.c:60
static SCIP_DECL_PROPCOPY(propCopyProbing)
Definition: prop_probing.c:734
static SCIP_DECL_PROPEXIT(propExitProbing)
Definition: prop_probing.c:788
static SCIP_DECL_PROPEXITPRE(propExitpreProbing)
Definition: prop_probing.c:823
#define DEFAULT_MAXUSELESS
Definition: prop_probing.c:88
static SCIP_DECL_PROPINITSOL(propInitsolProbing)
Definition: prop_probing.c:845
static SCIP_DECL_PROPFREE(propFreeProbing)
Definition: prop_probing.c:749
static SCIP_DECL_PROPPRESOL(propPresolProbing)
Definition: prop_probing.c:864
#define DEFAULT_MAXDEPTH
Definition: prop_probing.c:94
#define DEFAULT_MAXTOTALUSELESS
Definition: prop_probing.c:90
#define PROP_DELAY
Definition: prop_probing.c:65
static SCIP_RETCODE applyProbing(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR **vars, int nvars, int nbinvars, int *startidx, int *nfixedvars, int *naggrvars, int *nchgbds, int oldnfixedvars, int oldnaggrvars, SCIP_Bool *delay, SCIP_Bool *cutoff)
Definition: prop_probing.c:343
#define DEFAULT_PROPROUNDS
Definition: prop_probing.c:85
static SCIP_RETCODE initPropdata(SCIP_PROPDATA *propdata)
Definition: prop_probing.c:139
#define PROP_TIMING
Definition: prop_probing.c:62
static SCIP_RETCODE freeSortedvars(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_probing.c:167
static SCIP_DECL_PROPEXEC(propExecProbing)
Definition: prop_probing.c:998
#define DEFAULT_RANDSEED
Definition: prop_probing.c:95
#define DEFAULT_MAXSUMUSELESS
Definition: prop_probing.c:92
static SCIP_RETCODE sortVariables(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_VAR **vars, int nvars, int firstidx)
Definition: prop_probing.c:196
#define DEFAULT_MAXRUNS
Definition: prop_probing.c:84
#define PROP_FREQ
Definition: prop_probing.c:64
static SCIP_DECL_PROPINITPRE(propInitpreProbing)
Definition: prop_probing.c:808
#define PROP_PRIORITY
Definition: prop_probing.c:63
static SCIP_DECL_PROPRESPROP(propRespropProbing)
#define PROP_PRESOL_PRIORITY
Definition: prop_probing.c:67
#define DEFAULT_MAXFIXINGS
Definition: prop_probing.c:86
probing propagator
public methods for message output
#define SCIPdebug(x)
Definition: pub_message.h:93
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for propagators
public methods for branch and bound tree
public methods for problem variables
public methods for branching rule plugins and branching
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for propagator plugins
public methods for random numbers
public methods for querying solving statistics
public methods for timing
public methods for the branch-and-bound tree
public methods for SCIP variables
@ SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:57
@ SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:56
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
enum SCIP_VerbLevel SCIP_VERBLEVEL
Definition: type_message.h:59
@ SCIP_VERBLEVEL_HIGH
Definition: type_message.h:56
@ SCIP_VERBLEVEL_FULL
Definition: type_message.h:57
struct SCIP_PropData SCIP_PROPDATA
Definition: type_prop.h:52
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ 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_STAGE_SOLVING
Definition: type_set.h:53
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62
@ SCIP_LOCKTYPE_MODEL
Definition: type_var.h:97