SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
heur_dualval.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_dualval.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief dualval primal heuristic
28 * @author Tobias Buchwald
29 *
30 * This heuristic tries to find solutions by taking the LP or NLP, rounding solution values, fixing the variables to the
31 * rounded values and then changing some of the values.To determine which variable is changed we give each variable a
32 * ranking dependent on its dualvalue. We work with a transformed problem that is always feasible and has objective = 0
33 * iff the original problem is also feasible. Thus we cannot expect to find really good solutions.
34 */
35
36/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
37
39#include "scip/type_expr.h"
40#include "scip/cons_indicator.h"
41#include "scip/cons_knapsack.h"
42#include "scip/cons_linear.h"
43#include "scip/cons_logicor.h"
44#include "scip/cons_setppc.h"
45#include "scip/cons_varbound.h"
46#include "scip/heur_dualval.h"
47#include "scip/pub_cons.h"
48#include "scip/pub_event.h"
49#include "scip/pub_heur.h"
50#include "scip/pub_message.h"
51#include "scip/pub_misc.h"
52#include "scip/pub_misc_sort.h"
53#include "scip/pub_nlp.h"
54#include "scip/pub_sol.h"
55#include "scip/pub_var.h"
56#include "scip/scip_branch.h"
57#include "scip/scip_cons.h"
58#include "scip/scip_copy.h"
59#include "scip/scip_event.h"
60#include "scip/scip_general.h"
61#include "scip/scip_heur.h"
62#include "scip/scip_lp.h"
63#include "scip/scip_mem.h"
64#include "scip/scip_message.h"
65#include "scip/scip_nlp.h"
66#include "scip/scip_nlpi.h"
67#include "scip/scip_numerics.h"
68#include "scip/scip_param.h"
69#include "scip/scip_prob.h"
70#include "scip/scip_sol.h"
71#include "scip/scip_solve.h"
73#include "scip/scip_var.h"
74#include <string.h>
75
76#define HEUR_NAME "dualval"
77#define HEUR_DESC "primal heuristic using dual values"
78#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
79#define HEUR_PRIORITY -10
80#define HEUR_FREQ -1
81#define HEUR_FREQOFS 0
82#define HEUR_MAXDEPTH -1
83#define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
84#define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
85
86#define EVENTHDLR_NAME "lpsol_dualval"
87#define EVENTHDLR_DESC "event handler for lp solution found"
88
89/* default values for user parameters */
90/* boolean parameters */
91#define DEFAULT_FORCEIMPROVEMENTS FALSE /**< exit if objective doesn't improve */
92#define DEFAULT_ONLYCHEAPER TRUE /**< add constraint to ensure that discrete vars are improving */
93#define DEFAULT_ONLYLEAVES FALSE /**< disable the heuristic if it was not called at a leaf of the B&B tree */
94#define DEFAULT_RELAXINDICATORS FALSE /**< relax the indicator variables by introducing continuous copies */
95#define DEFAULT_RELAXCONTVARS FALSE /**< enable relaxation of continous variables */
96
97/* integer parameters */
98#define DEFAULT_HEURVERBLEVEL 0 /**< verblevel of the heuristic, default is 0 to display nothing */
99#define DEFAULT_NLPVERBLEVEL 0 /**< verblevel of the nlp solver, can be 0 or 1 */
100#define DEFAULT_RANKVALUE 10 /**< number of ranks that should be displayed when the heuristic is called */
101#define DEFAULT_MAXCALLS 25 /**< maximal number of recursive calls of the heuristic (if dynamicdepth is off) */
102#define DEFAULT_DYNAMICDEPTH 0 /**< says if and how the recursion depth is computed at runtime */
103#define DEFAULT_MAXEQUALRANKS 50 /**< maximal number of variables that may have maximal rank, quit if there are more, turn off by setting -1 */
104
105/* real value parameters */
106#define DEFAULT_MINGAP 5.0 /**< minimal gap for which we still run the heuristic, if gap is less we return without doing anything */
107#define DEFAULT_LAMBDASLACK 1.0 /**< value added to objective of slack variables, must not be zero */
108#define DEFAULT_LAMBDAOBJ 0.0 /**< scaling factor for the objective function */
109
110
111/**primal heuristic data */
112struct SCIP_HeurData
113{
114 SCIP* subscip; /**< copy of CIP */
115 SCIP_VAR** integervars; /**< array of all binary and integer variables of the original scip */
116 SCIP_HASHMAP* varsciptosubscip; /**< mapping variables in SCIP to sub-SCIP variables */
117 SCIP_HASHMAP* varsubsciptoscip; /**< mapping variables in sub-SCIP to SCIP variables */
118 SCIP_HASHMAP* origsubscipConsMap; /**< maps constraints from the transformed problem to corresponding constraints in subproblem */
119 SCIP_HASHMAP* switchedvars; /**< stores the last value of switched var to avoid cycling */
120 SCIP_HASHMAP* switchedvars2; /**< stores the second last value of switched vars to avoid cycling */
121 SCIP_HASHMAP* relaxcons; /**< maps subscip variables to their relaxation constraints */
122 SCIP_HASHMAP* relaxconsindi; /**< maps indicator variables and their copies to relaxation constraint */
123 SCIP_HASHMAP* slacktoindivarsmap; /**< maps slack variables of indicator constraint to indicator variable */
124 SCIP_HASHMAP* indicators; /**< maps indicator variables to their indicator constraint */
125 SCIP_HASHMAP* conss2nlrow; /**< maps constraint to the corresponding nlrow */
126 SCIP_HASHMAP* dualvalues; /**< maps constraints of the subscip to their dual values */
127 SCIP_HASHMAP* slack2var; /**< maps slack variables to the variable they actually relax */
128 SCIP_HASHMAP* indicopymap; /**< maps indicator variables to their copy variables */
129 SCIP_HASHMAP* indicopymapback; /**< maps copy variables to their indicator variables */
130 SCIP_HASHMAP* slackvarlbMap; /**< mapping used indicators to slack variables lower bound*/
131 SCIP_HASHMAP* slackvarubMap; /**< mapping used indicators to slack variables upper bound*/
132 SCIP_CONS* objbound; /**< contraint for upper bound of the objective function */
133 SCIP_Real prevobjective; /**< stores objective value (of the original) so we know if it improved */
134 SCIP_Real mingap; /**< don't run the heuristic if the gap is less than mingap */
135 SCIP_Real lambdaslack; /**< the value added to the objective function */
136 SCIP_Real lambdaobj; /**< the value the original objective function is scaled with */
137 int integervarssize; /**< size of integervars array */
138 int nintegervars; /**< number of integer variables in the original problem */
139 int heurverblevel; /**< verblevel, range is 0 to 4 */
140 int nlpverblevel; /**< sets verblevel of the included nlp */
141 int rankvalue; /**< print out the 'rankvalue' highest ranks during iterations */
142 int maxcalls; /**< maximum number of allowed iterations */
143 int nonimprovingRounds; /**< nr of rounds, where the algorithm has not improved */
144 int dynamicdepth; /**< how should the number of calls be computed? */
145 int maxequalranks; /**< maximum number of variables that may have maximal (absolute) rank */
146 int nvars; /**< number of active transformed variables in SCIP */
147 int nsubvars; /**< number of original variables in sub-SCIP */
148 int usedcalls; /**< number of currently used iterations */
149 SCIP_Bool isnlp; /**< tells us, whether we have nonlinearities in our program or not */
150 SCIP_Bool forceimprovements; /**< whether we exit on nonimproving objective in the relaxation or not */
151 SCIP_Bool prevInfeasible; /**< will tell us if the previous call led to an infeasible fixing */
152 SCIP_Bool solfound; /**< parameter says, if we already found a solution and have to go back */
153 SCIP_Bool subscipisvalid; /**< whether all constraints have been copied */
154 SCIP_Bool switchdifferent; /**< tells us that we want to go up one level and switch another variable */
155 SCIP_Bool triedsetupsubscip; /**< whether we have tried to setup a sub-SCIP */
156 SCIP_Bool onlycheaper; /**< add constraint to ensure that discrete vars are improving */
157 SCIP_Bool onlyleaves; /**< don't use heuristic if we are not in a leaf of the B&B tree */
158 SCIP_Bool relaxindicators; /**< additionally relax indicator variables */
159 SCIP_Bool relaxcontvars; /**< additionally relax continous variables */
160};
161
162/*
163 * event handler method
164 */
165
166/** initialization method of event handler (called after problem was transformed) */
167static
169{ /*lint --e{715}*/
170 assert(scip != NULL);
171 assert(eventhdlr != NULL);
172
173 /* notify SCIP that your event handler wants to react on the event type best solution found */
175
176 return SCIP_OKAY;
177}
178
179/** deinitialization method of event handler (called before transformed problem is freed) */
180static
182{ /*lint --e{715}*/
183 assert(scip != NULL);
184 assert(eventhdlr != NULL);
185
186 /* notify SCIP that your event handler wants to drop the event type best solution found */
188
189 return SCIP_OKAY;
190}
191
192/** execution method of event handler */
193static
195{ /*lint --e{715}*/
196 int i;
197 int nsubconss;
200 SCIP_Real* dualval;
201
202 assert(eventhdlr != NULL);
203 assert(event != NULL);
204 assert(scip != NULL);
206
210
211 /* free memory of all entries and clear the hashmap before filling it */
212 for( i = 0; i < nsubconss; i++ )
213 {
214 dualval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, subconss[i]);
215 if( dualval != NULL )
217 }
219
220 /* insert dualvalues from LP into a hashmap */
221 for( i = 0; i < nsubconss; i++ )
222 {
225
226 if( transcons == NULL )
227 continue;
228
229 if( SCIPconsGetHdlr(transcons) != SCIPfindConshdlr(heurdata->subscip, "linear") )
230 continue;
231
232 SCIP_CALL( SCIPallocBlockMemoryArray(heurdata->subscip, &dualval, 1) ); /*lint !e506*/
235 }
236 if( heurdata->heurverblevel > 2 )
237 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "LP solved event!\n");
238
239 return SCIP_OKAY;
240}
241
242/** includes event handler for best solution found */
243static
245 SCIP* scip, /**< SCIP data structure */
246 SCIP_HEURDATA* heurdata /**< heuristic data */
247 )
248{
249 SCIP_EVENTHDLRDATA* eventhdlrdata;
250 SCIP_EVENTHDLR* eventhdlr = NULL;
251
252 eventhdlrdata = (SCIP_EVENTHDLRDATA*)heurdata;
253
254 /* create event handler */
256 assert(eventhdlr != NULL);
257
260
261 return SCIP_OKAY;
262}
263
264/*
265 * Local methods
266 */
267
268/** releases all variables or constraints from given hash map */
269static
271 SCIP* scip, /**< SCIP data structure */
272 SCIP_HASHMAP* hashmap, /**< hashmap */
273 SCIP_Bool isvarmap /**< are the entries variables or constraints? */
274 )
275{
276 int nentries;
277 int i;
278
279 assert(scip != NULL);
280 assert(hashmap != NULL);
281
282 nentries = SCIPhashmapGetNEntries(hashmap);
283
284 for( i = 0; i < nentries; ++i )
285 {
287 entry = SCIPhashmapGetEntry(hashmap, i);
288
289 if( entry != NULL )
290 {
291 if( isvarmap )
292 {
293 SCIP_VAR* var;
295
297 }
298 else
299 {
300 SCIP_CONS* cons;
302
303 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
304 }
305 }
306 }
307
308 return SCIP_OKAY;
309}
310
311/** releases all NLP rows from given hash map */
312static
314 SCIP* scip, /**< SCIP data structure */
315 SCIP_HASHMAP* hashmap /**< hashmap */
316 )
317{
318 int nentries;
319 int i;
320
321 assert(scip != NULL);
322 assert(hashmap != NULL);
323
324 nentries = SCIPhashmapGetNEntries(hashmap);
325
326 for( i = 0; i < nentries; ++i )
327 {
329 entry = SCIPhashmapGetEntry(hashmap, i);
330 if( entry != NULL )
331 {
332 SCIP_NLROW* nlrow;
334
335 SCIP_CALL( SCIPreleaseNlRow(scip, &nlrow) );
336 }
337 }
338
339 return SCIP_OKAY;
340}
341
342
343/** adds linear constraints from a SCIP instance to its NLP */
344static
346 SCIP* scip, /**< SCIP data structure */
347 SCIP_CONSHDLR* conshdlr, /**< constraint handler for linear constraints */
348 SCIP_Bool addcombconss, /**< whether to add combinatorial linear constraints to NLP */
349 SCIP_Bool addcontconss, /**< whether to add continuous linear constraints to NLP */
350 SCIP_HEURDATA* heurdata /**< heuristic data structure */
351 )
352{
353 SCIP_CONS** conss;
354 SCIP_VAR** vars;
355 SCIP_NLROW* nlrow;
356 int nconss;
357 int i;
358 int j;
359 int nvars;
360 SCIP_Bool iscombinatorial;
361
362 assert(scip != NULL);
363 assert(conshdlr != NULL);
364
365 nconss = SCIPconshdlrGetNActiveConss(conshdlr);
366 conss = SCIPconshdlrGetConss(conshdlr);
367
368 if( nconss == 0 )
369 return SCIP_OKAY;
370
371 for( i = 0; i < nconss; ++i )
372 {
373 /* skip local and redundant constraints */
374 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) )
375 continue;
376
377 /* under some circumstances, this method may be called even though the problem has been shown to be
378 * infeasible in presolve already.
379 * this infeasibility may come from a linear constraint with lhs > rhs
380 * the NLP does not allow such constraints, so we skip them here
381 */
382 if( !SCIPisRelLE(scip, SCIPgetLhsLinear(scip, conss[i]), SCIPgetRhsLinear(scip, conss[i])) )
383 continue;
384
385 nvars = SCIPgetNVarsLinear(scip, conss[i]);
386 vars = SCIPgetVarsLinear(scip, conss[i]);
387
388 /* check if constraint should be added, only need this check if we do not wanna any constraint anyway */
389 if( !addcombconss || !addcontconss )
390 {
392
393 for( j = 0; j < nvars; ++j )
394 {
396 {
398 break;
399 }
400 }
401
402 /* skip constraint, if not of interest */
404 continue;
405 }
406
407 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0,
409 SCIPgetLhsLinear(scip, conss[i]), SCIPgetRhsLinear(scip, conss[i]),
411
412 SCIP_CALL( SCIPaddNlRow(scip, nlrow) );
413 SCIP_CALL( SCIPhashmapInsert(heurdata->conss2nlrow, conss[i], nlrow) );
414 SCIP_CALL( SCIPreleaseNlRow(scip, &nlrow) );
415 }
416
417 return SCIP_OKAY;
418}
419
420/** adds variable bound constraints from a SCIP instance to its NLP */
421static
423 SCIP* scip, /**< SCIP data structure */
424 SCIP_CONSHDLR* conshdlr, /**< constraint handler for linear constraints */
425 SCIP_Bool addcombconss, /**< whether to add combinatorial linear constraints to NLP */
426 SCIP_Bool addcontconss, /**< whether to add continuous linear constraints to NLP */
427 SCIP_HEURDATA* heurdata /**< heuristic data structure */
428 )
429{
430 SCIP_CONS** conss;
431 int nconss;
432 SCIP_NLROW* nlrow;
433 int i;
434 SCIP_VAR* vars[2];
435 SCIP_Real coefs[2];
436 SCIP_Bool iscombinatorial;
437
438 assert(scip != NULL);
439 assert(conshdlr != NULL);
440
441 nconss = SCIPconshdlrGetNActiveConss(conshdlr);
442 conss = SCIPconshdlrGetConss(conshdlr);
443
444 if( nconss == 0 )
445 return SCIP_OKAY;
446
447 for( i = 0; i < nconss; ++i )
448 {
449 /* skip local and redundant constraints */
450 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) )
451 continue;
452
453 vars[0] = SCIPgetVarVarbound(scip, conss[i]);
454 vars[1] = SCIPgetVbdvarVarbound(scip, conss[i]);
455
457
458 /* skip constraint, if not of interest */
460 continue;
461
462 coefs[0] = 1.0;
463 coefs[1] = SCIPgetVbdcoefVarbound(scip, conss[i]);
464
465 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0,
466 2, vars, coefs, NULL,
469
470 SCIP_CALL( SCIPaddNlRow(scip, nlrow) );
471 SCIP_CALL( SCIPhashmapInsert(heurdata->conss2nlrow, conss[i], nlrow) );
472 }
473
474 return SCIP_OKAY;
475}
476
477
478/** adds logic-or constraints to NLP */
479static
481 SCIP* scip, /**< SCIP data structure */
482 SCIP_CONSHDLR* conshdlr, /**< constraint handler for linear constraints */
483 SCIP_HEURDATA* heurdata /**< heuristic data structure */
484 )
485{
486 SCIP_CONS** conss;
487 int nconss;
488 SCIP_NLROW* nlrow;
489 int i;
490 int j;
491 SCIP_Real* coefs;
492 int coefssize;
493 int nvars;
494
495 assert(scip != NULL);
496 assert(conshdlr != NULL);
497
498 nconss = SCIPconshdlrGetNActiveConss(conshdlr);
499 if( !nconss )
500 return SCIP_OKAY;
501
502 conss = SCIPconshdlrGetConss(conshdlr);
503
504 coefs = NULL;
505 coefssize = 0;
506
507 for( i = 0; i < nconss; ++i )
508 {
509 /* skip local and redundant constraints */
510 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) )
511 continue;
512
513 nvars = SCIPgetNVarsLogicor(scip, conss[i]);
514
515 if( coefssize < nvars )
516 {
517 if( coefs == NULL )
518 {
520 }
521 else
522 {
524 }
525 for( j = coefssize; j < nvars; ++j )
526 coefs[j] = 1.0;
527 coefssize = nvars;
528 }
529
530 /* logic or constraints: 1 == sum_j x_j */
531 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0,
532 nvars, SCIPgetVarsLogicor(scip, conss[i]), coefs, NULL,
533 1.0, SCIPinfinity(scip),
535
536 SCIP_CALL( SCIPaddNlRow(scip, nlrow) );
537 SCIP_CALL( SCIPhashmapInsert(heurdata->conss2nlrow, conss[i], nlrow) );
538 }
539
541
542 return SCIP_OKAY;
543}
544
545/** adds setppc constraints to NLP */
546static
548 SCIP* scip, /**< SCIP data structure */
549 SCIP_CONSHDLR* conshdlr, /**< constraint handler for linear constraints */
550 SCIP_HEURDATA* heurdata /**< heuristic data structure */
551 )
552{
553 SCIP_CONS** conss;
554 int nconss;
555 SCIP_NLROW* nlrow;
556 int i;
557 int j;
558 SCIP_Real* coefs;
559 int coefssize;
560 int nvars;
561 SCIP_Real lhs;
562 SCIP_Real rhs;
563
564 assert(scip != NULL);
565 assert(conshdlr != NULL);
566
567 nconss = SCIPconshdlrGetNActiveConss(conshdlr);
568 if( nconss == 0 )
569 return SCIP_OKAY;
570
571 conss = SCIPconshdlrGetConss(conshdlr);
572
573 coefs = NULL;
574 coefssize = 0;
575
576 for( i = 0; i < nconss; ++i )
577 {
578 /* skip local and redundant constraints */
579 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) )
580 continue;
581
582 nvars = SCIPgetNVarsSetppc(scip, conss[i]);
583
584 if( coefssize < nvars )
585 {
586 if( coefs == NULL )
587 {
589 }
590 else
591 {
593 }
594 for( j = coefssize; j < nvars; ++j )
595 coefs[j] = 1.0;
596 coefssize = nvars;
597 }
598
599 /* setppc constraint: 1 ~ sum_j x_j */
600
601 switch( SCIPgetTypeSetppc(scip, conss[i]) )
602 {
604 lhs = 1.0;
605 rhs = 1.0;
606 break;
607
609 lhs = -SCIPinfinity(scip);
610 rhs = 1.0;
611 break;
612
614 lhs = 1.0;
615 rhs = SCIPinfinity(scip);
616 break;
617
618 default:
619 SCIPerrorMessage("unexpected setppc type\n");
620 return SCIP_ERROR;
621 }
622
623 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0,
624 nvars, SCIPgetVarsSetppc(scip, conss[i]), coefs, NULL,
625 lhs, rhs,
627
628 SCIP_CALL( SCIPaddNlRow(scip, nlrow) );
629 SCIP_CALL( SCIPhashmapInsert(heurdata->conss2nlrow, conss[i], nlrow) );
630 }
631
633
634 return SCIP_OKAY;
635}
636
637/** adds knapsack constraints to NLP */
638static
640 SCIP* scip, /**< SCIP data structure */
641 SCIP_CONSHDLR* conshdlr, /**< constraint handler for linear constraints */
642 SCIP_HEURDATA* heurdata /**< heuristic data structure */
643 )
644{
645 SCIP_CONS** conss;
646 int nconss;
647 SCIP_NLROW* nlrow;
648 int i;
649 int j;
650 SCIP_Real* coefs;
651 int coefssize;
652 int nvars;
653
654 assert(scip != NULL);
655 assert(conshdlr != NULL);
656
657 nconss = SCIPconshdlrGetNActiveConss(conshdlr);
658 if( nconss == 0 )
659 return SCIP_OKAY;
660
661 conss = SCIPconshdlrGetConss(conshdlr);
662 assert(conss != NULL);
663
664 coefs = NULL;
665 coefssize = 0;
666
667 for( i = 0; i < nconss; ++i )
668 {
669 SCIP_Longint* weights;
670
671 /* skip local and redundant constraints */
672 if( !SCIPconsIsEnabled(conss[i]) || !SCIPconsIsChecked(conss[i]) )
673 continue;
674
675 nvars = SCIPgetNVarsKnapsack(scip, conss[i]);
676
677 if( coefssize < nvars )
678 {
679 if( coefs == NULL )
680 {
682 }
683 else
684 {
686 }
687 coefssize = nvars;
688 }
689
690 weights = SCIPgetWeightsKnapsack(scip, conss[i]);
691 for( j = 0; j < nvars; ++j )
692 coefs[j] = (SCIP_Real)weights[j]; /*lint !e613*/
693
694 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0,
695 nvars, SCIPgetVarsKnapsack(scip, conss[i]), coefs, NULL,
696 -SCIPinfinity(scip), (SCIP_Real)SCIPgetCapacityKnapsack(scip, conss[i]),
698
699 SCIP_CALL( SCIPaddNlRow(scip, nlrow) );
700 SCIP_CALL( SCIPhashmapInsert(heurdata->conss2nlrow, conss[i], nlrow) );
701 }
702
704
705 return SCIP_OKAY;
706}
707
708
709/** adds combinatorial and/or continuous variants of linear constraints from a SCIP instance to its NLP */
710static
712 SCIP* scip, /**< SCIP data structure */
713 SCIP_Bool addcombconss, /**< whether to add combinatorial linear constraints to NLP */
714 SCIP_Bool addcontconss, /**< whether to add continuous linear constraints to NLP */
715 SCIP_HEURDATA* heurdata /**< heuristic data structure */
716 )
717{
718 SCIP_CONSHDLR* conshdlr;
719
720 /* add linear constraints */
721 conshdlr = SCIPfindConshdlr(scip, "linear");
722 if( conshdlr != NULL )
723 {
725 }
726
727 /* add varbound constraints */
728 conshdlr = SCIPfindConshdlr(scip, "varbound");
729 if( conshdlr != NULL )
730 {
732 }
733
734 if( addcombconss )
735 {
736 /* add logic-or constraints */
737 conshdlr = SCIPfindConshdlr(scip, "logicor");
738 if( conshdlr != NULL )
739 {
741 }
742
743 /* add setppc constraints */
744 conshdlr = SCIPfindConshdlr(scip, "setppc");
745 if( conshdlr != NULL )
746 {
748 }
749
750 /* add knapsack constraints */
751 conshdlr = SCIPfindConshdlr(scip, "knapsack");
752 if( conshdlr != NULL )
753 {
755 }
756 }
757
758 return SCIP_OKAY;
759}
760
761
762
763/** creates a SCIP_SOL in our SCIP space out of the SCIP_SOL from a sub-SCIP */
764static
766 SCIP* scip, /**< SCIP data structure */
767 SCIP_HEUR* heur, /**< heuristic data structure */
768 SCIP_SOL** sol, /**< buffer to store solution value; if pointing to NULL, a new solution
769 * is created, otherwise values in the given one are overwritten */
770 SCIP_SOL* subsol /**< solution of sub-SCIP */
771 )
772{
774 SCIP_VAR** vars;
775 SCIP_VAR** subvars;
776 SCIP_VAR* var;
778 SCIP_Real scalar;
779 SCIP_Real constant;
780 SCIP_Real val;
781 int i;
782 int nvars;
783
785 assert( heurdata != NULL );
786 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nvars, NULL, NULL, NULL, NULL) );
787
788 if( *sol == NULL )
789 {
791 }
792
795
796 for( i = 0; i < nvars; ++i )
797 {
798 var = vars[i];
799
800 constant = 0;
801 scalar = 1.0;
803 val = 0;
804
805 if( REALABS(scalar) > 0 )
806 {
807 SCIP_Real transval = 0.0;
808
809 subvar = (SCIP_VAR*) SCIPhashmapGetImage(heurdata->varsciptosubscip, (void*)var);
810 if( subvar == NULL )
811 {
812 SCIPdebugMsg(scip, "return14 : abort building solution since a variable was not in our list\n");
813
815 return SCIP_OKAY;
816 }
817
820 else
821 {
822 SCIP_Real tconstant = 0.0;
823 SCIP_Real tscalar = 1.0;
825
826 transval = 0.0;
827
828 if( REALABS(tscalar) > 0.0 )
829 {
830 assert(subvar != NULL);
832 }
833
834 /* recompute aggregations */
836 }
837 val = scalar * transval + constant;
838 }
839 else
840 {
841 /* recompute aggregations */
842 val = scalar * val + constant;
843 }
844
845 assert( val != SCIP_INVALID ); /*lint !e777*/
846 SCIP_CALL( SCIPsetSolVal(scip, *sol, vars[i], val) );
847 }
848
849 return SCIP_OKAY;
850}
851
852
853
854/** creates copy of CIP from problem in SCIP */
855static
857 SCIP* scip, /**< SCIP data structure */
858 SCIP_HEURDATA* heurdata /**< heuristic data structure */
859 )
860{
870 SCIP_CONSHDLR* conshdlrsetppc;
872 SCIP_CONS** conss;
877 SCIP_CONS* cons = NULL;
878 SCIP_VAR** vars;
879 SCIP_VAR** subvars;
880 SCIP_VAR* var;
888 char probname[SCIP_MAXSTRLEN];
890 char consname[SCIP_MAXSTRLEN];
891 SCIP_Real varobjective;
892 int nconss;
893 int nconsindicator;
894 int i;
895 int j;
896 int k;
897 int nvars;
898 int ncontvars;
899 SCIP_Bool feasible;
900 SCIP_Bool success;
901
902 assert( heurdata != NULL );
903 assert( heurdata->subscip == NULL );
904
905 heurdata->usedcalls = 0;
906 heurdata->solfound = FALSE;
907 heurdata->nonimprovingRounds = 0;
908
909 /* we can't change the vartype in some constraints, so we have to check that only the right constraints are present*/
910 conshdlrindi = SCIPfindConshdlr(scip, "indicator");
911 conshdlrlin = SCIPfindConshdlr(scip, "linear");
912 conshdlrnonlin = SCIPfindConshdlr(scip, "nonlinear");
916 conshdlrsetppc = SCIPfindConshdlr(scip, "setppc");
917
918 nconss = SCIPgetNOrigConss(scip);
919 conss = SCIPgetOrigConss(scip);
920
921 /* for each constraint ask if it has an allowed type */
922 for (i = 0; i < nconss; i++ )
923 {
924 cons = conss[i];
926
932 currentconshdlr == conshdlrsetppc ||
934 {
935 continue;
936 }
937 else
938 {
939 return SCIP_OKAY;
940 }
941 }
942
943 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, &ncontvars) );
944
945 if( heurdata->dynamicdepth == 1 )
946 {
947 heurdata->maxcalls = (int)SCIPfloor(scip, sqrt((double)(nvars - ncontvars)));
948 }
949
950 heurdata->triedsetupsubscip = TRUE;
951
952 /* initializing the subproblem */
953 SCIP_CALL( SCIPcreate(&heurdata->subscip) );
954
955 /* create variable hash mapping scip -> subscip */
957
958 SCIP_CALL( SCIPhashmapCreate(&heurdata->switchedvars, SCIPblkmem(scip), heurdata->maxcalls) );
959 SCIP_CALL( SCIPhashmapCreate(&heurdata->switchedvars2, SCIPblkmem(scip), heurdata->maxcalls) );
960
961 /* create sub-SCIP copy of CIP, copy interesting plugins */
962 success = TRUE;
965
966 if( success == FALSE )
967 {
968 SCIPdebugMsg(scip, "In heur_dualval: failed to copy some plugins to sub-SCIP, continue anyway\n");
969 }
970
971 /* copy parameter settings */
973
974 /* create problem in sub-SCIP */
975
976 /* get name of the original problem and add "dualval" */
977 (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_dualval", SCIPgetProbName(scip));
978 SCIP_CALL( SCIPcreateProb(heurdata->subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
979
981
982 /* copy all variables */
984
985 /* copy as many constraints as possible */
987 SCIP_CALL( SCIPcopyConss(scip, heurdata->subscip, varsmap, conssmap, TRUE, FALSE, &heurdata->subscipisvalid) );
988
990
991 nconss = SCIPgetNOrigConss(scip);
992 conss = SCIPgetOrigConss(scip);
993
994 /* fill constraint mapping from original scip to the subscip */
995 for( i = 0; i < nconss; ++i )
996 {
997 transcons = NULL;
999
1001 assert( subcons != NULL );
1002
1004 SCIP_CALL( SCIPhashmapInsert(heurdata->origsubscipConsMap, transcons, subcons) );
1005 }
1006
1008
1009 if( !heurdata->subscipisvalid )
1010 {
1011 SCIPdebugMsg(scip, "In heur_dualval: failed to copy some constraints to sub-SCIP, continue anyway\n");
1012 }
1013
1014 SCIP_CALL( SCIPgetVarsData(heurdata->subscip, &subvars, &heurdata->nsubvars, NULL, NULL, NULL, NULL) );
1015 heurdata->nvars = nvars;
1016
1017 /* create hashmaps from scip transformed vars to subscip original vars, and vice versa
1018 * capture variables in SCIP and sub-SCIP
1019 * catch global bound change events */
1022
1023 /* we need to get all subscip variables, also those which are copies of fixed variables from the main scip,
1024 * therefore we iterate over the hashmap */
1025 for( i = 0; i < SCIPhashmapGetNEntries(varsmap); ++i )
1026 {
1029 if( entry != NULL )
1030 {
1033
1035 assert( SCIPvarGetProbindex(subvar) <= heurdata->nsubvars );
1036
1037 if( SCIPvarIsActive(var) )
1038 {
1039 assert( SCIPvarGetProbindex(var) <= heurdata->nvars );
1040 /* assert that we have no mapping for this var yet */
1041 assert( SCIPhashmapGetImage(heurdata->varsciptosubscip,var) == NULL );
1042 SCIP_CALL( SCIPhashmapInsert(heurdata->varsciptosubscip, var, subvar) );
1043 }
1044
1045 assert( SCIPhashmapGetImage(heurdata->varsubsciptoscip, subvar) == NULL );
1046 SCIP_CALL( SCIPhashmapInsert(heurdata->varsubsciptoscip, subvar, var) );
1047
1050
1053 }
1054 }
1055
1056 /* we map all slack variables of indicator constraints to their indicator variables */
1057 conshdlrindicator = SCIPfindConshdlr(scip, "indicator");
1059
1066
1067 for( i = 0; i < nconsindicator; i++ )
1068 {
1071
1073 assert(currcons != NULL);
1074
1080 }
1081
1082 /* we introduce slackvariables s+ and s- for each constraint to ensure that the problem is feasible
1083 * we want to minimize over the sum of these variables, so set the objective to 1 */
1087
1090
1092 BMSclearMemoryArray(heurdata->integervars, nvars);
1093 heurdata->integervarssize = nvars;
1094 j = 0;
1095
1096 /* here we relax the variables (or indicator constraints, since indicator variables cannot be relaxed) */
1097 for( i = 0; i < nvars; ++i )
1098 {
1100 assert( var != NULL );
1101
1102 if( ! SCIPvarIsActive(var) )
1103 continue;
1104
1105 if( ! SCIPvarIsIntegral(var) )
1106 continue;
1107
1108 heurdata->integervars[j++] = vars[i];
1109
1110 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1111 if( var == NULL )
1112 continue;
1113
1114 /* in this case our variable is an indicator variable */
1115 if( SCIPhashmapGetImage(heurdata->indicators, SCIPhashmapGetImage(heurdata->varsubsciptoscip, var)) != NULL )
1116 {
1117 /* we have to find all the indicator constraints of this variable */
1118 for( k = 0; k < nconsindicator; k++ )
1119 {
1122 SCIP_VAR* negatedvar;
1124
1126 assert(currcons != NULL);
1127
1130
1131 SCIP_CALL( SCIPgetNegatedVar(scip, (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, var), &negatedvar) );
1132
1133 if( indicatorbinvar == SCIPhashmapGetImage(heurdata->varsubsciptoscip, var) || indicatorbinvar == negatedvar )
1134 {
1135 /* case that we have a negated variable */
1137 {
1138 assert(indicatorbinvar == negatedvar);
1139 varobjective = SCIPvarGetObj(negatedvar);
1140 }
1141 else
1142 {
1143 assert(indicatorbinvar != negatedvar);
1145 }
1146
1147 varobjective = heurdata->lambdaobj * REALABS(varobjective);
1148
1150 assert( indicons != NULL );
1151
1153
1154 assert( indicons != NULL );
1156
1161
1164 heurdata->lambdaslack * 100 + varobjective, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1166
1167 /* make a copy of the indicator to relax it if this parameter is set true */
1168 if( heurdata->relaxindicators )
1169 {
1171
1173
1174 SCIP_CALL( SCIPgetNegatedVar(heurdata->subscip, indicatorbinvar, &negatedvar) );
1175
1176 if( SCIPhashmapGetImage(heurdata->indicopymap, indicatorbinvar) == NULL &&
1177 SCIPhashmapGetImage(heurdata->indicopymap, negatedvar) == NULL)
1178 {
1179 SCIP_Bool negated = FALSE;
1180
1182 {
1183 indicatorbinvar = negatedvar;
1184 negated = TRUE;
1185 }
1186
1190
1192
1196
1199 heurdata->lambdaslack * 100 + varobjective, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1201
1204 heurdata->lambdaslack * 100 + varobjective, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1206
1207 /* create linking constraint */
1208 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "linking_%s", SCIPvarGetName(indicatorbinvar));
1209 cons = NULL;
1210 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, 0.0, 0.0,
1212 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indicatorbinvar, 1.0) );
1213 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indicatorcopy, -1.0) );
1214 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indislackvarpos, 1.0) );
1215 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indislackvarneg, -1.0) );
1216
1217 SCIP_CALL( SCIPhashmapInsert(heurdata->relaxconsindi, indicatorbinvar, cons) );
1218 SCIP_CALL( SCIPhashmapInsert(heurdata->relaxconsindi, indicatorcopy, cons) );
1219
1220 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1221 SCIP_CALL( SCIPcaptureCons(heurdata->subscip, cons) );
1222
1224
1225 if ( negated )
1226 {
1228 }
1229
1231
1234 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1235 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1238 }
1239 else
1240 {
1243 else
1244 {
1245 indicatorcopy = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->indicopymap, negatedvar);
1247 }
1248 }
1249
1250 cons = NULL;
1256 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1257
1258 /* delete old indicator constraints so we can relax the indicator variables */
1259 imagecons = (SCIP_CONS*) SCIPhashmapGetImage(heurdata->origsubscipConsMap, (void*)(currcons));
1260 assert(imagecons != NULL);
1262 SCIP_CALL( SCIPhashmapRemove(heurdata->origsubscipConsMap, currcons) );
1263 SCIP_CALL( SCIPhashmapInsert(heurdata->origsubscipConsMap, currcons, cons) );
1265 SCIP_CALL( SCIPdelCons(heurdata->subscip, indicons) );
1266 }
1267
1270 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1271 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1272
1277 }
1278 }
1279 continue;
1280 }
1281
1282 if( heurdata->relaxindicators )
1283 {
1284 /* relax the old indicator variables*/
1285 for( k = 0; k < nvars; k++ )
1286 {
1287 if( SCIPhashmapGetImage(heurdata->indicators, vars[k]) == NULL )
1288 continue;
1289
1290 tmpvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, vars[k]);
1294 }
1295
1296 /* we map all slack variables of indicator constraints to their indicator variables */
1297 conshdlrindicator = SCIPfindConshdlr(scip, "indicator");
1299
1300 /* delete old hashmaps and fill with the new indicators*/
1301 SCIP_CALL( releaseHashmapEntries(scip, heurdata->slacktoindivarsmap, TRUE) );
1303 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->slacktoindivarsmap) );
1304 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->indicators) );
1305
1306 /* fill hashmaps with new values */
1307 for( k = 0; k < nconsindicator; k++ )
1308 {
1311
1313 assert(currcons != NULL);
1314
1317
1321 }
1322 }
1323
1324 /* in this case, we have a normal variable */
1325 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "relax_%s", SCIPvarGetName(var));
1326 cons = NULL;
1327 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, 0.0, 0.0,
1329
1332 heurdata->lambdaslack * 100, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL,NULL) );
1334
1337 heurdata->lambdaslack * 100, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL,NULL) );
1339
1340 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, var, 1.0) );
1341 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarpos, 1.0) );
1342 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarneg, -1.0) );
1343
1344 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1345
1348 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1349 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1350 SCIP_CALL( SCIPhashmapInsert(heurdata->relaxcons, var, cons) );
1353
1354 /* if the var is no indicator, relax it to a continuous variable */
1355 if( SCIPhashmapGetImage(heurdata->indicators, SCIPhashmapGetImage(heurdata->varsubsciptoscip, var)) == NULL )
1356 {
1360 }
1361 }
1362
1363 /* set up relaxation constraints for continuous variables */
1364 if( heurdata->relaxcontvars )
1365 {
1366 for( i = 0; i < nvars; ++i )
1367 {
1369 assert( var != NULL );
1370
1371 if( ! SCIPvarIsActive(var) )
1372 continue;
1373
1374 if( SCIPvarIsIntegral(var) )
1375 continue;
1376
1378 continue;
1379
1381 continue;
1382
1383 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1384 if( var == NULL )
1385 continue;
1386
1387 /* in this case, we have a normal variable */
1388 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "relax_ub_%s", SCIPvarGetName(var));
1389 cons = NULL;
1390 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, -SCIPinfinity(heurdata->subscip), SCIPvarGetUbGlobal(var),
1392
1397
1398 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, var, 1.0) );
1399 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarpos, -1.0) );
1400
1401 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1402 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &cons) );
1403 SCIP_CALL( SCIPhashmapInsert(heurdata->slackvarubMap, var, slackvarpos) );
1405 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1406
1407 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "relax_lb_%s", SCIPvarGetName(var));
1408 cons = NULL;
1409 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, SCIPvarGetLbGlobal(var), SCIPinfinity(heurdata->subscip),
1411
1416
1417 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, var, 1.0) );
1418 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarneg, 1.0) );
1419
1420 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1421 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &cons) );
1422 SCIP_CALL( SCIPhashmapInsert(heurdata->slackvarlbMap, var, slackvarneg) );
1424 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1425
1428 }
1429 }
1430
1431 /* if we have a solution add constraint that the next solution must not be worse than the current one */
1432 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "objbound");
1433 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, -SCIPinfinity(scip),
1435 heurdata->objbound = cons;
1436
1437 for( i = 0; i < nvars; ++i )
1438 {
1440 assert( var != NULL );
1441
1442 if( !SCIPvarIsActive(var) )
1443 continue;
1444
1445 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1446 if( subvar == NULL )
1447 continue;
1448
1450
1451 SCIP_CALL( SCIPchgVarObj(heurdata->subscip, subvar, heurdata->lambdaobj * SCIPvarGetObj(subvar) ) );
1452 }
1453
1454 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1455 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &cons) );
1456
1457 /* do not need varsmap and conssmap anymore */
1460
1461 /* enable SCIP output if needed */
1462 if( heurdata->heurverblevel > 3 )
1463 {
1464 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "display/verblevel", 4) );
1465 }
1466 else
1467 {
1468 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "display/verblevel", 0) );
1469 }
1470
1471 heurdata->nintegervars = j;
1472
1473 return SCIP_OKAY;
1474}
1475
1476
1477/** free sub-SCIP data structure */
1478static
1480 SCIP* scip, /**< SCIP data structure */
1481 SCIP_HEURDATA* heurdata /**< heuristic data structure */
1482 )
1483{
1484 assert(scip != NULL);
1485 assert(heurdata != NULL);
1486 assert(heurdata->subscip != NULL);
1487
1488 heurdata->nsubvars = 0;
1489 heurdata->nvars = 0;
1490
1491 /* free sub-SCIP */
1492 SCIP_CALL( SCIPfree(&heurdata->subscip) );
1493
1494 return SCIP_OKAY;
1495}
1496
1497
1498/** create a solution from the values of current nonlinear program */
1499static
1501 SCIP* scip, /**< SCIP data structure */
1502 SCIP_HEUR* heur, /**< heuristic data structure */
1503 SCIP_SOL** sol /**< buffer to store solution value; if pointing to NULL a new solution is
1504 * created, otherwise values in the given one are overwritten */
1505 )
1506{
1508 SCIP_VAR** subvars;
1510 int i;
1511 int nsubvars;
1512
1513 assert(scip != NULL);
1514 assert(heur != NULL);
1515 assert(sol != NULL);
1516
1517 heurdata = SCIPheurGetData(heur);
1518 assert(heurdata != NULL);
1519
1520 if( *sol == NULL )
1521 {
1522 SCIP_CALL( SCIPcreateSol(scip, sol, heur) );
1523 }
1524
1525 /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
1526 * since constraint copying may have required the copy of variables that are fixed in the main SCIP */
1527 assert(heurdata->nsubvars <= SCIPgetNOrigVars(heurdata->subscip));
1528
1529 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, NULL, NULL, NULL, NULL) );
1530
1531 /* set solution values */
1532 for( i = 0; i < nsubvars; ++i )
1533 {
1534 subvar = subvars[i];
1535 assert(subvar != NULL);
1536
1538
1539 if( !SCIPvarIsActive(subvar) )
1540 continue;
1541
1542 assert(SCIPvarGetNLPSol(subvar) != SCIP_INVALID);/*lint !e777*/
1544 }
1545
1546 return SCIP_OKAY;
1547}
1548
1549#define BIG_VALUE 1E+10
1550
1551/** method to fix the (relaxed) discrete variables */
1552static
1554 SCIP* scip, /**< SCIP data structure */
1555 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
1556 SCIP_SOL* refpoint, /**< point to take fixation of discrete variables from;
1557 * if NULL, then LP solution is used */
1558 SCIP_SOL** transsol /**< pointer to new created solution with fixed values as solution value */
1559 )
1560{
1561 SCIP_Real fixval;
1562 SCIP_VAR* var;
1565 int i;
1566
1568
1569 /* fix discrete variables */
1570 for( i = 0; i < heurdata->nintegervars; i++ )
1571 {
1572 var = heurdata->integervars[i];
1573 assert(var != NULL);
1574
1576 assert(var != NULL);
1577 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1578
1579 if( subvar == NULL )
1580 continue;
1581
1582 if ( SCIPhashmapGetImage(heurdata->indicopymap, subvar) != NULL )
1584
1585 /* if we do not really have a startpoint, we set to 0.0 here and project on bounds below */
1587 fixval = 0.0;
1588 else
1589 {
1590 /* get value of the variables (NULL as refpoint gives the current LP solution, otherwise the start point) */
1591 fixval = SCIPgetSolVal(scip, refpoint, heurdata->integervars[i]);
1592
1593 /* take care that we do not fix variables to very large values (project on bounds below) */
1594 if( REALABS(fixval) > BIG_VALUE )
1595 fixval = 0.0;
1596 else
1597 {
1598 /* round fractional variables to the nearest integer, use exact integral value, if the variable is only
1599 * integral within numerical tolerances */
1600 fixval = SCIPfloor(scip, fixval + 0.5);
1601 }
1602 }
1603
1604 /* adjust value to the global bounds of the corresponding SCIP variable */
1605 fixval = MAX(fixval, SCIPvarGetLbGlobal(heurdata->integervars[i])); /*lint !e666*/
1606 fixval = MIN(fixval, SCIPvarGetUbGlobal(heurdata->integervars[i])); /*lint !e666*/
1607
1608 SCIP_CALL( SCIPsetSolVal(scip, *transsol, heurdata->integervars[i], fixval) );
1609
1610 /* adjust the relaxation constraints to the new fixval */
1612
1613 fixval = MAX(fixval, SCIPvarGetLbGlobal(subvar));/*lint !e666*/
1614 fixval = MIN(fixval, SCIPvarGetUbGlobal(subvar));/*lint !e666*/
1615 if( rcons == NULL )
1616 {
1619 continue;
1620 }
1621
1624 }
1625
1626 return SCIP_OKAY;
1627}
1628
1629/** method to free memory before leaving the heuristic or jumping up in the recursion */
1630static
1632 SCIP* scip, /**< scip data structure */
1633 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
1634 SCIP_SOL* transsol, /**< sol that has to be freed */
1635 SCIP_Real* absranks, /**< array of absolute rank values */
1636 SCIP_Real* ranks, /**< array of rank values */
1637 SCIP_VAR** sortedvars, /**< array of corresponding variables */
1638 SCIP_Bool beforeswitching, /**< did we call this method before or after switching variables? */
1639 SCIP_Bool clearswitchedvars /**< says if we should clear switchedvars or not */
1640 )
1641{
1642 SCIP_VAR** subvars;
1644 SCIP_VAR* var;
1645 SCIP_Real* val;
1646 int nsubvars;
1647 int nsubbinvars;
1648 int nsubintvars;
1649 int i;
1650
1651 if( clearswitchedvars )
1652 {
1653 /* free memory of the solution values in the hashmaps */
1654 for( i = 0; i < heurdata->nintegervars; i++ )
1655 {
1656 var = heurdata->integervars[i];
1657
1658 if( SCIPhashmapGetImage(heurdata->slacktoindivarsmap, var) != NULL )
1659 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->slacktoindivarsmap, var);
1660
1661 val = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars, var);
1662 if( val != NULL )
1663 {
1664 SCIPfreeBlockMemoryArray(heurdata->subscip, &val, 1);
1665 }
1666
1667 val = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars2, var);
1668 if( val != NULL )
1669 {
1670 SCIPfreeBlockMemoryArray(heurdata->subscip, &val, 1);
1671 }
1672 }
1673
1674 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->switchedvars) );
1675 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->switchedvars2) );
1676 }
1677
1680 SCIPfreeBufferArrayNull( scip, &sortedvars );
1681
1682 if( transsol != NULL )
1683 {
1685 }
1686
1687 if( beforeswitching )
1688 {
1690 }
1691
1692 /* undo fixing of discrete variables in sub-SCIP */
1693 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, &nsubbinvars, &nsubintvars, NULL, NULL) );
1694
1695 /* set bounds of discrete variables to original values */
1696 for( i = nsubbinvars + nsubintvars - 1; i >= 0; --i )
1697 {
1698 subvar = subvars[i];
1700
1701 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, subvar);
1702
1703 if (SCIPhashmapGetImage(heurdata->indicopymapback, subvar) != NULL)
1704 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, SCIPhashmapGetImage(heurdata->indicopymapback, subvar));
1705
1706 assert(var != NULL);
1707
1710 }
1711
1712 return SCIP_OKAY;
1713}
1714
1715/** computes the ranks, saves them into an array and sorts the variables according to absolute ranks */
1716static
1718 SCIP* scip, /**< scip data structure */
1719 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
1720 SCIP_Real* absranks, /**< array of absolute rank values */
1721 SCIP_Real* ranks, /**< array of rank values */
1722 SCIP_VAR** sortedvars /**< array of corresponding variables */
1723 )
1724{
1726 SCIP_CONS* relaxcons;
1730 SCIP_VAR* var;
1731 SCIP_Real* dualvalue;
1732 int nconsindicator;
1733 int j;
1734 int k;
1735
1736 conshdlrindicator = SCIPfindConshdlr(scip, "indicator");
1738
1739 /* Now we compute the rank of each variable */
1740 for( j = 0; j < heurdata->nintegervars; j++ )
1741 {
1742 sortedvars[j] = heurdata->integervars[j];
1743 ranks[j] = 0;
1744 absranks[j] = 0;
1745
1746 if( sortedvars[j] == NULL )
1747 break;
1748
1749 var = SCIPvarGetTransVar(sortedvars[j]);
1750 assert(var != NULL);
1751
1752 /* globally fixed variables get rank 0 */
1754 {
1755 ranks[j] = 0;
1756 continue;
1757 }
1758 else
1759 {
1760 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1761 assert(var != NULL);
1762 relaxcons = (SCIP_CONS*)SCIPhashmapGetImage(heurdata->relaxcons, (void*)(var));
1763
1764 /* get ranks */
1765 if( relaxcons != NULL )
1766 {
1767 SCIP_CALL( SCIPgetTransformedCons(heurdata->subscip, relaxcons, &transcons) );
1768 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)transcons);
1769
1770 if( dualvalue == NULL )
1771 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)(relaxcons));
1772
1773 if( dualvalue == NULL )
1774 continue;
1775
1776 assert(dualvalue != NULL);
1777 ranks[j] = (*dualvalue);
1778 }
1779 else /* if we have an indicator variable */
1780 {
1781 assert(ranks[j] == 0.0);
1782
1783 if (SCIPhashmapGetImage(heurdata->relaxconsindi, (void*)(var)) != NULL)
1784 {
1785 subcons = (SCIP_CONS*)SCIPhashmapGetImage(heurdata->relaxconsindi, (void*)(var));
1786
1787 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)(subcons));
1788
1789 if( dualvalue == NULL )
1790 continue;
1791
1792 assert(dualvalue != NULL);
1793
1794 ranks[j] = (*dualvalue);
1795 }
1796
1797 /* compute the rank of the indicators, we take the highest dualvalue of an indicator constraint */
1798 for( k = 0; k < nconsindicator; k++ )
1799 {
1803
1805 assert(currcons != NULL);
1806
1809
1810 if( indicatorbinvar == (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, var)
1812 {
1814 assert(indicons != NULL);
1815
1816 subcons = (SCIP_CONS*)SCIPhashmapGetImage(heurdata->origsubscipConsMap, (void*)(indicons));
1817 assert(subcons != NULL);
1818
1820 assert(subcons != NULL);
1821
1822 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)(subcons));
1823
1824 if( dualvalue == NULL )
1825 continue;
1826
1827 assert(dualvalue != NULL);
1828
1829 if( REALABS(ranks[j]) < REALABS(*dualvalue) )
1830 ranks[j] = (*dualvalue);
1831 }
1832 }
1833 }
1834 }
1835
1836 /* take the absolute value of each rank */
1837 absranks[j] = REALABS(ranks[j]);
1838 }
1839
1840 SCIPsortDownRealRealPtr(absranks, ranks, (void**)sortedvars, heurdata->nintegervars);
1841
1842 return SCIP_OKAY;
1843}
1844
1845/** compute maximal slack of a variable */
1846static
1848 SCIP* scip, /**< scip data structure */
1849 SCIP_HEURDATA* heurdata /**< heuristic data structure */
1850 )
1851{
1854 SCIP_SOL* bestsol;
1855 SCIP_Real maxslack;
1856 int i;
1857 int nsubvars;
1858 SCIP_Bool maxslackset;
1859
1860 /* compute maximal slack */
1861 nsubvars = SCIPgetNOrigVars(heurdata->subscip);
1862
1863 /* save information about maximal violation */
1864 maxvar = NULL;
1865 maxslack = -SCIPinfinity(heurdata->subscip);
1867
1868 bestsol = SCIPgetBestSol(heurdata->subscip);
1869
1870 /* search for variable with maximal slack */
1871 for( i = 0; i < nsubvars; i++ )
1872 {
1873 subvar = SCIPgetOrigVars(heurdata->subscip)[i];
1874 if( subvar == NULL)
1875 continue;
1876
1877 /* if variable is slack */
1878 if( SCIPhashmapGetImage(heurdata->slack2var, subvar) != NULL )
1879 {
1880 if( heurdata->isnlp )
1881 {
1882 if( maxslack < SCIPvarGetNLPSol(subvar) )
1883 {
1884 maxslack = SCIPvarGetNLPSol(subvar);
1885 maxvar = subvar;
1886 maxslackset = TRUE;
1887 }
1888 }
1889 else
1890 {
1891 assert(bestsol != NULL);
1892 if( maxslack < SCIPgetSolVal(heurdata->subscip, bestsol, subvar) )
1893 {
1894 maxslack = SCIPgetSolVal(heurdata->subscip, bestsol, subvar);
1895 maxvar = subvar;
1896 maxslackset = TRUE;
1897 }
1898 }
1899 }
1900 }
1901
1902 if( ! maxslackset )
1903 {
1904 maxslack = 0;
1905 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "could not find a variable with maximal slack!\n");
1906 }
1907
1908 assert(maxslack >= 0);
1909
1910 if( heurdata->heurverblevel > 0 && maxslackset )
1911 {
1912 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "maximum slack: %f %s\n", maxslack, SCIPvarGetName(maxvar));
1913 }
1914
1915 return maxslack;
1916}
1917
1918/** method called after a solution is found which is feasible in the original problem, stores it and cleans up */
1919static
1921 SCIP* scip, /**< SCIP data structure */
1922 SCIP_HEUR* heur, /**< heuristic data */
1923 SCIP_RESULT* result, /**< pointer to store result of: did not run, solution found,
1924 * no solution found, or fixing is infeasible (cutoff) */
1925 SCIP_SOL* transsol, /**< solution to fix variables */
1926 SCIP_SOL* bestsol /**< solution we create a original scip solution from */
1927 )
1928{
1930 SCIP_SOL* sol = NULL;
1931 SCIP_Bool stored;
1932 SCIP_Real primalobj;
1933
1934 /* get heuristic's data */
1935 heurdata = SCIPheurGetData(heur);
1936 assert(heurdata != NULL);
1937 SCIP_CALL( createSolFromSubScipSol(scip, heur, &sol, bestsol) );
1938
1939 /* if this happens, there was an ipopt error - stop the heuristic for there is no good starting point */
1941 {
1943 heurdata->solfound = TRUE;
1944
1945 /* here we can be sure that we are in the nlp case */
1946 assert( heurdata->isnlp );
1947 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) );
1948
1950
1951 /* don't use the heuristic anymore if IPOPT doesn't give proper solution
1952 * (normally then this happens in most ipopt runs that may follow) */
1953 SCIPheurSetFreq(heur, -1);
1954
1955 SCIPdebugMsg(scip, "return10 : turn off heuristic, ipopt error\n");
1956
1957 if( heurdata->heurverblevel > 1 )
1958 {
1959 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "turn off heuristic due to ipopt error");
1960 }
1961
1962 return SCIP_OKAY;
1963 }
1964
1966
1967 /* if there is a solution, try to add solution to storage and free it */
1968 if( sol != NULL )
1969 {
1971
1972 if( heurdata->heurverblevel > 0 )
1973 {
1975 }
1976 else
1977 {
1979 }
1980 }
1981 else
1982 stored = FALSE;
1983
1984 if( stored && heurdata->heurverblevel > 1 )
1985 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "accepted solution\n");
1986
1987 if( heurdata->isnlp )
1988 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) );
1989
1991
1992 if( !stored )
1993 {
1995 heurdata->solfound = TRUE;
1996
1997 if( heurdata->heurverblevel >= 1 )
1998 {
1999 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "return9 : found solution that was not stored, objective %f\n", primalobj);/*lint !e644*/
2000 }
2001
2002 return SCIP_OKAY;
2003 }
2004
2005 heurdata->prevInfeasible = FALSE;
2006 heurdata->solfound = TRUE;
2008
2009 if( heurdata->heurverblevel >= 1 )
2010 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "return 9 : found and stored new solution, objective %lf\n", primalobj);
2011
2012 return SCIP_OKAY;
2013}
2014
2015/** main procedure of the dualval heuristic */
2017 SCIP* scip, /**< original SCIP data structure */
2018 SCIP_HEUR* heur, /**< heuristic data structure */
2019 SCIP_RESULT* result, /**< pointer to store result of: did not run, solution found, no solution
2020 * found, or fixing is infeasible (cutoff) */
2021 SCIP_SOL* refpoint /**< point to take fixation of discrete variables from; if NULL, then LP
2022 * solution is used */
2023 )
2024{
2026 SCIP_NLROW* nlrow;
2028 SCIP_SOL* bestsol;
2031 SCIP_VAR** subvars;
2032 SCIP_VAR** sortedvars;
2033 SCIP_VAR* var;
2035 SCIP_VAR* v;
2036 SCIP_RETCODE retcode;
2037 SCIP_Real* absranks;
2038 SCIP_Real* ranks;
2039 SCIP_Real* startpoint;
2040 SCIP_Real* dualval;
2041 SCIP_Real* lastval;
2042 SCIP_Real* seclastval;
2043 SCIP_Real* newval;
2044 SCIP_Real bound;
2045 SCIP_Real maxslack;
2046 SCIP_Real objvalue;
2047 int i;
2048 int k;
2049 int nsubvars;
2050 int nsubbinvars;
2051 int nsubintvars;
2052 int nsubconss;
2053 int maxequalranks;
2054
2055 assert(scip != NULL);
2056 assert(heur != NULL);
2057
2058 /* dio not run without nlp solver */
2059 if( SCIPgetNNlpis(scip) <= 0 )
2060 return SCIP_OKAY;
2061
2062 /* get heuristic's data */
2063 heurdata = SCIPheurGetData(heur);
2064 assert(heurdata != NULL);
2065
2066 /* don't use the heuristic, if the gap is small so we don't expect to get better solutions than already found */
2067 if( SCIPgetGap(scip) * 100 < heurdata->mingap )
2068 {
2069 SCIPdebugMsg(scip, "return13 : gap is less than mingap\n");
2070 return SCIP_OKAY;
2071 }
2072
2073 /* in the mode 'onlyleaves' don't run the heuristic if we are not in a leaf of the B&B tree */
2074 if( heurdata->onlyleaves && (SCIPgetNLPBranchCands(scip) != 0 || SCIPgetNPseudoBranchCands(scip) != 0) )
2075 return SCIP_OKAY;
2076
2077 /* try to setup subscip if not tried before */
2078 if( heurdata->subscip == NULL && !heurdata->triedsetupsubscip )
2079 {
2081 }
2082
2083 /* quit the recursion if we have found a solution */
2084 if( heurdata->solfound )
2085 {
2086 SCIPdebugMsg(scip, "return1 : already found solution \n");
2087 return SCIP_OKAY;
2088 }
2089
2091
2092 /* not initialized */
2093 if( heurdata->subscip == NULL )
2094 {
2095 SCIPdebugMsg(scip, "return2 : subscip is NULL\n");
2096 return SCIP_OKAY;
2097 }
2098
2099 assert(heurdata->nsubvars > 0);
2100 assert(heurdata->varsubsciptoscip != NULL);
2101
2102 /* fix discrete variables in sub-SCIP */
2105
2106 if( heurdata->onlycheaper && !SCIPisInfinity(scip, bound) )
2107 {
2108 SCIP_CALL( SCIPchgRhsLinear( heurdata->subscip, heurdata->objbound, bound) );
2109 }
2110
2111 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "presolving/maxrounds", 1) );
2112 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "propagating/maxroundsroot", 0) );
2113
2114 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 1LL) );
2115 SCIP_CALL( SCIPpresolve(heurdata->subscip) );
2116
2118 {
2119 SCIPdebugMsg(scip, "return 4 : subscip is infeasible\n");
2120
2122 heurdata->prevInfeasible = TRUE;
2124
2125 return SCIP_OKAY;
2126 }
2127
2128 /* If no NLP was constructed, then there were no nonlinearities after presolve.
2129 * So we increase the nodelimit to 1 and hope that SCIP will find some solution to this probably linear subproblem.
2130 */
2131 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 0LL) );
2132 retcode = SCIPsolve(heurdata->subscip);
2133 heurdata->isnlp = TRUE;
2134
2135 bestsol = NULL;
2136
2137 /* we have no dualvalues, so give up */
2139 {
2142
2143 return SCIP_OKAY;
2144 }
2145
2146 if( ! SCIPisNLPConstructed(heurdata->subscip) && retcode == SCIP_OKAY )
2147 {
2148 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 1LL) );
2149 SCIP_CALL( SCIPsolve(heurdata->subscip) );
2150 heurdata->isnlp = FALSE;
2151 bestsol = SCIPgetBestSol(heurdata->subscip);
2152 }
2153
2154 if( heurdata->isnlp )
2155 {
2156 /* add non-combinatorial linear constraints from subscip into subNLP */
2158
2160
2161 /* set starting values (=refpoint, if not NULL; otherwise LP solution (or pseudo solution)) */
2162 for( i = 0; i < SCIPgetNNLPVars(heurdata->subscip); ++i )
2163 {
2164 SCIP_Real scalar = 1.0;
2165 SCIP_Real constant = 0.0;
2166
2167 subvar = SCIPgetNLPVars(heurdata->subscip)[i];
2168
2169 /* gets corresponding original variable */
2170 SCIP_CALL( SCIPvarGetOrigvarSum(&subvar, &scalar, &constant) );
2171 if( subvar == NULL )
2172 {
2173 startpoint[i] = constant;
2174 continue;
2175 }
2176
2177 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, subvar);
2178 if( var == NULL || REALABS( SCIPgetSolVal(scip, refpoint, var) ) > 1.0e+12 )
2179 {
2180 SCIP_Real tmpmax;
2181 tmpmax = MAX( 0.0, SCIPvarGetLbGlobal(subvar) );/*lint !e666*/
2182 startpoint[i] = MIN( tmpmax, SCIPvarGetUbGlobal(subvar) );/*lint !e666*/
2183 }
2184 else
2185 /* scalar*subvar+constant corresponds to nlpvar[i], so nlpvar[i] gets value scalar*varval+constant */
2186 startpoint[i] = scalar * SCIPgetSolVal(scip, refpoint, var) + constant;
2187 }
2188
2190
2191 /* don't need startpoint array anymore */
2193
2194 SCIP_CALL( SCIPsolveNLP(heurdata->subscip, .verblevel = (unsigned short)heurdata->nlpverblevel) ); /*lint !e666*/
2196
2197 /* in this case there was an error in ipopt, we try to give another startpoint */
2199 {
2201 SCIP_CALL( SCIPsolveNLP(heurdata->subscip, .verblevel = (unsigned short)heurdata->nlpverblevel) ); /*lint !e666*/
2203 }
2204
2207
2208 /* free memory of all entries and clear the hashmap before filling it */
2209 for( i = 0; i < nsubconss; i++ )
2210 {
2211 dualval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, subconss[i]);
2213 }
2214 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->dualvalues) );
2215
2216 /* save the dualvalues from our nlp solution */
2217 for( i = 0; i < nsubconss; i++ )
2218 {
2220
2222
2223 if( transcons == NULL )
2224 continue;
2225
2226 if( SCIPconsGetHdlr(transcons) != SCIPfindConshdlr(heurdata->subscip, "linear") )
2227 continue;
2228
2229 nlrow = (SCIP_NLROW*)SCIPhashmapGetImage(heurdata->conss2nlrow, transcons);
2230
2231 if (nlrow != NULL)
2232 {
2233 SCIP_CALL( SCIPallocBlockMemoryArray(heurdata->subscip, &dualval, 1) ); /*lint !e506*/
2234 *dualval = SCIPnlrowGetDualsol(nlrow);
2235 }
2236 else
2237 {
2238 SCIP_CALL( SCIPallocBlockMemoryArray(heurdata->subscip, &dualval, 1) ); /*lint !e506*/
2239 *dualval = 0;
2240 }
2241
2243 }
2244
2245 bestsol = NULL;
2246 SCIP_CALL( createSolFromNLP(heurdata->subscip, heur, &bestsol) );
2247 }
2248
2249 /* if we are infeasible, we can't do anything*/
2251 {
2252 SCIPdebugMsg(scip, "return4 : the subscip is infeasible\n");
2253
2255
2256 return SCIP_OKAY;
2257 }
2258
2259 maxslack = maximalslack(scip, heurdata);
2260 SCIPdebugMsg(scip, "origObj: %f\n", SCIPgetSolOrigObj(heurdata->subscip, bestsol));
2261 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, &nsubbinvars, &nsubintvars, NULL, NULL) );
2262 objvalue = 0.0;
2263 assert(bestsol != NULL);
2264
2265 /* save information about maximal violation */
2266 for( i = 0; i < nsubvars; i++ )
2267 {
2268 subvar = SCIPgetOrigVars(heurdata->subscip)[i];
2269
2270 if( SCIPhashmapGetImage(heurdata->slack2var, subvar) == NULL )
2271 objvalue += SCIPvarGetObj(subvar) * SCIPgetSolVal(heurdata->subscip, bestsol, subvar);
2272 }
2273
2274 /* we stop the heuristic if it does not come "closer" to a feasible solution*/
2275 if( heurdata->forceimprovements )
2276 {
2277 if( SCIPisGE(scip, SCIPgetSolOrigObj(heurdata->subscip, bestsol) - objvalue, heurdata->prevobjective) && maxslack > 0 )
2278 {
2279 heurdata->nonimprovingRounds++;
2280 SCIPdebugMsg(scip, "nonimpr rounds %d prevobj %f \n", heurdata->nonimprovingRounds, heurdata->prevobjective);
2281
2282 /* leave, if we have not improved some iterations*/
2283 if( heurdata->nonimprovingRounds > heurdata->maxcalls/8 )
2284 {
2286
2287 if( heurdata->isnlp )
2288 {
2289 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) );
2290 }
2291
2293
2294 heurdata->solfound = TRUE;
2295 heurdata->switchdifferent = TRUE;
2296
2297 SCIPdebugMsg(scip, "return11 : solution did not improve\n");
2298
2299 return SCIP_OKAY;
2300 }
2301 }
2302 }
2303
2304 heurdata->prevobjective = SCIPgetSolOrigObj(heurdata->subscip, bestsol) - objvalue;
2305
2306 /* in this case we found a feasible solution, store it, clean up and stop the heuristic*/
2307 if( SCIPisFeasLE(heurdata->subscip, maxslack, 0.0) )
2308 return storeSolution(scip, heur, result, transsol, bestsol);
2309
2310 SCIP_CALL( SCIPallocBufferArray(scip, &ranks, heurdata->nintegervars) );
2311 SCIP_CALL( SCIPallocBufferArray(scip, &sortedvars, heurdata->nintegervars) );
2313
2314 /* compute ranks and sort them in non-increasing order */
2315 SCIP_CALL( computeRanks(scip, heurdata, absranks, ranks, sortedvars) );
2316
2317 /* print out the highest ranks */
2318 if( heurdata->heurverblevel > 1 )
2319 {
2320 k = heurdata->rankvalue;
2321
2322 if( heurdata->nintegervars < heurdata->rankvalue )
2323 k = heurdata->nintegervars;
2324
2325 for( i = 0; i < k; i++ )
2326 {
2327 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%i. rank: %f name: %s\n", i, ranks[i], SCIPvarGetName(sortedvars[i]));
2328 }
2329 }
2330
2331 /* free solution */
2332 if( heurdata->isnlp )
2333 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) );
2334
2335 /* we don't allow more than a third of the variables to have the same rank */
2336 maxequalranks = MIN(heurdata->maxequalranks, heurdata->nintegervars/3);
2337
2338 if( heurdata->maxequalranks >= 0 && SCIPisFeasEQ(heurdata->subscip, REALABS(ranks[0]), REALABS(ranks[maxequalranks])) )
2339 {
2341
2342 SCIPdebugMsg(scip, "return12 : equal maxranks\n");
2343
2345 return SCIP_OKAY;
2346 }
2347
2348 /* now we can start switching the variable values */
2350
2351 /* set bounds of fixed discrete variables to original values so we can switch */
2352 for( k = 0; k < heurdata->nintegervars; ++k )
2353 {
2354 var = heurdata->integervars[k];
2355 if( var == NULL )
2356 break;
2357
2359 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
2360
2362 if( rcons != NULL )
2363 continue;
2364
2365 assert(var != NULL);
2366 assert(subvar != NULL);
2367
2368 if ( SCIPhashmapGetImage(heurdata->indicopymap, subvar) != NULL )
2370
2373 }
2374
2375 /* switch variable with maximum ranking if possible */
2376 for( i = 0; i < heurdata->nintegervars; i++ )
2377 {
2378 v = sortedvars[i];
2379 SCIP_CALL( SCIPallocBlockMemoryArray(heurdata->subscip, &newval, 1) ); /*lint !e506*/
2380
2381 /* compute the new value of the variable */
2382
2383 /* if we have an indicator constraint, we turn it off */
2384 if( SCIPhashmapGetImage(heurdata->slacktoindivarsmap, v) != NULL )
2385 {
2386 /* get the indicator var of this constraint */
2387 v = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->slacktoindivarsmap, v);
2388
2389 /* set the value to 0 */
2390 SCIP_CALL( SCIPsetSolVal(scip, transsol, v, 0.0) );
2391 if( heurdata->heurverblevel > 1 )
2392 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Setting value of %s%s to 0\n", SCIPvarIsNegated(v) ? "(negated) " : " ", SCIPvarGetName(v));
2393
2394 *newval = 0.0;
2395 SCIP_CALL( SCIPhashmapInsert(heurdata->switchedvars, v, newval) );
2396 }
2397 else
2398 {
2399 if( ranks[i] > 0 )
2400 {
2401 if( SCIPvarIsBinary(v) && SCIPisEQ(scip, 1.0, SCIPgetSolVal(scip, transsol, v)) )
2402 continue;
2403
2404 /* ignore fixed vars in input */
2406 continue;
2407
2408 *newval = SCIPgetSolVal(scip, transsol, v) + 1;
2409 }
2410 else
2411 {
2412 if( SCIPvarIsBinary(v) && SCIPisEQ(scip, 0.0, SCIPgetSolVal(scip, transsol, v)) )
2413 continue;
2414
2416 continue;
2417
2418 *newval = SCIPgetSolVal(scip, transsol, v) - 1;
2419 }
2420 }
2421 lastval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars, v);
2422 seclastval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars2, v);
2423
2424 /* we don't want to set a variable to a value it already had,or set a binary variable more than once */
2425 if( (lastval != NULL && (SCIPvarIsBinary(v) || SCIPisFeasEQ(scip, *lastval, *newval))) || (seclastval != NULL && SCIPisFeasEQ(scip, *seclastval, *newval)) )
2426 {
2427 SCIPfreeBlockMemoryArray(heurdata->subscip, &newval, 1);
2428 continue;
2429 }
2430 else /* update the switchedvars values, switchedvars2 is the second last and switchedvars the last value */
2431 {
2432 if( seclastval != NULL )
2434
2435 SCIP_CALL( SCIPhashmapRemove(heurdata->switchedvars2, v) );
2436 SCIP_CALL( SCIPhashmapInsert(heurdata->switchedvars2, v, lastval) );
2437 SCIP_CALL( SCIPhashmapRemove(heurdata->switchedvars, v) );
2438 SCIP_CALL( SCIPhashmapInsert(heurdata->switchedvars, v, newval) );
2439
2440 if( heurdata->heurverblevel > 1 )
2441 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Setting value of %s from %f to %f\n", SCIPvarGetName(v), SCIPgetSolVal(scip, transsol, v), *newval);
2442
2443 SCIP_CALL( SCIPsetSolVal(scip, transsol, v, *newval) );
2444 }
2445
2446 /* if we have exceeded our iterations limit give up without any solution */
2447 if( heurdata->usedcalls >= heurdata->maxcalls )
2448 {
2449 SCIPdebugMsg(scip, "return5 : reached iteration limit\n");
2450
2453 return SCIP_OKAY;
2454 }
2455
2456 heurdata->usedcalls++;
2457
2458 if( heurdata->heurverblevel > 1 )
2459 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "----- Total Calls: %d\n", heurdata->usedcalls);
2460
2461 /* recursive call of the heuristic */
2463
2464 /* just to go up in the recursion */
2465 if( *result == SCIP_DIDNOTFIND || heurdata->solfound || heurdata->prevInfeasible )
2466 {
2467 SCIPdebugMsg(scip, "return6 : go up\n");
2468
2469 /* here we only go up one step and try another switch (switch the same variables again is forbidden
2470 * since they are contained in switchedvars) */
2471 if( heurdata->switchdifferent )
2472 {
2473 heurdata->switchdifferent = FALSE;
2474 heurdata->solfound = FALSE;
2476 heurdata->nonimprovingRounds -= 2;
2477 }
2478
2479 if( heurdata->prevInfeasible )
2480 {
2481 heurdata->prevInfeasible = FALSE;
2482 heurdata->solfound = FALSE;
2484 heurdata->nonimprovingRounds++;
2485 }
2486
2488 return SCIP_OKAY;
2489 }
2490 }
2491
2492 if( heurdata->subscip == NULL )
2493 {
2494 /* something horrible must have happened that we decided to give up completely on this heuristic */
2496 SCIPdebugMsg(scip, "return7 : subscip was set NULL\n");
2497
2499 return SCIP_OKAY;
2500 }
2501 assert(!SCIPisTransformed(heurdata->subscip));
2502
2503 SCIPdebugMsg(scip, "return8 : cannot switch any variable\n");
2504
2506
2508 return SCIP_OKAY;
2509}
2510
2511
2512/* Callback methods of primal heuristic */
2513
2514/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
2515static
2517{
2519
2520 assert(scip != NULL);
2521 assert(heur != NULL);
2522
2523 heurdata = SCIPheurGetData(heur);
2524
2526
2527 return SCIP_OKAY;
2528}
2529
2530
2531/** initialization method of primal heuristic (called after problem was transformed) */
2532static
2534{ /*lint --e{715}*/
2536
2537 assert(scip != NULL);
2538 assert(heur != NULL);
2539
2540 /* skip setting up sub-SCIP if heuristic is disabled or we do not want to run the heuristic */
2541 if( SCIPheurGetFreq(heur) < 0 )
2542 return SCIP_OKAY;
2543
2544 SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrestarts", 0) );
2545
2546 heurdata = SCIPheurGetData(heur);
2547 assert(heurdata != NULL);
2548 assert(heurdata->subscip == NULL);
2549 assert(!heurdata->triedsetupsubscip);
2550
2551 /* create sub-SCIP for later use */
2553
2554 /* creating sub-SCIP may fail if the solver interfaces did not copy into subscip */
2555 if( heurdata->subscip == NULL )
2556 return SCIP_OKAY;
2557
2558 /* if the heuristic is called at the root node, we want to be called directly after the initial root LP solve */
2559 if( SCIPheurGetFreqofs(heur) == 0 )
2561
2562 SCIP_CALL( SCIPhashmapCreate(&heurdata->dualvalues, SCIPblkmem(scip), 512) );
2563
2564 return SCIP_OKAY;
2565}
2566
2567/** deinitialization method of primal heuristic (called before transformed problem is freed) */
2568static
2570{ /*lint --e{715}*/
2573 SCIP_Real* dualval;
2574 int i;
2575 int nsubconss;
2576
2577 assert(scip != NULL);
2578 assert(heur != NULL);
2579
2580 heurdata = SCIPheurGetData(heur);
2581 assert(heurdata != NULL);
2582
2583 SCIPfreeBlockMemoryArrayNull(scip, &heurdata->integervars, heurdata->integervarssize);
2584
2585 if( heurdata->subscip != NULL)
2586 {
2589
2590 /* free memory of all entries and clear the hashmap before filling it */
2591 for( i = 0; i < nsubconss; i++ )
2592 {
2593 dualval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, subconss[i]);
2595 }
2596 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->dualvalues) );
2597 SCIPhashmapFree(&heurdata->dualvalues);
2598
2599 if( heurdata->varsciptosubscip != NULL )
2600 {
2601 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->varsciptosubscip, TRUE) );
2602
2603 SCIPhashmapFree(&heurdata->varsciptosubscip);
2604 }
2605 if( heurdata->origsubscipConsMap != NULL )
2606 {
2607 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->origsubscipConsMap, FALSE) );
2608
2609 SCIPhashmapFree(&heurdata->origsubscipConsMap);
2610 }
2611 if( heurdata->relaxcons != NULL )
2612 {
2613 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->relaxcons, FALSE) );
2614
2615 SCIPhashmapFree(&heurdata->relaxcons);
2616 }
2617 if( heurdata->conss2nlrow != NULL )
2618 {
2619 SCIP_CALL( releaseHashmapNLPRows(heurdata->subscip, heurdata->conss2nlrow) );
2620
2621 SCIPhashmapFree(&heurdata->conss2nlrow);
2622 }
2623 if( heurdata->slack2var != NULL )
2624 {
2625 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->slack2var, TRUE) );
2626
2627 SCIPhashmapFree(&heurdata->slack2var);
2628 }
2629 if( heurdata->indicopymap != NULL )
2630 {
2631 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->indicopymap, TRUE) );
2632
2633 SCIPhashmapFree(&heurdata->indicopymap);
2634 }
2635 if( heurdata->indicopymapback != NULL )
2636 {
2637 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->indicopymapback, TRUE) );
2638
2639 SCIPhashmapFree(&heurdata->indicopymapback);
2640 }
2641 if( heurdata->relaxconsindi != NULL )
2642 {
2643 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->relaxconsindi, FALSE) );
2644
2645 SCIPhashmapFree(&heurdata->relaxconsindi);
2646 }
2647 if( heurdata->slackvarlbMap != NULL )
2648 {
2649 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->slackvarlbMap, TRUE) );
2650
2651 SCIPhashmapFree(&heurdata->slackvarlbMap);
2652 }
2653 if( heurdata->slackvarubMap != NULL )
2654 {
2655 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->slackvarubMap, TRUE) );
2656
2657 SCIPhashmapFree(&heurdata->slackvarubMap);
2658 }
2659
2660 if( heurdata->subscip != NULL )
2661 {
2663 }
2664 }
2665
2666 if( heurdata->varsubsciptoscip != NULL )
2667 {
2668 SCIP_CALL( releaseHashmapEntries(scip, heurdata->varsubsciptoscip, TRUE) );
2669
2670 SCIPhashmapFree(&heurdata->varsubsciptoscip);
2671 }
2672 if( heurdata->slacktoindivarsmap != NULL )
2673 {
2674 SCIP_CALL( releaseHashmapEntries(scip, heurdata->slacktoindivarsmap, TRUE) );
2675
2676 SCIPhashmapFree(&heurdata->slacktoindivarsmap);
2677 }
2678 if( heurdata->indicators != NULL )
2679 {
2681
2682 SCIPhashmapFree(&heurdata->indicators);
2683 }
2684 if( heurdata->switchedvars != NULL )
2685 {
2686 SCIPhashmapFree(&heurdata->switchedvars);
2687 }
2688 if( heurdata->switchedvars2 != NULL )
2689 {
2690 SCIPhashmapFree(&heurdata->switchedvars2);
2691 }
2692
2693 /* reset some flags and counters */
2694 heurdata->triedsetupsubscip = FALSE;
2695 heurdata->usedcalls = 0;
2696 heurdata->solfound = FALSE;
2697 heurdata->prevInfeasible = FALSE;
2698
2699 assert(heurdata->subscip == NULL);
2700 assert(heurdata->varsubsciptoscip == NULL);
2701 assert(heurdata->varsciptosubscip == NULL);
2702
2703 return SCIP_OKAY;
2704}
2705
2706/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
2707static
2709{
2711
2712 assert(scip != NULL);
2713 assert(heur != NULL);
2714
2715 /* skip setting up sub-SCIP if heuristic is disabled or we do not want to run the heuristic */
2716 if( SCIPheurGetFreq(heur) < 0 )
2717 return SCIP_OKAY;
2718
2719 heurdata = SCIPheurGetData(heur);
2720 assert(heurdata != NULL);
2721
2722 /* creating sub-SCIP may fail if the solver interfaces did not copy into subscip */
2723 if( heurdata->subscip == NULL )
2724 return SCIP_OKAY;
2725
2726 /* if the heuristic is called at the root node, we want to be called directly after the initial root LP solve */
2727 if( SCIPheurGetFreqofs(heur) == 0 )
2729
2730 return SCIP_OKAY;
2731}
2732
2733
2734/** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
2735static
2737{
2738 assert(scip != NULL);
2739 assert(heur != NULL);
2740
2742
2743 return SCIP_OKAY;
2744}
2745
2746
2747/** execution method of primal heuristic */
2748static
2750{ /*lint --e{715}*/
2752
2753 assert(scip != NULL);
2754 assert(heur != NULL);
2755 assert(result != NULL);
2756
2757 /* get heuristic's data */
2758 heurdata = SCIPheurGetData(heur);
2759 assert(heurdata != NULL);
2760
2761 /* obviously, we did not do anything yet */
2763
2764 /* init data */
2765 heurdata->usedcalls = 0;
2766 heurdata->prevInfeasible = FALSE;
2767 heurdata->solfound = FALSE;
2768 heurdata->nonimprovingRounds = 0;
2769 heurdata->prevobjective = INT_MAX;
2770
2772
2773 /* SCIP does not like cutoff as return, so we say didnotfind, since we did not find a solution */
2774 if( *result == SCIP_CUTOFF )
2776
2777 /* reset timing, if it was changed temporary (at the root node) */
2778 if( heurtiming != HEUR_TIMING )
2780
2781 return SCIP_OKAY;
2782}
2783
2784
2785/* primal heuristic specific interface methods */
2786
2787/** creates the dualval primal heuristic and includes it in SCIP */
2789 SCIP* scip /**< SCIP data structure */
2790 )
2791{
2793 SCIP_HEUR* heur = NULL;
2794
2795 /* create dualval primal heuristic data */
2798
2799 /* include primal heuristic */
2800
2801 /* use SCIPincludeHeurBasic() plus setter functions if you want to set callbacks one-by-one and your code should
2802 * compile independent of new callbacks being added in future SCIP versions */
2806
2807 assert(heur != NULL);
2808
2809 /* set non fundamental callbacks via setter functions */
2815
2816 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/forceimprovements",
2817 "exit if objective doesn't improve",
2818 &heurdata->forceimprovements, TRUE, DEFAULT_FORCEIMPROVEMENTS, NULL, NULL) );
2819
2820 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlycheaper",
2821 "add constraint to ensure that discrete vars are improving",
2822 &heurdata->onlycheaper, TRUE, DEFAULT_ONLYCHEAPER, NULL, NULL) );
2823
2824 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlyleaves",
2825 "disable the heuristic if it was not called at a leaf of the B&B tree",
2826 &heurdata->onlyleaves, FALSE, DEFAULT_ONLYLEAVES, NULL, NULL) );
2827
2828 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/relaxindicators",
2829 "relax the indicator variables by introducing continuous copies",
2830 &heurdata->relaxindicators, FALSE, DEFAULT_RELAXINDICATORS, NULL, NULL) );
2831
2832 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/relaxcontvars",
2833 "relax the continous variables",
2834 &heurdata->relaxcontvars, FALSE, DEFAULT_RELAXCONTVARS, NULL, NULL) );
2835
2836 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/heurverblevel",
2837 "verblevel of the heuristic, default is 0 to display nothing",
2838 &heurdata->heurverblevel, FALSE, DEFAULT_HEURVERBLEVEL, 0, 4, NULL, NULL) );
2839
2840 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nlpverblevel",
2841 "verblevel of the nlp solver, can be 0 or 1",
2842 &heurdata->nlpverblevel, FALSE, DEFAULT_NLPVERBLEVEL, 0, 1, NULL, NULL) );
2843
2844 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/rankvalue",
2845 "number of ranks that should be displayed when the heuristic is called",
2846 &heurdata->rankvalue, FALSE, DEFAULT_RANKVALUE, 0, INT_MAX, NULL, NULL) );
2847
2848 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxcalls",
2849 "maximal number of recursive calls of the heuristic (if dynamicdepth is off)",
2850 &heurdata->maxcalls, FALSE, DEFAULT_MAXCALLS, 0, INT_MAX, NULL, NULL) );
2851
2852 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/dynamicdepth",
2853 "says if and how the recursion depth is computed at runtime",
2854 &heurdata->dynamicdepth, FALSE, DEFAULT_DYNAMICDEPTH, 0, 1, NULL, NULL) );
2855
2856 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxequalranks",
2857 "maximal number of variables that may have maximal rank, quit if there are more, turn off by setting -1",
2858 &heurdata->maxequalranks, FALSE, DEFAULT_MAXEQUALRANKS, -1, INT_MAX, NULL, NULL) );
2859
2860 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/mingap",
2861 "minimal gap for which we still run the heuristic, if gap is less we return without doing anything",
2862 &heurdata->mingap, FALSE, DEFAULT_MINGAP, 0.0, 100.0, NULL, NULL) );
2863
2864 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lambdaslack",
2865 "value added to objective of slack variables, must not be zero",
2866 &heurdata->lambdaslack, FALSE, DEFAULT_LAMBDASLACK, 0.1, SCIPinfinity(scip), NULL, NULL) );
2867
2868 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lambdaobj",
2869 "scaling factor for the objective function",
2870 &heurdata->lambdaobj, FALSE, DEFAULT_LAMBDAOBJ, 0.0, 1.0, NULL, NULL) );
2871
2872 return SCIP_OKAY;
2873}
static long bound
constraint handler for indicator constraints
Constraint handler for knapsack constraints of the form , x binary and .
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 the set partitioning / packing / covering constraints .
Constraint handler for variable bound constraints .
#define SCIP_MAXSTRLEN
Definition def.h:302
#define SCIP_INVALID
Definition def.h:206
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define REALABS(x)
Definition def.h:210
#define SCIP_CALL(x)
Definition def.h:388
SCIP_RETCODE SCIPcreateConsIndicatorLinCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *binvar, SCIP_CONS *lincons, SCIP_VAR *slackvar, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Real SCIPgetDualsolLinear(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetBinaryVarIndicator(SCIP_CONS *cons)
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR * SCIPgetSlackVarIndicator(SCIP_CONS *cons)
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
SCIP_CONS * SCIPgetLinearConsIndicator(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 ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
@ SCIP_SETPPCTYPE_PARTITIONING
Definition cons_setppc.h:87
@ SCIP_SETPPCTYPE_COVERING
Definition cons_setppc.h:89
@ SCIP_SETPPCTYPE_PACKING
Definition cons_setppc.h:88
SCIP_RETCODE SCIPcopyVars(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool global)
Definition scip_copy.c:1178
SCIP_RETCODE SCIPcopyPlugins(SCIP *sourcescip, SCIP *targetscip, SCIP_Bool copyreaders, SCIP_Bool copypricers, SCIP_Bool copyconshdlrs, SCIP_Bool copyconflicthdlrs, SCIP_Bool copypresolvers, SCIP_Bool copyrelaxators, SCIP_Bool copyseparators, SCIP_Bool copycutselectors, SCIP_Bool copypropagators, SCIP_Bool copyheuristics, SCIP_Bool copyeventhdlrs, SCIP_Bool copynodeselectors, SCIP_Bool copybranchrules, SCIP_Bool copydisplays, SCIP_Bool copydialogs, SCIP_Bool copytables, SCIP_Bool copyexprhdlrs, SCIP_Bool copynlpis, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition scip_copy.c:275
SCIP_RETCODE SCIPcopyConss(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool *valid)
Definition scip_copy.c:1730
SCIP_RETCODE SCIPcopyParamSettings(SCIP *sourcescip, SCIP *targetscip)
Definition scip_copy.c:2564
SCIP_Bool SCIPisTransformed(SCIP *scip)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition scip_prob.c:1668
SCIP_RETCODE SCIPgetOrigVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition scip_prob.c:2357
const char * SCIPgetProbName(SCIP *scip)
Definition scip_prob.c:1067
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition scip_prob.c:1866
int SCIPgetNOrigConss(SCIP *scip)
Definition scip_prob.c:3134
SCIP_VAR ** SCIPgetOrigVars(SCIP *scip)
Definition scip_prob.c:2405
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2770
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2843
int SCIPgetNConss(SCIP *scip)
Definition scip_prob.c:3042
int SCIPgetNOrigVars(SCIP *scip)
Definition scip_prob.c:2432
SCIP_CONS ** SCIPgetOrigConss(SCIP *scip)
Definition scip_prob.c:3161
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 * SCIPhashmapEntryGetImage(SCIP_HASHMAPENTRY *entry)
Definition misc.c:3520
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3211
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition misc.c:3106
int SCIPhashmapGetNEntries(SCIP_HASHMAP *hashmap)
Definition misc.c:3491
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition misc.c:3499
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition misc.c:3024
void * SCIPhashmapEntryGetOrigin(SCIP_HASHMAPENTRY *entry)
Definition misc.c:3510
SCIP_RETCODE SCIPhashmapRemoveAll(SCIP_HASHMAP *hashmap)
Definition misc.c:3583
SCIP_RETCODE SCIPhashmapRemove(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3389
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
SCIP_RETCODE SCIPapplyHeurDualval(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_SOL *refpoint)
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 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 SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition scip_param.c:487
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 SCIPincludeHeurDualval(SCIP *scip)
int SCIPgetNLPBranchCands(SCIP *scip)
int SCIPgetNPseudoBranchCands(SCIP *scip)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4595
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
void SCIPconsAddUpgradeLocks(SCIP_CONS *cons, int nlocks)
Definition cons.c:8527
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition cons.c:8347
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition cons.c:8108
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition cons.c:8257
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition cons.c:8287
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition cons.c:8277
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition cons.c:8307
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition cons.c:8327
SCIP_Bool SCIPconsIsEnabled(SCIP_CONS *cons)
Definition cons.c:8185
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition cons.c:8088
SCIP_RETCODE SCIPgetTransformedCons(SCIP *scip, SCIP_CONS *cons, SCIP_CONS **transcons)
Definition scip_cons.c:1620
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition cons.c:8367
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1119
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition cons.c:8267
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_cons.c:1084
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition cons.c:8357
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition scip_event.c:104
SCIP_RETCODE SCIPsetEventhdlrExit(SCIP *scip, SCIP_EVENTHDLR *eventhdlr,)
Definition scip_event.c:178
SCIP_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition event.c:334
SCIP_RETCODE SCIPsetEventhdlrInit(SCIP *scip, SCIP_EVENTHDLR *eventhdlr,)
Definition scip_event.c:164
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition scip_event.c:286
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition scip_event.c:320
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
void SCIPheurSetFreq(SCIP_HEUR *heur, int freq)
Definition heur.c:1545
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition heur.c:1490
int SCIPheurGetFreqofs(SCIP_HEUR *heur)
Definition heur.c:1556
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:242
int SCIPheurGetFreq(SCIP_HEUR *heur)
Definition heur.c:1535
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
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition scip_lp.c:168
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition scip_mem.h:128
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:93
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition scip_mem.h:111
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition scip_mem.h:137
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
int SCIPgetNNlpis(SCIP *scip)
Definition scip_nlpi.c:199
SCIP_RETCODE SCIPaddNlRow(SCIP *scip, SCIP_NLROW *nlrow)
Definition scip_nlp.c:363
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 SCIPsetNLPInitialGuess(SCIP *scip, SCIP_Real *initialguess)
Definition scip_nlp.c:441
int SCIPgetNNLPVars(SCIP *scip)
Definition scip_nlp.c:201
SCIP_VAR ** SCIPgetNLPVars(SCIP *scip)
Definition scip_nlp.c:179
SCIP_RETCODE SCIPreleaseNlRow(SCIP *scip, SCIP_NLROW **nlrow)
Definition scip_nlp.c:1025
SCIP_Real SCIPnlrowGetDualsol(SCIP_NLROW *nlrow)
Definition nlp.c:1885
SCIP_RETCODE SCIPcreateNlRow(SCIP *scip, SCIP_NLROW **nlrow, const char *name, SCIP_Real constant, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, SCIP_EXPR *expr, SCIP_Real lhs, SCIP_Real rhs, SCIP_EXPRCURV curvature)
Definition scip_nlp.c:921
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition scip_sol.c:2313
SCIP_Real SCIPsolGetOrigObj(SCIP_SOL *sol)
Definition sol.c:2575
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition scip_sol.c:565
SCIP_RETCODE SCIPtrySolFree(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:3193
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1444
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition scip_sol.c:1221
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1361
SCIP_RETCODE SCIPpresolve(SCIP *scip)
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Real SCIPgetGap(SCIP *scip)
SCIP_Bool SCIPisRelLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition var.c:12763
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_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17748
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17406
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition scip_var.c:1794
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_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition scip_var.c:4943
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition var.c:17432
SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible)
Definition scip_var.c:8176
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition scip_var.c:1527
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition var.c:17396
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition scip_var.c:5032
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_VAR * SCIPvarGetTransVar(SCIP_VAR *var)
Definition var.c:17600
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 SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:1214
void SCIPsortDownRealRealPtr(SCIP_Real *realarray1, SCIP_Real *realarray2, void **ptrarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10788
return SCIP_OKAY
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
#define DEFAULT_RANKVALUE
#define DEFAULT_ONLYCHEAPER
static SCIP_RETCODE createSolFromSubScipSol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL **sol, SCIP_SOL *subsol)
static SCIP_RETCODE addSetppcConstraints(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_HEURDATA *heurdata)
#define DEFAULT_LAMBDAOBJ
#define DEFAULT_MINGAP
#define DEFAULT_HEURVERBLEVEL
static SCIP_RETCODE addLogicOrConstraints(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_HEURDATA *heurdata)
#define HEUR_TIMING
static SCIP_RETCODE createSolFromNLP(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL **sol)
#define HEUR_FREQOFS
static SCIP_RETCODE computeRanks(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Real *absranks, SCIP_Real *ranks, SCIP_VAR **sortedvars)
#define HEUR_DESC
static SCIP_RETCODE freeMemory(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_SOL *transsol, SCIP_Real *absranks, SCIP_Real *ranks, SCIP_VAR **sortedvars, SCIP_Bool beforeswitching, SCIP_Bool clearswitchedvars)
#define DEFAULT_RELAXINDICATORS
static SCIP_RETCODE releaseHashmapNLPRows(SCIP *scip, SCIP_HASHMAP *hashmap)
static SCIP_RETCODE addLinearConstraints(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_Bool addcombconss, SCIP_Bool addcontconss, SCIP_HEURDATA *heurdata)
#define DEFAULT_FORCEIMPROVEMENTS
#define HEUR_DISPCHAR
#define HEUR_MAXDEPTH
#define HEUR_PRIORITY
static SCIP_RETCODE storeSolution(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_SOL *transsol, SCIP_SOL *bestsol)
#define DEFAULT_LAMBDASLACK
#define HEUR_NAME
#define DEFAULT_RELAXCONTVARS
#define DEFAULT_MAXCALLS
static SCIP_Real maximalslack(SCIP *scip, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE SCIPincludeEventHdlrLPsol(SCIP *scip, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE createSubSCIP(SCIP *scip, SCIP_HEURDATA *heurdata)
#define BIG_VALUE
static SCIP_RETCODE fixDiscreteVars(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_SOL *refpoint, SCIP_SOL **transsol)
static SCIP_RETCODE addKnapsackConstraints(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_HEURDATA *heurdata)
#define DEFAULT_DYNAMICDEPTH
#define DEFAULT_ONLYLEAVES
static SCIP_RETCODE freeSubSCIP(SCIP *scip, SCIP_HEURDATA *heurdata)
#define DEFAULT_NLPVERBLEVEL
static SCIP_RETCODE releaseHashmapEntries(SCIP *scip, SCIP_HASHMAP *hashmap, SCIP_Bool isvarmap)
#define EVENTHDLR_DESC
#define DEFAULT_MAXEQUALRANKS
#define HEUR_FREQ
static SCIP_RETCODE addVarboundConstraints(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_Bool addcombconss, SCIP_Bool addcontconss, SCIP_HEURDATA *heurdata)
#define HEUR_USESSUBSCIP
static SCIP_RETCODE addLinearConstraintsToNlp(SCIP *scip, SCIP_Bool addcombconss, SCIP_Bool addcontconss, SCIP_HEURDATA *heurdata)
#define EVENTHDLR_NAME
primal heuristic that uses dualvalues for successive switching variable values
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_VAR ** vars
#define NULL
Definition lpi_spx1.cpp:161
memory allocation routines
#define BMSclearMemory(ptr)
Definition memory.h:131
#define BMSclearMemoryArray(ptr, num)
Definition memory.h:132
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition scip_mem.c:57
public methods for managing constraints
public methods for managing events
public methods for primal heuristics
public methods for message output
#define SCIPerrorMessage
Definition pub_message.h:64
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for NLP management
public methods for primal CIP solutions
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
public methods for event handler plugins and event handlers
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 NLPI solver interfaces
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for solutions
public solving methods
public methods for querying solving statistics
public methods for SCIP variables
#define MAX(x, y)
Definition tclique_def.h:92
#define SCIP_EVENTTYPE_FIRSTLPSOLVED
Definition type_event.h:100
#define SCIP_DECL_EVENTEXIT(x)
Definition type_event.h:207
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
Definition type_event.h:155
#define SCIP_DECL_EVENTEXEC(x)
Definition type_event.h:253
#define SCIP_DECL_EVENTINIT(x)
Definition type_event.h:199
#define SCIP_EVENTTYPE_LPSOLVED
Definition type_event.h:101
type and macro definitions related to algebraic expressions
@ SCIP_EXPRCURV_LINEAR
Definition type_expr.h:62
#define SCIP_DECL_HEURINITSOL(x)
Definition type_heur.h:131
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_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
@ SCIP_VERBLEVEL_HIGH
@ SCIP_NLPSOLSTAT_FEASIBLE
Definition type_nlpi.h:162
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_CUTOFF
Definition type_result.h:48
@ 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_ERROR
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_STAGE_SOLVING
Definition type_set.h:53
@ 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