SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
heuristics.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-2023 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 heuristics.c
26 * @ingroup OTHER_CFILES
27 * @brief methods commonly used by primal heuristics
28 * @author Gregor Hendel
29 */
30
31#include "scip/heuristics.h"
32#include "scip/cons_linear.h"
33#include "scip/scipdefplugins.h"
34
35#include "scip/pub_heur.h"
36
37/* the indicator and SOS1 constraint handlers are included for the diving algorithm SCIPperformGenericDivingAlgorithm() */
38#include "scip/cons_indicator.h"
39#include "scip/cons_sos1.h"
40
41#define MINLPITER 10000 /**< minimal number of LP iterations allowed in each LP solving call */
42
43
44/** solve probing LP */
45static
47 SCIP* scip, /**< SCIP data structure */
48 SCIP_DIVESET* diveset, /**< diving settings */
49 SCIP_Longint maxnlpiterations, /**< maximum number of allowed LP iterations */
50 SCIP_DIVECONTEXT divecontext, /**< context for diving statistics */
51 SCIP_Bool* lperror, /**< pointer to store if an internal LP error occurred */
52 SCIP_Bool* cutoff /**< pointer to store whether the LP was infeasible */
53 )
54{
57 SCIP_Longint nlpiterations;
58
60 assert(cutoff != NULL);
61
63
64 /* allow at least MINLPITER more iterations so as not to run out of LP iterations during this solve */
67
69
70 /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
71 * Hence in optimized mode, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
72 */
73#ifdef NDEBUG
74 if( retstat != SCIP_OKAY )
75 {
76 SCIPwarningMessage(scip, "Error while solving LP in %s diving heuristic; LP solve terminated with code <%d>.\n", SCIPdivesetGetName(diveset), retstat);
77 }
78#else
80#endif
81
82 /* update iteration count */
84
85 return SCIP_OKAY;
86}
87
88/** select the next variable and type of diving */
89static
91 SCIP* scip, /**< SCIP data structure */
92 SCIP_DIVESET* diveset, /**< dive set */
93 SCIP_SOL* worksol, /**< current working solution */
94 SCIP_Bool onlylpbranchcands, /**< should only LP branching candidates be considered? */
95 SCIP_Bool storelpcandscores, /**< should the scores of the LP candidates be updated? */
96 SCIP_VAR** lpcands, /**< LP branching candidates, or NULL if not needed */
97 SCIP_Real * lpcandssol, /**< solution values LP branching candidates, or NULL if not needed */
98 SCIP_Real* lpcandsfrac, /**< fractionalities of LP branching candidates, or NULL if not needed*/
99 SCIP_Real* lpcandsscores, /**< array with LP branching candidate scores, or NULL */
100 SCIP_Bool* lpcandroundup, /**< array to remember whether the preferred branching direction is upwards */
101 int* nviollpcands, /**< pointer to store the number of LP candidates whose solution value already violates local bounds */
102 int nlpcands, /**< number of current LP cands */
103 SCIP_Bool* enfosuccess, /**< pointer to store whether a candidate was sucessfully found */
104 SCIP_Bool* infeasible /**< pointer to store whether the diving can be immediately aborted because it is infeasible */
105 )
106{
107 assert(scip != NULL);
108 assert(worksol != NULL);
109 assert(!onlylpbranchcands || lpcandsscores != NULL);
110 assert(!onlylpbranchcands || lpcandroundup != NULL);
112 assert(infeasible != NULL);
114
115 *nviollpcands = 0;
116 /* we use diving solution enforcement provided by the constraint handlers */
117 if( !onlylpbranchcands )
118 {
120 }
121 else
122 {
123 int c;
124 int bestcandidx;
125 SCIP_Real bestscore;
126 SCIP_Real score;
127
129 bestcandidx = -1;
130
132
133 /* search for the candidate that maximizes the dive set score function and whose solution value is still feasible */
134 for( c = 0; c < nlpcands; ++c )
135 {
136 assert(SCIPgetSolVal(scip, worksol, lpcands[c]) == lpcandssol[c]); /*lint !e777 doesn't like comparing floats for equality */
137
138 /* scores are kept in arrays for faster reuse */
140 {
143 }
144
145 score = lpcandsscores[c];
146 /* update the best candidate if it has a higher score and a solution value which does not violate one of the local bounds */
148 {
149 if( score > bestscore )
150 {
151 bestcandidx = c;
152 bestscore = score;
153 }
154 }
155 else
156 ++(*nviollpcands);
157 }
158
159 /* there is no guarantee that a candidate is found since local bounds might render all solution values infeasible */
160 *enfosuccess = (bestcandidx >= 0);
161 if( *enfosuccess )
162 {
163 /* if we want to round up the best candidate, it is added as the preferred bound change */
168 }
169 }
170 return SCIP_OKAY;
171}
172
173/** return the LP iteration budget suggestion for this dive set */
174static
176 SCIP* scip, /**< SCIP data structure */
177 SCIP_DIVESET* diveset, /**< dive set data structure */
178 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
179 )
180{
181 SCIP_Longint iterlimit;
182 /*todo another factor of 10, REALLY? */
186
187 return iterlimit;
188}
189
190/** performs a diving within the limits of the @p diveset parameters
191 *
192 * This method performs a diving according to the settings defined by the diving settings @p diveset; Contrary to the
193 * name, SCIP enters probing mode (not diving mode) and dives along a path into the tree. Domain propagation
194 * is applied at every node in the tree, whereas probing LPs might be solved less frequently.
195 *
196 * Starting from the current LP solution, the algorithm selects candidates which maximize the
197 * score defined by the @p diveset and whose solution value has not yet been rendered infeasible by propagation,
198 * and propagates the bound change on this candidate.
199 *
200 * The algorithm iteratively selects the the next (unfixed) candidate in the list, until either enough domain changes
201 * or the resolve frequency of the LP trigger an LP resolve (and hence, the set of potential candidates changes),
202 * or the last node is proven to be infeasible. It optionally backtracks and tries the
203 * other branching direction.
204 *
205 * After the set of remaining candidates is empty or the targeted depth is reached, the node LP is
206 * solved, and the old candidates are replaced by the new LP candidates.
207 *
208 * @see heur_guideddiving.c for an example implementation of a dive set controlling the diving algorithm.
209 *
210 * @note the node from where the algorithm is called is checked for a basic LP solution. If the solution
211 * is non-basic, e.g., when barrier without crossover is used, the method returns without performing a dive.
212 *
213 * @note currently, when multiple diving heuristics call this method and solve an LP at the same node, only the first
214 * call will be executed, see SCIPgetLastDiveNode()
215 *
216 * @todo generalize method to work correctly with pseudo or external branching/diving candidates
217 */
219 SCIP* scip, /**< SCIP data structure */
220 SCIP_DIVESET* diveset, /**< settings for diving */
221 SCIP_SOL* worksol, /**< non-NULL working solution */
222 SCIP_HEUR* heur, /**< the calling primal heuristic */
223 SCIP_RESULT* result, /**< SCIP result pointer */
224 SCIP_Bool nodeinfeasible, /**< is the current node known to be infeasible? */
225 SCIP_Longint iterlim, /**< nonnegative iteration limit for the LP solves, or -1 for dynamic setting */
226 SCIP_DIVECONTEXT divecontext /**< context for diving statistics */
227 )
228{
229 SCIP_CONSHDLR* indconshdlr; /* constraint handler for indicator constraints */
230 SCIP_CONSHDLR* sos1conshdlr; /* constraint handler for SOS1 constraints */
232 SCIP_Real* lpcandssol;
233
235 SCIP_Real* lpcandsscores;
236 SCIP_Real* previousvals;
237 SCIP_Real* lpcandsfrac;
238 SCIP_Bool* lpcandroundup;
239 SCIP_Real searchubbound;
240 SCIP_Real searchavgbound;
241 SCIP_Real searchbound;
242 SCIP_Real ubquot;
243 SCIP_Real avgquot;
244 SCIP_Longint maxnlpiterations;
245 SCIP_Longint domreds;
246 int startndivecands;
247 int depth;
248 int maxdepth;
249 int maxdivedepth;
250 int totalnbacktracks;
252 int lastlpdepth;
255 int nviollpcands;
256 SCIP_Longint oldnsolsfound;
257 SCIP_Longint oldnbestsolsfound;
258 SCIP_Longint oldnconflictsfound;
259
260 SCIP_Bool success;
261 SCIP_Bool leafsol;
262 SCIP_Bool enfosuccess;
263 SCIP_Bool lperror;
264 SCIP_Bool cutoff;
265 SCIP_Bool backtracked;
266 SCIP_Bool backtrack;
267 SCIP_Bool onlylpbranchcands;
268
269 int nlpcands;
270 int lpsolvefreq;
271
272 assert(scip != NULL);
273 assert(heur != NULL);
274 assert(result != NULL);
275 assert(worksol != NULL);
276
278
279 /* do not call heuristic in node that was already detected to be infeasible */
280 if( nodeinfeasible )
281 return SCIP_OKAY;
282
283 /* only call heuristic, if an optimal LP solution is at hand */
285 return SCIP_OKAY;
286
287 /* only call heuristic, if the LP objective value is smaller than the cutoff bound */
289 return SCIP_OKAY;
290
291 /* only call heuristic, if the LP solution is basic (which allows fast resolve in diving) */
292 if( !SCIPisLPSolBasic(scip) )
293 return SCIP_OKAY;
294
295 /* don't dive two times at the same node */
297 return SCIP_OKAY;
298
300
301 /* only try to dive, if we are in the correct part of the tree, given by minreldepth and maxreldepth */
304 maxdepth = MAX(maxdepth, 30);
306 return SCIP_OKAY;
307
308 /* calculate the maximal number of LP iterations */
309 if( iterlim < 0 )
310 {
312 }
313 else
314 {
316 }
317
318 /* don't try to dive, if we took too many LP iterations during diving */
320 return SCIP_OKAY;
321
322 /* allow at least a certain number of LP iterations in this dive */
325
326 /* these constraint handlers are required for polishing an LP relaxation solution beyond rounding */
327 indconshdlr = SCIPfindConshdlr(scip, "indicator");
329
331
332 onlylpbranchcands = SCIPdivesetUseOnlyLPBranchcands(diveset);
333 /* don't try to dive, if there are no diving candidates */
334 if( onlylpbranchcands && nlpcands == 0 )
335 return SCIP_OKAY;
336
337 /* calculate the objective search bound */
338 if( SCIPgetNSolsFound(scip) == 0 )
339 {
342 }
343 else
344 {
347 }
348
349 if( ubquot > 0.0 )
351 else
353
354 if( avgquot > 0.0 )
356 else
358
360
363
364 /* calculate the maximal diving depth: 10 * min{number of integer variables, max depth} */
366 if ( sos1conshdlr != NULL )
369 maxdivedepth *= 10;
370
372
373 /* start probing mode */
375
376 /* enables collection of variable statistics during probing */
378
379 SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") executing %s heuristic: depth=%d, %d fractionals, dualbound=%g, avgbound=%g, cutoffbound=%g, searchbound=%g\n",
382
383 /* allocate buffer storage for previous candidates and their branching values for pseudo cost updates */
384 lpsolvefreq = SCIPdivesetGetLPSolveFreq(diveset);
385 previouscandssize = MAX(1, lpsolvefreq);
388
389 /* keep some statistics */
390 lperror = FALSE;
391 cutoff = FALSE;
392 lastlpdepth = -1;
394 totalnbacktracks = 0;
399
400 /* link the working solution to the dive set */
402
403 if( onlylpbranchcands )
404 {
407
409 }
410 else
411 {
415 }
416
418 leafsol = FALSE;
419
420 /* LP loop; every time a new LP was solved, conditions are checked
421 * dive as long we are in the given objective, depth and iteration limits and fractional variables exist, but
422 * - if possible, we dive at least with the depth 10
423 * - if the number of fractional variables decreased at least with 1 variable per 2 dive depths, we continue diving
424 */
426 && (SCIPgetProbingDepth(scip) < 10
429 && !SCIPisStopped(scip) )
430 {
431 SCIP_Real lastlpobjval;
432 int c;
433 SCIP_Bool allroundable;
434 SCIP_Bool infeasible;
436
437 /* remember the last LP depth */
440 domreds = 0;
441
442 SCIPdebugMsg(scip, "%s heuristic continues diving at depth %d, %d candidates left\n",
444
445 /* loop over candidates and determine if they are roundable */
447 c = 0;
448 while( allroundable && c < nlpcands )
449 {
452 else
454 ++c;
455 }
456
457 /* if all candidates are roundable, try to round the solution */
458 if( allroundable )
459 {
460 success = FALSE;
461
462 /* working solution must be linked to LP solution */
464 /* create solution from diving LP and try to round it */
466
467 /* adjust SOS1 constraints */
468 if( success && sos1conshdlr != NULL )
469 {
470 SCIP_Bool changed;
472 }
473
474 /* succesfully rounded solutions are tried for primal feasibility */
475 if( success )
476 {
477 SCIP_Bool changed = FALSE;
478 SCIPdebugMsg(scip, "%s found roundable primal solution: obj=%g\n", SCIPdivesetGetName(diveset), SCIPgetSolOrigObj(scip, worksol));
479
480 /* adjust indicator constraints */
481 if( indconshdlr != NULL )
482 {
484 }
485
486 success = FALSE;
487 /* try to add solution to SCIP */
489
490 /* check, if solution was feasible and good enough */
491 if( success )
492 {
493 SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
495 leafsol = (nlpcands == 0);
496
497 /* the rounded solution found above led to a cutoff of the node LP solution */
499 {
500 cutoff = TRUE;
501 break;
502 }
503 }
504 }
505 }
506
507 /* working solution must be linked to LP solution */
511
512 /* we must explicitly store the solution values by unlinking the solution, otherwise,
513 * the working solution may contain wrong entries, if, e.g., a backtrack occurred after an
514 * intermediate LP resolve or the LP was resolved during conflict analysis.
515 */
517
518 /* ensure array sizes for the diving on the fractional variables */
519 if( onlylpbranchcands && nlpcands > lpcandsscoressize )
520 {
521 assert(nlpcands > 0);
524
527
529 }
530
532 /* select the next diving action by selecting appropriate dive bound changes for the preferred and alternative child */
535 &enfosuccess, &infeasible) );
536
537 /* if we did not succeed finding an enforcement, the solution is potentially feasible and we break immediately */
538 if( ! enfosuccess )
539 break;
540
542
543 /* start propagating candidate variables
544 * - until the desired targetdepth is reached,
545 * - or there is no further candidate variable left because of intermediate bound changes,
546 * - or a cutoff is detected
547 */
548 do
549 {
551 SCIP_Real bdchgvalue;
552 SCIP_Longint localdomreds;
554 int nbdchanges;
555
556 /* ensure that a new candidate was successfully determined (usually at the end of the previous loop iteration) */
558 bdchgvar = NULL;
561
563 do
564 {
565 int d;
568 SCIP_Real* bdchgvals;
569
570 nbdchanges = 0;
571 /* get the bound change information stored in the dive set */
573
574 assert(nbdchanges > 0);
578
579 /* return if we reached the depth limit */
581 {
582 SCIPdebugMsg(scip, "depth limit reached, we stop diving immediately.\n");
583 goto TERMINATE;
584 }
585
586 /* dive deeper into the tree */
589
590 /* apply all suggested domain changes of the variables */
591 for( d = 0; d < nbdchanges; ++d )
592 {
593 SCIP_Real lblocal;
594 SCIP_Real ublocal;
595 SCIP_Bool infeasbdchange;
596
597 /* get the next bound change data: variable, direction, and value */
601
602 assert(bdchgvar != NULL);
605
606 SCIPdebugMsg(scip, " dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ": var <%s>, oldbounds=[%g,%g], newbounds=[%g,%g]\n",
612
614 /* tighten the lower and/or upper bound depending on the bound change type */
615 switch( bdchgdir )
616 {
618 /* test if bound change is possible, otherwise propagation might have deduced the same
619 * bound already or numerical troubles might have occurred */
622 else
623 {
624 /* round variable up */
626 }
627 break;
629 /* test if bound change is possible, otherwise propagation might have deduced the same
630 * bound already or numerical troubles might have occurred */
633 else
634 {
635 /* round variable down */
637 }
638 break;
640 /* test if bound change is possible, otherwise propagation might have deduced the same
641 * bound already or numerical troubles might have occurred */
645 else
646 {
647 /* fix variable to the bound change value */
649 {
651 }
653 {
655 }
656 }
657 break;
659 default:
660 SCIPerrorMessage("Error: Unsupported bound change direction <%d> specified for diving, aborting\n",bdchgdirs[d]);
661 SCIPABORT();
662 return SCIP_INVALIDDATA; /*lint !e527*/
663 }
664 /* if the variable domain has been shrunk in the meantime, numerical troubles may have
665 * occured or variable was fixed by propagation while backtracking => Abort diving!
666 */
667 if( infeasbdchange )
668 {
669 SCIPdebugMsg(scip, "\nSelected variable <%s> domain already [%g,%g] as least as tight as desired bound change, diving aborted \n",
671 cutoff = TRUE;
672 break;
673 }
674 }
675 /* break loop immediately if we detected a cutoff */
676 if( cutoff )
677 break;
678
679 /* apply domain propagation */
680 localdomreds = 0;
682
683 /* add the number of bound changes we applied by ourselves after propagation, otherwise the counter would have been reset */
685
686 SCIPdebugMsg(scip, "domain reductions: %" SCIP_LONGINT_FORMAT " (total: %" SCIP_LONGINT_FORMAT ")\n",
688
689 /* resolve the diving LP if the diving resolve frequency is reached or a sufficient number of intermediate bound changes
690 * was reached
691 */
692 if( ! cutoff
693 && ((lpsolvefreq > 0 && ((SCIPgetProbingDepth(scip) - lastlpdepth) % lpsolvefreq) == 0)
695 || (onlylpbranchcands && nviollpcands > (int)(SCIPdivesetGetLPResolveDomChgQuot(diveset) * nlpcands))) )
696 {
698
699 /* lp errors lead to early termination */
700 if( lperror )
701 {
702 cutoff = TRUE;
703 break;
704 }
705 }
706
707 /* perform backtracking if a cutoff was detected */
709 {
710 SCIPdebugMsg(scip, " *** cutoff detected at level %d - backtracking\n", SCIPgetProbingDepth(scip));
712 ++totalnbacktracks;
714 backtrack = TRUE;
715 cutoff = FALSE;
716 }
717 else
718 backtrack = FALSE;
719 }
720 while( backtrack );
721
722 /* we add the domain reductions from the last evaluated node */
723 domreds += localdomreds; /*lint !e771 lint thinks localdomreds has not been initialized */
724
725 /* store candidate for pseudo cost update and choose next candidate only if no cutoff was detected */
726 if( ! cutoff )
727 {
729 {
733 assert(bdchgvar != NULL);
734 assert(bdchgvalue != SCIP_INVALID); /*lint !e777 doesn't like comparing floats for equality */
735
736 /* extend array in case of a dynamic, domain change based LP resolve strategy */
738 {
742 }
744
745 /* store candidate for pseudo cost update */
748 }
749
750 /* choose next candidate variable and resolve the LP if none is found. */
752 {
755
756 /* select the next diving action */
759 &enfosuccess, &infeasible) );
760
761 /* in case of an unsuccesful candidate search, we solve the node LP */
762 if( !enfosuccess )
763 {
765
766 /* check for an LP error and terminate in this case, cutoffs lead to termination anyway */
767 if( lperror )
768 cutoff = TRUE;
769
770 /* enfosuccess must be set to TRUE for entering the main LP loop again */
772 }
773 }
774 }
775 }
777
779
782
783 /* check new LP candidates and use the LP Objective gain to update pseudo cost information */
785 {
786 int v;
787 SCIP_Real gain;
788
790
791 SCIPdebugMsg(scip, " -> lpsolstat=%d, objval=%g/%g, nfrac=%d\n", SCIPgetLPSolstat(scip), SCIPgetLPObjval(scip), searchbound, nlpcands);
792 /* distribute the gain equally over all variables that we rounded since the last LP */
794 gain = MAX(gain, 0.0);
796
797 /* loop over previously fixed candidates and share gain improvement */
798 for( v = 0; v <= prevcandsinsertidx; ++v )
799 {
801 SCIP_Real val = previousvals[v];
802 SCIP_Real solval = SCIPgetSolVal(scip, worksol, cand);
803
804 /* todo: should the gain be shared with a smaller weight, instead of dividing the gain itself? */
805 /* it may happen that a variable had an integral solution value beforehand, e.g., for indicator variables */
806 if( ! SCIPisZero(scip, val - solval) )
807 {
808 SCIP_CALL( SCIPupdateVarPseudocost(scip, cand, val - solval, gain, 1.0) );
809 }
810 }
811 }
812 else
813 nlpcands = 0;
814 }
815
816 success = FALSE;
817 /* check if a solution has been found */
819 {
820 /* create solution from diving LP */
822 SCIPdebugMsg(scip, "%s found primal solution: obj=%g\n", SCIPdivesetGetName(diveset), SCIPgetSolOrigObj(scip, worksol));
823
824 /* try to add solution to SCIP */
826
827 /* check, if solution was feasible and good enough */
828 if( success )
829 {
830 SCIPdebugMsg(scip, " -> solution was feasible and good enough\n");
832 leafsol = TRUE;
833 }
834 }
835
838
839 SCIPdebugMsg(scip, "(node %" SCIP_LONGINT_FORMAT ") finished %s diveset (%s heur): %d fractionals, dive %d/%d, LP iter %" SCIP_LONGINT_FORMAT "/%" SCIP_LONGINT_FORMAT ", objval=%g/%g, lpsolstat=%d, cutoff=%u\n",
842
843 TERMINATE:
844 /* end probing mode */
846
848
849 if( onlylpbranchcands )
850 {
853 }
856
857 return SCIP_OKAY;
858}
859
860
861/** creates the rows of the subproblem */
862static
864 SCIP* scip, /**< original SCIP data structure */
865 SCIP* subscip, /**< SCIP data structure for the subproblem */
866 SCIP_HASHMAP* varmap /**< a hashmap to store the mapping of source variables to the corresponding
867 * target variables */
868 )
869{
870 SCIP_ROW** rows; /* original scip rows */
871 SCIP_CONS* cons; /* new constraint */
872 SCIP_VAR** consvars; /* new constraint's variables */
873 SCIP_COL** cols; /* original row's columns */
874
875 SCIP_Real constant; /* constant added to the row */
876 SCIP_Real lhs; /* left hand side of the row */
877 SCIP_Real rhs; /* left right side of the row */
878 SCIP_Real* vals; /* variables' coefficient values of the row */
879
880 int nrows;
881 int nnonz;
882 int i;
883 int j;
884
885 /* get the rows and their number */
886 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
887
888 /* copy all rows to linear constraints */
889 for( i = 0; i < nrows; i++ )
890 {
891 /* ignore rows that are only locally valid */
892 if( SCIProwIsLocal(rows[i]) )
893 continue;
894
895 /* get the row's data */
896 constant = SCIProwGetConstant(rows[i]);
897 lhs = SCIProwGetLhs(rows[i]) - constant;
898 rhs = SCIProwGetRhs(rows[i]) - constant;
899 vals = SCIProwGetVals(rows[i]);
900 nnonz = SCIProwGetNNonz(rows[i]);
901 cols = SCIProwGetCols(rows[i]);
902
903 assert(lhs <= rhs);
904
905 /* allocate memory array to be filled with the corresponding subproblem variables */
906 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nnonz) );
907 for( j = 0; j < nnonz; j++ )
908 consvars[j] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, (SCIPcolGetVar(cols[j])));
909
910 /* create a new linear constraint and add it to the subproblem */
911 SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, SCIProwGetName(rows[i]), nnonz, consvars, vals, lhs, rhs,
913 SCIP_CALL( SCIPaddCons(subscip, cons) );
914 SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
915
916 /* free temporary memory */
917 SCIPfreeBufferArray(scip, &consvars);
918 }
919
920 return SCIP_OKAY;
921}
922
923
924/** get a sub-SCIP copy of the transformed problem */
926 SCIP* sourcescip, /**< source SCIP data structure */
927 SCIP* subscip, /**< sub-SCIP used by the heuristic */
928 SCIP_HASHMAP* varmap, /**< a hashmap to store the mapping of source variables to the corresponding
929 * target variables */
930 const char* suffix, /**< suffix for the problem name */
931 SCIP_VAR** fixedvars, /**< source variables whose copies should be fixed in the target SCIP environment, or NULL */
932 SCIP_Real* fixedvals, /**< array of fixing values for target SCIP variables, or NULL */
933 int nfixedvars, /**< number of source variables whose copies should be fixed in the target SCIP environment, or NULL */
934 SCIP_Bool uselprows, /**< should the linear relaxation of the problem defined by LP rows be copied? */
935 SCIP_Bool copycuts, /**< should cuts be copied (only if uselprows == FALSE) */
936 SCIP_Bool* success, /**< was the copying successful? */
937 SCIP_Bool* valid /**< pointer to store whether the copying was valid, or NULL */
938 )
939{
940 assert(sourcescip != NULL);
941 assert(suffix != NULL);
942 assert(subscip != NULL);
943 assert(varmap != NULL);
944 assert(success != NULL);
945
946 if( uselprows )
947 {
948 char probname[SCIP_MAXSTRLEN];
949
950 /* copy all plugins */
952
953 /* set name to the original problem name and possibly add a suffix */
954 (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_%s", SCIPgetProbName(sourcescip), suffix);
955
956 /* create the subproblem */
957 SCIP_CALL( SCIPcreateProb(subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
958
959 /* copy all variables */
960 SCIP_CALL( SCIPcopyVars(sourcescip, subscip, varmap, NULL, fixedvars, fixedvals, nfixedvars, TRUE) );
961
962 /* copy parameter settings */
963 SCIP_CALL( SCIPcopyParamSettings(sourcescip, subscip) );
964
965 /* create linear constraints from LP rows of the source problem */
966 SCIP_CALL( createRows(sourcescip, subscip, varmap) );
967 }
968 else
969 {
970 SCIP_CALL( SCIPcopyConsCompression(sourcescip, subscip, varmap, NULL, suffix, fixedvars, fixedvals, nfixedvars,
971 TRUE, FALSE, FALSE, TRUE, valid) );
972
973 if( copycuts )
974 {
975 /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
976 SCIP_CALL( SCIPcopyCuts(sourcescip, subscip, varmap, NULL, TRUE, NULL) );
977 }
978 }
979
980 *success = TRUE;
981
982 return SCIP_OKAY;
983}
984
985/** adds a trust region neighborhood constraint to the @p targetscip
986 *
987 * a trust region constraint measures the deviation from the current incumbent solution \f$x^*\f$ by an auxiliary
988 * continuous variable \f$v \geq 0\f$:
989 * \f[
990 * \sum\limits_{j\in B} |x_j^* - x_j| = v
991 * \f]
992 * Only binary variables are taken into account. The deviation is penalized in the objective function using
993 * a positive \p violpenalty.
994 *
995 * @note: the trust region constraint creates an auxiliary variable to penalize the deviation from
996 * the current incumbent solution. This variable can afterwards be accessed using SCIPfindVar() by its name
997 * 'trustregion_violationvar'
998 */
1000 SCIP* sourcescip, /**< the data structure for the main SCIP instance */
1001 SCIP* targetscip, /**< SCIP data structure of the subproblem */
1002 SCIP_VAR** subvars, /**< variables of the subproblem, NULL entries are ignored */
1003 SCIP_Real violpenalty /**< the penalty for violating the trust region */
1004 )
1005{
1008 SCIP_VAR** consvars;
1009 SCIP_VAR** vars;
1010 SCIP_SOL* bestsol;
1011
1012 int nvars;
1013 int nbinvars;
1014 int nconsvars;
1015 int i;
1016 SCIP_Real rhs;
1017 SCIP_Real* consvals;
1018 char name[SCIP_MAXSTRLEN];
1019
1020 /* get the data of the variables and the best solution */
1021 SCIP_CALL( SCIPgetVarsData(sourcescip, &vars, &nvars, &nbinvars, NULL, NULL, NULL) );
1022 bestsol = SCIPgetBestSol(sourcescip);
1023 assert(bestsol != NULL);
1024 /* otherwise, this neighborhood would not be active in the first place */
1025 assert(nbinvars > 0);
1026
1027 /* memory allocation */
1028 SCIP_CALL( SCIPallocBufferArray(sourcescip, &consvars, nbinvars + 1) );
1029 SCIP_CALL( SCIPallocBufferArray(sourcescip, &consvals, nbinvars + 1) );
1030 nconsvars = 0;
1031
1032 /* set initial left and right hand sides of trust region constraint */
1033 rhs = 0.0;
1034
1035 /* create the distance (to incumbent) function of the binary variables */
1036 for( i = 0; i < nbinvars; i++ )
1037 {
1038 SCIP_Real solval;
1039
1040 if( subvars[i] == NULL )
1041 continue;
1042
1043 solval = SCIPgetSolVal(sourcescip, bestsol, vars[i]);
1044 assert( SCIPisFeasIntegral(sourcescip,solval) );
1045
1046 /* is variable i part of the binary support of bestsol? */
1047 if( SCIPisFeasEQ(sourcescip, solval, 1.0) )
1048 {
1049 consvals[nconsvars] = -1.0;
1050 rhs -= 1.0;
1051 }
1052 else
1053 consvals[nconsvars] = 1.0;
1054 consvars[nconsvars] = subvars[i];
1055 assert(SCIPvarGetType(consvars[nconsvars]) == SCIP_VARTYPE_BINARY);
1056 ++nconsvars;
1057 }
1058
1059 /* adding the violation variable */
1060 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_trustregionviolvar", SCIPgetProbName(sourcescip));
1063 consvars[nconsvars] = violvar;
1064 consvals[nconsvars] = -1.0;
1065 ++nconsvars;
1066
1067 /* creates trustregion constraint and adds it to subscip */
1068 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_trustregioncons", SCIPgetProbName(sourcescip));
1069
1070 SCIP_CALL( SCIPcreateConsLinear(targetscip, &trustregioncons, name, nconsvars, consvars, consvals,
1071 rhs, rhs, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE) );
1074
1075 /* releasing the violation variable */
1077
1078 /* free local memory */
1079 SCIPfreeBufferArray(sourcescip, &consvals);
1080 SCIPfreeBufferArray(sourcescip, &consvars);
1081
1082 return SCIP_OKAY;
1083}
constraint handler for indicator constraints
Constraint handler for linear constraints in their most general form, .
constraint handler for SOS type 1 constraints
#define SCIP_MAXSTRLEN
Definition def.h:302
#define SCIP_Longint
Definition def.h:171
#define SCIP_MAXTREEDEPTH
Definition def.h:330
#define SCIP_INVALID
Definition def.h:206
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIPABORT()
Definition def.h:360
#define SCIP_REAL_MIN
Definition def.h:188
#define SCIP_CALL(x)
Definition def.h:388
SCIP_RETCODE SCIPmakeSOS1sFeasible(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed, SCIP_Bool *success)
SCIP_RETCODE SCIPmakeIndicatorsFeasible(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed)
int SCIPgetNSOS1Vars(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPcopyVars(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool global)
Definition scip_copy.c:1178
SCIP_RETCODE SCIPcopyConsCompression(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition scip_copy.c:2965
SCIP_RETCODE SCIPcopyCuts(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, int *ncutsadded)
Definition scip_copy.c:2130
SCIP_RETCODE SCIPcopyParamSettings(SCIP *sourcescip, SCIP *targetscip)
Definition scip_copy.c:2564
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition scip_prob.c:1668
int SCIPgetNIntVars(SCIP *scip)
Definition scip_prob.c:2082
const char * SCIPgetProbName(SCIP *scip)
Definition scip_prob.c:1067
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition scip_prob.c:1866
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2770
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
Definition scip_prob.c:117
int SCIPgetNBinVars(SCIP *scip)
Definition scip_prob.c:2037
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition scip_prob.c:1562
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3211
#define SCIPdebugMsg
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition lp.c:17042
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:886
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1119
SCIP_Real SCIPdivesetGetMaxLPIterQuot(SCIP_DIVESET *diveset)
Definition heur.c:653
SCIP_Real SCIPdivesetGetUbQuotNoSol(SCIP_DIVESET *diveset)
Definition heur.c:669
SCIP_Real SCIPdivesetGetMaxRelDepth(SCIP_DIVESET *diveset)
Definition heur.c:461
SCIP_Longint SCIPdivesetGetNSols(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition heur.c:639
SCIP_Real SCIPdivesetGetAvgQuot(SCIP_DIVESET *diveset)
Definition heur.c:692
SCIP_Bool SCIPdivesetUseBacktrack(SCIP_DIVESET *diveset)
Definition heur.c:700
int SCIPdivesetGetLPSolveFreq(SCIP_DIVESET *diveset)
Definition heur.c:708
SCIP_Real SCIPdivesetGetMinRelDepth(SCIP_DIVESET *diveset)
Definition heur.c:453
SCIP_Real SCIPdivesetGetUbQuot(SCIP_DIVESET *diveset)
Definition heur.c:684
SCIP_Bool SCIPdivesetUseOnlyLPBranchcands(SCIP_DIVESET *diveset)
Definition heur.c:741
SCIP_Longint SCIPdivesetGetNLPIterations(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition heur.c:587
const char * SCIPdivesetGetName(SCIP_DIVESET *diveset)
Definition heur.c:443
int SCIPdivesetGetNCalls(SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition heur.c:483
SCIP_Real SCIPdivesetGetAvgQuotNoSol(SCIP_DIVESET *diveset)
Definition heur.c:677
SCIP_Real SCIPdivesetGetLPResolveDomChgQuot(SCIP_DIVESET *diveset)
Definition heur.c:729
int SCIPdivesetGetMaxLPIterOffset(SCIP_DIVESET *diveset)
Definition heur.c:661
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition heur.c:1450
SCIP_Longint SCIPgetLastDivenode(SCIP *scip)
Definition scip_lp.c:2745
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition scip_lp.c:83
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition scip_lp.c:570
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition scip_lp.c:168
SCIP_Real SCIPgetLPObjval(SCIP *scip)
Definition scip_lp.c:247
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
Definition scip_lp.c:667
#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
void SCIPclearDiveBoundChanges(SCIP *scip)
int SCIPgetProbingDepth(SCIP *scip)
void SCIPupdateDivesetStats(SCIP *scip, SCIP_DIVESET *diveset, int nprobingnodes, int nbacktracks, SCIP_Longint nsolsfound, SCIP_Longint nbestsolsfound, SCIP_Longint nconflictsfound, SCIP_Bool leavewassol, SCIP_DIVECONTEXT divecontext)
void SCIPgetDiveBoundChangeData(SCIP *scip, SCIP_VAR ***variables, SCIP_BRANCHDIR **directions, SCIP_Real **values, int *ndivebdchgs, SCIP_Bool preferred)
SCIP_RETCODE SCIPgetDiveBoundChanges(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *sol, SCIP_Bool *success, SCIP_Bool *infeasible)
SCIP_RETCODE SCIPgetDivesetScore(SCIP *scip, SCIP_DIVESET *diveset, SCIP_DIVETYPE divetype, SCIP_VAR *divecand, SCIP_Real divecandsol, SCIP_Real divecandfrac, SCIP_Real *candscore, SCIP_Bool *roundup)
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
SCIP_RETCODE SCIPbacktrackProbing(SCIP *scip, int probingdepth)
void SCIPupdateDivesetLPStats(SCIP *scip, SCIP_DIVESET *diveset, SCIP_Longint niterstoadd, SCIP_DIVECONTEXT divecontext)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
SCIP_RETCODE SCIPaddDiveBoundChange(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR dir, SCIP_Real value, SCIP_Bool preferred)
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
SCIP_RETCODE SCIPsolveProbingLP(SCIP *scip, int itlim, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition lp.c:17292
int SCIProwGetNNonz(SCIP_ROW *row)
Definition lp.c:17213
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition lp.c:17238
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition lp.c:17302
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition lp.c:17401
const char * SCIProwGetName(SCIP_ROW *row)
Definition lp.c:17351
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
Definition lp.c:17258
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition lp.c:17248
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition scip_sol.c:2313
SCIP_RETCODE SCIPunlinkSol(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1190
SCIP_RETCODE SCIProundSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *success)
Definition scip_sol.c:2455
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition scip_sol.c:3098
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1444
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1361
SCIP_Real SCIPretransformObj(SCIP *scip, SCIP_Real obj)
Definition scip_sol.c:1576
SCIP_Longint SCIPgetNSolsFound(SCIP *scip)
int SCIPgetMaxDepth(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Real SCIPgetDualbound(SCIP *scip)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Real SCIPgetAvgLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNNodeLPIterations(SCIP *scip)
SCIP_Real SCIPgetAvgDualbound(SCIP *scip)
SCIP_Longint SCIPgetNBestSolsFound(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Longint SCIPgetNConflictConssFound(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
SCIP_RETCODE SCIPaddTrustregionNeighborhoodConstraint(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **subvars, SCIP_Real violpenalty)
Definition heuristics.c:999
SCIP_RETCODE SCIPcopyLargeNeighborhoodSearch(SCIP *sourcescip, SCIP *subscip, SCIP_HASHMAP *varmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool uselprows, SCIP_Bool copycuts, SCIP_Bool *success, SCIP_Bool *valid)
Definition heuristics.c:925
SCIP_RETCODE SCIPperformGenericDivingAlgorithm(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Bool nodeinfeasible, SCIP_Longint iterlim, SCIP_DIVECONTEXT divecontext)
Definition heuristics.c:218
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
Definition scip_tree.c:670
SCIP_Bool SCIPvarMayRoundUp(SCIP_VAR *var)
Definition var.c:3451
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:17966
SCIP_Bool SCIPvarMayRoundDown(SCIP_VAR *var)
Definition var.c:3440
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17406
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17241
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition scip_var.c:1248
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:17956
SCIP_RETCODE SCIPupdateVarPseudocost(SCIP *scip, SCIP_VAR *var, SCIP_Real solvaldelta, SCIP_Real objdelta, SCIP_Real weight)
Definition scip_var.c:8780
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition scip_var.c:194
void SCIPenableVarHistory(SCIP *scip)
Definition scip_var.c:8741
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10788
void SCIPdivesetSetWorkSolution(SCIP_DIVESET *diveset, SCIP_SOL *sol)
Definition heur.c:432
return SCIP_OKAY
static SCIP_DIVESET * diveset
int maxdivedepth
SCIP_Real searchavgbound
SCIP_Bool lperror
int c
SCIP_Real searchubbound
SCIP_Bool backtracked
heurdata nlpiterations
SCIPendProbing(scip))
SCIP_Real searchbound
SCIP_Longint maxnlpiterations
int maxdepth
int depth
SCIP_Bool cutoff
SCIP_Real * lpcandssol
int nlpcands
SCIP_VAR ** lpcands
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIPlinkLPSol(scip, sol))
SCIP_Real * lpcandsfrac
static SCIP_VAR ** vars
int nbinvars
#define MINLPITER
Definition heuristics.c:41
static SCIP_RETCODE solveLP(SCIP *scip, SCIP_DIVESET *diveset, SCIP_Longint maxnlpiterations, SCIP_DIVECONTEXT divecontext, SCIP_Bool *lperror, SCIP_Bool *cutoff)
Definition heuristics.c:46
static SCIP_RETCODE createRows(SCIP *scip, SCIP *subscip, SCIP_HASHMAP *varmap)
Definition heuristics.c:863
static SCIP_RETCODE selectNextDiving(SCIP *scip, SCIP_DIVESET *diveset, SCIP_SOL *worksol, SCIP_Bool onlylpbranchcands, SCIP_Bool storelpcandscores, SCIP_VAR **lpcands, SCIP_Real *lpcandssol, SCIP_Real *lpcandsfrac, SCIP_Real *lpcandsscores, SCIP_Bool *lpcandroundup, int *nviollpcands, int nlpcands, SCIP_Bool *enfosuccess, SCIP_Bool *infeasible)
Definition heuristics.c:90
static SCIP_Longint getDivesetIterLimit(SCIP *scip, SCIP_DIVESET *diveset, SCIP_DIVECONTEXT divecontext)
Definition heuristics.c:175
methods commonly used by primal heuristics
#define NULL
Definition lpi_spx1.cpp:161
public methods for primal heuristics
#define SCIPerrorMessage
Definition pub_message.h:64
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
default SCIP plugins
#define MAX(x, y)
Definition tclique_def.h:92
enum SCIP_DiveContext SCIP_DIVECONTEXT
Definition type_heur.h:72
#define SCIP_DIVETYPE_INTEGRALITY
Definition type_heur.h:60
@ SCIP_BRANCHDIR_DOWNWARDS
@ SCIP_BRANCHDIR_FIXED
@ SCIP_BRANCHDIR_AUTO
@ SCIP_BRANCHDIR_UPWARDS
enum SCIP_BranchDir SCIP_BRANCHDIR
@ SCIP_LPSOLSTAT_NOTSOLVED
Definition type_lp.h:42
@ SCIP_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
@ SCIP_LPSOLSTAT_INFEASIBLE
Definition type_lp.h:44
@ SCIP_LPSOLSTAT_OBJLIMIT
Definition type_lp.h:46
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_DELAYED
Definition type_result.h:43
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_FOUNDSOL
Definition type_result.h:56
enum SCIP_Result SCIP_RESULT
Definition type_result.h:61
@ SCIP_INVALIDDATA
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_CONTINUOUS
Definition type_var.h:71
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62