Scippy

SCIP

Solving Constraint Integer Programs

relax.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 relax.c
26 * @ingroup OTHER_CFILES
27 * @brief methods and datastructures for relaxation handlers
28 * @author Tobias Achterberg
29 * @author Timo Berthold
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
34#include <assert.h>
35#include <string.h>
36
37#include "scip/def.h"
38#include "scip/set.h"
39#include "scip/tree.h"
40#include "scip/stat.h"
41#include "scip/clock.h"
42#include "scip/paramset.h"
43#include "scip/scip.h"
44#include "scip/scip_cut.h"
45#include "scip/sol.h"
46#include "scip/var.h"
47#include "scip/relax.h"
48#include "scip/pub_message.h"
49#include "scip/pub_misc.h"
50
51#include "scip/struct_relax.h"
52
53
54
55/** compares two relaxation handlers w. r. to their priority */
57{ /*lint --e{715}*/
58 return ((SCIP_RELAX*)elem2)->priority - ((SCIP_RELAX*)elem1)->priority;
59}
60
61/** comparison method for sorting relaxators w.r.t. to their name */
62SCIP_DECL_SORTPTRCOMP(SCIPrelaxCompName)
63{
64 return strcmp(SCIPrelaxGetName((SCIP_RELAX*)elem1), SCIPrelaxGetName((SCIP_RELAX*)elem2));
65}
66
67/** method to call, when the priority of a relaxation handler was changed */
68static
69SCIP_DECL_PARAMCHGD(paramChgdRelaxPriority)
70{ /*lint --e{715}*/
71 SCIP_PARAMDATA* paramdata;
72
73 paramdata = SCIPparamGetData(param);
74 assert(paramdata != NULL);
75
76 /* use SCIPsetRelaxPriority() to mark the relaxs unsorted */
77 SCIP_CALL( SCIPsetRelaxPriority(scip, (SCIP_RELAX*)paramdata, SCIPparamGetInt(param)) ); /*lint !e740*/
78
79 return SCIP_OKAY;
80}
81
82/** copies the given relaxation handler to a new scip */
84 SCIP_RELAX* relax, /**< relaxation handler */
85 SCIP_SET* set /**< SCIP_SET of SCIP to copy to */
86 )
87{
88 assert(relax != NULL);
89 assert(set != NULL);
90 assert(set->scip != NULL);
91
92 if( relax->relaxcopy != NULL )
93 {
94 SCIPsetDebugMsg(set, "including relaxation handler %s in subscip %p\n", SCIPrelaxGetName(relax), (void*)set->scip);
95 SCIP_CALL( relax->relaxcopy(set->scip, relax) );
96 }
97 return SCIP_OKAY;
98}
99
100/** internal method for creating a relaxation handler */
101static
103 SCIP_RELAX** relax, /**< pointer to relaxation handler data structure */
104 SCIP_SET* set, /**< global SCIP settings */
105 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
106 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
107 const char* name, /**< name of relaxation handler */
108 const char* desc, /**< description of relaxation handler */
109 int priority, /**< priority of the relaxation handler (negative: after LP, non-negative: before LP) */
110 int freq, /**< frequency for calling relaxation handler */
111 SCIP_DECL_RELAXCOPY ((*relaxcopy)), /**< copy method of relaxation handler or NULL if you don't want to copy your plugin into sub-SCIPs */
112 SCIP_DECL_RELAXFREE ((*relaxfree)), /**< destructor of relaxation handler */
113 SCIP_DECL_RELAXINIT ((*relaxinit)), /**< initialize relaxation handler */
114 SCIP_DECL_RELAXEXIT ((*relaxexit)), /**< deinitialize relaxation handler */
115 SCIP_DECL_RELAXINITSOL((*relaxinitsol)), /**< solving process initialization method of relaxation handler */
116 SCIP_DECL_RELAXEXITSOL((*relaxexitsol)), /**< solving process deinitialization method of relaxation handler */
117 SCIP_DECL_RELAXEXEC ((*relaxexec)), /**< execution method of relaxation handler */
118 SCIP_RELAXDATA* relaxdata /**< relaxation handler data */
119 )
120{
122 char paramdesc[SCIP_MAXSTRLEN];
123
124 assert(relax != NULL);
125 assert(name != NULL);
126 assert(desc != NULL);
127 assert(freq >= -1);
128 assert(relaxexec != NULL);
129
130 SCIP_ALLOC( BMSallocMemory(relax) );
131 BMSclearMemory(*relax);
132
133 SCIP_ALLOC( BMSduplicateMemoryArray(&(*relax)->name, name, strlen(name)+1) );
134 SCIP_ALLOC( BMSduplicateMemoryArray(&(*relax)->desc, desc, strlen(desc)+1) );
135 (*relax)->priority = priority;
136 (*relax)->freq = freq;
137 (*relax)->relaxcopy = relaxcopy;
138 (*relax)->relaxfree = relaxfree;
139 (*relax)->relaxinit = relaxinit;
140 (*relax)->relaxexit = relaxexit;
141 (*relax)->relaxinitsol = relaxinitsol;
142 (*relax)->relaxexitsol = relaxexitsol;
143 (*relax)->relaxexec = relaxexec;
144 (*relax)->relaxdata = relaxdata;
145 SCIP_CALL( SCIPclockCreate(&(*relax)->setuptime, SCIP_CLOCKTYPE_DEFAULT) );
146 SCIP_CALL( SCIPclockCreate(&(*relax)->relaxclock, SCIP_CLOCKTYPE_DEFAULT) );
147 (*relax)->ncalls = 0;
148 (*relax)->ncutoffs = 0;
149 (*relax)->nimprbounds = 0;
150 (*relax)->imprtime = 0.0;
151 (*relax)->naddedconss = 0;
152 (*relax)->nreduceddom = 0;
153 (*relax)->nseparated = 0;
154 (*relax)->lastsolvednode = -1;
155 (*relax)->initialized = FALSE;
156
157 /* add parameters */
158 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "relaxing/%s/priority", name);
159 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "priority of relaxation handler <%s>", name);
160 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
161 &(*relax)->priority, FALSE, priority, INT_MIN/4, INT_MAX/4,
162 paramChgdRelaxPriority, (SCIP_PARAMDATA*)(*relax)) ); /*lint !e740*/
163 (void) SCIPsnprintf(paramname, SCIP_MAXSTRLEN, "relaxing/%s/freq", name);
164 (void) SCIPsnprintf(paramdesc, SCIP_MAXSTRLEN, "frequency for calling relaxation handler <%s> (-1: never, 0: only in root node)", name);
165 SCIP_CALL( SCIPsetAddIntParam(set, messagehdlr, blkmem, paramname, paramdesc,
166 &(*relax)->freq, FALSE, freq, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
167
168 return SCIP_OKAY;
169}
170
171/** creates a relaxation handler */
173 SCIP_RELAX** relax, /**< pointer to relaxation handler data structure */
174 SCIP_SET* set, /**< global SCIP settings */
175 SCIP_MESSAGEHDLR* messagehdlr, /**< message handler */
176 BMS_BLKMEM* blkmem, /**< block memory for parameter settings */
177 const char* name, /**< name of relaxation handler */
178 const char* desc, /**< description of relaxation handler */
179 int priority, /**< priority of the relaxation handler (negative: after LP, non-negative: before LP) */
180 int freq, /**< frequency for calling relaxation handler */
181 SCIP_DECL_RELAXCOPY ((*relaxcopy)), /**< copy method of relaxation handler or NULL if you don't want to copy your plugin into sub-SCIPs */
182 SCIP_DECL_RELAXFREE ((*relaxfree)), /**< destructor of relaxation handler */
183 SCIP_DECL_RELAXINIT ((*relaxinit)), /**< initialize relaxation handler */
184 SCIP_DECL_RELAXEXIT ((*relaxexit)), /**< deinitialize relaxation handler */
185 SCIP_DECL_RELAXINITSOL((*relaxinitsol)), /**< solving process initialization method of relaxation handler */
186 SCIP_DECL_RELAXEXITSOL((*relaxexitsol)), /**< solving process deinitialization method of relaxation handler */
187 SCIP_DECL_RELAXEXEC ((*relaxexec)), /**< execution method of relaxation handler */
188 SCIP_RELAXDATA* relaxdata /**< relaxation handler data */
189 )
190{
191 assert(relax != NULL);
192 assert(name != NULL);
193 assert(desc != NULL);
194 assert(freq >= -1);
195 assert(relaxexec != NULL);
196
197 SCIP_CALL_FINALLY( doRelaxCreate(relax, set, messagehdlr, blkmem, name, desc, priority, freq, relaxcopy, relaxfree,
198 relaxinit, relaxexit, relaxinitsol, relaxexitsol, relaxexec, relaxdata), (void) SCIPrelaxFree(relax, set) );
199
200 return SCIP_OKAY;
201}
202
203/** calls destructor and frees memory of relaxation handler */
205 SCIP_RELAX** relax, /**< pointer to relaxation handler data structure */
206 SCIP_SET* set /**< global SCIP settings */
207 )
208{
209 assert(relax != NULL);
210 if( *relax == NULL )
211 return SCIP_OKAY;
212 assert(!(*relax)->initialized);
213 assert(set != NULL);
214
215 /* call destructor of relaxation handler */
216 if( (*relax)->relaxfree != NULL )
217 {
218 SCIP_CALL( (*relax)->relaxfree(set->scip, *relax) );
219 }
220
221 SCIPclockFree(&(*relax)->relaxclock);
222 SCIPclockFree(&(*relax)->setuptime);
223 BMSfreeMemoryArrayNull(&(*relax)->name);
224 BMSfreeMemoryArrayNull(&(*relax)->desc);
225 BMSfreeMemory(relax);
226
227 return SCIP_OKAY;
228}
229
230/** initializes relaxation handler */
232 SCIP_RELAX* relax, /**< relaxation handler */
233 SCIP_SET* set /**< global SCIP settings */
234 )
235{
236 assert(relax != NULL);
237 assert(set != NULL);
238
239 if( relax->initialized )
240 {
241 SCIPerrorMessage("relaxation handler <%s> already initialized\n", relax->name);
242 return SCIP_INVALIDCALL;
243 }
244
245 if( set->misc_resetstat )
246 {
249 relax->ncalls = 0;
250 relax->ncutoffs = 0;
251 relax->nimprbounds = 0;
252 relax->imprtime = 0.0;
253 relax->naddedconss = 0;
254 relax->nreduceddom = 0;
255 relax->nseparated = 0;
256 relax->lastsolvednode = -1;
257 }
258
259 if( relax->relaxinit != NULL )
260 {
261 /* start timing */
263
264 SCIP_CALL( relax->relaxinit(set->scip, relax) );
265
266 /* stop timing */
267 SCIPclockStop(relax->setuptime, set);
268 }
269 relax->initialized = TRUE;
270
271 return SCIP_OKAY;
272}
273
274/** calls exit method of relaxation handler */
276 SCIP_RELAX* relax, /**< relaxation handler */
277 SCIP_SET* set /**< global SCIP settings */
278 )
279{
280 assert(relax != NULL);
281 assert(set != NULL);
282
283 if( !relax->initialized )
284 {
285 SCIPerrorMessage("relaxation handler <%s> not initialized\n", relax->name);
286 return SCIP_INVALIDCALL;
287 }
288
289 if( relax->relaxexit != NULL )
290 {
291 /* start timing */
293
294 SCIP_CALL( relax->relaxexit(set->scip, relax) );
295
296 /* stop timing */
297 SCIPclockStop(relax->setuptime, set);
298 }
299 relax->initialized = FALSE;
300
301 return SCIP_OKAY;
302}
303
304/** informs relaxation handler that the branch and bound process is being started */
306 SCIP_RELAX* relax, /**< relaxation handler */
307 SCIP_SET* set /**< global SCIP settings */
308 )
309{
310 assert(relax != NULL);
311 assert(set != NULL);
312
313 /* call solving process initialization method of relaxation handler */
314 if( relax->relaxinitsol != NULL )
315 {
316 /* start timing */
318
319 SCIP_CALL( relax->relaxinitsol(set->scip, relax) );
320
321 /* stop timing */
322 SCIPclockStop(relax->setuptime, set);
323 }
324
325 return SCIP_OKAY;
326}
327
328/** informs relaxation handler that the branch and bound process data is being freed */
330 SCIP_RELAX* relax, /**< relaxation handler */
331 SCIP_SET* set /**< global SCIP settings */
332 )
333{
334 assert(relax != NULL);
335 assert(set != NULL);
336
337 /* call solving process deinitialization method of relaxation handler */
338 if( relax->relaxexitsol != NULL )
339 {
340 /* start timing */
342
343 SCIP_CALL( relax->relaxexitsol(set->scip, relax) );
344
345 /* stop timing */
346 SCIPclockStop(relax->setuptime, set);
347 }
348
349 return SCIP_OKAY;
350}
351
352/** calls execution method of relaxation handler */
354 SCIP_RELAX* relax, /**< relaxation handler */
355 SCIP_SET* set, /**< global SCIP settings */
356 SCIP_TREE* tree, /**< branch and bound tree */
357 SCIP_STAT* stat, /**< dynamic problem statistics */
358 int depth, /**< depth of current node */
359 SCIP_Real* lowerbound, /**< pointer to lower bound computed by the relaxation handler */
360 SCIP_RESULT* result /**< pointer to store the result of the callback method */
361 )
362{
363 assert(relax != NULL);
364 assert(relax->relaxexec != NULL);
365 assert(relax->freq >= -1);
366 assert(set != NULL);
367 assert(set->scip != NULL);
368 assert(depth >= 0);
369 assert(result != NULL);
370
371 *result = SCIP_DIDNOTRUN;
372
373 /* check, if the relaxation is already solved */
374 if( relax->lastsolvednode == stat->ntotalnodes && ! SCIPinProbing(set->scip) )
375 return SCIP_OKAY;
376
377 relax->lastsolvednode = stat->ntotalnodes;
378
379 if( (depth == 0 && relax->freq == 0) || (relax->freq > 0 && depth % relax->freq == 0) )
380 {
381 SCIP_Real starttime;
382 int oldnactiveconss;
383 int oldncuts;
384
385 SCIPsetDebugMsg(set, "executing relaxation handler <%s>\n", relax->name);
386
387 oldnactiveconss = stat->nactiveconss;
388 oldncuts = SCIPgetNCuts(set->scip);
389
390 /* start timing */
391 starttime = SCIPclockGetTime(relax->relaxclock);
393
394 /* call external relaxation method */
395 SCIP_CALL( relax->relaxexec(set->scip, relax, lowerbound, result) );
396
397 /* stop timing */
399
400 /* evaluate result */
401 if( *result != SCIP_CUTOFF
402 && *result != SCIP_CONSADDED
403 && *result != SCIP_REDUCEDDOM
404 && *result != SCIP_SEPARATED
405 && *result != SCIP_SUCCESS
406 && *result != SCIP_SUSPENDED
407 && *result != SCIP_DIDNOTRUN )
408 {
409 SCIPerrorMessage("execution method of relaxation handler <%s> returned invalid result <%d>\n",
410 relax->name, *result);
411 return SCIP_INVALIDRESULT;
412 }
413 if( *result != SCIP_DIDNOTRUN )
414 {
415 relax->ncalls++;
416 stat->relaxcount++;
417 if( *result == SCIP_SUSPENDED )
419 else if( *result == SCIP_CUTOFF || SCIPsetIsInfinity(set, *lowerbound) )
420 {
421 ++relax->ncutoffs;
422 relax->imprtime += SCIPclockGetTime(relax->relaxclock) - starttime;
423 }
424 else
425 {
426 SCIP_NODE* node;
427 SCIP_Real oldlowerbound;
428
429 node = SCIPtreeGetCurrentNode(tree);
430 if( node != NULL )
431 oldlowerbound = SCIPnodeGetLowerbound(node);
432 else
433 oldlowerbound = -SCIPsetInfinity(set);
434
435 if( !SCIPsetIsInfinity(set, -*lowerbound) && SCIPsetIsRelGT(set, *lowerbound, oldlowerbound) )
436 {
437 ++relax->nimprbounds;
438 relax->imprtime += SCIPclockGetTime(relax->relaxclock) - starttime;
439 }
440
441 if( stat->nactiveconss > oldnactiveconss )
442 ++relax->naddedconss;
443 if( SCIPgetNCuts(set->scip) > oldncuts )
444 ++relax->nseparated;
445 if( *result == SCIP_REDUCEDDOM )
446 ++relax->nreduceddom;
447 }
448 }
449 }
450
451 return SCIP_OKAY;
452}
453
454/** gets user data of relaxation handler */
456 SCIP_RELAX* relax /**< relaxation handler */
457 )
458{
459 assert(relax != NULL);
460
461 return relax->relaxdata;
462}
463
464/** sets user data of relaxation handler; user has to free old data in advance! */
466 SCIP_RELAX* relax, /**< relaxation handler */
467 SCIP_RELAXDATA* relaxdata /**< new relaxation handler user data */
468 )
469{
470 assert(relax != NULL);
471
472 relax->relaxdata = relaxdata;
473}
474
475/** set copy method of relaxation handler */
477 SCIP_RELAX* relax, /**< relaxation handler */
478 SCIP_DECL_RELAXCOPY ((*relaxcopy)) /**< copy method of relaxation handler */
479 )
480{
481 assert(relax != NULL);
482
483 relax->relaxcopy = relaxcopy;
484}
485
486/** set destructor of relaxation handler */
488 SCIP_RELAX* relax, /**< relaxation handler */
489 SCIP_DECL_RELAXFREE ((*relaxfree)) /**< destructor of relaxation handler */
490 )
491{
492 assert(relax != NULL);
493
494 relax->relaxfree = relaxfree;
495}
496
497/** set initialization method of relaxation handler */
499 SCIP_RELAX* relax, /**< relaxation handler */
500 SCIP_DECL_RELAXINIT ((*relaxinit)) /**< initialize relaxation handler */
501 )
502{
503 assert(relax != NULL);
504
505 relax->relaxinit = relaxinit;
506}
507
508/** set deinitialization method of relaxation handler */
510 SCIP_RELAX* relax, /**< relaxation handler */
511 SCIP_DECL_RELAXEXIT ((*relaxexit)) /**< deinitialize relaxation handler */
512 )
513{
514 assert(relax != NULL);
515
516 relax->relaxexit = relaxexit;
517}
518
519/** set solving process initialization method of relaxation handler */
521 SCIP_RELAX* relax, /**< relaxation handler */
522 SCIP_DECL_RELAXINITSOL((*relaxinitsol)) /**< solving process initialization method of relaxation handler */
523 )
524{
525 assert(relax != NULL);
526
527 relax->relaxinitsol = relaxinitsol;
528}
529
530/** set solving process deinitialization method of relaxation handler */
532 SCIP_RELAX* relax, /**< relaxation handler */
533 SCIP_DECL_RELAXEXITSOL((*relaxexitsol)) /**< solving process deinitialization relaxation handler */
534 )
535{
536 assert(relax != NULL);
537
538 relax->relaxexitsol = relaxexitsol;
539}
540
541/** gets name of relaxation handler */
543 SCIP_RELAX* relax /**< relaxation handler */
544 )
545{
546 assert(relax != NULL);
547
548 return relax->name;
549}
550
551/** gets description of relaxation handler */
553 SCIP_RELAX* relax /**< relaxation handler */
554 )
555{
556 assert(relax != NULL);
557
558 return relax->desc;
559}
560
561/** gets priority of relaxation handler */
563 SCIP_RELAX* relax /**< relaxation handler */
564 )
565{
566 assert(relax != NULL);
567
568 return relax->priority;
569}
570
571/** sets priority of relaxation handler */
573 SCIP_RELAX* relax, /**< relaxation handler */
574 SCIP_SET* set, /**< global SCIP settings */
575 int priority /**< new priority of the relaxation handler */
576 )
577{
578 assert(relax != NULL);
579 assert(set != NULL);
580
581 relax->priority = priority;
582 set->relaxssorted = FALSE;
583}
584
585/** gets frequency of relaxation handler */
587 SCIP_RELAX* relax /**< relaxation handler */
588 )
589{
590 assert(relax != NULL);
591
592 return relax->freq;
593}
594
595/** gets time in seconds used in this relaxator for setting up for next stages */
597 SCIP_RELAX* relax /**< relaxator */
598 )
599{
600 assert(relax != NULL);
601
602 return SCIPclockGetTime(relax->setuptime);
603}
604
605/** enables or disables all clocks of \p relax, depending on the value of the flag */
607 SCIP_RELAX* relax, /**< the relaxation handler for which all clocks should be enabled or disabled */
608 SCIP_Bool enable /**< should the clocks of the relaxation handler be enabled? */
609 )
610{
611 assert(relax != NULL);
612
613 SCIPclockEnableOrDisable(relax->setuptime, enable);
614 SCIPclockEnableOrDisable(relax->relaxclock, enable);
615}
616
617/** gets time in seconds used in this relaxation handler */
619 SCIP_RELAX* relax /**< relaxation handler */
620 )
621{
622 assert(relax != NULL);
623
624 return SCIPclockGetTime(relax->relaxclock);
625}
626
627/** gets the total number of times the relaxation handler was called */
629 SCIP_RELAX* relax /**< relaxation handler */
630 )
631{
632 assert(relax != NULL);
633
634 return relax->ncalls;
635}
636
637/** gets the total number of times the relaxation handler cut off a node */
639 SCIP_RELAX* relax /**< relaxation handler */
640 )
641{
642 assert(relax != NULL);
643
644 return relax->ncutoffs;
645}
646
647/** gets the total number of times the relaxation handler improved a node's lower bound */
649 SCIP_RELAX* relax /**< relaxation handler */
650 )
651{
652 assert(relax != NULL);
653
654 return relax->nimprbounds;
655}
656
657/** gets the total number of times the relaxation handler added constraints */
659 SCIP_RELAX* relax /**< relaxation handler */
660 )
661{
662 assert(relax != NULL);
663
664 return relax->naddedconss;
665}
666
667/** gets the time in seconds spent for the execution of the relaxation handler when a node's lower bound could be improved (or a cutoff was found) */
669 SCIP_RELAX* relax /**< relaxation handler */
670 )
671{
672 assert(relax != NULL);
673
674 return relax->imprtime;
675}
676
677/** gets the total number of times the relaxation handler reduced variable domains */
679 SCIP_RELAX* relax /**< relaxation handler */
680 )
681{
682 assert(relax != NULL);
683
684 return relax->nreduceddom;
685}
686
687/** gets the total number of times the relaxation handler separated cutting planes */
689 SCIP_RELAX* relax /**< relaxation handler */
690 )
691{
692 assert(relax != NULL);
693
694 return relax->nseparated;
695}
696
697/** is relaxation handler initialized? */
699 SCIP_RELAX* relax /**< relaxation handler */
700 )
701{
702 assert(relax != NULL);
703
704 return relax->initialized;
705}
706
707/** returns whether the relaxation was completely solved at the current node */
709 SCIP_RELAX* relax, /**< relaxation handler */
710 SCIP_STAT* stat /**< dynamic problem statistics */
711 )
712{
713 assert(relax != NULL);
714 assert(stat != NULL);
715
716 return (relax->lastsolvednode == stat->ntotalnodes);
717}
718
719/** marks the current relaxation unsolved, s.t. the relaxation handler is called again in the next solving round */
721 SCIP_RELAX* relax /**< relaxation handler */
722 )
723{
724 assert(relax != NULL);
725
726 relax->lastsolvednode = -1;
727}
728
729/*
730 * methods for the global relaxation data
731 */
732
733/** creates global relaxation data */
735 SCIP_RELAXATION** relaxation, /**< global relaxation data */
736 BMS_BLKMEM* blkmem, /**< block memory */
737 SCIP_SET* set, /**< global SCIP settings */
738 SCIP_STAT* stat, /**< problem statistics data */
739 SCIP_PRIMAL* primal, /**< primal data */
740 SCIP_TREE* tree /**< branch and bound tree */
741 )
742{
743 assert(relaxation != NULL);
744 assert(blkmem != NULL);
745 assert(set != NULL);
746 assert(stat != NULL);
747 assert(primal != NULL);
748 assert(tree != NULL);
749
750 SCIP_ALLOC( BMSallocMemory(relaxation) );
751
752 (*relaxation)->relaxsolobjval = 0.0;
753 (*relaxation)->relaxsolvalid = FALSE;
754 (*relaxation)->relaxsolincludeslp = FALSE;
755 (*relaxation)->relaxsolzero = TRUE;
756 (*relaxation)->lastsolrelax = NULL;
757
758 return SCIP_OKAY;
759}
760
761/** frees global relaxation data */
763 SCIP_RELAXATION** relaxation /**< global relaxation data */
764 )
765{
766 assert(relaxation != NULL);
767
768 BMSfreeMemory(relaxation);
769
770 return SCIP_OKAY;
771}
772
773/** sets the relaxsolzero flag in the relaxation data to the given value */
775 SCIP_RELAXATION* relaxation, /**< global relaxation data */
776 SCIP_Bool iszero /**< are all values of the relaxation solution set to zero? */
777 )
778{
779 assert(relaxation != NULL);
780
781 relaxation->relaxsolzero = iszero;
782}
783
784/** returns whether the global relaxation solution is cleared and all values are set to zero */
786 SCIP_RELAXATION* relaxation /**< global relaxation data */
787 )
788{
789 assert(relaxation != NULL);
790
791 return relaxation->relaxsolzero;
792}
793
794/** sets the relaxsolvalid and includeslp flags in the relaxation data to the given values */
796 SCIP_RELAXATION* relaxation, /**< global relaxation data */
797 SCIP_Bool isvalid, /**< is the stored solution valid? */
798 SCIP_Bool includeslp /**< does the relaxator contain all cuts in the LP? */
799 )
800{
801 assert(relaxation != NULL);
802
803 relaxation->relaxsolvalid = isvalid;
804 relaxation->relaxsolincludeslp = includeslp;
805}
806
807/** returns whether the global relaxation solution is valid */
809 SCIP_RELAXATION* relaxation /**< global relaxation data */
810 )
811{
812 assert(relaxation != NULL);
813
814 return relaxation->relaxsolvalid;
815}
816
817/** returns whether the global relaxation solution was computed by a relaxator which included all LP cuts */
819 SCIP_RELAXATION* relaxation /**< global relaxation data */
820 )
821{
822 assert(relaxation != NULL);
823
824 return relaxation->relaxsolincludeslp;
825}
826
827/** sets the objective value of the global relaxation solution */
829 SCIP_RELAXATION* relaxation, /**< global relaxation data */
830 SCIP_Real obj /**< objective value */
831 )
832{
833 assert(relaxation != NULL);
834
835 relaxation->relaxsolobjval = obj;
836}
837
838/** returns the objective value of the global relaxation solution w.r.t. the transformed problem */
840 SCIP_RELAXATION* relaxation /**< global relaxation data */
841 )
842{
843 assert(relaxation != NULL);
844
845 return relaxation->relaxsolobjval;
846}
847
848/** adds the given value to the global relaxation solution's objective value */
850 SCIP_RELAXATION* relaxation, /**< global relaxation data */
851 SCIP_Real val /**< value to add to the objective value */
852 )
853{
854 assert(relaxation != NULL);
855
856 relaxation->relaxsolobjval += val;
857}
858
859/** updates objective value of current relaxation solution after change of objective coefficient */
861 SCIP_RELAXATION* relaxation, /**< global relaxation data */
862 SCIP_SET* set, /**< global SCIP settings */
863 SCIP_VAR* var, /**< variable with changed objective coefficient */
864 SCIP_Real oldobj, /**< old objective coefficient */
865 SCIP_Real newobj /**< new objective coefficient */
866 )
867{
868 SCIP_Real relaxsolval;
869
870 assert(relaxation != NULL);
871 assert(set != NULL);
872 assert(var != NULL);
874
875 relaxsolval = SCIPvarGetRelaxSol(var, set);
876 relaxation->relaxsolobjval += (newobj - oldobj) * relaxsolval;
877}
878
879/** store the most recent relaxation handler \p relax responsible for the solution */
881 SCIP_RELAXATION* relaxation, /**< global relaxation data */
882 SCIP_RELAX* relax /**< responsible relaxation handler, or NULL */
883 )
884{
885 assert(relaxation != NULL);
886
887 relaxation->lastsolrelax = relax;
888}
889
890/** returns the most recent relaxation handler responsible for the solution, or NULL if unspecified */
892 SCIP_RELAXATION* relaxation /**< global relaxation data */
893 )
894{
895 assert(relaxation != NULL);
896
897 return relaxation->lastsolrelax;
898}
void SCIPclockStop(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:360
void SCIPclockEnableOrDisable(SCIP_CLOCK *clck, SCIP_Bool enable)
Definition: clock.c:260
void SCIPclockStart(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:290
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
Definition: clock.c:438
void SCIPclockReset(SCIP_CLOCK *clck)
Definition: clock.c:209
void SCIPclockFree(SCIP_CLOCK **clck)
Definition: clock.c:185
SCIP_RETCODE SCIPclockCreate(SCIP_CLOCK **clck, SCIP_CLOCKTYPE clocktype)
Definition: clock.c:170
internal methods for clocks and timing issues
common defines and data types used in all packages of SCIP
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Longint
Definition: def.h:158
#define SCIP_MAXTREEDEPTH
Definition: def.h:316
#define SCIP_Bool
Definition: def.h:91
#define SCIP_ALLOC(x)
Definition: def.h:385
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL(x)
Definition: def.h:374
#define SCIP_CALL_FINALLY(x, y)
Definition: def.h:416
int SCIPgetNCuts(SCIP *scip)
Definition: scip_cut.c:787
SCIP_Real SCIPnodeGetLowerbound(SCIP_NODE *node)
Definition: tree.c:7513
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
void SCIPrelaxMarkUnsolved(SCIP_RELAX *relax)
Definition: relax.c:720
SCIP_Longint SCIPrelaxGetNAddedConss(SCIP_RELAX *relax)
Definition: relax.c:658
SCIP_Bool SCIPrelaxIsInitialized(SCIP_RELAX *relax)
Definition: relax.c:698
SCIP_Real SCIPrelaxGetTime(SCIP_RELAX *relax)
Definition: relax.c:618
int SCIPrelaxGetFreq(SCIP_RELAX *relax)
Definition: relax.c:586
const char * SCIPrelaxGetName(SCIP_RELAX *relax)
Definition: relax.c:542
SCIP_DECL_SORTPTRCOMP(SCIPrelaxComp)
Definition: relax.c:56
SCIP_Real SCIPrelaxGetSetupTime(SCIP_RELAX *relax)
Definition: relax.c:596
SCIP_RETCODE SCIPsetRelaxPriority(SCIP *scip, SCIP_RELAX *relax, int priority)
Definition: scip_relax.c:271
SCIP_Longint SCIPrelaxGetNCutoffs(SCIP_RELAX *relax)
Definition: relax.c:638
SCIP_Longint SCIPrelaxGetNSeparatedCuts(SCIP_RELAX *relax)
Definition: relax.c:688
void SCIPrelaxSetData(SCIP_RELAX *relax, SCIP_RELAXDATA *relaxdata)
Definition: relax.c:465
const char * SCIPrelaxGetDesc(SCIP_RELAX *relax)
Definition: relax.c:552
SCIP_Longint SCIPrelaxGetNReducedDomains(SCIP_RELAX *relax)
Definition: relax.c:678
SCIP_Real SCIPrelaxGetImprovedLowerboundTime(SCIP_RELAX *relax)
Definition: relax.c:668
int SCIPrelaxGetPriority(SCIP_RELAX *relax)
Definition: relax.c:562
SCIP_Longint SCIPrelaxGetNImprovedLowerbound(SCIP_RELAX *relax)
Definition: relax.c:648
SCIP_Longint SCIPrelaxGetNCalls(SCIP_RELAX *relax)
Definition: relax.c:628
SCIP_RELAXDATA * SCIPrelaxGetData(SCIP_RELAX *relax)
Definition: relax.c:455
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
static const char * paramname[]
Definition: lpi_msk.c:5096
#define BMSfreeMemory(ptr)
Definition: memory.h:145
#define BMSduplicateMemoryArray(ptr, source, num)
Definition: memory.h:143
#define BMSclearMemory(ptr)
Definition: memory.h:129
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:437
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:148
#define BMSallocMemory(ptr)
Definition: memory.h:118
SCIP_PARAMDATA * SCIPparamGetData(SCIP_PARAM *param)
Definition: paramset.c:679
int SCIPparamGetInt(SCIP_PARAM *param)
Definition: paramset.c:734
internal methods for handling parameter settings
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
public data structures and miscellaneous methods
void SCIPrelaxSetExitsol(SCIP_RELAX *relax, SCIP_DECL_RELAXEXITSOL((*relaxexitsol)))
Definition: relax.c:531
void SCIPrelaxSetInitsol(SCIP_RELAX *relax, SCIP_DECL_RELAXINITSOL((*relaxinitsol)))
Definition: relax.c:520
SCIP_RETCODE SCIPrelaxInit(SCIP_RELAX *relax, SCIP_SET *set)
Definition: relax.c:231
SCIP_Bool SCIPrelaxationIsSolZero(SCIP_RELAXATION *relaxation)
Definition: relax.c:785
SCIP_RETCODE SCIPrelaxCreate(SCIP_RELAX **relax, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int priority, int freq, SCIP_DECL_RELAXCOPY((*relaxcopy)), SCIP_DECL_RELAXFREE((*relaxfree)), SCIP_DECL_RELAXINIT((*relaxinit)), SCIP_DECL_RELAXEXIT((*relaxexit)), SCIP_DECL_RELAXINITSOL((*relaxinitsol)), SCIP_DECL_RELAXEXITSOL((*relaxexitsol)), SCIP_DECL_RELAXEXEC((*relaxexec)), SCIP_RELAXDATA *relaxdata)
Definition: relax.c:172
void SCIPrelaxationSetSolZero(SCIP_RELAXATION *relaxation, SCIP_Bool iszero)
Definition: relax.c:774
SCIP_RETCODE SCIPrelaxExit(SCIP_RELAX *relax, SCIP_SET *set)
Definition: relax.c:275
void SCIPrelaxationUpdateVarObj(SCIP_RELAXATION *relaxation, SCIP_SET *set, SCIP_VAR *var, SCIP_Real oldobj, SCIP_Real newobj)
Definition: relax.c:860
void SCIPrelaxationSetSolValid(SCIP_RELAXATION *relaxation, SCIP_Bool isvalid, SCIP_Bool includeslp)
Definition: relax.c:795
void SCIPrelaxSetInit(SCIP_RELAX *relax, SCIP_DECL_RELAXINIT((*relaxinit)))
Definition: relax.c:498
void SCIPrelaxSetExit(SCIP_RELAX *relax, SCIP_DECL_RELAXEXIT((*relaxexit)))
Definition: relax.c:509
static SCIP_DECL_PARAMCHGD(paramChgdRelaxPriority)
Definition: relax.c:69
SCIP_RETCODE SCIPrelaxFree(SCIP_RELAX **relax, SCIP_SET *set)
Definition: relax.c:204
void SCIPrelaxationSetSolObj(SCIP_RELAXATION *relaxation, SCIP_Real obj)
Definition: relax.c:828
void SCIPrelaxSetFree(SCIP_RELAX *relax, SCIP_DECL_RELAXFREE((*relaxfree)))
Definition: relax.c:487
SCIP_Real SCIPrelaxationGetSolObj(SCIP_RELAXATION *relaxation)
Definition: relax.c:839
void SCIPrelaxSetCopy(SCIP_RELAX *relax, SCIP_DECL_RELAXCOPY((*relaxcopy)))
Definition: relax.c:476
void SCIPrelaxationSolObjAdd(SCIP_RELAXATION *relaxation, SCIP_Real val)
Definition: relax.c:849
SCIP_RETCODE SCIPrelaxCopyInclude(SCIP_RELAX *relax, SCIP_SET *set)
Definition: relax.c:83
void SCIPrelaxationSetSolRelax(SCIP_RELAXATION *relaxation, SCIP_RELAX *relax)
Definition: relax.c:880
SCIP_Bool SCIPrelaxIsSolved(SCIP_RELAX *relax, SCIP_STAT *stat)
Definition: relax.c:708
static SCIP_RETCODE doRelaxCreate(SCIP_RELAX **relax, SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, const char *name, const char *desc, int priority, int freq, SCIP_DECL_RELAXCOPY((*relaxcopy)), SCIP_DECL_RELAXFREE((*relaxfree)), SCIP_DECL_RELAXINIT((*relaxinit)), SCIP_DECL_RELAXEXIT((*relaxexit)), SCIP_DECL_RELAXINITSOL((*relaxinitsol)), SCIP_DECL_RELAXEXITSOL((*relaxexitsol)), SCIP_DECL_RELAXEXEC((*relaxexec)), SCIP_RELAXDATA *relaxdata)
Definition: relax.c:102
SCIP_RETCODE SCIPrelaxationFree(SCIP_RELAXATION **relaxation)
Definition: relax.c:762
void SCIPrelaxEnableOrDisableClocks(SCIP_RELAX *relax, SCIP_Bool enable)
Definition: relax.c:606
SCIP_RETCODE SCIPrelaxationCreate(SCIP_RELAXATION **relaxation, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PRIMAL *primal, SCIP_TREE *tree)
Definition: relax.c:734
SCIP_RELAX * SCIPrelaxationGetSolRelax(SCIP_RELAXATION *relaxation)
Definition: relax.c:891
SCIP_RETCODE SCIPrelaxInitsol(SCIP_RELAX *relax, SCIP_SET *set)
Definition: relax.c:305
SCIP_RETCODE SCIPrelaxExec(SCIP_RELAX *relax, SCIP_SET *set, SCIP_TREE *tree, SCIP_STAT *stat, int depth, SCIP_Real *lowerbound, SCIP_RESULT *result)
Definition: relax.c:353
void SCIPrelaxSetPriority(SCIP_RELAX *relax, SCIP_SET *set, int priority)
Definition: relax.c:572
SCIP_Bool SCIPrelaxationIsLpIncludedForSol(SCIP_RELAXATION *relaxation)
Definition: relax.c:818
SCIP_Bool SCIPrelaxationIsSolValid(SCIP_RELAXATION *relaxation)
Definition: relax.c:808
SCIP_RETCODE SCIPrelaxExitsol(SCIP_RELAX *relax, SCIP_SET *set)
Definition: relax.c:329
internal methods for relaxators
SCIP callable library.
public methods for cuts and aggregation rows
SCIP_RETCODE SCIPsetAddIntParam(SCIP_SET *set, SCIP_MESSAGEHDLR *messagehdlr, BMS_BLKMEM *blkmem, 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: set.c:2984
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
Definition: set.c:6064
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6199
SCIP_Bool SCIPsetIsRelGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:7142
internal methods for global SCIP settings
#define SCIPsetDebugMsg
Definition: set.h:1784
internal methods for storing primal CIP solutions
internal methods for problem statistics
SCIP_RELAXDATA * relaxdata
Definition: struct_relax.h:64
SCIP_Real imprtime
Definition: struct_relax.h:67
SCIP_Longint lastsolvednode
Definition: struct_relax.h:54
SCIP_CLOCK * setuptime
Definition: struct_relax.h:65
SCIP_CLOCK * relaxclock
Definition: struct_relax.h:66
SCIP_Longint naddedconss
Definition: struct_relax.h:51
SCIP_Bool initialized
Definition: struct_relax.h:70
char * name
Definition: struct_relax.h:55
SCIP_Longint ncalls
Definition: struct_relax.h:48
SCIP_Longint nimprbounds
Definition: struct_relax.h:50
SCIP_Longint nreduceddom
Definition: struct_relax.h:52
SCIP_Longint ncutoffs
Definition: struct_relax.h:49
char * desc
Definition: struct_relax.h:56
SCIP_Longint nseparated
Definition: struct_relax.h:53
SCIP_Real relaxsolobjval
Definition: struct_relax.h:76
SCIP_Bool relaxsolincludeslp
Definition: struct_relax.h:78
SCIP_Bool relaxsolzero
Definition: struct_relax.h:79
SCIP_RELAX * lastsolrelax
Definition: struct_relax.h:80
SCIP_Bool relaxsolvalid
Definition: struct_relax.h:77
SCIP_Longint ntotalnodes
Definition: struct_stat.h:87
SCIP_Longint relaxcount
Definition: struct_stat.h:191
int nactiveconss
Definition: struct_stat.h:239
data structures for relaxators
Definition: heur_padm.c:135
SCIP_NODE * SCIPtreeGetCurrentNode(SCIP_TREE *tree)
Definition: tree.c:8435
internal methods for branch and bound tree
@ SCIP_CLOCKTYPE_DEFAULT
Definition: type_clock.h:43
struct SCIP_ParamData SCIP_PARAMDATA
Definition: type_paramset.h:87
#define SCIP_DECL_RELAXINIT(x)
Definition: type_relax.h:72
#define SCIP_DECL_RELAXEXITSOL(x)
Definition: type_relax.h:102
#define SCIP_DECL_RELAXFREE(x)
Definition: type_relax.h:64
#define SCIP_DECL_RELAXINITSOL(x)
Definition: type_relax.h:91
#define SCIP_DECL_RELAXCOPY(x)
Definition: type_relax.h:56
#define SCIP_DECL_RELAXEXEC(x)
Definition: type_relax.h:127
#define SCIP_DECL_RELAXEXIT(x)
Definition: type_relax.h:80
struct SCIP_RelaxData SCIP_RELAXDATA
Definition: type_relax.h:47
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ SCIP_CONSADDED
Definition: type_result.h:52
@ SCIP_SUSPENDED
Definition: type_result.h:57
@ SCIP_SEPARATED
Definition: type_result.h:49
@ SCIP_SUCCESS
Definition: type_result.h:58
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_INVALIDRESULT
Definition: type_retcode.h:53
@ SCIP_OKAY
Definition: type_retcode.h:42
@ SCIP_INVALIDCALL
Definition: type_retcode.h:51
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARSTATUS_COLUMN
Definition: type_var.h:51
SCIP_Real SCIPvarGetRelaxSol(SCIP_VAR *var, SCIP_SET *set)
Definition: var.c:13923
internal methods for problem variables