SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
heur_undercover.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 heur_undercover.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief Undercover primal heuristic for MINLPs
28 * @author Timo Berthold
29 * @author Ambros Gleixner
30 *
31 * The undercover heuristic is designed for mixed-integer nonlinear programs and tries to fix a subset of variables such
32 * as to make each constraint linear or convex. For this purpose it solves a binary program to automatically determine
33 * the minimum number of variable fixings necessary. As fixing values, we use values from the LP relaxation, the NLP
34 * relaxation, or the incumbent solution.
35 *
36 * @todo use the conflict analysis to analyze the infeasibility which arise after the probing of the cover worked and
37 * solve returned infeasible, instead of adding the Nogood/Conflict by hand; that has the advantage that the SCIP
38 * takes care of creating the conflict and might shrink the initial reason
39 *
40 * @todo do not use LP and NLP fixing values in the same run, e.g., fixingalts = "lni", but start a second dive if LP
41 * values fail
42 */
43
44/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
45
47#include "scip/cons_and.h"
49#include "scip/cons_nonlinear.h"
50#include "scip/cons_indicator.h"
51#include "scip/cons_linear.h"
52#include "scip/cons_logicor.h"
53#include "scip/cons_setppc.h"
54#include "scip/heur_subnlp.h"
56#include "scip/pub_cons.h"
57#include "scip/pub_expr.h"
58#include "scip/pub_heur.h"
59#include "scip/pub_message.h"
60#include "scip/pub_misc.h"
61#include "scip/pub_misc_sort.h"
62#include "scip/pub_nlp.h"
63#include "scip/pub_var.h"
64#include "scip/scip_branch.h"
65#include "scip/scip_cons.h"
66#include "scip/scip_copy.h"
67#include "scip/scipdefplugins.h"
68#include "scip/scip_general.h"
69#include "scip/scip_heur.h"
70#include "scip/scip_lp.h"
71#include "scip/scip_mem.h"
72#include "scip/scip_message.h"
73#include "scip/scip_nlp.h"
74#include "scip/scip_numerics.h"
75#include "scip/scip_param.h"
76#include "scip/scip_prob.h"
77#include "scip/scip_probing.h"
79#include "scip/scip_sol.h"
80#include "scip/scip_solve.h"
82#include "scip/scip_timing.h"
83#include "scip/scip_tree.h"
84#include "scip/scip_var.h"
85#include <string.h>
86
87#define HEUR_NAME "undercover"
88#define HEUR_DESC "solves a sub-CIP determined by a set covering approach"
89#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
90#define HEUR_PRIORITY -1110000
91#define HEUR_FREQ 0
92#define HEUR_FREQOFS 0
93#define HEUR_MAXDEPTH -1
94#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
95#define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
96
97/* default values for user parameters, grouped by parameter type */
98#define DEFAULT_FIXINGALTS "li" /**< sequence of fixing values used: 'l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution */
99
100#define DEFAULT_MAXNODES (SCIP_Longint)500/**< maximum number of nodes to regard in the subproblem */
101#define DEFAULT_MINNODES (SCIP_Longint)500/**< minimum number of nodes to regard in the subproblem */
102#define DEFAULT_NODESOFS (SCIP_Longint)500/**< number of nodes added to the contingent of the total nodes */
103
104#define DEFAULT_CONFLICTWEIGHT 1000.0 /**< weight for conflict score in fixing order */
105#define DEFAULT_CUTOFFWEIGHT 1.0 /**< weight for cutoff score in fixing order */
106#define DEFAULT_INFERENCEWEIGHT 1.0 /**< weight for inference score in fixing order */
107#define DEFAULT_MAXCOVERSIZEVARS 1.0 /**< maximum coversize (as fraction of total number of variables) */
108#define DEFAULT_MAXCOVERSIZECONSS SCIP_REAL_MAX /**< maximum coversize (as ratio to the percentage of non-affected constraints) */
109#define DEFAULT_MINCOVEREDREL 0.15 /**< minimum percentage of nonlinear constraints in the original problem */
110#define DEFAULT_MINCOVEREDABS 5 /**< minimum number of nonlinear constraints in the original problem */
111#define DEFAULT_MINIMPROVE 0.0 /**< factor by which heuristic should at least improve the incumbent */
112#define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */
113#define DEFAULT_RECOVERDIV 0.9 /**< fraction of covering variables in the last cover which need to change their value when recovering */
114
115#define DEFAULT_MAXBACKTRACKS 6 /**< maximum number of backtracks */
116#define DEFAULT_MAXRECOVERS 0 /**< maximum number of recoverings */
117#define DEFAULT_MAXREORDERS 1 /**< maximum number of reorderings of the fixing order */
118
119#define DEFAULT_COVERINGOBJ 'u' /**< objective function of the covering problem */
120#define DEFAULT_FIXINGORDER 'v' /**< order in which variables should be fixed */
121
122#define DEFAULT_BEFORECUTS TRUE /**< should undercover called at root node before cut separation? */
123#define DEFAULT_FIXINTFIRST FALSE /**< should integer variables in the cover be fixed first? */
124#define DEFAULT_LOCKSROUNDING TRUE /**< shall LP values for integer vars be rounded according to locks? */
125#define DEFAULT_ONLYCONVEXIFY FALSE /**< should we only fix/dom.red. variables creating nonconvexity? */
126#define DEFAULT_POSTNLP TRUE /**< should the NLP heuristic be called to polish a feasible solution? */
127#define DEFAULT_COVERBD FALSE /**< should bounddisjunction constraints be covered (or just copied)? */
128#define DEFAULT_REUSECOVER FALSE /**< shall the cover be re-used if a conflict was added after an infeasible subproblem? */
129#define DEFAULT_COPYCUTS TRUE /**< should all active cuts from the cutpool of the original scip be copied
130 * to constraints of the subscip
131 */
132#define DEFAULT_RANDSEED 43 /* initial random seed */
133
134/* local defines */
135#define COVERINGOBJS "cdlmtu" /**< list of objective functions of the covering problem */
136#define FIXINGORDERS "CcVv" /**< list of orders in which variables can be fixed */
137#define MAXNLPFAILS 1 /**< maximum number of fails after which we give up solving the NLP relaxation */
138#define MAXPOSTNLPFAILS 1 /**< maximum number of fails after which we give up calling NLP local search */
139#define MINTIMELEFT 1.0 /**< don't start expensive parts of the heuristics if less than this amount of time left */
140#define SUBMIPSETUPCOSTS 200 /**< number of nodes equivalent for the costs for setting up the sub-CIP */
141
142
143/*
144 * Data structures
145 */
146
147/** primal heuristic data */
148struct SCIP_HeurData
149{
150 SCIP_CONSHDLR** nlconshdlrs; /**< array of nonlinear constraint handlers */
151 SCIP_HEUR* nlpheur; /**< pointer to NLP local search heuristics */
152 SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
153 char* fixingalts; /**< sequence of fixing values used: 'l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution */
154 SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
155 SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
156 SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
157 SCIP_Longint nusednodes; /**< nodes already used by heuristic in earlier calls */
158 SCIP_Real conflictweight; /**< weight for conflict score in fixing order */
159 SCIP_Real cutoffweight; /**< weight for cutoff score in fixing order */
160 SCIP_Real inferenceweight; /**< weight for inference score in foxing order */
161 SCIP_Real maxcoversizevars; /**< maximum coversize (as fraction of total number of variables) */
162 SCIP_Real maxcoversizeconss; /**< maximum coversize (as ratio to the percentage of non-affected constraints) */
163 SCIP_Real mincoveredrel; /**< minimum percentage of nonlinear constraints in the original problem */
164 SCIP_Real minimprove; /**< factor by which heuristic should at least improve the incumbent */
165 SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
166 SCIP_Real recoverdiv; /**< fraction of covering variables in the last cover which need to change their value when recovering */
167 int mincoveredabs; /**< minimum number of nonlinear constraints in the original problem */
168 int maxbacktracks; /**< maximum number of backtracks */
169 int maxrecovers; /**< maximum number of recoverings */
170 int maxreorders; /**< maximum number of reorderings of the fixing order */
171 int nfixingalts; /**< number of fixing alternatives */
172 int nnlpfails; /**< number of fails when solving the NLP relaxation after last success */
173 int npostnlpfails; /**< number of fails of the NLP local search after last success */
174 int nnlconshdlrs; /**< number of nonlinear constraint handlers */
175 char coveringobj; /**< objective function of the covering problem */
176 char fixingorder; /**< order in which variables should be fixed */
177 SCIP_Bool beforecuts; /**< should undercover be called at root node before cut separation? */
178 SCIP_Bool fixintfirst; /**< should integer variables in the cover be fixed first? */
179 SCIP_Bool globalbounds; /**< should global bounds on variables be used instead of local bounds at focus node? */
180 SCIP_Bool locksrounding; /**< shall LP values for integer vars be rounded according to locks? */
181 SCIP_Bool nlpsolved; /**< has current NLP relaxation already been solved successfully? */
182 SCIP_Bool nlpfailed; /**< has solving the NLP relaxation failed? */
183 SCIP_Bool onlyconvexify; /**< should we only fix/dom.red. variables creating nonconvexity? */
184 SCIP_Bool postnlp; /**< should the NLP heuristic be called to polish a feasible solution? */
185 SCIP_Bool coverbd; /**< should bounddisjunction constraints be covered (or just copied)? */
186 SCIP_Bool reusecover; /**< shall the cover be re-used if a conflict was added after an infeasible subproblem? */
187 SCIP_Bool copycuts; /**< should all active cuts from cutpool be copied to constraints in
188 * subproblem? */
189};
190
191/*
192 * Local methods
193 */
194
195
196/** determines, whether a variable is fixed to the given value */
197static
198SCIP_Bool varIsFixed(
199 SCIP* scip, /**< SCIP data structure */
200 SCIP_VAR* var, /**< variable to check */
201 SCIP_Real val, /**< value to check */
202 SCIP_Bool global /**< should global bounds be used? */
203 )
204{
205 SCIP_Bool isfixed;
206
207 if( global )
209 else
211
212 return isfixed;
213}
214
215
216/** determines, whether a term is already constant, because the variable is fixed or the coefficient is zero */
217static
219 SCIP* scip, /**< SCIP data structure */
220 SCIP_VAR* var, /**< variable to check */
221 SCIP_Real coeff, /**< coefficient to check */
222 SCIP_Bool global /**< should global bounds be used? */
223 )
224{
225 /* if the variable has zero coefficient in the original problem, the term is linear */
226 if( SCIPisZero(scip, coeff) )
227 return TRUE;
228
229 /* if the variable is fixed in the original problem, the term is linear */
230 if( global )
232 else
234}
235
236
237/** determines, whether a term is convex */
238static
239SCIP_Bool termIsConvex(
240 SCIP* scip, /**< SCIP data structure */
241 SCIP_Real lhs, /**< left hand side of the constraint */
242 SCIP_Real rhs, /**< right hand side of the constraint */
243 SCIP_Bool sign /**< signature of the term */
244 )
245{
246 return sign ? SCIPisInfinity(scip, -lhs) : SCIPisInfinity(scip, rhs);
247}
248
249
250/** increases counters */
251static
253 int* termcounter, /**< array to count in how many nonlinear terms a variable appears */
254 int* conscounter, /**< array to count in how many constraints a variable appears */
255 SCIP_Bool* consmarker, /**< was this variable already counted for this constraint? */
256 int idx /**< problem index of the variable */
257 )
258{
259 termcounter[idx]++;
260 if( !consmarker[idx] )
261 {
262 conscounter[idx]++;
263 consmarker[idx] = TRUE;
264 }
265 return;
266}
267
268
269/** update time limit */
270static
272 SCIP* scip, /**< SCIP data structure */
273 SCIP_CLOCK* clck, /**< clock timer */
274 SCIP_Real* timelimit /**< time limit */
275 )
276{
277 *timelimit -= SCIPgetClockTime(scip, clck);
280
281 return SCIP_OKAY;
282}
283
284
285/** analyzes a nonlinear row and adds constraints and fixings to the covering problem */
286static
288 SCIP* scip, /**< original SCIP data structure */
289 SCIP_NLROW* nlrow, /**< nonlinear row representation of a nonlinear constraint */
290 SCIP* coveringscip, /**< SCIP data structure for the covering problem */
291 int nvars, /**< number of variables */
292 SCIP_VAR** coveringvars, /**< array to store the covering problem's variables */
293 int* termcounter, /**< counter array for number of nonlinear nonzeros per variable */
294 int* conscounter, /**< counter array for number of nonlinear constraints per variable */
295 SCIP_Bool* consmarker, /**< marker array if constraint has been counted in conscounter */
296 SCIP_Bool globalbounds, /**< should global bounds on variables be used instead of local bounds at focus node? */
297 SCIP_Bool onlyconvexify, /**< should we only fix/dom.red. variables creating nonconvexity? */
298 SCIP_Bool* success /**< pointer to store whether row was processed successfully */
299 )
300{
301 SCIP_EXPR* expr;
302 SCIP_Bool infeas;
303 SCIP_Bool fixed;
304 int t;
305 char name[SCIP_MAXSTRLEN];
306
307 assert(scip != NULL);
308 assert(nlrow != NULL);
310 assert(nvars >= 1);
315 assert(success != NULL);
316
317 *success = FALSE;
318
319 /* if we only want to convexify and curvature and bounds prove already convexity, nothing to do */
320 if( onlyconvexify
324 {
325 *success = TRUE;
326 return SCIP_OKAY;
327 }
328
330
331 /* go through expression */
332 expr = SCIPnlrowGetExpr(nlrow);
333 if( expr != NULL )
334 {
335 SCIP_Bool isquadratic;
336
339 {
340 int nquadexprs;
341 int nbilinexprs;
342
343 SCIPexprGetQuadraticData(expr, NULL, NULL, NULL, NULL, &nquadexprs, &nbilinexprs, NULL, NULL);
344
345 /* go through all quadratic terms */
346 for( t = 0; t < nquadexprs; ++t )
347 {
349 SCIP_Real sqrcoef;
350 int probidx;
351
352 SCIPexprGetQuadraticQuadTerm(expr, t, &varexpr, NULL, &sqrcoef, 0, NULL, NULL);
353
354 /* term is constant, nothing to do */
355 if( termIsConstant(scip, SCIPgetVarExprVar(varexpr), sqrcoef, globalbounds) )
356 continue;
357
358 /* if we only convexify and term is convex considering the bounds of the nlrow, nothing to do */
359 if( onlyconvexify && termIsConvex(scip, SCIPnlrowGetLhs(nlrow), SCIPnlrowGetRhs(nlrow), sqrcoef >= 0) )
360 continue;
361
363 if( probidx == -1 )
364 {
365 SCIPdebugMsg(scip, "inactive variable detected in nonlinear row <%s>\n", SCIPnlrowGetName(nlrow));
366 return SCIP_OKAY;
367 }
369
370 /* otherwise variable has to be in the cover */
372 assert(!infeas);
373 assert(fixed);
374
375 /* update counters */
377
378 SCIPdebugMsg(scip, "fixing var <%s> in covering problem to 1\n", SCIPvarGetName(coveringvars[probidx]));
379 }
380
381 /* go through all bilinear terms */
382 for( t = 0; t < nbilinexprs; ++t )
383 {
386 SCIP_Real bilincoef;
387 int probidx1;
388 int probidx2;
391
393
394 /* if the term is linear because one of the variables is fixed or the coefficient is zero, nothing to do */
397 continue;
398
401 if( probidx1 == -1 || probidx2 == -1 )
402 {
403 SCIPdebugMsg(scip, "inactive variables detected in nonlinear row <%s>\n", SCIPnlrowGetName(nlrow));
404 return SCIP_OKAY;
405 }
408
409 /* create covering constraint */
410 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering%d", SCIPnlrowGetName(nlrow), t);
415
416 if( coveringcons == NULL )
417 {
418 SCIPdebugMsg(scip, "failed to create set covering constraint <%s>\n", name);
419 return SCIP_OKAY;
420 }
421
422 /* add and release covering constraint */
425
426 /* update counters for both variables */
429 }
430 }
431 else
432 {
433 /* fix all variables contained in the expression */
435 int probidx;
436
439 for( ; !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it) ) /*lint !e441*/ /*lint !e440*/
440 {
441 if( !SCIPisExprVar(scip, expr) )
442 continue;
443
444 /* if constraints with inactive variables are present, we will have difficulties creating the sub-CIP later */
446 if( probidx == -1 )
447 {
448 SCIPdebugMsg(scip, "strange: inactive variable <%s> detected in nonlinear row <%s>\n",
450 return SCIP_OKAY;
451 }
453
454 /* term is constant, nothing to do */
455 if( termIsConstant(scip, SCIPgetVarExprVar(expr), 1.0, globalbounds) )
456 continue;
457
458 /* otherwise fix variable */
460 assert(!infeas);
461 assert(fixed);
462
463 /* update counters */
465
466 SCIPdebugMsg(scip, "fixing var <%s> in covering problem to 1\n", SCIPvarGetName(coveringvars[probidx]));
467 }
469 }
470 }
471 *success = TRUE;
472
473 return SCIP_OKAY;
474}
475
476
477/** creates the covering problem to determine a number of variables to be fixed */
478static
480 SCIP* scip, /**< original SCIP data structure */
481 SCIP* coveringscip, /**< SCIP data structure for the covering problem */
482 SCIP_VAR** coveringvars, /**< array to store the covering problem's variables */
483 SCIP_Bool globalbounds, /**< should global bounds on variables be used instead of local bounds at focus node? */
484 SCIP_Bool onlyconvexify, /**< should we only fix/dom.red. variables creating nonconvexity? */
485 SCIP_Bool coverbd, /**< should bounddisjunction constraints be covered (or just copied)? */
486 char coveringobj, /**< objective function of the covering problem */
487 SCIP_Bool* success /**< pointer to store whether the problem was created successfully */
488 )
489{
490 SCIP_VAR** vars;
491 SCIP_CONSHDLR* conshdlr;
492 SCIP_Bool* consmarker;
493 int* conscounter;
494 int* termcounter;
495
496 int nlocksup;
497 int nlocksdown;
498 int nvars;
499 int i;
500 int probindex;
501 char name[SCIP_MAXSTRLEN];
502
503 assert(scip != NULL);
506 assert(success != NULL);
507
508 *success = FALSE;
509
510 /* get required data of the original problem */
512
513 /* create problem data structure */
514 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPgetProbName(scip));
517
518 /* allocate and initialize to zero counter arrays for weighted objectives */
524
525 /* create covering variable for each variable in the original problem (fix it or not?) in the same order as in the
526 * original problem
527 */
528 for( i = 0; i < nvars; i++ )
529 {
530 SCIP_Real ub = 1.0;
531
533 {
534 /* skip relaxation-only variables; they cannot appear in constraints */
536 continue;
537 }
538
539 /* if the variable in the original problem is fixed, then the corresponding cover variable cannot be 1 in any
540 * optimal solution of the covering problem (see special termIsConstant treatment below)
541 * since some calling code may assume that no fixed variables will appear in the cover (see #1845), but we
542 * might not compute an optimal cover here, we fix these variable to 0 here
543 */
544 if( globalbounds )
545 {
547 ub = 0.0;
548 }
549 else
550 {
552 ub = 0.0;
553 }
554
555 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPvarGetName(vars[i]));
557 TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
560 }
561
562 /* go through all AND constraints in the original problem */
563 conshdlr = SCIPfindConshdlr(scip, "and");
564 if( conshdlr != NULL )
565 {
566 int c;
567
568 for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- )
569 {
575 SCIP_Real* coveringconsvals;
576 SCIP_Bool negated;
577
578 int ntofix;
579 int v;
580
581 /* get constraint and variables */
582 andcons = SCIPconshdlrGetConss(conshdlr)[c];
583 assert(andcons != NULL);
585 assert(andvars != NULL);
586
587 /* allocate memory for covering constraint */
590
591 /* collect unfixed variables */
593 ntofix = 0;
594 for( v = SCIPgetNVarsAnd(scip, andcons)-1; v >= 0; v-- )
595 {
596 assert(andvars[v] != NULL);
597 negated = FALSE;
598
599 /* if variable is fixed to 0, entire constraint can be linearized */
600 if( varIsFixed(scip, andvars[v], 0.0, globalbounds) )
601 {
602 ntofix = 0;
603 break;
604 }
605
606 /* if variable is fixed, nothing to do */
607 if( termIsConstant(scip, andvars[v], 1.0, globalbounds) )
608 {
609 continue;
610 }
611
612 /* if constraints with inactive variables are present, we have to find the corresponding active variable */
613 probindex = SCIPvarGetProbindex(andvars[v]);
614 if( probindex == -1 )
615 {
617
618 /* get binary representative of variable */
620 assert(repvar != NULL);
622
624 {
625 SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(andvars[v]));
626 SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(andcons));
629 goto TERMINATE;
630 }
631
632 /* check for negation */
634 {
636 negated = TRUE;
637 }
638 else
639 {
641 probindex = SCIPvarGetProbindex(repvar);
642 negated = FALSE;
643 }
644 }
645 assert(probindex >= 0);
646 assert(coveringvars[probindex] != NULL);
647
648 /* add covering variable for unfixed original variable */
649 if( negated )
650 {
652 }
653 else
656 ntofix++;
657 }
658 negated = FALSE;
659
660 /* if constraints with inactive variables are present, we have to find the corresponding active variable */
662 assert(andres != NULL);
663 probindex = SCIPvarGetProbindex(andres);
664
665 /* if resultant is fixed this constraint can be either linearized or is redundant because all operands can be fixed */
666 if( termIsConstant(scip, andres, 1.0, globalbounds) )
667 {
668 /* free memory for covering constraint */
671
672 continue;
673 }
674
675 if( probindex == -1 )
676 {
678
679 /* get binary representative of variable */
681 assert(repvar != NULL);
683
685 {
686 SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(SCIPgetResultantAnd(scip, andcons)));
687 SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(andcons));
690 goto TERMINATE;
691 }
692
693 /* check for negation */
695 {
697 negated = TRUE;
698 }
699 else
700 {
702 probindex = SCIPvarGetProbindex(repvar);
703 negated = FALSE;
704 }
705 }
706 else if( SCIPvarGetLbGlobal(andres) > 0.5 || SCIPvarGetUbGlobal(andres) < 0.5 )
707 {
708 /* free memory for covering constraint */
711
712 continue;
713 }
714 assert(probindex >= 0);
715 assert(coveringvars[probindex] != NULL);
716 assert(!termIsConstant(scip, (negated ? SCIPvarGetNegatedVar(vars[probindex]) : vars[probindex]), 1.0, globalbounds));
717
718 /* if less than two variables are unfixed or the resultant variable is fixed, the entire constraint can be linearized anyway */
719 if( ntofix >= 2 )
720 {
722
723 /* add covering variable for unfixed resultant */
724 if( negated )
725 {
727 }
728 else
731 ntofix++;
732
733 /* create covering constraint */
734 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPconsGetName(andcons));
736 (SCIP_Real)(ntofix - 1), SCIPinfinity(coveringscip),
738
739 if( coveringcons == NULL )
740 {
741 SCIPdebugMsg(scip, "failed to create linear constraint <%s>\n", name);
744 goto TERMINATE;
745 }
746
747 /* add and release covering constraint */
750
751 /* update counters */
752 for( v = ntofix-1; v >= 0; v-- )
755 else
757 }
758
759 /* free memory for covering constraint */
762 }
763 }
764
765 /* go through all bounddisjunction constraints in the original problem */
766 conshdlr = SCIPfindConshdlr(scip, "bounddisjunction");
767 if( conshdlr != NULL && coverbd )
768 {
769 int c;
770
771 for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- )
772 {
777 SCIP_Real* coveringconsvals;
778
779 int nbdvars;
780 int ntofix;
781 int v;
782
783 /* get constraint and variables */
784 bdcons = SCIPconshdlrGetConss(conshdlr)[c];
785 assert(bdcons != NULL);
787 assert(bdvars != NULL);
789
790 /* bounddisjunction constraints are not passed to the NLP, hence nothing to store in the hash map */
791
792 /* allocate memory for covering constraint */
795
796 /* collect unfixed variables */
798 ntofix = 0;
799 for( v = nbdvars-1; v >= 0; v-- )
800 {
801 SCIP_Bool negated;
802
803 assert(bdvars[v] != NULL);
804 negated = FALSE;
805
806 /* if variable is fixed, nothing to do */
807 if( varIsFixed(scip, bdvars[v], globalbounds ? SCIPvarGetLbGlobal(bdvars[v]) : SCIPvarGetLbLocal(bdvars[v]),
808 globalbounds) )
809 {
810 continue;
811 }
812
813 /* if constraints with inactive variables are present, we have to find the corresponding active variable */
814 probindex = SCIPvarGetProbindex(bdvars[v]);
815 if( probindex == -1 )
816 {
818
819 /* get binary representative of variable */
821 assert(repvar != NULL);
823
825 {
826 SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(bdvars[v]));
827 SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(bdcons));
830 goto TERMINATE;
831 }
832
833 /* check for negation */
835 {
837 negated = TRUE;
838 }
839 else
840 {
842 probindex = SCIPvarGetProbindex(repvar);
843 negated = FALSE;
844 }
845 }
846 assert(probindex >= 0);
847 assert(coveringvars[probindex] != NULL);
848
849 /* add covering variable for unfixed original variable */
850 if( negated )
851 {
853 }
854 else
857 ntofix++;
858 }
859
860 /* if less than two variables are unfixed, the entire constraint can be linearized anyway */
861 if( ntofix >= 2 )
862 {
864
865 /* create covering constraint */
866 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_covering", SCIPconsGetName(bdcons));
868 (SCIP_Real)(ntofix - 1), SCIPinfinity(coveringscip),
870
871 if( coveringcons == NULL )
872 {
873 SCIPdebugMsg(scip, "failed to create linear constraint <%s>\n", name);
876 goto TERMINATE;
877 }
878
879 /* add and release covering constraint */
882
883 /* update counters */
884 for( v = ntofix-1; v >= 0; v-- )
887 else
889 }
890
891 /* free memory for covering constraint */
894 }
895 }
896
897 /* go through all indicator constraints in the original problem; fix the binary variable */
898 conshdlr = SCIPfindConshdlr(scip, "indicator");
899 if( conshdlr != NULL )
900 {
901 int c;
902
903 for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- )
904 {
906 SCIP_VAR* binvar;
908
909 /* get constraint and variables */
910 indcons = SCIPconshdlrGetConss(conshdlr)[c];
911 assert(indcons != NULL);
913 assert(binvar != NULL);
914
915 /* indicator constraints are not passed to the NLP, hence nothing to store in the hash map */
916
917 /* if variable is fixed, nothing to do */
918 if( varIsFixed(scip, binvar, globalbounds ? SCIPvarGetLbGlobal(binvar) : SCIPvarGetLbLocal(binvar), globalbounds) )
919 {
920 continue;
921 }
922
923 /* if constraints with inactive variables are present, we have to find the corresponding active variable */
924 probindex = SCIPvarGetProbindex(binvar);
925 if( probindex == -1 )
926 {
928 SCIP_Bool negated;
929
930 /* get binary representative of variable */
931 negated = FALSE;
933 assert(repvar != NULL);
935
937 {
938 SCIPdebugMsg(scip, "strange: multiaggregated variable found <%s>\n", SCIPvarGetName(binvar));
939 SCIPdebugMsg(scip, "inactive variables detected in constraint <%s>\n", SCIPconsGetName(indcons));
940 goto TERMINATE;
941 }
942
943 /* check for negation */
946 else
947 {
949 probindex = SCIPvarGetProbindex(repvar);
950 }
951 }
952 assert(probindex >= 0);
953 assert(coveringvars[probindex] != NULL);
954
955 /* get covering variable for unfixed binary variable in indicator constraint */
956 coveringvar = coveringvars[probindex];
957
958 /* require covering variable to be fixed such that indicator is linearized */
960
961 /* update counters */
964 }
965 }
966
967 /* go through all nonlinear constraints in the original problem
968 * @todo: some expr constraints might be SOC and these only need to have all but one variable fixed in order to be
969 * linear; however, by just looking at the nlrow representation of a soc constraint, processNlRow doesn't realize
970 * this. if more specific information is accessible from expr constrains, then this can be improved
971 */
972 conshdlr = SCIPfindConshdlr(scip, "nonlinear");
973 if( conshdlr != NULL )
974 {
975 int c;
976
977 for( c = SCIPconshdlrGetNActiveConss(conshdlr)-1; c >= 0; c-- )
978 {
980 SCIP_NLROW* nlrow;
981
982 /* get constraint */
983 exprcons = SCIPconshdlrGetConss(conshdlr)[c];
984 assert(exprcons != NULL);
985
986 /* get nlrow representation and store it in hash map */
988 assert(nlrow != NULL);
989
990 /* process nlrow */
991 *success = FALSE;
993 termcounter, conscounter, consmarker, globalbounds, onlyconvexify, success) );
994
995 if( *success == FALSE )
996 goto TERMINATE;
997 }
998
999 *success = FALSE;
1000 }
1001
1002 /* set objective function of covering problem */
1003 switch( coveringobj )
1004 {
1005 case 'c': /* number of influenced nonlinear constraints */
1006 for( i = nvars-1; i >= 0; i-- )
1007 {
1008 if( coveringvars[i] == NULL )
1009 continue;
1011 }
1012 break;
1013 case 'd': /* domain size */
1014 for( i = nvars-1; i >= 0; i-- )
1015 {
1016 if( coveringvars[i] == NULL )
1017 continue;
1020 }
1021 break;
1022 case 'l': /* number of locks */
1023 for( i = nvars-1; i >= 0; i-- )
1024 {
1025 if( coveringvars[i] == NULL )
1026 continue;
1029 SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], (SCIP_Real) (nlocksup+nlocksdown+1)) );
1030 }
1031 break;
1032 case 'm': /* min(up locks, down locks)+1 */
1033 for( i = nvars-1; i >= 0; i-- )
1034 {
1035 if( coveringvars[i] == NULL )
1036 continue;
1039 SCIP_CALL( SCIPchgVarObj(coveringscip, coveringvars[i], (SCIP_Real) (MIN(nlocksup, nlocksdown)+1)) );
1040 }
1041 break;
1042 case 't': /* number of influenced nonlinear terms */
1043 for( i = nvars-1; i >= 0; i-- )
1044 {
1045 if( coveringvars[i] == NULL )
1046 continue;
1048 }
1049 break;
1050 case 'u': /* unit penalties */
1051 for( i = nvars-1; i >= 0; i-- )
1052 {
1053 if( coveringvars[i] == NULL )
1054 continue;
1056 }
1057 break;
1058 default:
1059 SCIPerrorMessage("invalid choice <%c> for covering objective\n", coveringobj);
1060 goto TERMINATE;
1061 }
1062
1063 /* covering problem successfully set up */
1064 *success = TRUE;
1065
1066 TERMINATE:
1068 {
1069 int nnonzs;
1070 nnonzs = 0;
1071 for( i = 0; i < nvars; ++i)
1072 nnonzs += termcounter[i];
1073 SCIPstatisticPrintf("UCstats nnz/var: %9.6f\n", nnonzs/(SCIP_Real)nvars);
1074 nnonzs = 0;
1075 for( i = 0; i < nvars; ++i)
1076 if( conscounter[i] > 0 )
1077 nnonzs++;
1078 SCIPstatisticPrintf("UCstats nlvars: %6d\n", nnonzs);
1079 }
1080 );
1081
1082 /* free counter arrays for weighted objectives */
1086
1087 return SCIP_OKAY;
1088}
1089
1090
1091/** adds a constraint to the covering problem to forbid the given cover */
1092static
1094 SCIP* scip, /**< SCIP data structure of the covering problem */
1095 int nvars, /**< number of variables */
1096 SCIP_VAR** vars, /**< variable array */
1097 int coversize, /**< size of the cover */
1098 int* cover, /**< problem indices of the variables in the cover */
1099 int diversification, /**< how many unfixed variables have to change their value? */
1100 SCIP_Bool* success, /**< pointer to store whether the cutoff constraint was created successfully */
1101 SCIP_Bool* infeas /**< pointer to store whether the cutoff proves (local or global) infeasibility */
1102 )
1103{
1104 SCIP_CONS* cons;
1105 SCIP_VAR** consvars;
1106
1107 char name[SCIP_MAXSTRLEN];
1108 int nconsvars;
1109 int i;
1110
1111 assert(scip != NULL);
1112 assert(vars != NULL);
1113 assert(nvars >= 1);
1114 assert(cover != NULL);
1115 assert(coversize >= 1);
1117 assert(diversification >= 1);
1118 assert(success != NULL);
1119 assert(infeas != NULL);
1120
1121 *success = FALSE;
1122 *infeas = FALSE;
1123
1124 /* allocate memory for constraint variables */
1126 nconsvars = 0;
1127 cons = NULL;
1128
1129 /* create constraint name */
1130 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "forbid_cover_assignment");
1131
1132 /* if all variables in the cover are binary and we require only one variable to change its value, then we create a
1133 * set covering constraint
1134 */
1135 if( diversification == 1 )
1136 {
1137 /* build up constraint */
1138 for( i = coversize-1; i >= 0; i-- )
1139 {
1140 if( vars[cover[i]] != NULL && !SCIPisFeasGE(scip, SCIPvarGetLbLocal(vars[cover[i]]), 1.0) )
1141 {
1142 SCIP_CALL( SCIPgetNegatedVar(scip, vars[cover[i]], &consvars[nconsvars]) );
1143 nconsvars++;
1144 }
1145 }
1146
1147 /* if all covering variables are fixed to one, the constraint cannot be satisfied */
1148 if( nconsvars == 0 )
1149 {
1150 *infeas = TRUE;
1151 }
1152 else
1153 {
1154 /* create constraint */
1155 SCIP_CALL( SCIPcreateConsSetcover(scip, &cons, name, nconsvars, consvars,
1157 }
1158 }
1159 /* if all variables in the cover are binary and we require more variables to change their value, then we create a
1160 * linear constraint
1161 */
1162 else
1163 {
1164 SCIP_Real* consvals;
1165 SCIP_Real rhs;
1166
1167 /* build up constraint */
1169 for( i = coversize-1; i >= 0; i-- )
1170 {
1171 if( vars[cover[i]] != NULL && !SCIPisFeasGE(scip, SCIPvarGetLbLocal(vars[cover[i]]), 1.0) )
1172 {
1173 consvars[nconsvars] = vars[cover[i]];
1174 consvals[nconsvars] = 1.0;
1175 nconsvars++;
1176 }
1177 }
1178 rhs = (SCIP_Real) (nconsvars-diversification);
1179
1180 /* if too many covering variables are fixed to 1, the constraint cannot be satisfied */
1181 if( rhs < 0 )
1182 {
1183 *infeas = TRUE;
1184 }
1185 else
1186 {
1187 /* create constraint */
1188 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name,
1189 nconsvars, consvars, consvals, -SCIPinfinity(scip), rhs,
1191 }
1192
1193 /* free memory */
1195 }
1196
1197 /* free memory */
1198 SCIPfreeBufferArray(scip, &consvars);
1199
1200 /* if proven infeasible, we do not even add the constraint; otherwise we add and release the constraint if created
1201 * successfully
1202 */
1203 if( !(*infeas) && cons != NULL )
1204 {
1205 SCIP_CALL( SCIPaddCons(scip, cons) );
1206 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
1207 *success = TRUE;
1208 }
1209
1210 return SCIP_OKAY;
1211}
1212
1213
1214/** adds a set covering or bound disjunction constraint to the original problem */
1215static
1217 SCIP* scip, /**< SCIP data structure */
1218 int bdlen, /**< length of bound disjunction */
1219 SCIP_VAR** bdvars, /**< array of variables in bound disjunction */
1220 SCIP_BOUNDTYPE* bdtypes, /**< array of bound types in bound disjunction */
1221 SCIP_Real* bdbounds, /**< array of bounds in bound disjunction */
1222 SCIP_Bool local, /**< is constraint valid only locally? */
1223 SCIP_Bool dynamic, /**< is constraint subject to aging? */
1224 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? */
1225 SCIP_Bool* success /**< pointer to store whether the cutoff constraint was created successfully */
1226 )
1227{
1228 SCIP_CONS* cons;
1229 SCIP_VAR** consvars;
1230 SCIP_Bool isbinary;
1231 char name[SCIP_MAXSTRLEN];
1232 int i;
1233
1234 assert(scip != NULL);
1235 assert(bdlen >= 1);
1236 assert(bdvars != NULL);
1237 assert(bdtypes != NULL);
1238 assert(bdbounds != NULL);
1239 assert(success != NULL);
1240
1241 /* initialize */
1242 *success = FALSE;
1243 cons = NULL;
1244 consvars = NULL;
1245
1246 /* create constraint name */
1247 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "undercover_cutoff");
1248
1249 /* check if all variables in the cover are binary */
1250 isbinary = TRUE;
1251 for( i = bdlen-1; i >= 0 && isbinary; i-- )
1252 {
1254 }
1255
1256 /* if all variables in the cover are binary, then we create a logicor constraint */
1257 if( isbinary )
1258 {
1259 /* allocate memory for constraint variables */
1260 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, bdlen) );
1261
1262 /* build up constraint */
1263 for( i = bdlen-1; i >= 0; i-- )
1264 {
1267
1269 {
1270 consvars[i] = bdvars[i];
1271 }
1272 else
1273 {
1275 SCIP_CALL( SCIPgetNegatedVar(scip, bdvars[i], &consvars[i]) );
1276 }
1277 }
1278
1279 /* create conflict constraint */
1280 SCIP_CALL( SCIPcreateConsLogicor(scip, &cons, name, bdlen, consvars,
1281 FALSE, TRUE, FALSE, FALSE, TRUE, local, FALSE, dynamic, removable, FALSE) );
1282 }
1283 /* otherwise we create a bound disjunction constraint as given */
1284 else
1285 {
1286 /* create conflict constraint */
1288 FALSE, TRUE, FALSE, FALSE, TRUE, local, FALSE, dynamic, removable, FALSE) );
1289 }
1290
1291 /* add and release constraint if created successfully */
1292 if( cons != NULL )
1293 {
1294 if( local )
1295 {
1297 }
1298 else
1299 {
1300 SCIP_CALL( SCIPaddCons(scip, cons) );
1301 }
1302
1303 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
1304 *success = TRUE;
1305 }
1306
1307 /* free memory */
1308 SCIPfreeBufferArrayNull(scip, &consvars);
1309
1310 return SCIP_OKAY;
1311}
1312
1313
1314/** solve covering problem */
1315static
1317 SCIP* coveringscip, /**< SCIP data structure for the covering problem */
1318 int ncoveringvars, /**< number of the covering problem's variables */
1319 SCIP_VAR** coveringvars, /**< array of the covering problem's variables */
1320 int* coversize, /**< size of the computed cover */
1321 int* cover, /**< array to store indices of the variables in the computed cover
1322 * (should be ready to hold ncoveringvars entries) */
1323 SCIP_Real timelimit, /**< time limit */
1324 SCIP_Real memorylimit, /**< memory limit */
1325 SCIP_Real objlimit, /**< upper bound on the cover size */
1326 SCIP_Bool* success /**< feasible cover found? */
1327 )
1328{
1329 SCIP_Real totalpenalty;
1330 SCIP_RETCODE retcode;
1331 int i;
1332
1335 assert(cover != NULL);
1336 assert(coversize != NULL);
1337 assert(timelimit > 0.0);
1338 assert(memorylimit > 0.0);
1339 assert(success != NULL);
1340
1341 *success = FALSE;
1342
1343 /* forbid call of heuristics and separators solving sub-CIPs */
1345
1346 /* set presolving and separation to fast */
1349
1350 /* use inference branching */
1351 if( SCIPfindBranchrule(coveringscip, "inference") != NULL && !SCIPisParamFixed(coveringscip, "branching/inference/priority") )
1352 {
1353 SCIP_CALL( SCIPsetIntParam(coveringscip, "branching/inference/priority", INT_MAX/4) );
1354 }
1355
1356 /* only solve root */
1357 SCIP_CALL( SCIPsetLongintParam(coveringscip, "limits/nodes", 1LL) );
1358
1359 SCIPdebugMsg(coveringscip, "timelimit = %g, memlimit = %g\n", timelimit, memorylimit);
1360
1361 /* set time, memory, and objective limit */
1362 SCIP_CALL( SCIPsetRealParam(coveringscip, "limits/time", timelimit) );
1363 SCIP_CALL( SCIPsetRealParam(coveringscip, "limits/memory", memorylimit) );
1365
1366 /* do not abort on CTRL-C */
1367 SCIP_CALL( SCIPsetBoolParam(coveringscip, "misc/catchctrlc", FALSE) );
1368
1369 /* disable output to console in optimized mode, enable in SCIP's debug mode */
1370#ifdef SCIP_DEBUG
1371 SCIP_CALL( SCIPsetIntParam(coveringscip, "display/verblevel", 5) );
1372 SCIP_CALL( SCIPsetIntParam(coveringscip, "display/freq", 100000) );
1373#else
1374 SCIP_CALL( SCIPsetIntParam(coveringscip, "display/verblevel", 0) );
1375#endif
1376
1377 /* solve covering problem */
1378 retcode = SCIPsolve(coveringscip);
1379
1380 /* errors in solving the covering problem should not kill the overall solving process;
1381 * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
1382 */
1383 if( retcode != SCIP_OKAY )
1384 {
1385#ifndef NDEBUG
1386 SCIP_CALL( retcode );
1387#endif
1388 SCIPwarningMessage(coveringscip, "Error while solving covering problem in Undercover heuristic; sub-SCIP terminated with code <%d>\n",retcode);
1389 return SCIP_OKAY;
1390 }
1391
1392 /* check, whether a feasible cover was found */
1393 if( SCIPgetNSols(coveringscip) == 0 )
1394 return SCIP_OKAY;
1395
1396 /* store solution */
1397 *coversize = 0;
1398 totalpenalty = 0.0;
1399 for( i = 0; i < ncoveringvars; i++ )
1400 {
1401 if( coveringvars[i] == NULL )
1402 continue;
1403
1405 {
1406 cover[*coversize] = i;
1407 (*coversize)++;
1408 }
1410 }
1411
1412 /* print solution if we are in SCIP's debug mode */
1414 SCIPdebugMsg(coveringscip, "found a feasible cover: %d/%d variables fixed, normalized penalty=%g\n\n",
1417 SCIPdebugMsg(coveringscip, "\r \n");
1418
1419 *success = TRUE;
1420
1421 return SCIP_OKAY;
1422}
1423
1424
1425/** computes fixing order and returns whether order has really been changed */
1426static
1428 SCIP* scip, /**< original SCIP data structure */
1429 SCIP_HEURDATA* heurdata, /**< heuristic data */
1430 int nvars, /**< number of variables in the original problem */
1431 SCIP_VAR** vars, /**< variables in the original problem */
1432 int coversize, /**< size of the cover */
1433 int* cover, /**< problem indices of the variables in the cover */
1434 int lastfailed, /**< position in cover array of the variable the fixing of which yielded
1435 * infeasibility in last dive (or >= coversize, in which case *success
1436 * is always TRUE) */
1437 SCIP_Bool* success /**< has order really been changed? */
1438 )
1439{
1440 SCIP_Real* scores;
1441 SCIP_Real bestscore;
1442 SCIP_Bool sortdown;
1443 int i;
1444
1445 assert(scip != NULL);
1446 assert(heurdata != NULL);
1447 assert(nvars >= 1);
1448 assert(vars != NULL);
1449 assert(coversize >= 1);
1450 assert(cover != NULL);
1451 assert(lastfailed >= 0);
1452
1453 *success = FALSE;
1454
1455 /* if fixing the first variable had failed, do not try with another order */
1456 if( lastfailed == 0 )
1457 return SCIP_OKAY;
1458
1459 /* allocate buffer array for score values */
1461
1462 /* initialize best score to infinite value */
1463 sortdown = (heurdata->fixingorder == 'c' || heurdata->fixingorder == 'v' );
1465
1466 /* compute score values */
1467 for( i = coversize-1; i >= 0; i-- )
1468 {
1469 SCIP_VAR* var;
1470
1471 /* get variable in the cover */
1472 assert(cover[i] >= 0);
1473 assert(cover[i] < nvars);
1474 var = vars[cover[i]];
1475
1476 if( heurdata->fixingorder == 'C' || heurdata->fixingorder == 'c' )
1477 {
1478 /* add a small pertubation value to the score to reduce performance variability */
1479 scores[i] = heurdata->conflictweight * SCIPgetVarConflictScore(scip, var)
1480 + heurdata->inferenceweight * SCIPgetVarAvgInferenceCutoffScore(scip, var, heurdata->cutoffweight)
1481 + SCIPrandomGetReal(heurdata->randnumgen, 0.0, SCIPepsilon(scip));
1482 }
1483 else if( heurdata->fixingorder == 'V' || heurdata->fixingorder == 'v' )
1484 scores[i] = cover[i];
1485 else
1487
1488 assert(scores[i] >= 0.0);
1489
1490 /* update best score */
1491 if( sortdown )
1492 bestscore = MAX(bestscore, scores[i]);
1493 else
1494 bestscore = MIN(bestscore, scores[i]);
1495 }
1496
1497 /* put integers to the front */
1498 if( heurdata->fixintfirst )
1499 {
1500 for( i = coversize-1; i >= 0; i-- )
1501 {
1502 if( SCIPvarIsIntegral(vars[cover[i]]) )
1503 {
1504 if( sortdown )
1505 scores[i] += bestscore+1.0;
1506 else
1507 scores[i] = bestscore - 1.0/(scores[i]+1.0);
1508 }
1509 }
1510 }
1511
1512 /* put last failed variable to the front */
1513 if( lastfailed < coversize )
1514 {
1515 if( sortdown )
1516 scores[lastfailed] += bestscore+2.0;
1517 else
1518 scores[lastfailed] = bestscore - 2.0/(scores[lastfailed]+1.0);
1519 i = cover[lastfailed];
1520 }
1521
1522 /* sort by non-decreasing (negative) score */
1523 if( sortdown )
1525 else
1527
1528 assert(lastfailed >= coversize || cover[0] == i);
1529
1530 /* free buffer memory */
1531 SCIPfreeBufferArray(scip, &scores);
1532
1533 *success = TRUE;
1534
1535 return SCIP_OKAY;
1536}
1537
1538
1539/** gets fixing value */
1540static
1542 SCIP* scip, /**< original SCIP data structure */
1543 SCIP_HEURDATA* heurdata, /**< heuristic data */
1544 SCIP_VAR* var, /**< variable in the original problem */
1545 SCIP_Real* val, /**< buffer for returning fixing value */
1546 char fixalt, /**< source of the fixing value: 'l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution */
1547 SCIP_Bool* success, /**< could value be retrieved successfully? */
1548 int bdlen, /**< current length of probing path */
1549 SCIP_VAR** bdvars, /**< array of variables with bound changes along probing path */
1550 SCIP_BOUNDTYPE* bdtypes, /**< array of bound types in bound disjunction */
1551 SCIP_Real* oldbounds /**< array of bounds before fixing */
1552 )
1553{
1554 assert(scip != NULL);
1555 assert(heurdata != NULL);
1556 assert(var != NULL);
1557 assert(val != NULL);
1558 assert(success != NULL);
1559
1560 *success = FALSE;
1561
1562 switch( fixalt )
1563 {
1564 case 'l':
1565 /* get the last LP solution value */
1566 *val = SCIPvarGetLPSol(var);
1567 *success = TRUE;
1568 break;
1569 case 'n':
1570 /* only call this function if NLP relaxation is available */
1572
1573 /* the solution values are already available */
1574 if( heurdata->nlpsolved )
1575 {
1576 assert(!heurdata->nlpfailed);
1577
1578 /* retrieve NLP solution value */
1579 *val = SCIPvarGetNLPSol(var);
1580 *success = TRUE;
1581 }
1582 /* solve NLP relaxation unless it has not failed too often before */
1583 else if( !heurdata->nlpfailed )
1584 { /*lint --e{850}*/
1585 SCIP_NLPSOLSTAT stat;
1586 int i;
1587
1588 /* restore bounds at start of probing, since otherwise, if in backtrack mode, NLP solver becomes most likely
1589 * locally infeasible
1590 */
1592
1593 for( i = bdlen-1; i >= 0; i-- )
1594 {
1596 SCIP_Real lb;
1597 SCIP_Real ub;
1598
1599 relaxvar = bdvars[i];
1600
1601 /* both bounds were tightened */
1602 if( i > 0 && bdvars[i-1] == relaxvar )
1603 {
1604 assert(bdtypes[i] != bdtypes[i-1]);
1605
1608 i--;
1609 }
1610 /* lower bound was tightened */
1611 else if( bdtypes[i] == SCIP_BOUNDTYPE_UPPER )
1612 {
1613 lb = oldbounds[i];
1615 }
1616 /* upper bound was tightened */
1617 else
1618 {
1620 ub = oldbounds[i];
1621 }
1622
1625
1626 /* relax bounds */
1628 }
1629
1630 /* set starting point to lp solution */
1632
1633 /* solve NLP relaxation */
1634 SCIP_CALL( SCIPsolveNLP(scip) ); /*lint !e666*/
1635 stat = SCIPgetNLPSolstat(scip);
1637
1638 SCIPdebugMsg(scip, "solving NLP relaxation to obtain fixing values %s (stat=%d)\n", *success ? "successful" : "failed", stat);
1639
1640 if( *success )
1641 {
1642 /* solving succeeded */
1643 heurdata->nnlpfails = 0;
1644 heurdata->nlpsolved = TRUE;
1645
1646 /* retrieve NLP solution value */
1647 *val = SCIPvarGetNLPSol(var);
1648 }
1649 else
1650 {
1651 /* solving failed */
1652 heurdata->nnlpfails++;
1653 heurdata->nlpfailed = TRUE;
1654 heurdata->nlpsolved = FALSE;
1655
1656 SCIPdebugMsg(scip, "solving NLP relaxation failed (%d time%s%s)\n",
1657 heurdata->nnlpfails, heurdata->nnlpfails > 1 ? "s" : "", heurdata->nnlpfails >= MAXNLPFAILS ? ", will not be called again" : "");
1658 }
1659 }
1660 break;
1661 case 'i':
1662 /* only call this function if a feasible solution is available */
1664
1665 /* get value in the incumbent solution */
1667 *success = TRUE;
1668 break;
1669 default:
1670 break;
1671 }
1672
1673 /* due to propagation (during probing) it might happen that the LP and NLP solution value of var might be outside of
1674 * its bounds
1675 */
1676 *val = MAX(*val, SCIPvarGetLbLocal(var)); /*lint !e666*/
1677 *val = MIN(*val, SCIPvarGetUbLocal(var)); /*lint !e666*/
1678
1679 return SCIP_OKAY;
1680}
1681
1682
1683/** calculates up to four alternative values for backtracking, if fixing the variable failed.
1684 * The alternatives are the two bounds of the variable, and the averages of the bounds and the fixing value.
1685 * For infinite bounds, fixval +/- abs(fixval) will be used instead.
1686 */
1687static
1689 SCIP* scip, /**< original SCIP data structure */
1690 SCIP_VAR* var, /**< variable to calculate alternatives for */
1691 SCIP_Real fixval, /**< reference fixing value */
1692 int* nalternatives, /**< number of fixing values computed */
1693 SCIP_Real* alternatives /**< array to store the alternative fixing values */
1694 )
1695{
1696 SCIP_Real lb;
1697 SCIP_Real ub;
1698
1699 /* for binary variables, there is only two possible fixing values */
1700 if( SCIPvarIsBinary(var) )
1701 {
1702 if( SCIPisFeasEQ(scip, fixval, 0.0) || SCIPisFeasEQ(scip, fixval, 1.0) )
1703 {
1704 alternatives[0] = 1.0 - fixval;
1705 *nalternatives = 1;
1706 }
1707 else
1708 {
1709 alternatives[0] = 0.0;
1710 alternatives[1] = 1.0;
1711 *nalternatives = 2;
1712 }
1713 return;
1714 }
1715
1716 /* get bounds */
1717 lb = SCIPvarGetLbLocal(var);
1718 ub = SCIPvarGetUbLocal(var);
1719
1720 /* if lower bound is infinite, use x'-|x'|; if x' is zero, use -1.0 instead */
1721 if( SCIPisInfinity(scip, -lb) )
1722 lb = SCIPisFeasZero(scip, fixval) ? -1.0 : fixval - ABS(fixval);
1723
1724 /* if upper bound is infinite, use x'+|x'|; if x' is zero, use 1.0 instead */
1725 if( SCIPisInfinity(scip, ub) )
1726 ub = SCIPisFeasZero(scip, fixval) ? 1.0 : fixval + ABS(fixval);
1727
1728 assert(!SCIPisEQ(scip, lb, ub));
1729
1730 /* collect alternatives */
1731 *nalternatives = 0;
1732
1733 /* use lower bound if not equal to x' */
1734 if( !SCIPisFeasEQ(scip, lb, fixval) )
1735 {
1737 (*nalternatives)++;
1738 }
1739
1740 /* use upper bound if not equal to x' */
1741 if( !SCIPisFeasEQ(scip, ub, fixval) )
1742 {
1744 (*nalternatives)++;
1745 }
1746
1747 /* use the average of x' and lower bound as alternative value, if this is not equal to any of the other values */
1748 if( !SCIPisFeasEQ(scip, lb, fixval) && (!SCIPvarIsIntegral(var) || !SCIPisFeasEQ(scip, lb, fixval-1)) )
1749 {
1750 alternatives[*nalternatives] = (lb+fixval)/2.0;
1751 (*nalternatives)++;
1752 }
1753
1754 /* use the average of x' and upper bound as alternative value, if this is not equal to any of the other values */
1755 if( !SCIPisFeasEQ(scip, ub, fixval) && (!SCIPvarIsIntegral(var) || !SCIPisFeasEQ(scip, ub, fixval+1)) )
1756 {
1757 alternatives[*nalternatives] = (ub+fixval)/2.0;
1758 (*nalternatives)++;
1759 }
1760
1761 assert(*nalternatives <= 4);
1762
1763 return;
1764}
1765
1766
1767/** rounds the given fixing value */
1768static
1770 SCIP* scip, /**< original SCIP data structure */
1771 SCIP_Real* val, /**< fixing value to be rounded */
1772 SCIP_VAR* var, /**< corresponding variable */
1773 SCIP_Bool locksrounding /**< shall we round according to locks? (otherwise to nearest integer) */
1774 )
1775{
1776 SCIP_Real x;
1777
1778 x = *val;
1779
1780 /* if integral within feasibility tolerance, only shift to nearest integer */
1781 if( SCIPisFeasIntegral(scip, x) )
1783
1784 /* round in the direction of least locks with fractionality as tie breaker */
1785 else if( locksrounding )
1786 {
1788 x = SCIPfeasFloor(scip, x);
1790 x = SCIPfeasCeil(scip, x);
1791 else
1793 }
1794 /* round in the direction of least fractionality with locks as tie breaker */
1795 else
1796 {
1797 if( SCIPfeasFrac(scip, x) < 0.5)
1798 x = SCIPfeasFloor(scip, x);
1799 else if( SCIPfeasFrac(scip, x) > 0.5 )
1800 x = SCIPfeasCeil(scip, x);
1801 else
1803 }
1804
1805 /* return rounded fixing value */
1806 *val = x;
1807
1808 return SCIP_OKAY;
1809}
1810
1811/** solve subproblem and pass best feasible solution to original SCIP instance */
1812static
1814 SCIP* scip, /**< SCIP data structure of the original problem */
1815 SCIP_HEUR* heur, /**< heuristic data structure */
1816 int coversize, /**< size of the cover */
1817 int* cover, /**< problem indices of the variables in the cover */
1818 SCIP_Real* fixedvals, /**< fixing values for the variables in the cover */
1819 SCIP_Real timelimit, /**< time limit */
1820 SCIP_Real memorylimit, /**< memory limit */
1821 SCIP_Longint nodelimit, /**< node limit */
1822 SCIP_Longint nstallnodes, /**< number of stalling nodes for the subproblem */
1823 SCIP_Bool* validsolved, /**< was problem constructed from a valid copy and solved (proven optimal or infeasible)? */
1824 SCIP_SOL** sol, /**< best solution found in subproblem (if feasible); *sol must be NULL, solution will be created */
1825 SCIP_Longint* nusednodes /**< number of nodes used for solving the subproblem */
1826 )
1827{
1829 SCIP* subscip;
1830 SCIP_VAR** subvars;
1831 SCIP_VAR** vars;
1832 SCIP_HASHMAP* varmap;
1833 SCIP_VAR** fixedvars;
1834 int nfixedvars;
1835
1836 SCIP_RETCODE retcode;
1837
1838 int nvars;
1839 int i;
1840
1841 assert(scip != NULL);
1842 assert(heur != NULL);
1843 assert(cover != NULL);
1844 assert(fixedvals != NULL);
1845 assert(coversize >= 1);
1846 assert(timelimit > 0.0);
1847 assert(memorylimit > 0.0);
1848 assert(nodelimit >= 1);
1849 assert(nstallnodes >= 1);
1851 assert(sol != NULL);
1852 assert(*sol == NULL);
1853 assert(nusednodes != NULL);
1854
1855 *validsolved = FALSE;
1856 *nusednodes = 0;
1857
1858 /* get heuristic data */
1859 heurdata = SCIPheurGetData(heur);
1860 assert(heurdata != NULL);
1861
1862 /* get required data of the original problem */
1864
1866 nfixedvars = coversize;
1867 /* fix subproblem variables in the cover */
1868 SCIPdebugMsg(scip, "fixing variables\n");
1869 for( i = coversize-1; i >= 0; i-- )
1870 {
1871 assert(cover[i] >= 0);
1872 assert(cover[i] < nvars);
1873
1874 fixedvars[i] = vars[cover[i]];
1875 }
1876
1877 /* create subproblem */
1878 SCIP_CALL( SCIPcreate(&subscip) );
1880
1881 /* create the variable mapping hash map */
1882 SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(subscip), nvars) );
1883
1884 /* copy original problem to subproblem; do not copy pricers */
1885 SCIP_CALL( SCIPcopyConsCompression(scip, subscip, varmap, NULL, "undercoversub", fixedvars, fixedvals, nfixedvars,
1886 heurdata->globalbounds, FALSE, FALSE, TRUE, validsolved) );
1887
1888 if( heurdata->copycuts )
1889 {
1890 /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
1891 SCIP_CALL( SCIPcopyCuts(scip, subscip, varmap, NULL, heurdata->globalbounds, NULL) );
1892 }
1893
1894 SCIPdebugMsg(scip, "problem copied, copy %svalid\n", *validsolved ? "" : "in");
1895
1896 /* store subproblem variables */
1897 for( i = nvars-1; i >= 0; i-- )
1898 subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[i]);
1899
1900 /* free variable mapping hash map */
1901 SCIPhashmapFree(&varmap);
1902
1903 /* set the parameters such that good solutions are found fast */
1904 SCIPdebugMsg(scip, "setting subproblem parameters\n");
1908
1909 /* deactivate expensive pre-root heuristics, since it may happen that the lp relaxation of the subproblem is already
1910 * infeasible; in this case, we do not want to waste time on heuristics before solving the root lp */
1911 if( !SCIPisParamFixed(subscip, "heuristics/shiftandpropagate/freq") )
1912 {
1913 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/shiftandpropagate/freq", -1) );
1914 }
1915
1916 /* forbid recursive call of undercover heuristic */
1917 if( SCIPisParamFixed(subscip, "heuristics/" HEUR_NAME "/freq") )
1918 {
1919 SCIPwarningMessage(scip, "unfixing parameter heuristics/" HEUR_NAME "/freq in subscip of undercover heuristic to avoid recursive calls\n");
1920 SCIP_CALL( SCIPunfixParam(subscip, "heuristics/" HEUR_NAME "/freq") );
1921 }
1922 SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/" HEUR_NAME "/freq", -1) );
1923
1924 SCIPdebugMsg(scip, "timelimit = %g, memlimit = %g, nodelimit = %" SCIP_LONGINT_FORMAT ", nstallnodes = %" SCIP_LONGINT_FORMAT "\n", timelimit, memorylimit, nodelimit, nstallnodes);
1925
1926 SCIPdebugMsg(scip, "timelimit = %g, memlimit = %g, nodelimit = %" SCIP_LONGINT_FORMAT ", nstallnodes = %" SCIP_LONGINT_FORMAT "\n", timelimit, memorylimit, nodelimit, nstallnodes);
1927
1928 /* disable statistic timing inside sub SCIP */
1929 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
1930
1931 /* set time, memory and node limits */
1932 SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
1933 SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
1934 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) );
1935 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", nstallnodes) );
1936
1937 /* do not abort subproblem on CTRL-C */
1938 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
1939
1940 /* disable output to console in optimized mode, enable in SCIP's debug mode */
1941#ifdef SCIP_DEBUG
1942 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
1943 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000) );
1944#else
1945 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
1946#endif
1947
1948 /* if there is already a solution, add an objective cutoff; note: this does not affect the validity of the subproblem
1949 * if we find solutions later, thus we do not set *validsolved to FALSE */
1950 if( SCIPgetNSols(scip) > 0 )
1951 {
1952 SCIP_Real cutoff;
1953 SCIP_Real upperbound;
1954
1956 upperbound = SCIPgetUpperbound(scip);
1957
1959 cutoff = (upperbound >= 0 ? 1.0 - heurdata->minimprove : 1.0 + heurdata->minimprove) * upperbound;
1960 else
1961 cutoff = (1.0 - heurdata->minimprove) * upperbound + heurdata->minimprove * SCIPgetLowerbound(scip);
1962
1963 cutoff = MIN(upperbound, cutoff);
1964 SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
1965
1966 SCIPdebugMsg(scip, "adding objective cutoff=%g (minimprove=%g)\n", cutoff, heurdata->minimprove);
1967 }
1968
1969 /* solve subproblem */
1970 SCIPdebugMsg(scip, "solving subproblem started\n");
1971 retcode = SCIPsolve(subscip);
1972
1973 /* Errors in solving the subproblem should not kill the overall solving process
1974 * Hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
1975 */
1976 if( retcode != SCIP_OKAY )
1977 {
1978#ifndef NDEBUG
1979 SCIP_CALL( retcode );
1980#endif
1981 SCIPwarningMessage(scip, "Error while solving subproblem in Undercover heuristic; sub-SCIP terminated with code <%d>\n",retcode);
1982 /* free array of subproblem variables, and subproblem */
1983 SCIPfreeBufferArray(scip, &subvars);
1984 SCIPfreeBufferArray(scip, &fixedvars);
1985 SCIP_CALL( SCIPfree(&subscip) );
1986 return SCIP_OKAY;
1987 }
1988
1989 /* print solving statistics of subproblem if we are in SCIP's debug mode */
1991
1992 /* store solving status; note: if we proved infeasibility in presence of an objective cutoff beyond the primal bound,
1993 * the subproblem was not a valid copy */
1995 || (SCIPgetStatus(subscip) == SCIP_STATUS_INFEASIBLE && (SCIPgetNSols(scip) == 0 || heurdata->minimprove <= 0.0)));
1996 *nusednodes = SCIPgetNNodes(subscip);
1997
1998 /* if a solution was found for the subproblem, create corresponding solution in the original problem */
1999 if( SCIPgetNSols(subscip) > 0 && (SCIPgetStatus(subscip) != SCIP_STATUS_INFEASIBLE || heurdata->minimprove > 0.0) )
2000 {
2001 SCIP_SOL** subsols;
2002 SCIP_Bool success = FALSE;
2003 int nsubsols;
2004
2005 /* check, whether a solution was found;
2006 * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted */
2007 nsubsols = SCIPgetNSols(subscip);
2008 subsols = SCIPgetSols(subscip);
2009 assert(subsols != NULL);
2010
2011 for( i = 0; i < nsubsols; i++ )
2012 {
2013 /* transform solution to original problem */
2014 SCIP_CALL( SCIPtranslateSubSol(scip, subscip, subsols[i], heur, subvars, sol) );
2015
2016 /* try to add new solution to scip */
2018
2019 if( success )
2020 {
2021 SCIPdebugMsg(scip, "heuristic found %d solutions in subproblem; solution %d feasible in original problem\n", nsubsols, i);
2022 break;
2023 }
2024 else
2025 {
2026 /* free solution structure, since SCIPtranslateSubSol would recreate in the next round */
2028 assert(*sol == NULL);
2029 }
2030 }
2031
2032 /* if the best subproblem solution was not accepted in the original problem, then we do not trust the solving status */
2033 if( !success || i > 0 )
2034 *validsolved = FALSE;
2035 }
2036
2037 if( *validsolved )
2038 {
2039 SCIP_CALL( SCIPmergeVariableStatistics(subscip, scip, subvars, vars, nvars) );
2040 }
2041
2042 /* free array of subproblem variables, and subproblem */
2043 SCIPfreeBufferArray(scip, &subvars);
2044 SCIPfreeBufferArray(scip, &fixedvars);
2045 SCIP_CALL( SCIPfree(&subscip) );
2046
2047 return SCIP_OKAY;
2048}
2049
2050
2051/** perform fixing of a variable and record bound disjunction information */
2052static
2054 SCIP* scip, /**< SCIP data structure */
2055 SCIP_VAR* var, /**< variable to fix */
2056 SCIP_Real val, /**< fixing value */
2057 SCIP_Bool* infeas, /**< pointer to store whether the fixing lead to infeasibility */
2058 int* bdlen, /**< current length of bound disjunction */
2059 SCIP_VAR** bdvars, /**< array of variables in bound disjunction */
2060 SCIP_BOUNDTYPE* bdtypes, /**< array of bound types in bound disjunction */
2061 SCIP_Real* bdbounds, /**< array of bounds in bound disjunction */
2062 SCIP_Real* oldbounds /**< array of bounds before fixing */
2063 )
2064{
2065 SCIP_Longint ndomredsfound;
2066 SCIP_Real oldlb;
2067 SCIP_Real oldub;
2068 int oldbdlen;
2069
2070 assert(scip != NULL);
2071 assert(var != NULL);
2072 assert(val >= SCIPvarGetLbLocal(var));
2073 assert(val <= SCIPvarGetUbLocal(var));
2074 assert(infeas != NULL);
2075 assert(bdlen != NULL);
2076 assert(*bdlen >= 0);
2077 assert(*bdlen < 2*SCIPgetNVars(scip)-1);
2078 assert(bdvars != NULL);
2079 assert(bdtypes != NULL);
2080 assert(bdbounds != NULL);
2081
2083
2084 /* remember length of probing path */
2085 oldbdlen = *bdlen;
2086
2087 /* get bounds of the variable to fix */
2090
2091 /* decrease upper bound to fixing value */
2092 *infeas = FALSE;
2093 if( SCIPisUbBetter(scip, val, oldlb, oldub) )
2094 {
2095 /* we only want to open a new probing node if we do not exceed the maximal tree depth */
2097 {
2098 /* create next probing node */
2100 }
2102
2103 SCIPdebugMsg(scip, "tentatively decreasing upper bound of variable <%s> to %g for probing\n",
2104 SCIPvarGetName(var), val);
2105
2106 /* store bound disjunction information */
2107 bdvars[*bdlen] = var;
2109 bdbounds[*bdlen] = SCIPvarIsIntegral(var) ? SCIPfeasCeil(scip, val)+1.0 : val;
2110 oldbounds[*bdlen] = oldub;
2111 (*bdlen)++;
2112
2113 /* propagate the bound change; conflict analysis is performed automatically */
2114 SCIP_CALL( SCIPpropagateProbing(scip, 0, infeas, &ndomredsfound) );
2115 SCIPdebugMsg(scip, " --> propagation reduced %" SCIP_LONGINT_FORMAT " further domains\n", ndomredsfound);
2116
2117 /* if propagation led to a cutoff, we backtrack immediately */
2118 if( *infeas )
2119 {
2120 *bdlen = oldbdlen;
2121 return SCIP_OKAY;
2122 }
2123
2124 /* store bound before propagation */
2125 oldbounds[*bdlen] = oldlb;
2126
2127 /* move fixing value into the new domain, since it may be outside due to numerical issues or previous propagation */
2130 val = MIN(val, oldub);
2131 val = MAX(val, oldlb);
2132
2134 }
2135
2136 /* update lower bound to fixing value */
2137 *infeas = FALSE;
2138 if( SCIPisLbBetter(scip, val, oldlb, oldub) )
2139 {
2140 /* we only want to open a new probing node if we do not exceed the maximal tree depth */
2142 {
2143 /* create next probing node */
2145 }
2147
2148 SCIPdebugMsg(scip, "tentatively increasing lower bound of variable <%s> to %g for probing\n",
2149 SCIPvarGetName(var), val);
2150
2151 /* store bound disjunction information */
2152 bdvars[*bdlen] = var;
2154 bdbounds[*bdlen] = SCIPvarIsIntegral(var) ? SCIPfeasCeil(scip, val)-1.0 : val;
2155 (*bdlen)++;
2156
2157 /* propagate the bound change */
2158 SCIP_CALL( SCIPpropagateProbing(scip, 0, infeas, &ndomredsfound) );
2159 SCIPdebugMsg(scip, " --> propagation reduced %" SCIP_LONGINT_FORMAT " further domains\n", ndomredsfound);
2160
2161 /* if propagation led to a cutoff, we backtrack immediately */
2162 if( *infeas )
2163 {
2164 *bdlen = oldbdlen;
2165 return SCIP_OKAY;
2166 }
2167 }
2168
2169 return SCIP_OKAY;
2170}
2171
2172static
2174 SCIP* scip, /**< original SCIP data structure */
2175 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
2176 int* cover, /**< array with indices of the variables in the computed cover */
2177 int coversize, /**< size of the cover */
2178 SCIP_Real* fixingvals, /**< fixing values for the variables in the cover */
2179 int* bdlen, /**< current length of bound disjunction along the probing path */
2180 SCIP_VAR** bdvars, /**< array of variables in bound disjunction */
2181 SCIP_BOUNDTYPE* bdtypes, /**< array of bound types in bound disjunction */
2182 SCIP_Real* bdbounds, /**< array of bounds in bound disjunction */
2183 SCIP_Real* oldbounds, /**< array of bounds before fixing */
2184 int* nfixedints, /**< pointer to store number of fixed integer variables */
2185 int* nfixedconts, /**< pointer to store number of fixed continuous variables */
2186 int* lastfailed, /**< position in cover array of the variable the fixing of which yielded
2187 * infeasibility */
2188 SCIP_Bool* infeas /**< pointer to store whether fix-and-propagate led to an infeasibility */
2189 )
2190{
2191 SCIP_VAR** vars; /* original problem's variables */
2192
2193 int i;
2194 SCIP_Bool lpsolved;
2195
2196 /* start probing in original problem */
2199
2200 /* initialize data */
2201 *nfixedints = 0;
2202 *nfixedconts = 0;
2203 *bdlen = 0;
2205
2206 /* round-fix-propagate-analyze-backtrack for each variable in the cover
2207 * TODO doing a fix-and-propagate for one variable at a time can be very expensive for large covers
2208 * (try, e.g., junkturn with maxcoversizevars=1)
2209 * consider splitting the cover into at most, say, 100 batches, and fix a complete batch before propagating
2210 */
2211 for( i = 0; i < coversize && !(*infeas); i++ )
2212 {
2213 SCIP_Real* boundalts;
2214 SCIP_Real* usedvals;
2215 SCIP_Real val;
2216 int nbacktracks;
2217 int nboundalts;
2218 int nfailedvals;
2219 int nusedvals;
2220 int probingdepth;
2221 int idx;
2222
2223 /* get probindex of next variable in the cover */
2224 idx = cover[i];
2225
2226 /* nothing to do if the variable was already fixed, e.g., by propagation */
2228 {
2230 continue;
2231 }
2232
2233 /* we will store the fixing values already used to avoid try the same value twice */
2234 SCIP_CALL( SCIPallocBufferArray(scip, &usedvals, heurdata->maxbacktracks+1) );
2235 nusedvals = 0;
2236
2237 /* backtracking loop */
2238 *infeas = TRUE;
2239 nfailedvals = 0;
2240 nboundalts = 0;
2241 boundalts = NULL;
2242 val = 0.0;
2243 for( nbacktracks = 0; nbacktracks <= heurdata->maxbacktracks+nfailedvals && *infeas; nbacktracks++ )
2244 {
2245 SCIP_Real oldlb;
2246 SCIP_Real oldub;
2247 SCIP_Bool usedbefore;
2248 int j;
2249
2251
2252 /* get fixing value */
2253 if( nbacktracks < heurdata->nfixingalts )
2254 {
2255 SCIP_Bool success;
2256
2257 /* if the lp relaxation is not solved, we do not even try to retrieve the lp solution value;
2258 * if the NLP relaxation is not constructed, we do not even try to retrieve the NLP solution value;
2259 * if there is no feasible solution yet, we do not even try to obtain the value in the incumbent */
2260 success = FALSE;
2261 if( (heurdata->fixingalts[nbacktracks] != 'l' || lpsolved)
2262 && (heurdata->fixingalts[nbacktracks] != 'n' || !heurdata->nlpfailed)
2263 && (heurdata->fixingalts[nbacktracks] != 'i' || SCIPgetBestSol(scip) != NULL) )
2264 {
2265 SCIP_CALL( getFixingValue(scip, heurdata, vars[idx], &val, heurdata->fixingalts[nbacktracks], &success, *bdlen, bdvars, bdtypes, oldbounds) );
2266 }
2267
2268 if( !success )
2269 {
2270 SCIPdebugMsg(scip, "retrieving fixing value '%c' for variable <%s> failed, trying next in the list\n",
2271 heurdata->fixingalts[nbacktracks], SCIPvarGetName(vars[idx]));
2272 nfailedvals++;
2273 continue;
2274 }
2275
2276 /* for the first (successfully retrieved) fixing value, compute (at most 4) bound dependent
2277 * alternative fixing values */
2278 if( boundalts == NULL )
2279 {
2281 nboundalts = 0;
2283 assert(nboundalts >= 0);
2284 assert(nboundalts <= 4);
2285 }
2286 }
2287 /* get alternative fixing value */
2288 else if( boundalts != NULL && nbacktracks < heurdata->nfixingalts+nboundalts )
2289 {
2290 assert(nbacktracks-heurdata->nfixingalts >= 0);
2291 val = boundalts[nbacktracks-heurdata->nfixingalts];
2292 }
2293 else
2294 break;
2295
2296 /* round fixing value */
2297 if( SCIPvarIsIntegral(vars[idx]) && !SCIPisIntegral(scip, val) )
2298 {
2299 SCIP_CALL( roundFixingValue(scip, &val, vars[idx], heurdata->locksrounding) );
2300 assert(SCIPisIntegral(scip, val));
2301 }
2302
2303 /* move value into the domain, since it may be outside due to numerical issues or previous propagation */
2306 val = MIN(val, oldub);
2307 val = MAX(val, oldlb);
2308
2310
2311 /* check if this fixing value was already used */
2312 usedbefore = FALSE;
2313 for( j = nusedvals-1; j >= 0 && !usedbefore; j-- )
2315
2316 if( usedbefore )
2317 {
2318 nfailedvals++;
2319 continue;
2320 }
2321
2322 /* store fixing value */
2323 assert(nusedvals < heurdata->maxbacktracks);
2324 usedvals[nusedvals] = val;
2325 nusedvals++;
2326
2327 /* fix-propagate-analyze */
2329
2330 /* if infeasible, backtrack and try alternative fixing value */
2331 if( *infeas )
2332 {
2333 SCIPdebugMsg(scip, " --> cutoff detected - backtracking\n");
2335 }
2336 }
2337
2338 /* free array of alternative backtracking values */
2339 if( boundalts != NULL)
2342
2343 /* backtracking loop unsuccessful */
2344 if( *infeas )
2345 {
2346 SCIPdebugMsg(scip, "no feasible fixing value found for variable <%s> in fixing order\n",
2347 SCIPvarGetName(vars[idx]));
2348 break;
2349 }
2350 /* fixing successful */
2351 else
2352 {
2353 /* store successful fixing value */
2354 fixingvals[i] = val;
2355
2356 /* statistics */
2358 (*nfixedconts)++;
2359 else
2360 (*nfixedints)++;
2361 }
2362 }
2363 assert(*infeas || i == coversize);
2364 assert(!(*infeas) || i < coversize);
2365
2366 /* end of dive */
2368
2369 *lastfailed = i;
2370
2371 return SCIP_OKAY;
2372}
2373
2374/** main procedure of the undercover heuristic */
2375static
2377 SCIP* scip, /**< original SCIP data structure */
2378 SCIP_HEUR* heur, /**< heuristic data structure */
2379 SCIP_RESULT* result, /**< result data structure */
2380 SCIP_Real timelimit, /**< time limit */
2381 SCIP_Real memorylimit, /**< memory limit */
2382 SCIP_Longint nstallnodes /**< number of stalling nodes for the subproblem */
2383 )
2384{
2385 SCIP_HEURDATA* heurdata; /* heuristic data */
2386 SCIP_VAR** vars; /* original problem's variables */
2387 SCIP_CLOCK* clock; /* clock for updating time limit */
2388
2389 SCIP* coveringscip; /* SCIP data structure for covering problem */
2390 SCIP_VAR** coveringvars; /* covering variables */
2391 SCIP_Real* fixingvals; /* array for storing fixing values used */
2392 int* cover; /* array to store problem indices of variables in the computed cover */
2393
2394 SCIP_VAR** bdvars; /* array of variables in bound disjunction along the probing path */
2395 SCIP_BOUNDTYPE* bdtypes; /* array of bound types in bound disjunction along the probing path */
2396 SCIP_Real* bdbounds; /* array of bounds in bound disjunction along the probing path */
2397 SCIP_Real* oldbounds; /* array of bounds before fixing along the probing path */
2398
2399 SCIP_Real maxcoversize;
2400
2401 int coversize;
2402 int nvars;
2403 int ncovers;
2404 int nunfixeds;
2405 int nnlconss;
2406 int i;
2407
2408 SCIP_Bool success;
2409 SCIP_Bool reusecover;
2410
2411 assert(scip != NULL);
2412 assert(heur != NULL);
2413 assert(result != NULL);
2415
2416 /* create and start timing */
2419
2420 /* initialize */
2421 fixingvals = NULL;
2422 cover = NULL;
2423 bdvars = NULL;
2424 bdtypes = NULL;
2425 bdbounds = NULL;
2426 oldbounds = NULL;
2427 coversize = 0;
2428
2429 /* get heuristic data */
2430 heurdata = SCIPheurGetData(heur);
2431 assert(heurdata != NULL);
2432
2433 /* NLP relaxation has not been solved yet (only solve once, not again for each cover or dive, because it is expensive) */
2434 heurdata->nlpsolved = FALSE;
2435
2436 /* if solving the NLP relaxation has failed too often in previous runs, or NLP and NLP solver is not available, we do
2437 * not even try
2438 */
2439 heurdata->nlpfailed = heurdata->nnlpfails >= MAXNLPFAILS || !SCIPisNLPConstructed(scip) || SCIPgetNNlpis(scip) == 0;
2440
2441 /* get variable data of original problem */
2443
2444 /* get number of nonlinear constraints */
2445 nnlconss = 0;
2446 for( i = 0; i < heurdata->nnlconshdlrs; ++i )
2448 assert(nnlconss >= 0);
2450
2451 /* run only if problem is sufficiently nonlinear */
2452 if( nnlconss < (SCIP_Real) SCIPgetNConss(scip) * heurdata->mincoveredrel || nnlconss < heurdata->mincoveredabs )
2453 {
2454 SCIPdebugMsg(scip, "too few nonlinear constraints present, not running\n");
2455
2456 /* free clock */
2458
2459 return SCIP_OKAY;
2460 }
2461
2462 /* calculate upper bound for cover size */
2463 if( heurdata->maxcoversizevars < 1.0 )
2464 {
2465 maxcoversize = 0.0;
2466 for( i = 0; i < nvars; ++i )
2468 maxcoversize += 1.0;
2469 maxcoversize *= heurdata->maxcoversizevars;
2470 }
2471 else
2472 {
2473 /* if maxcoversizevars == 1.0, then there is no limit derived from number of variables */
2475 }
2476 if( heurdata->maxcoversizeconss < SCIP_REAL_MAX )
2477 {
2478 SCIP_Real maxcoversizeconss;
2479 maxcoversizeconss = heurdata->maxcoversizeconss * nnlconss / ((SCIP_Real) SCIPgetNConss(scip));
2480 maxcoversize = MIN(maxcoversize, maxcoversizeconss);
2481 }
2482
2483 /* create covering problem */
2484 success = FALSE;
2489 heurdata->coverbd, heurdata->coveringobj, &success) );
2490
2491 if( !success )
2492 {
2493 SCIPdebugMsg(scip, "creating covering problem failed, terminating\n");
2494 goto TERMINATE;
2495 }
2496 else
2497 {
2498 SCIPdebugMsg(scip, "covering problem created successfully\n");
2499 }
2500
2501 /* count number of unfixed covering variables */
2502 nunfixeds = 0;
2503 for( i = nvars-1; i >= 0; i-- )
2504 {
2506 nunfixeds++;
2507 }
2508
2509 /* update time limit */
2510 SCIP_CALL( updateTimelimit(scip, clock, &timelimit) );
2511
2512 if( timelimit <= MINTIMELEFT )
2513 {
2514 SCIPdebugMsg(scip, "time limit hit, terminating\n");
2515 goto TERMINATE;
2516 }
2517
2518 /* update memory left */
2519 memorylimit -= SCIPgetMemUsed(coveringscip)/1048576.0;
2520 memorylimit -= SCIPgetMemExternEstim(coveringscip)/1048576.0;
2521
2522 /* allocate memory for storing bound disjunction information along probing path */
2527
2528 /* initialize data for recovering loop */
2531 ncovers = 0;
2532 success = FALSE;
2533 reusecover = FALSE;
2534
2535 heurdata->nfixingalts = (int) strlen(heurdata->fixingalts);
2536 assert(heurdata->nfixingalts >= 1);
2537
2538 /* recovering loop */
2539 while( (ncovers <= heurdata->maxrecovers || reusecover) && !success )
2540 {
2541 int lastfailed;
2542 int ndives;
2543 int nfixedints;
2544 int nfixedconts;
2545 int bdlen; /* current length of bound disjunction along the probing path */
2546
2547 SCIP_Bool conflictcreated;
2548
2549 SCIPdebugMsg(scip, "solving covering problem\n\n");
2550 success = FALSE;
2551 bdlen = 0;
2553
2554 /* solve covering problem */
2555 if( !reusecover )
2556 {
2558 timelimit, memorylimit + (SCIPgetMemExternEstim(coveringscip)+SCIPgetMemUsed(coveringscip))/1048576.0, maxcoversize, &success) );
2559
2561 if( ncovers == 0 && success )
2562 SCIPstatisticPrintf("UCstats coversize abs: %6d rel: %9.6f\n", coversize, 100.0*coversize /(SCIP_Real)nvars);
2563 );
2564
2565 assert(coversize >= 0);
2567 ncovers++;
2568
2569 /* free transformed covering problem immediately */
2571
2572 /* terminate if no feasible cover was found */
2573 if( !success )
2574 {
2575 SCIPdebugMsg(scip, "no feasible cover found in covering problem %d, terminating\n", ncovers);
2576 goto TERMINATE;
2577 }
2578
2579 /* terminate, if cover is empty or too large */
2580 if( coversize == 0 || coversize > maxcoversize )
2581 {
2582 SCIPdebugMsg(scip, "terminating due to coversize=%d\n", coversize);
2583 goto TERMINATE;
2584 }
2585
2586 /* terminate, if cover too large for the ratio of nonlinear constraints */
2587 if( heurdata->maxcoversizeconss < SCIP_REAL_MAX && coversize > heurdata->maxcoversizeconss * nnlconss / (SCIP_Real) SCIPgetNConss(scip) )
2588 {
2589 SCIPdebugMsg(scip, "terminating due to coversize=%d\n", coversize);
2590 goto TERMINATE;
2591 }
2592 }
2593
2594 /* data setup */
2595 ndives = 0;
2596 nfixedints = 0;
2597 nfixedconts = 0;
2598 success = FALSE;
2599 lastfailed = reusecover ? MAX(1, coversize-1) : coversize;
2600
2601 /* round-fix-propagate-analyze-backtrack-reorder loop */
2602 while( ndives <= heurdata->maxreorders && !success )
2603 {
2604 SCIP_Bool reordered;
2605 SCIP_Bool infeas;
2606
2607 /* compute fixing order */
2609 reordered = reordered || ndives == 0;
2610 SCIPdebugMsg(scip, "%sordering variables in cover %s\n", ndives == 0 ? "" : "re", reordered ? "" : "failed");
2611
2612 /* stop if order has not changed */
2613 if( !reordered )
2614 break;
2615
2616 infeas = FALSE;
2619 ndives++;
2620 success = !infeas;
2621 }
2622
2623 /* update time limit */
2624 SCIPdebugMsg(scip, "%d dive%s of fix-and-propagate for cover %d took %.1f seconds\n", ndives, ndives > 1 ? "s" : "", ncovers, SCIPgetClockTime(scip, clock));
2625 SCIP_CALL( updateTimelimit(scip, clock, &timelimit) );
2626
2627 if( timelimit <= MINTIMELEFT )
2628 {
2629 SCIPdebugMsg(scip, "time limit hit, terminating\n");
2630 goto TERMINATE;
2631 }
2632
2633 /* no feasible fixing could be found for the current cover */
2634 if( !success )
2635 {
2636 SCIPdebugMsg(scip, "no feasible fixing values found for cover %d\n", ncovers);
2637 }
2638 else
2639 {
2640 SCIP_SOL* sol;
2641 SCIP_Longint nsubnodes;
2642 SCIP_Bool validsolved;
2643
2644 SCIPdebugMsg(scip, "heuristic successfully fixed %d variables (%d integral, %d continuous) during probing\n",
2645 nfixedints+nfixedconts, nfixedints, nfixedconts); /*lint !e771*/
2646
2647 /* solve sub-CIP and pass feasible solutions to original problem */
2648 success = FALSE;
2650 sol = NULL;
2651 nsubnodes = 0;
2652
2654 timelimit, memorylimit, heurdata->maxnodes, nstallnodes, &validsolved, &sol, &nsubnodes) );
2655
2656 /* update number of sub-CIP nodes used by heuristic so far */
2657 heurdata->nusednodes += nsubnodes;
2658
2659 /* if the subproblem was constructed from a valid copy and solved, try to forbid the assignment of fixing
2660 * values to variables in the cover
2661 */
2662 if( validsolved )
2663 {
2664 SCIP_Real maxvarsfac;
2665 SCIP_Bool useconf;
2666 int minmaxvars;
2667
2668 SCIP_CALL( SCIPgetIntParam(scip, "conflict/minmaxvars", &minmaxvars) );
2669 SCIP_CALL( SCIPgetRealParam(scip, "conflict/maxvarsfac", &maxvarsfac) );
2670
2671 useconf = bdlen > 0 && (bdlen <= minmaxvars || bdlen < maxvarsfac*nvars);
2672
2673 if( useconf )
2674 {
2675 /* even if we had reset the global bounds at start of probing, the constraint might be only locally valid due to local constraints/cuts */
2678 }
2679
2680 SCIPdebugMsg(scip, "subproblem solved (%s), forbidding assignment in original problem %s, %sconflict length=%d\n",
2681 sol == NULL ? "infeasible" : "optimal",
2682 success ? "successful" : "failed", useconf ? "" : "skipped due to ", bdlen);
2683 }
2684
2685 /* heuristic succeeded */
2686 success = (sol != NULL);
2687 if( success )
2688 {
2690 success = TRUE;
2691
2692 /* call NLP local search heuristic unless it has failed too often */
2693 if( heurdata->postnlp && heurdata->npostnlpfails < MAXPOSTNLPFAILS )
2694 {
2695 if( nfixedconts == 0 && validsolved )
2696 {
2697 SCIPdebugMsg(scip, "subproblem solved to optimality while all covering variables are integral, hence skipping NLP local search\n");
2698 }
2699 else if( heurdata->nlpheur == NULL )
2700 {
2701 SCIPdebugMsg(scip, "NLP heuristic not found, skipping NLP local search\n");
2702 }
2703 else
2704 {
2706
2708 SCIPdebugMsg(scip, "NLP local search %s\n", nlpresult == SCIP_FOUNDSOL ? "successful" : "failed");
2709
2710 if( nlpresult == SCIP_FOUNDSOL )
2711 heurdata->npostnlpfails = 0;
2712 else
2713 heurdata->npostnlpfails++;
2714 }
2715 }
2716
2717 /* free solution */
2719 }
2720 }
2721
2722 /* heuristic failed but we have another recovering try, hence we forbid the current cover in the covering problem */
2723 if( !success && ncovers <= heurdata->maxrecovers )
2724 {
2725 SCIP_Bool infeas;
2726 int diversification;
2727
2728 /* compute minimal number of unfixed covering variables (in the cover) which have to change their value */
2729 diversification = (int) SCIPfeasCeil(scip, (heurdata->recoverdiv) * (SCIP_Real) nunfixeds);
2731
2732 /* forbid unsuccessful cover globally in covering problem */
2734
2735 if( infeas )
2736 {
2737 SCIPdebugMsg(scip, "recovering problem infeasible (diversification=%d), terminating\n", diversification);
2738 goto TERMINATE;
2739 }
2740 else if( !success )
2741 {
2742 SCIPdebugMsg(scip, "failed to forbid current cover in the covering problem, terminating\n");
2743 goto TERMINATE;
2744 }
2745 else
2746 {
2747 SCIPdebugMsg(scip, "added constraint to the covering problem in order to forbid current cover\n");
2748 success = FALSE;
2749 }
2750 }
2751
2752 /* try to re-use the same cover at most once */
2753 if( heurdata->reusecover && !reusecover && conflictcreated )
2754 reusecover = TRUE;
2755 else
2756 reusecover = FALSE;
2757 }
2758
2759 TERMINATE:
2760 if( *result != SCIP_FOUNDSOL && *result != SCIP_DELAYED )
2761 {
2762 SCIPdebugMsg(scip, "heuristic terminating unsuccessfully\n");
2763 }
2764
2765 /* we must remain in NLP diving mode until here to be able to retrieve NLP solution values easily */
2766 /* assert((SCIPisNLPConstructed(scip) == FALSE && heurdata->nlpsolved == FALSE) ||
2767 * (SCIPisNLPConstructed(scip) == TRUE && heurdata->nlpsolved == SCIPnlpIsDiving(SCIPgetNLP(scip))));
2768 */
2769 if( heurdata->nlpsolved )
2770 {
2772 }
2773
2774 /* free arrays for storing the cover */
2777
2778 /* free arrays for storing bound disjunction information along probing path */
2783
2784 /* free covering problem */
2785 for( i = nvars-1; i >= 0; i-- )
2786 {
2787 if( coveringvars[i] == NULL )
2788 continue;
2790 }
2793
2794 /* free clock */
2796
2797 return SCIP_OKAY;
2798}
2799
2800
2801/*
2802 * Callback methods of primal heuristic
2803 */
2804
2805/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
2806static
2808{ /*lint --e{715}*/
2809 assert(scip != NULL);
2810 assert(heur != NULL);
2811 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2812
2813 /* call inclusion method of primal heuristic */
2815
2816 return SCIP_OKAY;
2817}
2818
2819/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
2820static
2822{ /*lint --e{715}*/
2824
2825 assert(scip != NULL);
2826 assert(heur != NULL);
2827
2828 /* get heuristic data */
2829 heurdata = SCIPheurGetData(heur);
2830 assert(heurdata != NULL);
2831
2832 /* free heuristic data */
2834 SCIPheurSetData(heur, NULL);
2835
2836 return SCIP_OKAY;
2837}
2838
2839/** initialization method of primal heuristic (called after problem was transformed) */
2840static
2842{ /*lint --e{715}*/
2844
2845 assert(heur != NULL);
2846 assert(scip != NULL);
2847
2848 /* get heuristic's data */
2849 heurdata = SCIPheurGetData(heur);
2850 assert(heurdata != NULL);
2851
2852 /* create random number generator */
2853 SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen,
2855
2856 return SCIP_OKAY;
2857}
2858
2859/** deinitialization method of primal heuristic */
2860static
2862{ /*lint --e{715}*/
2864
2865 assert(heur != NULL);
2866 assert(scip != NULL);
2867
2868 /* get heuristic's data */
2869 heurdata = SCIPheurGetData(heur);
2870 assert(heurdata != NULL);
2871
2872 /* free random number generator */
2873 SCIPfreeRandom(scip, &heurdata->randnumgen);
2874
2875 return SCIP_OKAY;
2876}
2877
2878/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
2879static
2881{ /*lint --e{715}*/
2883 int h;
2884
2885 assert(heur != NULL);
2886 assert(scip != NULL);
2887
2888 /* get heuristic's data */
2889 heurdata = SCIPheurGetData(heur);
2890 assert(heurdata != NULL);
2891
2892 /* initialize counters to zero */
2893 heurdata->nusednodes = 0;
2894 heurdata->npostnlpfails = 0;
2895 heurdata->nnlpfails = 0;
2896
2897 /* if the heuristic is called at the root node, we may want to be called directly after the initial root LP solve */
2898 if( heurdata->beforecuts && SCIPheurGetFreqofs(heur) == 0 )
2900
2901 /* find nonlinear constraint handlers */
2902 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &heurdata->nlconshdlrs, 4) );/*lint !e506*/
2903 h = 0;
2904
2905 heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "and");
2906 if( heurdata->nlconshdlrs[h] != NULL )
2907 h++;
2908
2909 heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "nonlinear");
2910 if( heurdata->nlconshdlrs[h] != NULL )
2911 h++;
2912
2913 if( heurdata->coverbd )
2914 {
2915 heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "bounddisjunction");
2916 if( heurdata->nlconshdlrs[h] != NULL )
2917 h++;
2918 }
2919
2920 heurdata->nlconshdlrs[h] = SCIPfindConshdlr(scip, "indicator");
2921 if( heurdata->nlconshdlrs[h] != NULL )
2922 h++;
2923
2924 heurdata->nnlconshdlrs = h;
2925 assert( heurdata->nnlconshdlrs <= 4 );
2926
2927 /* find NLP local search heuristic */
2928 heurdata->nlpheur = SCIPfindHeur(scip, "subnlp");
2929
2930 return SCIP_OKAY;
2931}
2932
2933/** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
2934static
2936{
2938
2939 assert(heur != NULL);
2940 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
2941
2942 /* get heuristic's data */
2943 heurdata = SCIPheurGetData(heur);
2944 assert(heurdata != NULL);
2945
2946 /* free array of nonlinear constraint handlers */
2947 SCIPfreeBlockMemoryArray(scip, &heurdata->nlconshdlrs, 4);
2948
2949 /* reset timing, if it was changed temporary (at the root node) */
2951
2952 return SCIP_OKAY;
2953}
2954
2955/** execution method of primal heuristic */
2956static
2958{ /*lint --e{715}*/
2959 SCIP_HEURDATA* heurdata; /* heuristic data */
2960 SCIP_Real timelimit; /* time limit for the subproblem */
2961 SCIP_Real memorylimit; /* memory limit for the subproblem */
2962 SCIP_Longint nstallnodes; /* number of stalling nodes for the subproblem */
2963 SCIP_Bool run;
2964 SCIP_Bool avoidmemout;
2965
2966 int h;
2967
2968 assert(heur != NULL);
2969 assert(scip != NULL);
2970 assert(result != NULL);
2971
2973
2974 /* do not call heuristic of node was already detected to be infeasible */
2975 if( nodeinfeasible )
2976 return SCIP_OKAY;
2977
2978 /* get heuristic's data */
2979 heurdata = SCIPheurGetData(heur);
2980 assert(heurdata != NULL);
2981
2982 /* only call heuristic once at the root */
2983 if( SCIPgetDepth(scip) == 0 && SCIPheurGetNCalls(heur) > 0 )
2984 return SCIP_OKAY;
2985
2986 /* if we want to use NLP fixing values exclusively and no NLP solver is available, we cannot run */
2987 if( strcmp(heurdata->fixingalts, "n") == 0 && SCIPgetNNlpis(scip) == 0 )
2988 {
2989 SCIPdebugMsg(scip, "skipping undercover heuristic: want to use NLP fixing values exclusively, but no NLP solver available\n");
2990 return SCIP_OKAY;
2991 }
2992
2993 /* calculate stallnode limit */
2995
2996 /* reward heuristic if it succeeded often */
2997 nstallnodes = (SCIP_Longint)(nstallnodes * 3.0 * (SCIPheurGetNBestSolsFound(heur) + 1.0)/(SCIPheurGetNCalls(heur) + 1.0));
2998 nstallnodes -= SUBMIPSETUPCOSTS * SCIPheurGetNCalls(heur); /* account for the setup costs of the sub-CIP */
2999 nstallnodes += heurdata->nodesofs;
3000
3001 /* determine the node limit for the current process */
3002 nstallnodes -= heurdata->nusednodes;
3003 nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
3005
3006 /* only call heuristics if we have enough nodes left to call sub-CIP solving */
3007 if( nstallnodes < heurdata->minnodes )
3008 {
3009 SCIPdebugMsg(scip, "skipping undercover heuristic: nstallnodes=%" SCIP_LONGINT_FORMAT ", minnodes=%" SCIP_LONGINT_FORMAT "\n", nstallnodes, heurdata->minnodes);
3010 return SCIP_OKAY;
3011 }
3012
3013 /* only call heuristics if we have enough time left */
3014 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
3015 if( !SCIPisInfinity(scip, timelimit) )
3016 timelimit -= SCIPgetSolvingTime(scip);
3017 if( timelimit <= 2*MINTIMELEFT )
3018 {
3019 SCIPdebugMsg(scip, "skipping undercover heuristic: time left=%g\n", timelimit);
3020 return SCIP_OKAY;
3021 }
3022
3023 /* only call heuristics if we have enough memory left */
3024 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
3025 SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) );
3026 if( !SCIPisInfinity(scip, memorylimit) )
3027 {
3028 memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
3029 memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
3030 }
3031
3032 if( avoidmemout && memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
3033 {
3034 SCIPdebugMsg(scip, "skipping undercover heuristic: too little memory\n");
3035 return SCIP_OKAY;
3036 }
3037
3038 /* only call heuristic if nonlinear constraints are present */
3039 run = FALSE;
3040 for( h = heurdata->nnlconshdlrs-1; h >= 0 && !run; h-- )
3041 {
3042 run = (SCIPconshdlrGetNActiveConss(heurdata->nlconshdlrs[h]) > 0);
3043 }
3044
3045 /* go through all nlrows and check for general nonlinearities */
3047 {
3048 SCIP_NLROW** nlrows;
3049 int nnlrows;
3050 int i;
3051
3052 /* get nlrows */
3053 nnlrows = SCIPgetNNLPNlRows(scip);
3054 nlrows = SCIPgetNLPNlRows(scip);
3055
3056 /* check for a nonlinear nlrow; start from the end since we expect the linear nlrows at the end */
3057 for( i = nnlrows-1; i >= 0 && !run; i-- )
3058 {
3059 assert(nlrows[i] != NULL);
3060 run = SCIPnlrowGetExpr(nlrows[i]) != NULL;
3061 }
3062 }
3063
3064 if( !run )
3065 {
3066 SCIPdebugMsg(scip, "skipping undercover heuristic: no nonlinear constraints found\n");
3067 return SCIP_OKAY;
3068 }
3069
3070 /* only call heuristics if solving has not stopped yet */
3071 if( SCIPisStopped(scip) )
3072 return SCIP_OKAY;
3073
3074 /* reset timing, if it was changed temporary (at the root node) */
3075 if( heurtiming != HEUR_TIMING )
3077
3078 /* call heuristic */
3080 SCIPdebugMsg(scip, "calling undercover heuristic for <%s> at depth %d\n", SCIPgetProbName(scip), SCIPgetDepth(scip));
3081
3082 SCIP_CALL( SCIPapplyUndercover(scip, heur, result, timelimit, memorylimit, nstallnodes) );
3083
3084 return SCIP_OKAY;
3085}
3086
3087
3088/*
3089 * primal heuristic specific interface methods
3090 */
3091
3092/** creates the undercover primal heuristic and includes it in SCIP */
3094 SCIP* scip /**< SCIP data structure */
3095 )
3096{
3098 SCIP_HEUR* heur;
3099
3100 /* create undercover primal heuristic data */
3102
3103 /* always use local bounds */
3104 heurdata->globalbounds = FALSE;
3105
3106 /* include primal heuristic */
3110
3111 assert(heur != NULL);
3112
3113 /* set non-NULL pointers to callback methods */
3120
3121 /* add string parameters */
3122 heurdata->fixingalts = NULL;
3123 SCIP_CALL( SCIPaddStringParam(scip, "heuristics/" HEUR_NAME "/fixingalts",
3124 "prioritized sequence of fixing values used ('l'p relaxation, 'n'lp relaxation, 'i'ncumbent solution)",
3125 &heurdata->fixingalts, FALSE, DEFAULT_FIXINGALTS, NULL, NULL) );
3126
3127 /* add longint parameters */
3128 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
3129 "maximum number of nodes to regard in the subproblem",
3131
3132 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
3133 "minimum number of nodes required to start the subproblem",
3135
3136 SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/nodesofs",
3137 "number of nodes added to the contingent of the total nodes",
3139
3140 /* add real parameters */
3141 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/conflictweight",
3142 "weight for conflict score in fixing order",
3144
3145 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/cutoffweight",
3146 "weight for cutoff score in fixing order",
3147 &heurdata->cutoffweight, TRUE, DEFAULT_CUTOFFWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3148
3149 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/inferenceweight",
3150 "weight for inference score in fixing order",
3152
3153 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxcoversizevars",
3154 "maximum coversize (as fraction of total number of variables)",
3155 &heurdata->maxcoversizevars, TRUE, DEFAULT_MAXCOVERSIZEVARS, 0.0, 1.0, NULL, NULL) );
3156
3157 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxcoversizeconss",
3158 "maximum coversize (as ratio to the percentage of non-affected constraints)",
3159 &heurdata->maxcoversizeconss, TRUE, DEFAULT_MAXCOVERSIZECONSS, 0.0, SCIP_REAL_MAX, NULL, NULL) );
3160
3161 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/mincoveredrel",
3162 "minimum percentage of nonlinear constraints in the original problem",
3163 &heurdata->mincoveredrel, TRUE, DEFAULT_MINCOVEREDREL, 0.0, 1.0, NULL, NULL) );
3164
3165 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/minimprove",
3166 "factor by which the heuristic should at least improve the incumbent",
3167 &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, -1.0, 1.0, NULL, NULL) );
3168
3169 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodesquot",
3170 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
3171 &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
3172
3173 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/recoverdiv",
3174 "fraction of covering variables in the last cover which need to change their value when recovering",
3175 &heurdata->recoverdiv, TRUE, DEFAULT_RECOVERDIV, 0.0, 1.0, NULL, NULL) );
3176
3177 /* add int parameters */
3178 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/mincoveredabs",
3179 "minimum number of nonlinear constraints in the original problem",
3180 &heurdata->mincoveredabs, TRUE, DEFAULT_MINCOVEREDABS, 0, INT_MAX, NULL, NULL) );
3181
3182 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxbacktracks",
3183 "maximum number of backtracks in fix-and-propagate",
3184 &heurdata->maxbacktracks, TRUE, DEFAULT_MAXBACKTRACKS, 0, INT_MAX, NULL, NULL) );
3185
3186 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxrecovers",
3187 "maximum number of recoverings",
3188 &heurdata->maxrecovers, TRUE, DEFAULT_MAXRECOVERS, 0, INT_MAX, NULL, NULL) );
3189
3190 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxreorders",
3191 "maximum number of reorderings of the fixing order",
3192 &heurdata->maxreorders, TRUE, DEFAULT_MAXREORDERS, 0, INT_MAX, NULL, NULL) );
3193
3194 /* add char parameters */
3195 SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/coveringobj",
3196 "objective function of the covering problem (influenced nonlinear 'c'onstraints/'t'erms, 'd'omain size, 'l'ocks, 'm'in of up/down locks, 'u'nit penalties)",
3197 &heurdata->coveringobj, TRUE, DEFAULT_COVERINGOBJ, COVERINGOBJS, NULL, NULL) );
3198
3199 SCIP_CALL( SCIPaddCharParam(scip, "heuristics/" HEUR_NAME "/fixingorder",
3200 "order in which variables should be fixed (increasing 'C'onflict score, decreasing 'c'onflict score, increasing 'V'ariable index, decreasing 'v'ariable index",
3201 &heurdata->fixingorder, TRUE, DEFAULT_FIXINGORDER, FIXINGORDERS, NULL, NULL) );
3202
3203 /* add bool parameters */
3204 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/beforecuts",
3205 "should the heuristic be called at root node before cut separation?",
3206 &heurdata->beforecuts, TRUE, DEFAULT_BEFORECUTS, NULL, NULL) );
3207
3208 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/fixintfirst",
3209 "should integer variables in the cover be fixed first?",
3210 &heurdata->fixintfirst, TRUE, DEFAULT_FIXINTFIRST, NULL, NULL) );
3211
3212 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/locksrounding",
3213 "shall LP values for integer vars be rounded according to locks?",
3214 &heurdata->locksrounding, TRUE, DEFAULT_LOCKSROUNDING, NULL, NULL) );
3215
3216 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlyconvexify",
3217 "should we only fix variables in order to obtain a convex problem?",
3218 &heurdata->onlyconvexify, FALSE, DEFAULT_ONLYCONVEXIFY, NULL, NULL) );
3219
3220 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/postnlp",
3221 "should the NLP heuristic be called to polish a feasible solution?",
3222 &heurdata->postnlp, FALSE, DEFAULT_POSTNLP, NULL, NULL) );
3223
3224 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/coverbd",
3225 "should bounddisjunction constraints be covered (or just copied)?",
3226 &heurdata->coverbd, TRUE, DEFAULT_COVERBD, NULL, NULL) );
3227
3228 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/copycuts",
3229 "should all active cuts from cutpool be copied to constraints in subproblem?",
3230 &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
3231
3232 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/reusecover",
3233 "shall the cover be reused if a conflict was added after an infeasible subproblem?",
3234 &heurdata->reusecover, TRUE, DEFAULT_REUSECOVER, NULL, NULL) );
3235
3236 return SCIP_OKAY;
3237}
3238
3239/** create and solve covering problem */
3240static
3242 SCIP* scip, /**< SCIP data structure */
3243 SCIP* coveringscip, /**< SCIP instance for covering problem */
3244 int* coversize, /**< buffer for the size of the computed cover */
3245 SCIP_VAR** cover, /**< pointer to store the variables (of the original SCIP) in the computed cover
3246 * (should be ready to hold SCIPgetNVars(scip) entries) */
3247 SCIP_Real timelimit, /**< time limit */
3248 SCIP_Real memorylimit, /**< memory limit */
3249 SCIP_Real objlimit, /**< objective limit: upper bound on coversize */
3250 SCIP_Bool globalbounds, /**< should global bounds on variables be used instead of local bounds at focus node? */
3251 SCIP_Bool onlyconvexify, /**< should we only fix/dom.red. variables creating nonconvexity? */
3252 SCIP_Bool coverbd, /**< should bounddisjunction constraints be covered (or just copied)? */
3253 char coveringobj, /**< objective function of the covering problem ('b'ranching status,
3254 * influenced nonlinear 'c'onstraints/'t'erms, 'd'omain size, 'l'ocks,
3255 * 'm'in of up/down locks, 'u'nit penalties, constraint 'v'iolation) */
3256 SCIP_Bool* success /**< feasible cover found? */
3257 )
3258{
3259 SCIP_VAR** coveringvars; /* covering variables */
3260 SCIP_VAR** vars; /* original variables */
3261 int* coverinds; /* indices of variables in the cover */
3262 int nvars; /* number of original variables */
3263 int i;
3264
3265 assert(scip != NULL);
3267
3269
3270 /* allocate memory for variables of the covering problem */
3274
3275 SCIP_CALL( createCoveringProblem(scip, coveringscip, coveringvars, globalbounds, onlyconvexify, coverbd, coveringobj, success) );
3276
3277 if( *success )
3278 {
3279 /* solve covering problem */
3280 SCIPdebugMsg(scip, "solving covering problem\n\n");
3281
3283 timelimit, memorylimit + (SCIPgetMemExternEstim(coveringscip)+SCIPgetMemUsed(coveringscip))/1048576.0, objlimit, success) );
3284
3285 if( *success )
3286 {
3287 assert(*coversize >= 0);
3288 assert(*coversize <= nvars);
3289
3290 /* return original variables in the cover */
3291 for( i = *coversize-1; i >= 0; i-- )
3292 {
3293 assert(coverinds[i] >= 0);
3294 assert(coverinds[i] < nvars);
3295 cover[i] = vars[coverinds[i]];
3296 }
3297 }
3298 }
3299 else
3300 {
3301 SCIPdebugMsg(scip, "failure: covering problem could not be created\n");
3302 }
3303
3304 /* free covering problem */
3305 for( i = nvars-1; i >= 0; i-- )
3306 {
3307 if( coveringvars[i] == NULL )
3308 continue;
3310 }
3313
3314 return SCIP_OKAY;
3315}
3316
3317/** computes a minimal set of covering variables */
3319 SCIP* scip, /**< SCIP data structure */
3320 int* coversize, /**< buffer for the size of the computed cover */
3321 SCIP_VAR** cover, /**< pointer to store the variables (of the original SCIP) in the computed cover
3322 * (should be ready to hold SCIPgetNVars(scip) entries) */
3323 SCIP_Real timelimit, /**< time limit */
3324 SCIP_Real memorylimit, /**< memory limit */
3325 SCIP_Real objlimit, /**< objective limit: upper bound on coversize */
3326 SCIP_Bool globalbounds, /**< should global bounds on variables be used instead of local bounds at focus node? */
3327 SCIP_Bool onlyconvexify, /**< should we only fix/dom.red. variables creating nonconvexity? */
3328 SCIP_Bool coverbd, /**< should bounddisjunction constraints be covered (or just copied)? */
3329 char coveringobj, /**< objective function of the covering problem ('b'ranching status,
3330 * influenced nonlinear 'c'onstraints/'t'erms, 'd'omain size, 'l'ocks,
3331 * 'm'in of up/down locks, 'u'nit penalties, constraint 'v'iolation) */
3332 SCIP_Bool* success /**< feasible cover found? */
3333 )
3334{
3335 SCIP* coveringscip; /* SCIP instance for covering problem */
3336 SCIP_RETCODE retcode;
3337
3338 assert(scip != NULL);
3339 assert(coversize != NULL);
3340 assert(success != NULL);
3341
3342 *success = FALSE;
3343
3344 /* create covering problem */
3346
3348 timelimit, memorylimit, objlimit,
3349 globalbounds, onlyconvexify, coverbd, coveringobj, success);
3350
3351 /* free the covering problem scip instance before reacting on potential errors */
3353
3354 SCIP_CALL( retcode );
3355
3356 return SCIP_OKAY;
3357}
SCIP_VAR * h
SCIP_VAR ** x
Constraint handler for AND constraints, .
constraint handler for bound disjunction constraints
constraint handler for indicator constraints
Constraint handler for linear constraints in their most general form, .
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
constraint handler for nonlinear constraints specified by algebraic expressions
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIP_MAXSTRLEN
Definition def.h:302
#define SCIP_Longint
Definition def.h:171
#define SCIP_MAXTREEDEPTH
Definition def.h:330
#define SCIP_REAL_MAX
Definition def.h:187
#define SCIP_Real
Definition def.h:186
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIP_REAL_MIN
Definition def.h:188
#define SCIP_LONGINT_MAX
Definition def.h:172
#define SCIP_CALL(x)
Definition def.h:388
SCIP_VAR * SCIPgetResultantAnd(SCIP *scip, SCIP_CONS *cons)
Definition cons_and.c:5175
SCIP_RETCODE SCIPcreateConsBounddisjunction(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_BOUNDTYPE *boundtypes, SCIP_Real *bounds, 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 SCIPgetNlRowNonlinear(SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow)
int SCIPgetNVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition cons_and.c:5126
int SCIPgetNVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetBinaryVarIndicator(SCIP_CONS *cons)
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_VAR ** SCIPgetVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition cons_and.c:5150
SCIP_RETCODE SCIPcreateConsLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, 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 SCIPcreateConsSetcover(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, 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_VAR ** SCIPgetVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
void SCIPsetSubscipDepth(SCIP *scip, int newdepth)
Definition scip_copy.c:2626
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
int SCIPgetSubscipDepth(SCIP *scip)
Definition scip_copy.c:2605
SCIP_RETCODE SCIPmergeVariableStatistics(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR **sourcevars, SCIP_VAR **targetvars, int nvars)
Definition scip_copy.c:1265
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 SCIPtranslateSubSol(SCIP *scip, SCIP *subscip, SCIP_SOL *subsol, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_SOL **newsol)
Definition scip_copy.c:1408
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition scip_prob.c:1668
const char * SCIPgetProbName(SCIP *scip)
Definition scip_prob.c:1067
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
Definition scip_prob.c:1422
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
int SCIPgetNConss(SCIP *scip)
Definition scip_prob.c:3042
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition scip_prob.c:1947
int SCIPgetNOrigVars(SCIP *scip)
Definition scip_prob.c:2432
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
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition misc.c:3058
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3211
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition misc.c:3024
SCIP_RETCODE SCIPaddConsLocal(SCIP *scip, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition scip_prob.c:3393
#define SCIPdebugMsg
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPapplyHeurSubNlp(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_SOL *refpoint, SCIP_SOL *resultsol)
SCIP_RETCODE SCIPcomputeCoverUndercover(SCIP *scip, int *coversize, SCIP_VAR **cover, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Real objlimit, SCIP_Bool globalbounds, SCIP_Bool onlyconvexify, SCIP_Bool coverbd, char coveringobj, SCIP_Bool *success)
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition scip_param.c:250
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:111
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition scip_param.c:219
SCIP_RETCODE SCIPaddCharParam(SCIP *scip, const char *name, const char *desc, char *valueptr, SCIP_Bool isadvanced, char defaultvalue, const char *allowedvalues, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:167
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
SCIP_RETCODE SCIPaddStringParam(SCIP *scip, const char *name, const char *desc, char **valueptr, SCIP_Bool isadvanced, const char *defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:194
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition scip_param.c:545
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:139
SCIP_RETCODE SCIPsetHeuristics(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition scip_param.c:906
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition scip_param.c:487
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition scip_param.c:883
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition scip_param.c:307
SCIP_RETCODE SCIPunfixParam(SCIP *scip, const char *name)
Definition scip_param.c:385
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition scip_param.c:932
SCIP_RETCODE SCIPsetEmphasis(SCIP *scip, SCIP_PARAMEMPHASIS paramemphasis, SCIP_Bool quiet)
Definition scip_param.c:861
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:57
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition scip_param.c:269
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition scip_param.c:429
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition scip_param.c:603
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition scip_param.c:958
SCIP_RETCODE SCIPincludeHeurUndercover(SCIP *scip)
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:886
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4629
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4552
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition cons.c:8088
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1119
void SCIPexprGetQuadraticBilinTerm(SCIP_EXPR *expr, int termidx, SCIP_EXPR **expr1, SCIP_EXPR **expr2, SCIP_Real *coef, int *pos2, SCIP_EXPR **prodexpr)
Definition expr.c:4145
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
Definition expriter.c:968
SCIP_Bool SCIPexprAreQuadraticExprsVariables(SCIP_EXPR *expr)
Definition expr.c:4181
void SCIPexprGetQuadraticData(SCIP_EXPR *expr, SCIP_Real *constant, int *nlinexprs, SCIP_EXPR ***linexprs, SCIP_Real **lincoefs, int *nquadexprs, int *nbilinexprs, SCIP_Real **eigenvalues, SCIP_Real **eigenvectors)
Definition expr.c:4060
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1421
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
Definition scip_expr.c:2296
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition expriter.c:857
SCIP_RETCODE SCIPcheckExprQuadratic(SCIP *scip, SCIP_EXPR *expr, SCIP_Bool *isquadratic)
Definition scip_expr.c:2336
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
Definition expr_var.c:416
void SCIPexprGetQuadraticQuadTerm(SCIP_EXPR *quadexpr, int termidx, SCIP_EXPR **expr, SCIP_Real *lincoef, SCIP_Real *sqrcoef, int *nadjbilin, int **adjbilin, SCIP_EXPR **sqrexpr)
Definition expr.c:4105
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
Definition scip_expr.c:2310
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
Definition expriter.c:500
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:178
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition heur.c:1361
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition scip_heur.c:117
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:226
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
Definition heur.c:1596
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:162
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition heur.c:1490
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition heur.c:1576
int SCIPheurGetFreqofs(SCIP_HEUR *heur)
Definition heur.c:1556
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:242
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition scip_heur.c:258
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:210
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:194
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition heur.c:1450
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition heur.c:1371
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition scip_lp.c:168
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition scip_mem.c:126
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition scip_mem.c:100
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:93
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition scip_mem.h:137
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_RETCODE SCIPendDiveNLP(SCIP *scip)
Definition scip_nlp.c:797
SCIP_RETCODE SCIPstartDiveNLP(SCIP *scip)
Definition scip_nlp.c:769
SCIP_RETCODE SCIPchgVarBoundsDiveNLP(SCIP *scip, SCIP_VAR *var, SCIP_Real lb, SCIP_Real ub)
Definition scip_nlp.c:853
int SCIPgetNNlpis(SCIP *scip)
Definition scip_nlpi.c:199
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition scip_nlp.c:110
SCIP_NLPSOLSTAT SCIPgetNLPSolstat(SCIP *scip)
Definition scip_nlp.c:541
#define SCIPsolveNLP(...)
Definition scip_nlp.h:340
SCIP_RETCODE SCIPsetNLPInitialGuessSol(SCIP *scip, SCIP_SOL *sol)
Definition scip_nlp.c:468
int SCIPgetNNLPNlRows(SCIP *scip)
Definition scip_nlp.c:341
SCIP_NLROW ** SCIPgetNLPNlRows(SCIP *scip)
Definition scip_nlp.c:319
const char * SCIPnlrowGetName(SCIP_NLROW *nlrow)
Definition nlp.c:1852
SCIP_Real SCIPnlrowGetRhs(SCIP_NLROW *nlrow)
Definition nlp.c:1823
SCIP_Real SCIPnlrowGetLhs(SCIP_NLROW *nlrow)
Definition nlp.c:1813
SCIP_EXPRCURV SCIPnlrowGetCurvature(SCIP_NLROW *nlrow)
Definition nlp.c:1833
SCIP_EXPR * SCIPnlrowGetExpr(SCIP_NLROW *nlrow)
Definition nlp.c:1803
int SCIPgetProbingDepth(SCIP *scip)
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)
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition scip_sol.c:2313
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition scip_sol.c:1775
int SCIPgetNSols(SCIP *scip)
Definition scip_sol.c:2214
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition scip_sol.c:2263
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_RETCODE SCIPfreeTransform(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_RETCODE SCIPcreateClock(SCIP *scip, SCIP_CLOCK **clck)
Definition scip_timing.c:76
SCIP_RETCODE SCIPresetClock(SCIP *scip, SCIP_CLOCK *clck)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_RETCODE SCIPfreeClock(SCIP *scip, SCIP_CLOCK **clck)
SCIP_Real SCIPgetClockTime(SCIP *scip, SCIP_CLOCK *clck)
SCIP_RETCODE SCIPstartClock(SCIP *scip, SCIP_CLOCK *clck)
SCIP_Bool SCIPisUbBetter(SCIP *scip, SCIP_Real newub, SCIP_Real oldlb, SCIP_Real oldub)
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 SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLbBetter(SCIP *scip, SCIP_Real newlb, SCIP_Real oldlb, SCIP_Real oldub)
SCIP_Real SCIPfeasCeil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasIntegral(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_Real SCIPsumepsilon(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
Definition scip_tree.c:670
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition var.c:17716
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition var.c:17570
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition var.c:17421
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition scip_var.c:4676
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17360
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3353
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:17966
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17748
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17406
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:17910
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition var.c:17590
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17241
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition scip_var.c:1248
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition var.c:17432
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition var.c:18274
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition scip_var.c:1527
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:17956
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition var.c:17396
SCIP_Bool SCIPvarIsRelaxationOnly(SCIP_VAR *var)
Definition var.c:17528
SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
Definition var.c:17726
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition scip_var.c:114
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:17900
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition scip_var.c:8276
SCIP_Real SCIPgetVarConflictScore(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:9241
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition scip_var.c:4513
SCIP_Real SCIPvarGetNLPSol(SCIP_VAR *var)
Definition var.c:18287
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
Definition scip_var.c:1597
SCIP_Real SCIPgetVarAvgInferenceCutoffScore(SCIP *scip, SCIP_VAR *var, SCIP_Real cutoffweight)
Definition scip_var.c:9790
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3295
SCIP_Real SCIPrandomGetReal(SCIP_RANDNUMGEN *randnumgen, SCIP_Real minrandval, SCIP_Real maxrandval)
Definition misc.c:10041
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10788
return SCIP_OKAY
SCIPfreeSol(scip, &heurdata->sol))
SCIPfreeRandom(scip, &heurdata->randnumgen)
int c
SCIPendProbing(scip))
SCIP_Bool cutoff
SCIPcreateRandom(scip, &heurdata->randnumgen, DEFAULT_RANDSEED, TRUE))
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_VAR ** vars
NLP local search primal heuristic using sub-SCIPs.
static SCIP_RETCODE performFixing(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_Bool *infeas, int *bdlen, SCIP_VAR **bdvars, SCIP_BOUNDTYPE *bdtypes, SCIP_Real *bdbounds, SCIP_Real *oldbounds)
static SCIP_RETCODE getFixingValue(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_VAR *var, SCIP_Real *val, char fixalt, SCIP_Bool *success, int bdlen, SCIP_VAR **bdvars, SCIP_BOUNDTYPE *bdtypes, SCIP_Real *oldbounds)
#define DEFAULT_MAXRECOVERS
static void incCounters(int *termcounter, int *conscounter, SCIP_Bool *consmarker, int idx)
#define DEFAULT_NODESQUOT
#define MAXPOSTNLPFAILS
static SCIP_RETCODE solveSubproblem(SCIP *scip, SCIP_HEUR *heur, int coversize, int *cover, SCIP_Real *fixedvals, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint nodelimit, SCIP_Longint nstallnodes, SCIP_Bool *validsolved, SCIP_SOL **sol, SCIP_Longint *nusednodes)
#define DEFAULT_FIXINGALTS
#define DEFAULT_NODESOFS
#define DEFAULT_COPYCUTS
#define DEFAULT_MAXNODES
#define DEFAULT_COVERBD
#define DEFAULT_MINCOVEREDABS
#define HEUR_TIMING
#define DEFAULT_MINNODES
static SCIP_RETCODE createCoveringProblem(SCIP *scip, SCIP *coveringscip, SCIP_VAR **coveringvars, SCIP_Bool globalbounds, SCIP_Bool onlyconvexify, SCIP_Bool coverbd, char coveringobj, SCIP_Bool *success)
#define MAXNLPFAILS
#define HEUR_FREQOFS
#define DEFAULT_ONLYCONVEXIFY
#define HEUR_DESC
static SCIP_Bool termIsConstant(SCIP *scip, SCIP_VAR *var, SCIP_Real coeff, SCIP_Bool global)
#define FIXINGORDERS
static SCIP_RETCODE fixAndPropagate(SCIP *scip, SCIP_HEURDATA *heurdata, int *cover, int coversize, SCIP_Real *fixingvals, int *bdlen, SCIP_VAR **bdvars, SCIP_BOUNDTYPE *bdtypes, SCIP_Real *bdbounds, SCIP_Real *oldbounds, int *nfixedints, int *nfixedconts, int *lastfailed, SCIP_Bool *infeas)
#define DEFAULT_RECOVERDIV
#define SUBMIPSETUPCOSTS
#define DEFAULT_INFERENCEWEIGHT
#define DEFAULT_POSTNLP
#define DEFAULT_MINCOVEREDREL
#define DEFAULT_MAXCOVERSIZECONSS
#define DEFAULT_CONFLICTWEIGHT
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
#define DEFAULT_REUSECOVER
#define DEFAULT_FIXINGORDER
#define DEFAULT_CUTOFFWEIGHT
#define DEFAULT_MINIMPROVE
static SCIP_RETCODE forbidCover(SCIP *scip, int nvars, SCIP_VAR **vars, int coversize, int *cover, int diversification, SCIP_Bool *success, SCIP_Bool *infeas)
#define HEUR_NAME
static SCIP_RETCODE roundFixingValue(SCIP *scip, SCIP_Real *val, SCIP_VAR *var, SCIP_Bool locksrounding)
static SCIP_RETCODE computeCoverUndercover(SCIP *scip, SCIP *coveringscip, int *coversize, SCIP_VAR **cover, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Real objlimit, SCIP_Bool globalbounds, SCIP_Bool onlyconvexify, SCIP_Bool coverbd, char coveringobj, SCIP_Bool *success)
static SCIP_RETCODE updateTimelimit(SCIP *scip, SCIP_CLOCK *clck, SCIP_Real *timelimit)
static SCIP_Bool termIsConvex(SCIP *scip, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool sign)
static SCIP_RETCODE solveCoveringProblem(SCIP *coveringscip, int ncoveringvars, SCIP_VAR **coveringvars, int *coversize, int *cover, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Real objlimit, SCIP_Bool *success)
static SCIP_RETCODE SCIPapplyUndercover(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real timelimit, SCIP_Real memorylimit, SCIP_Longint nstallnodes)
#define DEFAULT_MAXCOVERSIZEVARS
#define DEFAULT_MAXBACKTRACKS
#define DEFAULT_COVERINGOBJ
#define DEFAULT_RANDSEED
#define DEFAULT_LOCKSROUNDING
static void calculateAlternatives(SCIP *scip, SCIP_VAR *var, SCIP_Real fixval, int *nalternatives, SCIP_Real *alternatives)
static SCIP_RETCODE processNlRow(SCIP *scip, SCIP_NLROW *nlrow, SCIP *coveringscip, int nvars, SCIP_VAR **coveringvars, int *termcounter, int *conscounter, SCIP_Bool *consmarker, SCIP_Bool globalbounds, SCIP_Bool onlyconvexify, SCIP_Bool *success)
#define COVERINGOBJS
#define HEUR_FREQ
static SCIP_Bool varIsFixed(SCIP *scip, SCIP_VAR *var, SCIP_Real val, SCIP_Bool global)
#define DEFAULT_FIXINTFIRST
#define DEFAULT_BEFORECUTS
#define HEUR_USESSUBSCIP
#define MINTIMELEFT
static SCIP_RETCODE createConflict(SCIP *scip, int bdlen, SCIP_VAR **bdvars, SCIP_BOUNDTYPE *bdtypes, SCIP_Real *bdbounds, SCIP_Bool local, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool *success)
#define DEFAULT_MAXREORDERS
static SCIP_RETCODE computeFixingOrder(SCIP *scip, SCIP_HEURDATA *heurdata, int nvars, SCIP_VAR **vars, int coversize, int *cover, int lastfailed, SCIP_Bool *success)
Undercover primal heuristic for MINLPs.
#define NULL
Definition lpi_spx1.cpp:161
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
Definition memory.h:132
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition scip_mem.c:57
public methods for managing constraints
public functions to work with algebraic expressions
public methods for primal heuristics
public methods for message output
#define SCIPerrorMessage
Definition pub_message.h:64
#define SCIPdebug(x)
Definition pub_message.h:93
#define SCIPstatisticPrintf
#define SCIPstatistic(x)
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for NLP management
public methods for problem variables
public methods for branching rule plugins and branching
public methods for constraint handler plugins and constraints
public methods for problem copies
general public methods
public methods for primal heuristic plugins and divesets
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for nonlinear relaxation
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 random numbers
public methods for solutions
public solving methods
public methods for querying solving statistics
public methods for timing
public methods for the branch-and-bound tree
public methods for SCIP variables
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
default SCIP plugins
#define MAX(x, y)
Definition tclique_def.h:92
@ SCIP_EXPRCURV_CONVEX
Definition type_expr.h:60
@ SCIP_EXPRCURV_LINEAR
Definition type_expr.h:62
@ SCIP_EXPRCURV_CONCAVE
Definition type_expr.h:61
@ SCIP_EXPRITER_DFS
Definition type_expr.h:700
#define SCIP_DECL_HEURINITSOL(x)
Definition type_heur.h:131
#define SCIP_DECL_HEURCOPY(x)
Definition type_heur.h:96
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:76
#define SCIP_DECL_HEURINIT(x)
Definition type_heur.h:112
#define SCIP_DECL_HEUREXIT(x)
Definition type_heur.h:120
#define SCIP_DECL_HEURFREE(x)
Definition type_heur.h:104
#define SCIP_DECL_HEUREXITSOL(x)
Definition type_heur.h:142
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:162
@ 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_NlpSolStat SCIP_NLPSOLSTAT
Definition type_nlpi.h:168
@ SCIP_NLPSOLSTAT_FEASIBLE
Definition type_nlpi.h:162
@ SCIP_NLPSOLSTAT_LOCOPT
Definition type_nlpi.h:161
@ SCIP_NLPSOLSTAT_GLOBOPT
Definition type_nlpi.h:160
@ SCIP_PARAMSETTING_AGGRESSIVE
@ SCIP_PARAMSETTING_FAST
@ SCIP_PARAMEMPHASIS_FEASIBILITY
@ 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_PARAMETERWRONGVAL
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_STATUS_OPTIMAL
Definition type_stat.h:61
@ SCIP_STATUS_INFEASIBLE
Definition type_stat.h:62
#define SCIP_HEURTIMING_DURINGLPLOOP
Definition type_timing.h:79
@ SCIP_VARTYPE_CONTINUOUS
Definition type_var.h:71
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62
@ SCIP_VARSTATUS_FIXED
Definition type_var.h:52
@ SCIP_VARSTATUS_MULTAGGR
Definition type_var.h:54
@ SCIP_LOCKTYPE_MODEL
Definition type_var.h:97