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-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file 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 /* disable objective stop in subscip */
975 SCIP_CALL( SCIPresetParam(heurdata->subscip, "limits/objectivestop") );
976
977 /* create problem in sub-SCIP */
978
979 /* get name of the original problem and add "dualval" */
980 (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_dualval", SCIPgetProbName(scip));
981 SCIP_CALL( SCIPcreateProb(heurdata->subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
982
984
985 /* copy all variables */
987
988 /* copy as many constraints as possible */
990 SCIP_CALL( SCIPcopyConss(scip, heurdata->subscip, varsmap, conssmap, TRUE, FALSE, &heurdata->subscipisvalid) );
991
993
994 nconss = SCIPgetNOrigConss(scip);
995 conss = SCIPgetOrigConss(scip);
996
997 /* fill constraint mapping from original scip to the subscip */
998 for( i = 0; i < nconss; ++i )
999 {
1000 transcons = NULL;
1002
1004 assert( subcons != NULL );
1005
1007 SCIP_CALL( SCIPhashmapInsert(heurdata->origsubscipConsMap, transcons, subcons) );
1008 }
1009
1011
1012 if( !heurdata->subscipisvalid )
1013 {
1014 SCIPdebugMsg(scip, "In heur_dualval: failed to copy some constraints to sub-SCIP, continue anyway\n");
1015 }
1016
1017 SCIP_CALL( SCIPgetVarsData(heurdata->subscip, &subvars, &heurdata->nsubvars, NULL, NULL, NULL, NULL) );
1018 heurdata->nvars = nvars;
1019
1020 /* create hashmaps from scip transformed vars to subscip original vars, and vice versa
1021 * capture variables in SCIP and sub-SCIP
1022 * catch global bound change events */
1025
1026 /* we need to get all subscip variables, also those which are copies of fixed variables from the main scip,
1027 * therefore we iterate over the hashmap */
1028 for( i = 0; i < SCIPhashmapGetNEntries(varsmap); ++i )
1029 {
1032 if( entry != NULL )
1033 {
1036
1038 assert( SCIPvarGetProbindex(subvar) <= heurdata->nsubvars );
1039
1040 if( SCIPvarIsActive(var) )
1041 {
1042 assert( SCIPvarGetProbindex(var) <= heurdata->nvars );
1043 /* assert that we have no mapping for this var yet */
1044 assert( SCIPhashmapGetImage(heurdata->varsciptosubscip,var) == NULL );
1045 SCIP_CALL( SCIPhashmapInsert(heurdata->varsciptosubscip, var, subvar) );
1046 }
1047
1048 assert( SCIPhashmapGetImage(heurdata->varsubsciptoscip, subvar) == NULL );
1049 SCIP_CALL( SCIPhashmapInsert(heurdata->varsubsciptoscip, subvar, var) );
1050
1053
1056 }
1057 }
1058
1059 /* we map all slack variables of indicator constraints to their indicator variables */
1060 conshdlrindicator = SCIPfindConshdlr(scip, "indicator");
1062
1069
1070 for( i = 0; i < nconsindicator; i++ )
1071 {
1074
1076 assert(currcons != NULL);
1077
1083 }
1084
1085 /* we introduce slackvariables s+ and s- for each constraint to ensure that the problem is feasible
1086 * we want to minimize over the sum of these variables, so set the objective to 1 */
1090
1093
1095 BMSclearMemoryArray(heurdata->integervars, nvars);
1096 heurdata->integervarssize = nvars;
1097 j = 0;
1098
1099 /* here we relax the variables (or indicator constraints, since indicator variables cannot be relaxed) */
1100 for( i = 0; i < nvars; ++i )
1101 {
1103 assert( var != NULL );
1104
1105 if( ! SCIPvarIsActive(var) )
1106 continue;
1107
1108 if( ! SCIPvarIsIntegral(var) )
1109 continue;
1110
1111 heurdata->integervars[j++] = vars[i];
1112
1113 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1114 if( var == NULL )
1115 continue;
1116
1117 /* in this case our variable is an indicator variable */
1118 if( SCIPhashmapGetImage(heurdata->indicators, SCIPhashmapGetImage(heurdata->varsubsciptoscip, var)) != NULL )
1119 {
1120 /* we have to find all the indicator constraints of this variable */
1121 for( k = 0; k < nconsindicator; k++ )
1122 {
1125 SCIP_VAR* negatedvar;
1127
1129 assert(currcons != NULL);
1130
1133
1134 SCIP_CALL( SCIPgetNegatedVar(scip, (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, var), &negatedvar) );
1135
1136 if( indicatorbinvar == SCIPhashmapGetImage(heurdata->varsubsciptoscip, var) || indicatorbinvar == negatedvar )
1137 {
1138 /* case that we have a negated variable */
1140 {
1141 assert(indicatorbinvar == negatedvar);
1142 varobjective = SCIPvarGetObj(negatedvar);
1143 }
1144 else
1145 {
1146 assert(indicatorbinvar != negatedvar);
1148 }
1149
1150 varobjective = heurdata->lambdaobj * REALABS(varobjective);
1151
1153 assert( indicons != NULL );
1154
1156
1157 assert( indicons != NULL );
1159
1164
1167 heurdata->lambdaslack * 100 + varobjective, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1169
1170 /* make a copy of the indicator to relax it if this parameter is set true */
1171 if( heurdata->relaxindicators )
1172 {
1174
1176
1177 SCIP_CALL( SCIPgetNegatedVar(heurdata->subscip, indicatorbinvar, &negatedvar) );
1178
1179 if( SCIPhashmapGetImage(heurdata->indicopymap, indicatorbinvar) == NULL &&
1180 SCIPhashmapGetImage(heurdata->indicopymap, negatedvar) == NULL)
1181 {
1182 SCIP_Bool negated = FALSE;
1183
1185 {
1186 indicatorbinvar = negatedvar;
1187 negated = TRUE;
1188 }
1189
1193
1195
1199
1202 heurdata->lambdaslack * 100 + varobjective, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1204
1207 heurdata->lambdaslack * 100 + varobjective, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1209
1210 /* create linking constraint */
1211 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "linking_%s", SCIPvarGetName(indicatorbinvar));
1212 cons = NULL;
1213 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, 0.0, 0.0,
1215 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indicatorbinvar, 1.0) );
1216 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indicatorcopy, -1.0) );
1217 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indislackvarpos, 1.0) );
1218 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indislackvarneg, -1.0) );
1219
1220 SCIP_CALL( SCIPhashmapInsert(heurdata->relaxconsindi, indicatorbinvar, cons) );
1221 SCIP_CALL( SCIPhashmapInsert(heurdata->relaxconsindi, indicatorcopy, cons) );
1222
1223 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1224 SCIP_CALL( SCIPcaptureCons(heurdata->subscip, cons) );
1225
1227
1228 if ( negated )
1229 {
1231 }
1232
1234
1237 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1238 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1241 }
1242 else
1243 {
1246 else
1247 {
1248 indicatorcopy = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->indicopymap, negatedvar);
1250 }
1251 }
1252
1253 cons = NULL;
1259 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1260
1261 /* delete old indicator constraints so we can relax the indicator variables */
1262 imagecons = (SCIP_CONS*) SCIPhashmapGetImage(heurdata->origsubscipConsMap, (void*)(currcons));
1263 assert(imagecons != NULL);
1265 SCIP_CALL( SCIPhashmapRemove(heurdata->origsubscipConsMap, currcons) );
1266 SCIP_CALL( SCIPhashmapInsert(heurdata->origsubscipConsMap, currcons, cons) );
1268 SCIP_CALL( SCIPdelCons(heurdata->subscip, indicons) );
1269 }
1270
1273 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1274 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1275
1280 }
1281 }
1282 continue;
1283 }
1284
1285 if( heurdata->relaxindicators )
1286 {
1287 /* relax the old indicator variables*/
1288 for( k = 0; k < nvars; k++ )
1289 {
1290 if( SCIPhashmapGetImage(heurdata->indicators, vars[k]) == NULL )
1291 continue;
1292
1293 tmpvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, vars[k]);
1297 }
1298
1299 /* we map all slack variables of indicator constraints to their indicator variables */
1300 conshdlrindicator = SCIPfindConshdlr(scip, "indicator");
1302
1303 /* delete old hashmaps and fill with the new indicators*/
1304 SCIP_CALL( releaseHashmapEntries(scip, heurdata->slacktoindivarsmap, TRUE) );
1306 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->slacktoindivarsmap) );
1307 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->indicators) );
1308
1309 /* fill hashmaps with new values */
1310 for( k = 0; k < nconsindicator; k++ )
1311 {
1314
1316 assert(currcons != NULL);
1317
1320
1324 }
1325 }
1326
1327 /* in this case, we have a normal variable */
1328 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "relax_%s", SCIPvarGetName(var));
1329 cons = NULL;
1330 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, 0.0, 0.0,
1332
1335 heurdata->lambdaslack * 100, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL,NULL) );
1337
1340 heurdata->lambdaslack * 100, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL,NULL) );
1342
1343 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, var, 1.0) );
1344 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarpos, 1.0) );
1345 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarneg, -1.0) );
1346
1347 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1348
1351 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1352 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1353 SCIP_CALL( SCIPhashmapInsert(heurdata->relaxcons, var, cons) );
1356
1357 /* if the var is no indicator, relax it to a continuous variable */
1358 if( SCIPhashmapGetImage(heurdata->indicators, SCIPhashmapGetImage(heurdata->varsubsciptoscip, var)) == NULL )
1359 {
1363 }
1364 }
1365
1366 /* set up relaxation constraints for continuous variables */
1367 if( heurdata->relaxcontvars )
1368 {
1369 for( i = 0; i < nvars; ++i )
1370 {
1372 assert( var != NULL );
1373
1374 if( ! SCIPvarIsActive(var) )
1375 continue;
1376
1377 if( SCIPvarIsIntegral(var) )
1378 continue;
1379
1381 continue;
1382
1384 continue;
1385
1386 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1387 if( var == NULL )
1388 continue;
1389
1390 /* in this case, we have a normal variable */
1391 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "relax_ub_%s", SCIPvarGetName(var));
1392 cons = NULL;
1393 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, -SCIPinfinity(heurdata->subscip), SCIPvarGetUbGlobal(var),
1395
1400
1401 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, var, 1.0) );
1402 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarpos, -1.0) );
1403
1404 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1405 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &cons) );
1406 SCIP_CALL( SCIPhashmapInsert(heurdata->slackvarubMap, var, slackvarpos) );
1408 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1409
1410 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "relax_lb_%s", SCIPvarGetName(var));
1411 cons = NULL;
1412 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, SCIPvarGetLbGlobal(var), SCIPinfinity(heurdata->subscip),
1414
1419
1420 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, var, 1.0) );
1421 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarneg, 1.0) );
1422
1423 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1424 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &cons) );
1425 SCIP_CALL( SCIPhashmapInsert(heurdata->slackvarlbMap, var, slackvarneg) );
1427 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1428
1431 }
1432 }
1433
1434 /* if we have a solution add constraint that the next solution must not be worse than the current one */
1435 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "objbound");
1436 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, -SCIPinfinity(scip),
1438 heurdata->objbound = cons;
1439
1440 for( i = 0; i < nvars; ++i )
1441 {
1443 assert( var != NULL );
1444
1445 if( !SCIPvarIsActive(var) )
1446 continue;
1447
1448 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1449 if( subvar == NULL )
1450 continue;
1451
1453
1454 SCIP_CALL( SCIPchgVarObj(heurdata->subscip, subvar, heurdata->lambdaobj * SCIPvarGetObj(subvar) ) );
1455 }
1456
1457 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1458 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &cons) );
1459
1460 /* do not need varsmap and conssmap anymore */
1463
1464 /* enable SCIP output if needed */
1465 if( heurdata->heurverblevel > 3 )
1466 {
1467 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "display/verblevel", 4) );
1468 }
1469 else
1470 {
1471 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "display/verblevel", 0) );
1472 }
1473
1474 heurdata->nintegervars = j;
1475
1476 return SCIP_OKAY;
1477}
1478
1479
1480/** free sub-SCIP data structure */
1481static
1483 SCIP* scip, /**< SCIP data structure */
1484 SCIP_HEURDATA* heurdata /**< heuristic data structure */
1485 )
1486{
1487 assert(scip != NULL);
1488 assert(heurdata != NULL);
1489 assert(heurdata->subscip != NULL);
1490
1491 heurdata->nsubvars = 0;
1492 heurdata->nvars = 0;
1493
1494 /* free sub-SCIP */
1495 SCIP_CALL( SCIPfree(&heurdata->subscip) );
1496
1497 return SCIP_OKAY;
1498}
1499
1500
1501/** create a solution from the values of current nonlinear program */
1502static
1504 SCIP* scip, /**< SCIP data structure */
1505 SCIP_HEUR* heur, /**< heuristic data structure */
1506 SCIP_SOL** sol /**< buffer to store solution value; if pointing to NULL a new solution is
1507 * created, otherwise values in the given one are overwritten */
1508 )
1509{
1511 SCIP_VAR** subvars;
1513 int i;
1514 int nsubvars;
1515
1516 assert(scip != NULL);
1517 assert(heur != NULL);
1518 assert(sol != NULL);
1519
1520 heurdata = SCIPheurGetData(heur);
1521 assert(heurdata != NULL);
1522
1523 if( *sol == NULL )
1524 {
1525 SCIP_CALL( SCIPcreateSol(scip, sol, heur) );
1526 }
1527
1528 /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
1529 * since constraint copying may have required the copy of variables that are fixed in the main SCIP */
1530 assert(heurdata->nsubvars <= SCIPgetNOrigVars(heurdata->subscip));
1531
1532 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, NULL, NULL, NULL, NULL) );
1533
1534 /* set solution values */
1535 for( i = 0; i < nsubvars; ++i )
1536 {
1537 subvar = subvars[i];
1538 assert(subvar != NULL);
1539
1541
1542 if( !SCIPvarIsActive(subvar) )
1543 continue;
1544
1545 assert(SCIPvarGetNLPSol(subvar) != SCIP_INVALID);/*lint !e777*/
1547 }
1548
1549 return SCIP_OKAY;
1550}
1551
1552#define BIG_VALUE 1E+10
1553
1554/** method to fix the (relaxed) discrete variables */
1555static
1557 SCIP* scip, /**< SCIP data structure */
1558 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
1559 SCIP_SOL* refpoint, /**< point to take fixation of discrete variables from;
1560 * if NULL, then LP solution is used */
1561 SCIP_SOL** transsol /**< pointer to new created solution with fixed values as solution value */
1562 )
1563{
1564 SCIP_Real fixval;
1565 SCIP_VAR* var;
1568 int i;
1569
1571
1572 /* fix discrete variables */
1573 for( i = 0; i < heurdata->nintegervars; i++ )
1574 {
1575 var = heurdata->integervars[i];
1576 assert(var != NULL);
1577
1579 assert(var != NULL);
1580 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1581
1582 if( subvar == NULL )
1583 continue;
1584
1585 if ( SCIPhashmapGetImage(heurdata->indicopymap, subvar) != NULL )
1587
1588 /* if we do not really have a startpoint, we set to 0.0 here and project on bounds below */
1590 fixval = 0.0;
1591 else
1592 {
1593 /* get value of the variables (NULL as refpoint gives the current LP solution, otherwise the start point) */
1594 fixval = SCIPgetSolVal(scip, refpoint, heurdata->integervars[i]);
1595
1596 /* take care that we do not fix variables to very large values (project on bounds below) */
1597 if( REALABS(fixval) > BIG_VALUE )
1598 fixval = 0.0;
1599 else
1600 {
1601 /* round fractional variables to the nearest integer, use exact integral value, if the variable is only
1602 * integral within numerical tolerances */
1603 fixval = SCIPfloor(scip, fixval + 0.5);
1604 }
1605 }
1606
1607 /* adjust value to the global bounds of the corresponding SCIP variable */
1608 fixval = MAX(fixval, SCIPvarGetLbGlobal(heurdata->integervars[i])); /*lint !e666*/
1609 fixval = MIN(fixval, SCIPvarGetUbGlobal(heurdata->integervars[i])); /*lint !e666*/
1610
1611 SCIP_CALL( SCIPsetSolVal(scip, *transsol, heurdata->integervars[i], fixval) );
1612
1613 /* adjust the relaxation constraints to the new fixval */
1615
1616 fixval = MAX(fixval, SCIPvarGetLbGlobal(subvar));/*lint !e666*/
1617 fixval = MIN(fixval, SCIPvarGetUbGlobal(subvar));/*lint !e666*/
1618 if( rcons == NULL )
1619 {
1622 continue;
1623 }
1624
1627 }
1628
1629 return SCIP_OKAY;
1630}
1631
1632/** method to free memory before leaving the heuristic or jumping up in the recursion */
1633static
1635 SCIP* scip, /**< scip data structure */
1636 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
1637 SCIP_SOL* transsol, /**< sol that has to be freed */
1638 SCIP_Real* absranks, /**< array of absolute rank values */
1639 SCIP_Real* ranks, /**< array of rank values */
1640 SCIP_VAR** sortedvars, /**< array of corresponding variables */
1641 SCIP_Bool beforeswitching, /**< did we call this method before or after switching variables? */
1642 SCIP_Bool clearswitchedvars /**< says if we should clear switchedvars or not */
1643 )
1644{
1645 SCIP_VAR** subvars;
1647 SCIP_VAR* var;
1648 SCIP_Real* val;
1649 int nsubvars;
1650 int nsubbinvars;
1651 int nsubintvars;
1652 int i;
1653
1654 if( clearswitchedvars )
1655 {
1656 /* free memory of the solution values in the hashmaps */
1657 for( i = 0; i < heurdata->nintegervars; i++ )
1658 {
1659 var = heurdata->integervars[i];
1660
1661 if( SCIPhashmapGetImage(heurdata->slacktoindivarsmap, var) != NULL )
1662 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->slacktoindivarsmap, var);
1663
1664 val = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars, var);
1665 if( val != NULL )
1666 {
1667 SCIPfreeBlockMemoryArray(heurdata->subscip, &val, 1);
1668 }
1669
1670 val = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars2, var);
1671 if( val != NULL )
1672 {
1673 SCIPfreeBlockMemoryArray(heurdata->subscip, &val, 1);
1674 }
1675 }
1676
1677 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->switchedvars) );
1678 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->switchedvars2) );
1679 }
1680
1683 SCIPfreeBufferArrayNull( scip, &sortedvars );
1684
1685 if( transsol != NULL )
1686 {
1688 }
1689
1690 if( beforeswitching )
1691 {
1693 }
1694
1695 /* undo fixing of discrete variables in sub-SCIP */
1696 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, &nsubbinvars, &nsubintvars, NULL, NULL) );
1697
1698 /* set bounds of discrete variables to original values */
1699 for( i = nsubbinvars + nsubintvars - 1; i >= 0; --i )
1700 {
1701 subvar = subvars[i];
1703
1704 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, subvar);
1705
1706 if (SCIPhashmapGetImage(heurdata->indicopymapback, subvar) != NULL)
1707 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, SCIPhashmapGetImage(heurdata->indicopymapback, subvar));
1708
1709 assert(var != NULL);
1710
1713 }
1714
1715 return SCIP_OKAY;
1716}
1717
1718/** computes the ranks, saves them into an array and sorts the variables according to absolute ranks */
1719static
1721 SCIP* scip, /**< scip data structure */
1722 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
1723 SCIP_Real* absranks, /**< array of absolute rank values */
1724 SCIP_Real* ranks, /**< array of rank values */
1725 SCIP_VAR** sortedvars /**< array of corresponding variables */
1726 )
1727{
1729 SCIP_CONS* relaxcons;
1733 SCIP_VAR* var;
1734 SCIP_Real* dualvalue;
1735 int nconsindicator;
1736 int j;
1737 int k;
1738
1739 conshdlrindicator = SCIPfindConshdlr(scip, "indicator");
1741
1742 /* Now we compute the rank of each variable */
1743 for( j = 0; j < heurdata->nintegervars; j++ )
1744 {
1745 sortedvars[j] = heurdata->integervars[j];
1746 ranks[j] = 0;
1747 absranks[j] = 0;
1748
1749 if( sortedvars[j] == NULL )
1750 break;
1751
1752 var = SCIPvarGetTransVar(sortedvars[j]);
1753 assert(var != NULL);
1754
1755 /* globally fixed variables get rank 0 */
1757 {
1758 ranks[j] = 0;
1759 continue;
1760 }
1761 else
1762 {
1763 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1764 assert(var != NULL);
1765 relaxcons = (SCIP_CONS*)SCIPhashmapGetImage(heurdata->relaxcons, (void*)(var));
1766
1767 /* get ranks */
1768 if( relaxcons != NULL )
1769 {
1770 SCIP_CALL( SCIPgetTransformedCons(heurdata->subscip, relaxcons, &transcons) );
1771 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)transcons);
1772
1773 if( dualvalue == NULL )
1774 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)(relaxcons));
1775
1776 if( dualvalue == NULL )
1777 continue;
1778
1779 assert(dualvalue != NULL);
1780 ranks[j] = (*dualvalue);
1781 }
1782 else /* if we have an indicator variable */
1783 {
1784 assert(ranks[j] == 0.0);
1785
1786 if (SCIPhashmapGetImage(heurdata->relaxconsindi, (void*)(var)) != NULL)
1787 {
1788 subcons = (SCIP_CONS*)SCIPhashmapGetImage(heurdata->relaxconsindi, (void*)(var));
1789
1790 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)(subcons));
1791
1792 if( dualvalue == NULL )
1793 continue;
1794
1795 assert(dualvalue != NULL);
1796
1797 ranks[j] = (*dualvalue);
1798 }
1799
1800 /* compute the rank of the indicators, we take the highest dualvalue of an indicator constraint */
1801 for( k = 0; k < nconsindicator; k++ )
1802 {
1806
1808 assert(currcons != NULL);
1809
1812
1813 if( indicatorbinvar == (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, var)
1815 {
1817 assert(indicons != NULL);
1818
1819 subcons = (SCIP_CONS*)SCIPhashmapGetImage(heurdata->origsubscipConsMap, (void*)(indicons));
1820 assert(subcons != NULL);
1821
1823 assert(subcons != NULL);
1824
1825 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)(subcons));
1826
1827 if( dualvalue == NULL )
1828 continue;
1829
1830 assert(dualvalue != NULL);
1831
1832 if( REALABS(ranks[j]) < REALABS(*dualvalue) )
1833 ranks[j] = (*dualvalue);
1834 }
1835 }
1836 }
1837 }
1838
1839 /* take the absolute value of each rank */
1840 absranks[j] = REALABS(ranks[j]);
1841 }
1842
1843 SCIPsortDownRealRealPtr(absranks, ranks, (void**)sortedvars, heurdata->nintegervars);
1844
1845 return SCIP_OKAY;
1846}
1847
1848/** compute maximal slack of a variable */
1849static
1851 SCIP* scip, /**< scip data structure */
1852 SCIP_HEURDATA* heurdata /**< heuristic data structure */
1853 )
1854{
1857 SCIP_SOL* bestsol;
1858 SCIP_Real maxslack;
1859 int i;
1860 int nsubvars;
1861 SCIP_Bool maxslackset;
1862
1863 /* compute maximal slack */
1864 nsubvars = SCIPgetNOrigVars(heurdata->subscip);
1865
1866 /* save information about maximal violation */
1867 maxvar = NULL;
1868 maxslack = -SCIPinfinity(heurdata->subscip);
1870
1871 bestsol = SCIPgetBestSol(heurdata->subscip);
1872
1873 /* search for variable with maximal slack */
1874 for( i = 0; i < nsubvars; i++ )
1875 {
1876 subvar = SCIPgetOrigVars(heurdata->subscip)[i];
1877 if( subvar == NULL)
1878 continue;
1879
1880 /* if variable is slack */
1881 if( SCIPhashmapGetImage(heurdata->slack2var, subvar) != NULL )
1882 {
1883 if( heurdata->isnlp )
1884 {
1885 if( maxslack < SCIPvarGetNLPSol(subvar) )
1886 {
1887 maxslack = SCIPvarGetNLPSol(subvar);
1888 maxvar = subvar;
1889 maxslackset = TRUE;
1890 }
1891 }
1892 else
1893 {
1894 assert(bestsol != NULL);
1895 if( maxslack < SCIPgetSolVal(heurdata->subscip, bestsol, subvar) )
1896 {
1897 maxslack = SCIPgetSolVal(heurdata->subscip, bestsol, subvar);
1898 maxvar = subvar;
1899 maxslackset = TRUE;
1900 }
1901 }
1902 }
1903 }
1904
1905 if( ! maxslackset )
1906 {
1907 maxslack = 0;
1908 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "could not find a variable with maximal slack!\n");
1909 }
1910
1911 assert(maxslack >= 0);
1912
1913 if( heurdata->heurverblevel > 0 && maxslackset )
1914 {
1915 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "maximum slack: %f %s\n", maxslack, SCIPvarGetName(maxvar));
1916 }
1917
1918 return maxslack;
1919}
1920
1921/** method called after a solution is found which is feasible in the original problem, stores it and cleans up */
1922static
1924 SCIP* scip, /**< SCIP data structure */
1925 SCIP_HEUR* heur, /**< heuristic data */
1926 SCIP_RESULT* result, /**< pointer to store result of: did not run, solution found,
1927 * no solution found, or fixing is infeasible (cutoff) */
1928 SCIP_SOL* transsol, /**< solution to fix variables */
1929 SCIP_SOL* bestsol /**< solution we create a original scip solution from */
1930 )
1931{
1933 SCIP_SOL* sol = NULL;
1934 SCIP_Bool stored;
1935 SCIP_Real primalobj;
1936
1937 /* get heuristic's data */
1938 heurdata = SCIPheurGetData(heur);
1939 assert(heurdata != NULL);
1940 SCIP_CALL( createSolFromSubScipSol(scip, heur, &sol, bestsol) );
1941
1942 /* if this happens, there was an ipopt error - stop the heuristic for there is no good starting point */
1944 {
1946 heurdata->solfound = TRUE;
1947
1948 /* here we can be sure that we are in the nlp case */
1949 assert( heurdata->isnlp );
1950 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) );
1951
1953
1954 /* don't use the heuristic anymore if IPOPT doesn't give proper solution
1955 * (normally then this happens in most ipopt runs that may follow) */
1956 SCIPheurSetFreq(heur, -1);
1957
1958 SCIPdebugMsg(scip, "return10 : turn off heuristic, ipopt error\n");
1959
1960 if( heurdata->heurverblevel > 1 )
1961 {
1962 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "turn off heuristic due to ipopt error");
1963 }
1964
1965 return SCIP_OKAY;
1966 }
1967
1969
1970 /* if there is a solution, try to add solution to storage and free it */
1971 if( sol != NULL )
1972 {
1974
1975 if( heurdata->heurverblevel > 0 )
1976 {
1978 }
1979 else
1980 {
1982 }
1983 }
1984 else
1985 stored = FALSE;
1986
1987 if( stored && heurdata->heurverblevel > 1 )
1988 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "accepted solution\n");
1989
1990 if( heurdata->isnlp )
1991 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) );
1992
1994
1995 if( !stored )
1996 {
1998 heurdata->solfound = TRUE;
1999
2000 if( heurdata->heurverblevel >= 1 )
2001 {
2002 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "return9 : found solution that was not stored, objective %f\n", primalobj);/*lint !e644*/
2003 }
2004
2005 return SCIP_OKAY;
2006 }
2007
2008 heurdata->prevInfeasible = FALSE;
2009 heurdata->solfound = TRUE;
2011
2012 if( heurdata->heurverblevel >= 1 )
2013 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "return 9 : found and stored new solution, objective %lf\n", primalobj);
2014
2015 return SCIP_OKAY;
2016}
2017
2018/** main procedure of the dualval heuristic */
2020 SCIP* scip, /**< original SCIP data structure */
2021 SCIP_HEUR* heur, /**< heuristic data structure */
2022 SCIP_RESULT* result, /**< pointer to store result of: did not run, solution found, no solution
2023 * found, or fixing is infeasible (cutoff) */
2024 SCIP_SOL* refpoint /**< point to take fixation of discrete variables from; if NULL, then LP
2025 * solution is used */
2026 )
2027{
2029 SCIP_NLROW* nlrow;
2031 SCIP_SOL* bestsol;
2034 SCIP_VAR** subvars;
2035 SCIP_VAR** sortedvars;
2036 SCIP_VAR* var;
2038 SCIP_VAR* v;
2039 SCIP_RETCODE retcode;
2040 SCIP_Real* absranks;
2041 SCIP_Real* ranks;
2042 SCIP_Real* startpoint;
2043 SCIP_Real* dualval;
2044 SCIP_Real* lastval;
2045 SCIP_Real* seclastval;
2046 SCIP_Real* newval;
2047 SCIP_Real bound;
2048 SCIP_Real maxslack;
2049 SCIP_Real objvalue;
2050 int i;
2051 int k;
2052 int nsubvars;
2053 int nsubbinvars;
2054 int nsubintvars;
2055 int nsubconss;
2056 int maxequalranks;
2057
2058 assert(scip != NULL);
2059 assert(heur != NULL);
2060
2061 /* dio not run without nlp solver */
2062 if( SCIPgetNNlpis(scip) <= 0 )
2063 return SCIP_OKAY;
2064
2065 /* get heuristic's data */
2066 heurdata = SCIPheurGetData(heur);
2067 assert(heurdata != NULL);
2068
2069 /* don't use the heuristic, if the gap is small so we don't expect to get better solutions than already found */
2070 if( SCIPgetGap(scip) * 100 < heurdata->mingap )
2071 {
2072 SCIPdebugMsg(scip, "return13 : gap is less than mingap\n");
2073 return SCIP_OKAY;
2074 }
2075
2076 /* in the mode 'onlyleaves' don't run the heuristic if we are not in a leaf of the B&B tree */
2077 if( heurdata->onlyleaves && (SCIPgetNLPBranchCands(scip) != 0 || SCIPgetNPseudoBranchCands(scip) != 0) )
2078 return SCIP_OKAY;
2079
2080 /* try to setup subscip if not tried before */
2081 if( heurdata->subscip == NULL && !heurdata->triedsetupsubscip )
2082 {
2084 }
2085
2086 /* quit the recursion if we have found a solution */
2087 if( heurdata->solfound )
2088 {
2089 SCIPdebugMsg(scip, "return1 : already found solution \n");
2090 return SCIP_OKAY;
2091 }
2092
2094
2095 /* not initialized */
2096 if( heurdata->subscip == NULL )
2097 {
2098 SCIPdebugMsg(scip, "return2 : subscip is NULL\n");
2099 return SCIP_OKAY;
2100 }
2101
2102 assert(heurdata->nsubvars > 0);
2103 assert(heurdata->varsubsciptoscip != NULL);
2104
2105 /* fix discrete variables in sub-SCIP */
2108
2109 if( heurdata->onlycheaper && !SCIPisInfinity(scip, bound) )
2110 {
2111 SCIP_CALL( SCIPchgRhsLinear( heurdata->subscip, heurdata->objbound, bound) );
2112 }
2113
2114 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "presolving/maxrounds", 1) );
2115 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "propagating/maxroundsroot", 0) );
2116
2117 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 1LL) );
2118 SCIP_CALL( SCIPpresolve(heurdata->subscip) );
2119
2121 {
2122 SCIPdebugMsg(scip, "return 4 : subscip is infeasible\n");
2123
2125 heurdata->prevInfeasible = TRUE;
2127
2128 return SCIP_OKAY;
2129 }
2130
2131 /* If no NLP was constructed, then there were no nonlinearities after presolve.
2132 * So we increase the nodelimit to 1 and hope that SCIP will find some solution to this probably linear subproblem.
2133 */
2134 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 0LL) );
2135 retcode = SCIPsolve(heurdata->subscip);
2136 heurdata->isnlp = TRUE;
2137
2138 bestsol = NULL;
2139
2140 /* we have no dualvalues, so give up */
2142 {
2145
2146 return SCIP_OKAY;
2147 }
2148
2149 if( ! SCIPisNLPConstructed(heurdata->subscip) && retcode == SCIP_OKAY )
2150 {
2151 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 1LL) );
2152 SCIP_CALL( SCIPsolve(heurdata->subscip) );
2153 heurdata->isnlp = FALSE;
2154 bestsol = SCIPgetBestSol(heurdata->subscip);
2155 }
2156
2157 if( heurdata->isnlp )
2158 {
2159 /* add non-combinatorial linear constraints from subscip into subNLP */
2161
2163
2164 /* set starting values (=refpoint, if not NULL; otherwise LP solution (or pseudo solution)) */
2165 for( i = 0; i < SCIPgetNNLPVars(heurdata->subscip); ++i )
2166 {
2167 SCIP_Real scalar = 1.0;
2168 SCIP_Real constant = 0.0;
2169
2170 subvar = SCIPgetNLPVars(heurdata->subscip)[i];
2171
2172 /* gets corresponding original variable */
2173 SCIP_CALL( SCIPvarGetOrigvarSum(&subvar, &scalar, &constant) );
2174 if( subvar == NULL )
2175 {
2176 startpoint[i] = constant;
2177 continue;
2178 }
2179
2180 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, subvar);
2181 if( var == NULL || REALABS( SCIPgetSolVal(scip, refpoint, var) ) > 1.0e+12 )
2182 {
2183 SCIP_Real tmpmax;
2184 tmpmax = MAX( 0.0, SCIPvarGetLbGlobal(subvar) );/*lint !e666*/
2185 startpoint[i] = MIN( tmpmax, SCIPvarGetUbGlobal(subvar) );/*lint !e666*/
2186 }
2187 else
2188 /* scalar*subvar+constant corresponds to nlpvar[i], so nlpvar[i] gets value scalar*varval+constant */
2189 startpoint[i] = scalar * SCIPgetSolVal(scip, refpoint, var) + constant;
2190 }
2191
2193
2194 /* don't need startpoint array anymore */
2196
2197 SCIP_CALL( SCIPsolveNLP(heurdata->subscip, .verblevel = (unsigned short)heurdata->nlpverblevel) ); /*lint !e666*/
2199
2200 /* in this case there was an error in ipopt, we try to give another startpoint */
2202 {
2204 SCIP_CALL( SCIPsolveNLP(heurdata->subscip, .verblevel = (unsigned short)heurdata->nlpverblevel) ); /*lint !e666*/
2206 }
2207
2210
2211 /* free memory of all entries and clear the hashmap before filling it */
2212 for( i = 0; i < nsubconss; i++ )
2213 {
2214 dualval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, subconss[i]);
2216 }
2217 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->dualvalues) );
2218
2219 /* save the dualvalues from our nlp solution */
2220 for( i = 0; i < nsubconss; i++ )
2221 {
2223
2225
2226 if( transcons == NULL )
2227 continue;
2228
2229 if( SCIPconsGetHdlr(transcons) != SCIPfindConshdlr(heurdata->subscip, "linear") )
2230 continue;
2231
2232 nlrow = (SCIP_NLROW*)SCIPhashmapGetImage(heurdata->conss2nlrow, transcons);
2233
2234 if (nlrow != NULL)
2235 {
2236 SCIP_CALL( SCIPallocBlockMemoryArray(heurdata->subscip, &dualval, 1) ); /*lint !e506*/
2237 *dualval = SCIPnlrowGetDualsol(nlrow);
2238 }
2239 else
2240 {
2241 SCIP_CALL( SCIPallocBlockMemoryArray(heurdata->subscip, &dualval, 1) ); /*lint !e506*/
2242 *dualval = 0;
2243 }
2244
2246 }
2247
2248 bestsol = NULL;
2249 SCIP_CALL( createSolFromNLP(heurdata->subscip, heur, &bestsol) );
2250 }
2251
2252 /* if we are infeasible, we can't do anything*/
2254 {
2255 SCIPdebugMsg(scip, "return4 : the subscip is infeasible\n");
2256
2258
2259 return SCIP_OKAY;
2260 }
2261
2262 maxslack = maximalslack(scip, heurdata);
2263 SCIPdebugMsg(scip, "origObj: %f\n", SCIPgetSolOrigObj(heurdata->subscip, bestsol));
2264 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, &nsubbinvars, &nsubintvars, NULL, NULL) );
2265 objvalue = 0.0;
2266 assert(bestsol != NULL);
2267
2268 /* save information about maximal violation */
2269 for( i = 0; i < nsubvars; i++ )
2270 {
2271 subvar = SCIPgetOrigVars(heurdata->subscip)[i];
2272
2273 if( SCIPhashmapGetImage(heurdata->slack2var, subvar) == NULL )
2274 objvalue += SCIPvarGetObj(subvar) * SCIPgetSolVal(heurdata->subscip, bestsol, subvar);
2275 }
2276
2277 /* we stop the heuristic if it does not come "closer" to a feasible solution*/
2278 if( heurdata->forceimprovements )
2279 {
2280 if( SCIPisGE(scip, SCIPgetSolOrigObj(heurdata->subscip, bestsol) - objvalue, heurdata->prevobjective) && maxslack > 0 )
2281 {
2282 heurdata->nonimprovingRounds++;
2283 SCIPdebugMsg(scip, "nonimpr rounds %d prevobj %f \n", heurdata->nonimprovingRounds, heurdata->prevobjective);
2284
2285 /* leave, if we have not improved some iterations*/
2286 if( heurdata->nonimprovingRounds > heurdata->maxcalls/8 )
2287 {
2289
2290 if( heurdata->isnlp )
2291 {
2292 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) );
2293 }
2294
2296
2297 heurdata->solfound = TRUE;
2298 heurdata->switchdifferent = TRUE;
2299
2300 SCIPdebugMsg(scip, "return11 : solution did not improve\n");
2301
2302 return SCIP_OKAY;
2303 }
2304 }
2305 }
2306
2307 heurdata->prevobjective = SCIPgetSolOrigObj(heurdata->subscip, bestsol) - objvalue;
2308
2309 /* in this case we found a feasible solution, store it, clean up and stop the heuristic*/
2310 if( SCIPisFeasLE(heurdata->subscip, maxslack, 0.0) )
2311 return storeSolution(scip, heur, result, transsol, bestsol);
2312
2313 SCIP_CALL( SCIPallocBufferArray(scip, &ranks, heurdata->nintegervars) );
2314 SCIP_CALL( SCIPallocBufferArray(scip, &sortedvars, heurdata->nintegervars) );
2316
2317 /* compute ranks and sort them in non-increasing order */
2318 SCIP_CALL( computeRanks(scip, heurdata, absranks, ranks, sortedvars) );
2319
2320 /* print out the highest ranks */
2321 if( heurdata->heurverblevel > 1 )
2322 {
2323 k = heurdata->rankvalue;
2324
2325 if( heurdata->nintegervars < heurdata->rankvalue )
2326 k = heurdata->nintegervars;
2327
2328 for( i = 0; i < k; i++ )
2329 {
2330 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%i. rank: %f name: %s\n", i, ranks[i], SCIPvarGetName(sortedvars[i]));
2331 }
2332 }
2333
2334 /* free solution */
2335 if( heurdata->isnlp )
2336 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) );
2337
2338 /* we don't allow more than a third of the variables to have the same rank */
2339 maxequalranks = MIN(heurdata->maxequalranks, heurdata->nintegervars/3);
2340
2341 if( heurdata->maxequalranks >= 0 && SCIPisFeasEQ(heurdata->subscip, REALABS(ranks[0]), REALABS(ranks[maxequalranks])) )
2342 {
2344
2345 SCIPdebugMsg(scip, "return12 : equal maxranks\n");
2346
2348 return SCIP_OKAY;
2349 }
2350
2351 /* now we can start switching the variable values */
2353
2354 /* set bounds of fixed discrete variables to original values so we can switch */
2355 for( k = 0; k < heurdata->nintegervars; ++k )
2356 {
2357 var = heurdata->integervars[k];
2358 if( var == NULL )
2359 break;
2360
2362 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
2363
2365 if( rcons != NULL )
2366 continue;
2367
2368 assert(var != NULL);
2369 assert(subvar != NULL);
2370
2371 if ( SCIPhashmapGetImage(heurdata->indicopymap, subvar) != NULL )
2373
2376 }
2377
2378 /* switch variable with maximum ranking if possible */
2379 for( i = 0; i < heurdata->nintegervars; i++ )
2380 {
2381 v = sortedvars[i];
2382 SCIP_CALL( SCIPallocBlockMemoryArray(heurdata->subscip, &newval, 1) ); /*lint !e506*/
2383
2384 /* compute the new value of the variable */
2385
2386 /* if we have an indicator constraint, we turn it off */
2387 if( SCIPhashmapGetImage(heurdata->slacktoindivarsmap, v) != NULL )
2388 {
2389 /* get the indicator var of this constraint */
2390 v = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->slacktoindivarsmap, v);
2391
2392 /* set the value to 0 */
2393 SCIP_CALL( SCIPsetSolVal(scip, transsol, v, 0.0) );
2394 if( heurdata->heurverblevel > 1 )
2395 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Setting value of %s%s to 0\n", SCIPvarIsNegated(v) ? "(negated) " : " ", SCIPvarGetName(v));
2396
2397 *newval = 0.0;
2398 SCIP_CALL( SCIPhashmapInsert(heurdata->switchedvars, v, newval) );
2399 }
2400 else
2401 {
2402 if( ranks[i] > 0 )
2403 {
2404 if( SCIPvarIsBinary(v) && SCIPisEQ(scip, 1.0, SCIPgetSolVal(scip, transsol, v)) )
2405 continue;
2406
2407 /* ignore fixed vars in input */
2409 continue;
2410
2411 *newval = SCIPgetSolVal(scip, transsol, v) + 1;
2412 }
2413 else
2414 {
2415 if( SCIPvarIsBinary(v) && SCIPisEQ(scip, 0.0, SCIPgetSolVal(scip, transsol, v)) )
2416 continue;
2417
2419 continue;
2420
2421 *newval = SCIPgetSolVal(scip, transsol, v) - 1;
2422 }
2423 }
2424 lastval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars, v);
2425 seclastval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars2, v);
2426
2427 /* we don't want to set a variable to a value it already had,or set a binary variable more than once */
2428 if( (lastval != NULL && (SCIPvarIsBinary(v) || SCIPisFeasEQ(scip, *lastval, *newval))) || (seclastval != NULL && SCIPisFeasEQ(scip, *seclastval, *newval)) )
2429 {
2430 SCIPfreeBlockMemoryArray(heurdata->subscip, &newval, 1);
2431 continue;
2432 }
2433 else /* update the switchedvars values, switchedvars2 is the second last and switchedvars the last value */
2434 {
2435 if( seclastval != NULL )
2437
2438 SCIP_CALL( SCIPhashmapRemove(heurdata->switchedvars2, v) );
2439 SCIP_CALL( SCIPhashmapInsert(heurdata->switchedvars2, v, lastval) );
2440 SCIP_CALL( SCIPhashmapRemove(heurdata->switchedvars, v) );
2441 SCIP_CALL( SCIPhashmapInsert(heurdata->switchedvars, v, newval) );
2442
2443 if( heurdata->heurverblevel > 1 )
2444 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Setting value of %s from %f to %f\n", SCIPvarGetName(v), SCIPgetSolVal(scip, transsol, v), *newval);
2445
2446 SCIP_CALL( SCIPsetSolVal(scip, transsol, v, *newval) );
2447 }
2448
2449 /* if we have exceeded our iterations limit give up without any solution */
2450 if( heurdata->usedcalls >= heurdata->maxcalls )
2451 {
2452 SCIPdebugMsg(scip, "return5 : reached iteration limit\n");
2453
2456 return SCIP_OKAY;
2457 }
2458
2459 heurdata->usedcalls++;
2460
2461 if( heurdata->heurverblevel > 1 )
2462 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "----- Total Calls: %d\n", heurdata->usedcalls);
2463
2464 /* recursive call of the heuristic */
2466
2467 /* just to go up in the recursion */
2468 if( *result == SCIP_DIDNOTFIND || heurdata->solfound || heurdata->prevInfeasible )
2469 {
2470 SCIPdebugMsg(scip, "return6 : go up\n");
2471
2472 /* here we only go up one step and try another switch (switch the same variables again is forbidden
2473 * since they are contained in switchedvars) */
2474 if( heurdata->switchdifferent )
2475 {
2476 heurdata->switchdifferent = FALSE;
2477 heurdata->solfound = FALSE;
2479 heurdata->nonimprovingRounds -= 2;
2480 }
2481
2482 if( heurdata->prevInfeasible )
2483 {
2484 heurdata->prevInfeasible = FALSE;
2485 heurdata->solfound = FALSE;
2487 heurdata->nonimprovingRounds++;
2488 }
2489
2491 return SCIP_OKAY;
2492 }
2493 }
2494
2495 if( heurdata->subscip == NULL )
2496 {
2497 /* something horrible must have happened that we decided to give up completely on this heuristic */
2499 SCIPdebugMsg(scip, "return7 : subscip was set NULL\n");
2500
2502 return SCIP_OKAY;
2503 }
2504 assert(!SCIPisTransformed(heurdata->subscip));
2505
2506 SCIPdebugMsg(scip, "return8 : cannot switch any variable\n");
2507
2509
2511 return SCIP_OKAY;
2512}
2513
2514
2515/* Callback methods of primal heuristic */
2516
2517/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
2518static
2520{
2522
2523 assert(scip != NULL);
2524 assert(heur != NULL);
2525
2526 heurdata = SCIPheurGetData(heur);
2527
2529
2530 return SCIP_OKAY;
2531}
2532
2533
2534/** initialization method of primal heuristic (called after problem was transformed) */
2535static
2537{ /*lint --e{715}*/
2539
2540 assert(scip != NULL);
2541 assert(heur != NULL);
2542
2543 /* skip setting up sub-SCIP if heuristic is disabled or we do not want to run the heuristic */
2544 if( SCIPheurGetFreq(heur) < 0 )
2545 return SCIP_OKAY;
2546
2547 SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrestarts", 0) );
2548
2549 heurdata = SCIPheurGetData(heur);
2550 assert(heurdata != NULL);
2551 assert(heurdata->subscip == NULL);
2552 assert(!heurdata->triedsetupsubscip);
2553
2554 /* create sub-SCIP for later use */
2556
2557 /* creating sub-SCIP may fail if the solver interfaces did not copy into subscip */
2558 if( heurdata->subscip == NULL )
2559 return SCIP_OKAY;
2560
2561 /* if the heuristic is called at the root node, we want to be called directly after the initial root LP solve */
2562 if( SCIPheurGetFreqofs(heur) == 0 )
2564
2565 SCIP_CALL( SCIPhashmapCreate(&heurdata->dualvalues, SCIPblkmem(scip), 512) );
2566
2567 return SCIP_OKAY;
2568}
2569
2570/** deinitialization method of primal heuristic (called before transformed problem is freed) */
2571static
2573{ /*lint --e{715}*/
2576 SCIP_Real* dualval;
2577 int i;
2578 int nsubconss;
2579
2580 assert(scip != NULL);
2581 assert(heur != NULL);
2582
2583 heurdata = SCIPheurGetData(heur);
2584 assert(heurdata != NULL);
2585
2586 SCIPfreeBlockMemoryArrayNull(scip, &heurdata->integervars, heurdata->integervarssize);
2587
2588 if( heurdata->subscip != NULL)
2589 {
2592
2593 /* free memory of all entries and clear the hashmap before filling it */
2594 for( i = 0; i < nsubconss; i++ )
2595 {
2596 dualval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, subconss[i]);
2598 }
2599 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->dualvalues) );
2600 SCIPhashmapFree(&heurdata->dualvalues);
2601
2602 if( heurdata->varsciptosubscip != NULL )
2603 {
2604 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->varsciptosubscip, TRUE) );
2605
2606 SCIPhashmapFree(&heurdata->varsciptosubscip);
2607 }
2608 if( heurdata->origsubscipConsMap != NULL )
2609 {
2610 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->origsubscipConsMap, FALSE) );
2611
2612 SCIPhashmapFree(&heurdata->origsubscipConsMap);
2613 }
2614 if( heurdata->relaxcons != NULL )
2615 {
2616 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->relaxcons, FALSE) );
2617
2618 SCIPhashmapFree(&heurdata->relaxcons);
2619 }
2620 if( heurdata->conss2nlrow != NULL )
2621 {
2622 SCIP_CALL( releaseHashmapNLPRows(heurdata->subscip, heurdata->conss2nlrow) );
2623
2624 SCIPhashmapFree(&heurdata->conss2nlrow);
2625 }
2626 if( heurdata->slack2var != NULL )
2627 {
2628 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->slack2var, TRUE) );
2629
2630 SCIPhashmapFree(&heurdata->slack2var);
2631 }
2632 if( heurdata->indicopymap != NULL )
2633 {
2634 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->indicopymap, TRUE) );
2635
2636 SCIPhashmapFree(&heurdata->indicopymap);
2637 }
2638 if( heurdata->indicopymapback != NULL )
2639 {
2640 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->indicopymapback, TRUE) );
2641
2642 SCIPhashmapFree(&heurdata->indicopymapback);
2643 }
2644 if( heurdata->relaxconsindi != NULL )
2645 {
2646 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->relaxconsindi, FALSE) );
2647
2648 SCIPhashmapFree(&heurdata->relaxconsindi);
2649 }
2650 if( heurdata->slackvarlbMap != NULL )
2651 {
2652 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->slackvarlbMap, TRUE) );
2653
2654 SCIPhashmapFree(&heurdata->slackvarlbMap);
2655 }
2656 if( heurdata->slackvarubMap != NULL )
2657 {
2658 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->slackvarubMap, TRUE) );
2659
2660 SCIPhashmapFree(&heurdata->slackvarubMap);
2661 }
2662
2663 if( heurdata->subscip != NULL )
2664 {
2666 }
2667 }
2668
2669 if( heurdata->varsubsciptoscip != NULL )
2670 {
2671 SCIP_CALL( releaseHashmapEntries(scip, heurdata->varsubsciptoscip, TRUE) );
2672
2673 SCIPhashmapFree(&heurdata->varsubsciptoscip);
2674 }
2675 if( heurdata->slacktoindivarsmap != NULL )
2676 {
2677 SCIP_CALL( releaseHashmapEntries(scip, heurdata->slacktoindivarsmap, TRUE) );
2678
2679 SCIPhashmapFree(&heurdata->slacktoindivarsmap);
2680 }
2681 if( heurdata->indicators != NULL )
2682 {
2684
2685 SCIPhashmapFree(&heurdata->indicators);
2686 }
2687 if( heurdata->switchedvars != NULL )
2688 {
2689 SCIPhashmapFree(&heurdata->switchedvars);
2690 }
2691 if( heurdata->switchedvars2 != NULL )
2692 {
2693 SCIPhashmapFree(&heurdata->switchedvars2);
2694 }
2695
2696 /* reset some flags and counters */
2697 heurdata->triedsetupsubscip = FALSE;
2698 heurdata->usedcalls = 0;
2699 heurdata->solfound = FALSE;
2700 heurdata->prevInfeasible = FALSE;
2701
2702 assert(heurdata->subscip == NULL);
2703 assert(heurdata->varsubsciptoscip == NULL);
2704 assert(heurdata->varsciptosubscip == NULL);
2705
2706 return SCIP_OKAY;
2707}
2708
2709/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
2710static
2712{
2714
2715 assert(scip != NULL);
2716 assert(heur != NULL);
2717
2718 /* skip setting up sub-SCIP if heuristic is disabled or we do not want to run the heuristic */
2719 if( SCIPheurGetFreq(heur) < 0 )
2720 return SCIP_OKAY;
2721
2722 heurdata = SCIPheurGetData(heur);
2723 assert(heurdata != NULL);
2724
2725 /* creating sub-SCIP may fail if the solver interfaces did not copy into subscip */
2726 if( heurdata->subscip == NULL )
2727 return SCIP_OKAY;
2728
2729 /* if the heuristic is called at the root node, we want to be called directly after the initial root LP solve */
2730 if( SCIPheurGetFreqofs(heur) == 0 )
2732
2733 return SCIP_OKAY;
2734}
2735
2736
2737/** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
2738static
2740{
2741 assert(scip != NULL);
2742 assert(heur != NULL);
2743
2745
2746 return SCIP_OKAY;
2747}
2748
2749
2750/** execution method of primal heuristic */
2751static
2753{ /*lint --e{715}*/
2755
2756 assert(scip != NULL);
2757 assert(heur != NULL);
2758 assert(result != NULL);
2759
2760 /* get heuristic's data */
2761 heurdata = SCIPheurGetData(heur);
2762 assert(heurdata != NULL);
2763
2764 /* obviously, we did not do anything yet */
2766
2767 /* init data */
2768 heurdata->usedcalls = 0;
2769 heurdata->prevInfeasible = FALSE;
2770 heurdata->solfound = FALSE;
2771 heurdata->nonimprovingRounds = 0;
2772 heurdata->prevobjective = INT_MAX;
2773
2775
2776 /* SCIP does not like cutoff as return, so we say didnotfind, since we did not find a solution */
2777 if( *result == SCIP_CUTOFF )
2779
2780 /* reset timing, if it was changed temporary (at the root node) */
2781 if( heurtiming != HEUR_TIMING )
2783
2784 return SCIP_OKAY;
2785}
2786
2787
2788/* primal heuristic specific interface methods */
2789
2790/** creates the dualval primal heuristic and includes it in SCIP */
2792 SCIP* scip /**< SCIP data structure */
2793 )
2794{
2796 SCIP_HEUR* heur = NULL;
2797
2798 /* create dualval primal heuristic data */
2801
2802 /* include primal heuristic */
2803
2804 /* use SCIPincludeHeurBasic() plus setter functions if you want to set callbacks one-by-one and your code should
2805 * compile independent of new callbacks being added in future SCIP versions */
2809
2810 assert(heur != NULL);
2811
2812 /* set non fundamental callbacks via setter functions */
2818
2819 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/forceimprovements",
2820 "exit if objective doesn't improve",
2821 &heurdata->forceimprovements, TRUE, DEFAULT_FORCEIMPROVEMENTS, NULL, NULL) );
2822
2823 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlycheaper",
2824 "add constraint to ensure that discrete vars are improving",
2825 &heurdata->onlycheaper, TRUE, DEFAULT_ONLYCHEAPER, NULL, NULL) );
2826
2827 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlyleaves",
2828 "disable the heuristic if it was not called at a leaf of the B&B tree",
2829 &heurdata->onlyleaves, FALSE, DEFAULT_ONLYLEAVES, NULL, NULL) );
2830
2831 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/relaxindicators",
2832 "relax the indicator variables by introducing continuous copies",
2833 &heurdata->relaxindicators, FALSE, DEFAULT_RELAXINDICATORS, NULL, NULL) );
2834
2835 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/relaxcontvars",
2836 "relax the continous variables",
2837 &heurdata->relaxcontvars, FALSE, DEFAULT_RELAXCONTVARS, NULL, NULL) );
2838
2839 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/heurverblevel",
2840 "verblevel of the heuristic, default is 0 to display nothing",
2841 &heurdata->heurverblevel, FALSE, DEFAULT_HEURVERBLEVEL, 0, 4, NULL, NULL) );
2842
2843 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nlpverblevel",
2844 "verblevel of the nlp solver, can be 0 or 1",
2845 &heurdata->nlpverblevel, FALSE, DEFAULT_NLPVERBLEVEL, 0, 1, NULL, NULL) );
2846
2847 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/rankvalue",
2848 "number of ranks that should be displayed when the heuristic is called",
2849 &heurdata->rankvalue, FALSE, DEFAULT_RANKVALUE, 0, INT_MAX, NULL, NULL) );
2850
2851 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxcalls",
2852 "maximal number of recursive calls of the heuristic (if dynamicdepth is off)",
2853 &heurdata->maxcalls, FALSE, DEFAULT_MAXCALLS, 0, INT_MAX, NULL, NULL) );
2854
2855 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/dynamicdepth",
2856 "says if and how the recursion depth is computed at runtime",
2857 &heurdata->dynamicdepth, FALSE, DEFAULT_DYNAMICDEPTH, 0, 1, NULL, NULL) );
2858
2859 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxequalranks",
2860 "maximal number of variables that may have maximal rank, quit if there are more, turn off by setting -1",
2861 &heurdata->maxequalranks, FALSE, DEFAULT_MAXEQUALRANKS, -1, INT_MAX, NULL, NULL) );
2862
2863 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/mingap",
2864 "minimal gap for which we still run the heuristic, if gap is less we return without doing anything",
2865 &heurdata->mingap, FALSE, DEFAULT_MINGAP, 0.0, 100.0, NULL, NULL) );
2866
2867 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lambdaslack",
2868 "value added to objective of slack variables, must not be zero",
2869 &heurdata->lambdaslack, FALSE, DEFAULT_LAMBDASLACK, 0.1, SCIPinfinity(scip), NULL, NULL) );
2870
2871 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lambdaobj",
2872 "scaling factor for the objective function",
2873 &heurdata->lambdaobj, FALSE, DEFAULT_LAMBDAOBJ, 0.0, 1.0, NULL, NULL) );
2874
2875 return SCIP_OKAY;
2876}
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 NULL
Definition def.h:267
#define SCIP_MAXSTRLEN
Definition def.h:288
#define SCIP_INVALID
Definition def.h:193
#define MIN(x, y)
Definition def.h:243
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define MAX(x, y)
Definition def.h:239
#define REALABS(x)
Definition def.h:197
#define SCIP_CALL(x)
Definition def.h:374
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:3108
void * SCIPhashmapEntryGetImage(SCIP_HASHMAPENTRY *entry)
Definition misc.c:3570
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3261
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition misc.c:3156
int SCIPhashmapGetNEntries(SCIP_HASHMAP *hashmap)
Definition misc.c:3541
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition misc.c:3549
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition misc.c:3074
void * SCIPhashmapEntryGetOrigin(SCIP_HASHMAPENTRY *entry)
Definition misc.c:3560
SCIP_RETCODE SCIPhashmapRemoveAll(SCIP_HASHMAP *hashmap)
Definition misc.c:3633
SCIP_RETCODE SCIPhashmapRemove(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3439
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 SCIPresetParam(SCIP *scip, const char *name)
Definition scip_param.c:835
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:4636
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:941
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4670
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4593
void SCIPconsAddUpgradeLocks(SCIP_CONS *cons, int nlocks)
Definition cons.c:8653
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition cons.c:8473
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition cons.c:8234
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition cons.c:8383
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition cons.c:8413
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition cons.c:8403
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition cons.c:8433
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition cons.c:8453
SCIP_Bool SCIPconsIsEnabled(SCIP_CONS *cons)
Definition cons.c:8311
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition cons.c:8214
SCIP_RETCODE SCIPgetTransformedCons(SCIP *scip, SCIP_CONS *cons, SCIP_CONS **transcons)
Definition scip_cons.c:1675
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition cons.c:8493
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1174
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition cons.c:8393
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_cons.c:1139
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition cons.c:8483
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:1364
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:1548
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition heur.c:1493
int SCIPheurGetFreqofs(SCIP_HEUR *heur)
Definition heur.c:1559
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur,)
Definition scip_heur.c:242
int SCIPheurGetFreq(SCIP_HEUR *heur)
Definition heur.c:1538
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:200
SCIP_RETCODE SCIPaddNlRow(SCIP *scip, SCIP_NLROW *nlrow)
Definition scip_nlp.c:396
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition scip_nlp.c:110
SCIP_NLPSOLSTAT SCIPgetNLPSolstat(SCIP *scip)
Definition scip_nlp.c:574
#define SCIPsolveNLP(...)
Definition scip_nlp.h:361
SCIP_RETCODE SCIPsetNLPInitialGuess(SCIP *scip, SCIP_Real *initialguess)
Definition scip_nlp.c:474
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:1058
SCIP_Real SCIPnlrowGetDualsol(SCIP_NLROW *nlrow)
Definition nlp.c:1969
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:954
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition scip_sol.c:2169
SCIP_Real SCIPsolGetOrigObj(SCIP_SOL *sol)
Definition sol.c:2741
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition scip_sol.c:421
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:3050
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition scip_sol.c:1300
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition scip_sol.c:1077
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1217
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:12774
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition var.c:17894
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition var.c:17748
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition var.c:17599
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17926
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17584
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition scip_var.c:1796
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:18088
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition var.c:17768
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17419
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition scip_var.c:1250
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition scip_var.c:4945
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition var.c:17610
SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible)
Definition scip_var.c:8178
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition scip_var.c:1529
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition var.c:17574
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition scip_var.c:5034
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:18078
SCIP_VAR * SCIPvarGetTransVar(SCIP_VAR *var)
Definition var.c:17778
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition scip_var.c:4515
SCIP_Real SCIPvarGetNLPSol(SCIP_VAR *var)
Definition var.c:18465
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:1216
void SCIPsortDownRealRealPtr(SCIP_Real *realarray1, SCIP_Real *realarray2, void **ptrarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10877
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
memory allocation routines
#define BMSclearMemory(ptr)
Definition memory.h:129
#define BMSclearMemoryArray(ptr, num)
Definition memory.h:130
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 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:65
#define SCIP_DECL_HEURINITSOL(x)
Definition type_heur.h:132
struct SCIP_HeurData SCIP_HEURDATA
Definition type_heur.h:77
#define SCIP_DECL_HEURINIT(x)
Definition type_heur.h:113
#define SCIP_DECL_HEUREXIT(x)
Definition type_heur.h:121
#define SCIP_DECL_HEURFREE(x)
Definition type_heur.h:105
#define SCIP_DECL_HEUREXITSOL(x)
Definition type_heur.h:143
#define SCIP_DECL_HEUREXEC(x)
Definition type_heur.h:163
@ 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