Scippy

SCIP

Solving Constraint Integer Programs

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
168SCIP_DECL_EVENTINIT(eventInitLPsol)
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
181SCIP_DECL_EVENTEXIT(eventExitLPsol)
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
194SCIP_DECL_EVENTEXEC(eventExecLPsol)
195{ /*lint --e{715}*/
196 int i;
197 int nsubconss;
198 SCIP_HEURDATA* heurdata;
199 SCIP_CONS** subconss;
200 SCIP_Real* dualval;
201
202 assert(eventhdlr != NULL);
203 assert(event != NULL);
204 assert(scip != NULL);
206
207 heurdata = (SCIP_HEURDATA* )SCIPeventhdlrGetData(eventhdlr);
208 nsubconss = SCIPgetNOrigConss(heurdata->subscip);
209 subconss = SCIPgetOrigConss(heurdata->subscip);
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 )
216 SCIPfreeBlockMemoryArray(heurdata->subscip, &dualval, 1);
217 }
218 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->dualvalues) );
219
220 /* insert dualvalues from LP into a hashmap */
221 for( i = 0; i < nsubconss; i++ )
222 {
223 SCIP_CONS* transcons = NULL;
224 SCIP_CALL( SCIPgetTransformedCons(heurdata->subscip, subconss[i], &transcons) );
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*/
233 *dualval = -SCIPgetDualsolLinear(heurdata->subscip, transcons );
234 SCIP_CALL( SCIPhashmapInsert(heurdata->dualvalues, subconss[i], dualval) );
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 */
255 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecLPsol, eventhdlrdata) );
256 assert(eventhdlr != NULL);
257
258 SCIP_CALL( SCIPsetEventhdlrInit(scip, eventhdlr, eventInitLPsol) );
259 SCIP_CALL( SCIPsetEventhdlrExit(scip, eventhdlr, eventExitLPsol) );
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 {
286 SCIP_HASHMAPENTRY* entry;
287 entry = SCIPhashmapGetEntry(hashmap, i);
288
289 if( entry != NULL )
290 {
291 if( isvarmap )
292 {
293 SCIP_VAR* var;
294 var = (SCIP_VAR*) SCIPhashmapEntryGetImage(entry);
295
296 SCIP_CALL( SCIPreleaseVar(scip, &var) );
297 }
298 else
299 {
300 SCIP_CONS* cons;
301 cons = (SCIP_CONS*) SCIPhashmapEntryGetImage(entry);
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 {
328 SCIP_HASHMAPENTRY* entry;
329 entry = SCIPhashmapGetEntry(hashmap, i);
330 if( entry != NULL )
331 {
332 SCIP_NLROW* nlrow;
333 nlrow = (SCIP_NLROW*) SCIPhashmapEntryGetImage(entry);
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 {
391 iscombinatorial = TRUE;
392
393 for( j = 0; j < nvars; ++j )
394 {
396 {
397 iscombinatorial = FALSE;
398 break;
399 }
400 }
401
402 /* skip constraint, if not of interest */
403 if( (iscombinatorial && !addcombconss) || (!iscombinatorial && !addcontconss) )
404 continue;
405 }
406
407 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[i]), 0.0,
408 SCIPgetNVarsLinear(scip, conss[i]), SCIPgetVarsLinear(scip, conss[i]), SCIPgetValsLinear(scip, conss[i]), NULL,
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
456 iscombinatorial = SCIPvarGetType(vars[0]) < SCIP_VARTYPE_CONTINUOUS && SCIPvarGetType(vars[1]) < SCIP_VARTYPE_CONTINUOUS;
457
458 /* skip constraint, if not of interest */
459 if( (iscombinatorial && !addcombconss) || (!iscombinatorial && !addcontconss) )
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,
467 SCIPgetLhsVarbound(scip, conss[i]), SCIPgetRhsVarbound(scip, conss[i]),
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 {
519 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nvars) );
520 }
521 else
522 {
523 SCIP_CALL( SCIPreallocBufferArray(scip, &coefs, nvars) );
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 {
588 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nvars) );
589 }
590 else
591 {
592 SCIP_CALL( SCIPreallocBufferArray(scip, &coefs, nvars) );
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 {
681 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, nvars) );
682 }
683 else
684 {
685 SCIP_CALL( SCIPreallocBufferArray(scip, &coefs, nvars) );
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,
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 {
724 SCIP_CALL( addLinearConstraints(scip, conshdlr, addcombconss, addcontconss, heurdata) );
725 }
726
727 /* add varbound constraints */
728 conshdlr = SCIPfindConshdlr(scip, "varbound");
729 if( conshdlr != NULL )
730 {
731 SCIP_CALL( addVarboundConstraints(scip, conshdlr, addcombconss, addcontconss, heurdata) );
732 }
733
734 if( addcombconss )
735 {
736 /* add logic-or constraints */
737 conshdlr = SCIPfindConshdlr(scip, "logicor");
738 if( conshdlr != NULL )
739 {
740 SCIP_CALL( addLogicOrConstraints(scip, conshdlr, heurdata) );
741 }
742
743 /* add setppc constraints */
744 conshdlr = SCIPfindConshdlr(scip, "setppc");
745 if( conshdlr != NULL )
746 {
747 SCIP_CALL( addSetppcConstraints(scip, conshdlr, heurdata) );
748 }
749
750 /* add knapsack constraints */
751 conshdlr = SCIPfindConshdlr(scip, "knapsack");
752 if( conshdlr != NULL )
753 {
754 SCIP_CALL( addKnapsackConstraints(scip, conshdlr, heurdata) );
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{
773 SCIP_HEURDATA* heurdata;
774 SCIP_VAR** vars;
775 SCIP_VAR** subvars;
776 SCIP_VAR* var;
777 SCIP_VAR* subvar;
778 SCIP_Real scalar;
779 SCIP_Real constant;
780 SCIP_Real val;
781 int i;
782 int nvars;
783
784 heurdata = SCIPheurGetData(heur);
785 assert( heurdata != NULL );
786 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nvars, NULL, NULL, NULL, NULL) );
787
788 if( *sol == NULL )
789 {
790 SCIP_CALL( SCIPcreateOrigSol(scip, sol, heur) );
791 }
792
793 vars = SCIPgetOrigVars(scip);
794 nvars = SCIPgetNOrigVars(scip);
795
796 for( i = 0; i < nvars; ++i )
797 {
798 var = vars[i];
799
800 constant = 0;
801 scalar = 1.0;
802 var = SCIPvarGetTransVar(var);
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
814 SCIP_CALL( SCIPfreeSol(scip, sol) );
815 return SCIP_OKAY;
816 }
817
818 if( SCIPvarIsBinary(subvar) )
819 transval = SCIPvarGetLbGlobal(subvar);
820 else
821 {
822 SCIP_Real tconstant = 0.0;
823 SCIP_Real tscalar = 1.0;
824 SCIP_CALL( SCIPgetProbvarSum(heurdata->subscip, &subvar, &tscalar, &tconstant) );
825
826 transval = 0.0;
827
828 if( REALABS(tscalar) > 0.0 )
829 {
830 assert(subvar != NULL);
831 transval = SCIPgetSolVal(heurdata->subscip, subsol, subvar);
832 }
833
834 /* recompute aggregations */
835 transval = tscalar * transval + tconstant;
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{
861 SCIP_HASHMAP* varsmap;
862 SCIP_HASHMAP* conssmap;
863 SCIP_CONSHDLR* conshdlrindicator;
864 SCIP_CONSHDLR* conshdlrindi;
865 SCIP_CONSHDLR* conshdlrlin;
866 SCIP_CONSHDLR* conshdlrnonlin;
867 SCIP_CONSHDLR* conshdlrvarbound;
868 SCIP_CONSHDLR* conshdlrknapsack;
869 SCIP_CONSHDLR* conshdlrlogicor;
870 SCIP_CONSHDLR* conshdlrsetppc;
871 SCIP_CONSHDLR* currentconshdlr;
872 SCIP_CONS** conss;
873 SCIP_CONS* subcons;
874 SCIP_CONS* transcons;
875 SCIP_CONS* linindicons;
876 SCIP_CONS* indicons;
877 SCIP_CONS* cons = NULL;
878 SCIP_VAR** vars;
879 SCIP_VAR** subvars;
880 SCIP_VAR* var;
881 SCIP_VAR* tmpvar;
882 SCIP_VAR* subvar;
883 SCIP_VAR* slackvarpos;
884 SCIP_VAR* slackvarneg;
885 SCIP_VAR* indislackvarpos;
886 SCIP_VAR* indislackvarneg;
887 SCIP_VAR* indicatorcopy;
888 char probname[SCIP_MAXSTRLEN];
889 char varname[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");
913 conshdlrvarbound = SCIPfindConshdlr(scip, "varbound");
914 conshdlrknapsack = SCIPfindConshdlr(scip, "knapsack");
915 conshdlrlogicor = SCIPfindConshdlr(scip, "logicor");
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];
925 currentconshdlr = SCIPconsGetHdlr(cons);
926
927 if( currentconshdlr == conshdlrindi ||
928 currentconshdlr == conshdlrnonlin ||
929 currentconshdlr == conshdlrvarbound ||
930 currentconshdlr == conshdlrknapsack ||
931 currentconshdlr == conshdlrlogicor ||
932 currentconshdlr == conshdlrsetppc ||
933 currentconshdlr == conshdlrlin )
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 */
956 SCIP_CALL( SCIPhashmapCreate(&varsmap, SCIPblkmem(scip), nvars) );
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;
963 SCIP_CALL( SCIPcopyPlugins(scip, heurdata->subscip, TRUE, FALSE, TRUE, FALSE, TRUE,
964 FALSE, FALSE, FALSE, TRUE, FALSE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE, &success) );
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 */
972 SCIP_CALL( SCIPcopyParamSettings(scip, heurdata->subscip) );
973
974 /* disable bound limits */
975 SCIP_CALL( SCIPsetRealParam(heurdata->subscip, "limits/primal", SCIP_INVALID) );
976 SCIP_CALL( SCIPsetRealParam(heurdata->subscip, "limits/dual", SCIP_INVALID) );
977
978 /* create problem in sub-SCIP */
979
980 /* get name of the original problem and add "dualval" */
981 (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_dualval", SCIPgetProbName(scip));
982 SCIP_CALL( SCIPcreateProb(heurdata->subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
983
984 SCIP_CALL( SCIPincludeEventHdlrLPsol(heurdata->subscip, heurdata) );
985
986 /* copy all variables */
987 SCIP_CALL( SCIPcopyVars(scip, heurdata->subscip, varsmap, NULL, NULL, NULL, 0, TRUE) );
988
989 /* copy as many constraints as possible */
991 SCIP_CALL( SCIPcopyConss(scip, heurdata->subscip, varsmap, conssmap, TRUE, FALSE, &heurdata->subscipisvalid) );
992
993 SCIP_CALL( SCIPhashmapCreate(&heurdata->origsubscipConsMap, SCIPblkmem(scip), SCIPgetNConss(scip)) );
994
995 nconss = SCIPgetNOrigConss(scip);
996 conss = SCIPgetOrigConss(scip);
997
998 /* fill constraint mapping from original scip to the subscip */
999 for( i = 0; i < nconss; ++i )
1000 {
1001 transcons = NULL;
1002 SCIP_CALL( SCIPgetTransformedCons(scip, conss[i], &transcons) );
1003
1004 subcons = (SCIP_CONS*)SCIPhashmapGetImage(conssmap, transcons);
1005 assert( subcons != NULL );
1006
1007 SCIP_CALL( SCIPcaptureCons(heurdata->subscip, subcons) );
1008 SCIP_CALL( SCIPhashmapInsert(heurdata->origsubscipConsMap, transcons, subcons) );
1009 }
1010
1011 SCIP_CALL( SCIPhashmapCreate(&heurdata->conss2nlrow, SCIPblkmem(scip), SCIPgetNConss(scip)) );
1012
1013 if( !heurdata->subscipisvalid )
1014 {
1015 SCIPdebugMsg(scip, "In heur_dualval: failed to copy some constraints to sub-SCIP, continue anyway\n");
1016 }
1017
1018 SCIP_CALL( SCIPgetVarsData(heurdata->subscip, &subvars, &heurdata->nsubvars, NULL, NULL, NULL, NULL) );
1019 heurdata->nvars = nvars;
1020
1021 /* create hashmaps from scip transformed vars to subscip original vars, and vice versa
1022 * capture variables in SCIP and sub-SCIP
1023 * catch global bound change events */
1024 SCIP_CALL( SCIPhashmapCreate(&heurdata->varsubsciptoscip, SCIPblkmem(scip), SCIPgetNOrigVars(scip)) );
1025 SCIP_CALL( SCIPhashmapCreate(&heurdata->varsciptosubscip, SCIPblkmem(scip), SCIPgetNOrigVars(scip)) );
1026
1027 /* we need to get all subscip variables, also those which are copies of fixed variables from the main scip,
1028 * therefore we iterate over the hashmap */
1029 for( i = 0; i < SCIPhashmapGetNEntries(varsmap); ++i )
1030 {
1031 SCIP_HASHMAPENTRY* entry;
1032 entry = SCIPhashmapGetEntry(varsmap, i);
1033 if( entry != NULL )
1034 {
1035 var = (SCIP_VAR*) SCIPhashmapEntryGetOrigin(entry);
1036 subvar = (SCIP_VAR*) SCIPhashmapEntryGetImage(entry);
1037
1038 assert( SCIPvarGetProbindex(subvar) >= 0 );
1039 assert( SCIPvarGetProbindex(subvar) <= heurdata->nsubvars );
1040
1041 if( SCIPvarIsActive(var) )
1042 {
1043 assert( SCIPvarGetProbindex(var) <= heurdata->nvars );
1044 /* assert that we have no mapping for this var yet */
1045 assert( SCIPhashmapGetImage(heurdata->varsciptosubscip,var) == NULL );
1046 SCIP_CALL( SCIPhashmapInsert(heurdata->varsciptosubscip, var, subvar) );
1047 }
1048
1049 assert( SCIPhashmapGetImage(heurdata->varsubsciptoscip, subvar) == NULL );
1050 SCIP_CALL( SCIPhashmapInsert(heurdata->varsubsciptoscip, subvar, var) );
1051
1052 SCIP_CALL( SCIPcaptureVar(scip, var) );
1053 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, subvar) );
1054
1055 assert( SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetLbGlobal(subvar)) );
1056 assert( SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(var), SCIPvarGetUbGlobal(subvar)) );
1057 }
1058 }
1059
1060 /* we map all slack variables of indicator constraints to their indicator variables */
1061 conshdlrindicator = SCIPfindConshdlr(scip, "indicator");
1062 nconsindicator = SCIPconshdlrGetNConss(conshdlrindicator);
1063
1064 SCIP_CALL( SCIPhashmapCreate(&heurdata->slacktoindivarsmap, SCIPblkmem(scip), nconsindicator) );
1065 SCIP_CALL( SCIPhashmapCreate(&heurdata->indicators, SCIPblkmem(scip), nconsindicator) );
1066 SCIP_CALL( SCIPhashmapCreate(&heurdata->indicopymap, SCIPblkmem(scip), nconsindicator) );
1067 SCIP_CALL( SCIPhashmapCreate(&heurdata->indicopymapback, SCIPblkmem(scip), nconsindicator) );
1068 SCIP_CALL( SCIPhashmapCreate(&heurdata->slackvarlbMap, SCIPblkmem(scip), SCIPgetNOrigVars(scip)) );
1069 SCIP_CALL( SCIPhashmapCreate(&heurdata->slackvarubMap, SCIPblkmem(scip), SCIPgetNOrigVars(scip)) );
1070
1071 for( i = 0; i < nconsindicator; i++ )
1072 {
1073 SCIP_CONS** indicatorconss = SCIPconshdlrGetConss(conshdlrindicator);
1074 SCIP_CONS* currcons;
1075
1076 currcons = indicatorconss[i];
1077 assert(currcons != NULL);
1078
1079 SCIP_CALL( SCIPhashmapInsert(heurdata->slacktoindivarsmap, SCIPgetSlackVarIndicator(currcons),
1080 SCIPgetBinaryVarIndicator(currcons)) );
1081 SCIP_CALL( SCIPhashmapInsert(heurdata->indicators, SCIPgetBinaryVarIndicator(currcons), currcons) );
1082 SCIP_CALL( SCIPcaptureCons(scip, currcons) );
1084 }
1085
1086 /* we introduce slackvariables s+ and s- for each constraint to ensure that the problem is feasible
1087 * we want to minimize over the sum of these variables, so set the objective to 1 */
1088 SCIP_CALL( SCIPhashmapCreate(&heurdata->relaxcons, SCIPblkmem(scip), nvars) );
1089 SCIP_CALL( SCIPhashmapCreate(&heurdata->relaxconsindi, SCIPblkmem(scip), nvars) );
1090 SCIP_CALL( SCIPhashmapCreate(&heurdata->slack2var, SCIPblkmem(scip), nvars) );
1091
1092 vars = SCIPgetOrigVars(scip);
1093 nvars = SCIPgetNOrigVars(scip);
1094
1095 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(heurdata->integervars), nvars) );
1096 BMSclearMemoryArray(heurdata->integervars, nvars);
1097 heurdata->integervarssize = nvars;
1098 j = 0;
1099
1100 /* here we relax the variables (or indicator constraints, since indicator variables cannot be relaxed) */
1101 for( i = 0; i < nvars; ++i )
1102 {
1103 var = SCIPvarGetTransVar(vars[i]);
1104 assert( var != NULL );
1105
1106 if( ! SCIPvarIsActive(var) )
1107 continue;
1108
1109 if( ! SCIPvarIsIntegral(var) )
1110 continue;
1111
1112 heurdata->integervars[j++] = vars[i];
1113
1114 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1115 if( var == NULL )
1116 continue;
1117
1118 /* in this case our variable is an indicator variable */
1119 if( SCIPhashmapGetImage(heurdata->indicators, SCIPhashmapGetImage(heurdata->varsubsciptoscip, var)) != NULL )
1120 {
1121 /* we have to find all the indicator constraints of this variable */
1122 for( k = 0; k < nconsindicator; k++ )
1123 {
1124 SCIP_CONS** indicatorconss = SCIPconshdlrGetConss(conshdlrindicator);
1125 SCIP_CONS* currcons;
1126 SCIP_VAR* negatedvar;
1127 SCIP_VAR* indicatorbinvar;
1128
1129 currcons = indicatorconss[k];
1130 assert(currcons != NULL);
1131
1132 indicatorbinvar = SCIPgetBinaryVarIndicator(currcons);
1133 assert(indicatorbinvar != NULL);
1134
1135 SCIP_CALL( SCIPgetNegatedVar(scip, (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, var), &negatedvar) );
1136
1137 if( indicatorbinvar == SCIPhashmapGetImage(heurdata->varsubsciptoscip, var) || indicatorbinvar == negatedvar )
1138 {
1139 /* case that we have a negated variable */
1140 if( SCIPvarIsNegated(indicatorbinvar) )
1141 {
1142 assert(indicatorbinvar == negatedvar);
1143 varobjective = SCIPvarGetObj(negatedvar);
1144 }
1145 else
1146 {
1147 assert(indicatorbinvar != negatedvar);
1148 varobjective = SCIPvarGetObj(indicatorbinvar);
1149 }
1150
1151 varobjective = heurdata->lambdaobj * REALABS(varobjective);
1152
1153 indicons = currcons;
1154 assert( indicons != NULL );
1155
1156 indicons = (SCIP_CONS*)SCIPhashmapGetImage(conssmap, indicons);
1157
1158 assert( indicons != NULL );
1159 linindicons = SCIPgetLinearConsIndicator(indicons);
1160
1161 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_pos3", SCIPconsGetName(linindicons));
1162 SCIP_CALL( SCIPcreateVar(heurdata->subscip, &slackvarpos, varname, 0.0, SCIPinfinity(heurdata->subscip),
1163 heurdata->lambdaslack *100 + varobjective, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1164 SCIP_CALL( SCIPaddVar(heurdata->subscip, slackvarpos) );
1165
1166 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_neg3", SCIPconsGetName(linindicons));
1167 SCIP_CALL( SCIPcreateVar(heurdata->subscip, &slackvarneg, varname, 0.0, SCIPinfinity(heurdata->subscip),
1168 heurdata->lambdaslack * 100 + varobjective, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1169 SCIP_CALL( SCIPaddVar(heurdata->subscip, slackvarneg) );
1170
1171 /* make a copy of the indicator to relax it if this parameter is set true */
1172 if( heurdata->relaxindicators )
1173 {
1174 SCIP_CONS* imagecons;
1175
1176 indicatorbinvar = SCIPgetBinaryVarIndicator(indicons);
1177
1178 SCIP_CALL( SCIPgetNegatedVar(heurdata->subscip, indicatorbinvar, &negatedvar) );
1179
1180 if( SCIPhashmapGetImage(heurdata->indicopymap, indicatorbinvar) == NULL &&
1181 SCIPhashmapGetImage(heurdata->indicopymap, negatedvar) == NULL)
1182 {
1183 SCIP_Bool negated = FALSE;
1184
1185 if (SCIPvarIsNegated(indicatorbinvar))
1186 {
1187 indicatorbinvar = negatedvar;
1188 negated = TRUE;
1189 }
1190
1191 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "indicopy_%s", SCIPvarGetName(indicatorbinvar));
1192 SCIP_CALL( SCIPcreateVar(heurdata->subscip, &indicatorcopy, varname, SCIPvarGetLbGlobal(indicatorbinvar), SCIPvarGetUbGlobal(indicatorbinvar),
1193 SCIPvarGetObj(indicatorbinvar), SCIP_VARTYPE_BINARY, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1194
1195 SCIP_CALL( SCIPaddVar(heurdata->subscip, indicatorcopy) );
1196
1197 SCIP_CALL( SCIPhashmapInsert(heurdata->indicopymap, indicatorbinvar, indicatorcopy) );
1198 SCIP_CALL( SCIPhashmapInsert(heurdata->indicopymapback, indicatorcopy, indicatorbinvar) );
1199 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, indicatorbinvar) );
1200
1201 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_pos1", SCIPvarGetName(indicatorbinvar));
1202 SCIP_CALL( SCIPcreateVar(heurdata->subscip, &indislackvarpos, varname, 0.0, SCIPinfinity(heurdata->subscip),
1203 heurdata->lambdaslack * 100 + varobjective, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1204 SCIP_CALL( SCIPaddVar(heurdata->subscip, indislackvarpos) );
1205
1206 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_neg1", SCIPvarGetName(indicatorbinvar));
1207 SCIP_CALL( SCIPcreateVar(heurdata->subscip, &indislackvarneg, varname, 0.0, SCIPinfinity(heurdata->subscip),
1208 heurdata->lambdaslack * 100 + varobjective, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1209 SCIP_CALL( SCIPaddVar(heurdata->subscip, indislackvarneg) );
1210
1211 /* create linking constraint */
1212 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "linking_%s", SCIPvarGetName(indicatorbinvar));
1213 cons = NULL;
1214 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, 0.0, 0.0,
1216 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indicatorbinvar, 1.0) );
1217 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indicatorcopy, -1.0) );
1218 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indislackvarpos, 1.0) );
1219 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, indislackvarneg, -1.0) );
1220
1221 SCIP_CALL( SCIPhashmapInsert(heurdata->relaxconsindi, indicatorbinvar, cons) );
1222 SCIP_CALL( SCIPhashmapInsert(heurdata->relaxconsindi, indicatorcopy, cons) );
1223
1224 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1225 SCIP_CALL( SCIPcaptureCons(heurdata->subscip, cons) );
1226
1227 assert( SCIPhashmapGetImage(heurdata->indicopymap, indicatorbinvar) != NULL );
1228
1229 if ( negated )
1230 {
1231 SCIP_CALL( SCIPgetNegatedVar(heurdata->subscip, indicatorcopy, &indicatorcopy) );
1232 }
1233
1234 SCIP_CALL( SCIPchgVarType(heurdata->subscip, indicatorbinvar, SCIP_VARTYPE_CONTINUOUS, &feasible) );
1235
1236 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, indislackvarpos, var) );
1237 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, indislackvarneg, var) );
1238 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1239 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1240 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &indislackvarpos) );
1241 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &indislackvarneg) );
1242 }
1243 else
1244 {
1245 if (!SCIPvarIsNegated(indicatorbinvar))
1246 indicatorcopy = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->indicopymap, indicatorbinvar);
1247 else
1248 {
1249 indicatorcopy = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->indicopymap, negatedvar);
1250 SCIP_CALL( SCIPgetNegatedVar(heurdata->subscip, indicatorcopy, &indicatorcopy) );
1251 }
1252 }
1253
1254 cons = NULL;
1255 SCIP_CALL( SCIPcreateConsIndicatorLinCons(heurdata->subscip, &cons, SCIPconsGetName(indicons), indicatorcopy,
1257 SCIPconsIsSeparated(indicons), SCIPconsIsEnforced(indicons), SCIPconsIsChecked(indicons),
1258 SCIPconsIsPropagated(indicons), SCIPconsIsLocal(indicons), SCIPconsIsDynamic(indicons),
1259 SCIPconsIsRemovable(indicons), SCIPconsIsStickingAtNode(indicons)) );
1260 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1261
1262 /* delete old indicator constraints so we can relax the indicator variables */
1263 imagecons = (SCIP_CONS*) SCIPhashmapGetImage(heurdata->origsubscipConsMap, (void*)(currcons));
1264 assert(imagecons != NULL);
1265 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &imagecons) );
1266 SCIP_CALL( SCIPhashmapRemove(heurdata->origsubscipConsMap, currcons) );
1267 SCIP_CALL( SCIPhashmapInsert(heurdata->origsubscipConsMap, currcons, cons) );
1269 SCIP_CALL( SCIPdelCons(heurdata->subscip, indicons) );
1270 }
1271
1272 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, slackvarpos, var) );
1273 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, slackvarneg, var) );
1274 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1275 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1276
1277 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, linindicons, slackvarpos, 1.0) );
1278 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, linindicons, slackvarneg, -1.0) );
1279 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &slackvarpos) );
1280 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &slackvarneg) );
1281 }
1282 }
1283 continue;
1284 }
1285
1286 if( heurdata->relaxindicators )
1287 {
1288 /* relax the old indicator variables*/
1289 for( k = 0; k < nvars; k++ )
1290 {
1291 if( SCIPhashmapGetImage(heurdata->indicators, vars[k]) == NULL )
1292 continue;
1293
1294 tmpvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, vars[k]);
1295 SCIP_CALL( SCIPchgVarType(heurdata->subscip, tmpvar, SCIP_VARTYPE_CONTINUOUS, &feasible) );
1296 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, tmpvar, -SCIPinfinity(heurdata->subscip)) );
1297 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, tmpvar, SCIPinfinity(heurdata->subscip)) );
1298 }
1299
1300 /* we map all slack variables of indicator constraints to their indicator variables */
1301 conshdlrindicator = SCIPfindConshdlr(scip, "indicator");
1302 nconsindicator = SCIPconshdlrGetNConss(conshdlrindicator);
1303
1304 /* delete old hashmaps and fill with the new indicators*/
1305 SCIP_CALL( releaseHashmapEntries(scip, heurdata->slacktoindivarsmap, TRUE) );
1306 SCIP_CALL( releaseHashmapEntries(scip, heurdata->indicators, FALSE) );
1307 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->slacktoindivarsmap) );
1308 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->indicators) );
1309
1310 /* fill hashmaps with new values */
1311 for( k = 0; k < nconsindicator; k++ )
1312 {
1313 SCIP_CONS** indicatorconss = SCIPconshdlrGetConss(conshdlrindicator);
1314 SCIP_CONS* currcons;
1315
1316 currcons = indicatorconss[k];
1317 assert(currcons != NULL);
1318
1320 SCIP_CALL( SCIPcaptureCons(scip, currcons) );
1321
1322 SCIP_CALL( SCIPhashmapInsert(heurdata->slacktoindivarsmap, SCIPgetSlackVarIndicator(currcons),
1323 SCIPgetBinaryVarIndicator(currcons)) );
1324 SCIP_CALL( SCIPhashmapInsert(heurdata->indicators, SCIPgetBinaryVarIndicator(currcons), currcons) );
1325 }
1326 }
1327
1328 /* in this case, we have a normal variable */
1329 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "relax_%s", SCIPvarGetName(var));
1330 cons = NULL;
1331 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, 0.0, 0.0,
1333
1334 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_pos0", SCIPvarGetName(var));
1335 SCIP_CALL( SCIPcreateVar( heurdata->subscip, &slackvarpos, varname, 0.0, SCIPinfinity(heurdata->subscip),
1336 heurdata->lambdaslack * 100, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL,NULL) );
1337 SCIP_CALL( SCIPaddVar(heurdata->subscip, slackvarpos) );
1338
1339 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_neg0", SCIPvarGetName(var));
1340 SCIP_CALL( SCIPcreateVar(heurdata->subscip, &slackvarneg, varname, 0.0, SCIPinfinity(heurdata->subscip),
1341 heurdata->lambdaslack * 100, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL,NULL) );
1342 SCIP_CALL( SCIPaddVar(heurdata->subscip, slackvarneg) );
1343
1344 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, var, 1.0) );
1345 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarpos, 1.0) );
1346 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarneg, -1.0) );
1347
1348 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1349
1350 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, slackvarpos, var) );
1351 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, slackvarneg, var) );
1352 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1353 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1354 SCIP_CALL( SCIPhashmapInsert(heurdata->relaxcons, var, cons) );
1355 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &slackvarpos) );
1356 SCIP_CALL( SCIPreleaseVar(heurdata->subscip, &slackvarneg) );
1357
1358 /* if the var is no indicator, relax it to a continuous variable */
1359 if( SCIPhashmapGetImage(heurdata->indicators, SCIPhashmapGetImage(heurdata->varsubsciptoscip, var)) == NULL )
1360 {
1361 SCIP_CALL( SCIPchgVarType(heurdata->subscip, var, SCIP_VARTYPE_CONTINUOUS, &feasible) );
1362 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, var, -SCIPinfinity(heurdata->subscip)) );
1363 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, var, SCIPinfinity(heurdata->subscip)) );
1364 }
1365 }
1366
1367 /* set up relaxation constraints for continuous variables */
1368 if( heurdata->relaxcontvars )
1369 {
1370 for( i = 0; i < nvars; ++i )
1371 {
1372 var = SCIPvarGetTransVar(vars[i]);
1373 assert( var != NULL );
1374
1375 if( ! SCIPvarIsActive(var) )
1376 continue;
1377
1378 if( SCIPvarIsIntegral(var) )
1379 continue;
1380
1382 continue;
1383
1385 continue;
1386
1387 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1388 if( var == NULL )
1389 continue;
1390
1391 /* in this case, we have a normal variable */
1392 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "relax_ub_%s", SCIPvarGetName(var));
1393 cons = NULL;
1394 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, -SCIPinfinity(heurdata->subscip), SCIPvarGetUbGlobal(var),
1396
1397 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_pos2", SCIPvarGetName(var));
1398 SCIP_CALL( SCIPcreateVar( heurdata->subscip, &slackvarpos, varname, 0.0, SCIPinfinity(heurdata->subscip),
1399 heurdata->lambdaslack, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL,NULL) );
1400 SCIP_CALL( SCIPaddVar(heurdata->subscip, slackvarpos) );
1401
1402 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, var, 1.0) );
1403 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarpos, -1.0) );
1404
1405 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1406 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &cons) );
1407 SCIP_CALL( SCIPhashmapInsert(heurdata->slackvarubMap, var, slackvarpos) );
1408 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, slackvarpos, var) );
1409 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1410
1411 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "relax_lb_%s", SCIPvarGetName(var));
1412 cons = NULL;
1413 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, SCIPvarGetLbGlobal(var), SCIPinfinity(heurdata->subscip),
1415
1416 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "relax_%s_neg2", SCIPvarGetName(var));
1417 SCIP_CALL( SCIPcreateVar( heurdata->subscip, &slackvarneg, varname, 0.0, SCIPinfinity(heurdata->subscip),
1418 heurdata->lambdaslack, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL,NULL) );
1419 SCIP_CALL( SCIPaddVar(heurdata->subscip, slackvarneg) );
1420
1421 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, var, 1.0) );
1422 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, slackvarneg, 1.0) );
1423
1424 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1425 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &cons) );
1426 SCIP_CALL( SCIPhashmapInsert(heurdata->slackvarlbMap, var, slackvarneg) );
1427 SCIP_CALL( SCIPhashmapInsert(heurdata->slack2var, slackvarneg, var) );
1428 SCIP_CALL( SCIPcaptureVar(heurdata->subscip, var) );
1429
1430 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, var, -SCIPinfinity(heurdata->subscip)) );
1431 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, var, SCIPinfinity(heurdata->subscip)) );
1432 }
1433 }
1434
1435 /* if we have a solution add constraint that the next solution must not be worse than the current one */
1436 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "objbound");
1437 SCIP_CALL( SCIPcreateConsLinear( heurdata->subscip, &cons, consname, 0, NULL, NULL, -SCIPinfinity(scip),
1439 heurdata->objbound = cons;
1440
1441 for( i = 0; i < nvars; ++i )
1442 {
1443 var = SCIPvarGetTransVar(vars[i]);
1444 assert( var != NULL );
1445
1446 if( !SCIPvarIsActive(var) )
1447 continue;
1448
1449 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1450 if( subvar == NULL )
1451 continue;
1452
1453 SCIP_CALL( SCIPaddCoefLinear(heurdata->subscip, cons, subvar, SCIPvarGetObj(var)) );
1454
1455 SCIP_CALL( SCIPchgVarObj(heurdata->subscip, subvar, heurdata->lambdaobj * SCIPvarGetObj(subvar) ) );
1456 }
1457
1458 SCIP_CALL( SCIPaddCons(heurdata->subscip, cons) );
1459 SCIP_CALL( SCIPreleaseCons(heurdata->subscip, &cons) );
1460
1461 /* do not need varsmap and conssmap anymore */
1462 SCIPhashmapFree(&conssmap);
1463 SCIPhashmapFree(&varsmap);
1464
1465 /* enable SCIP output if needed */
1466 if( heurdata->heurverblevel > 3 )
1467 {
1468 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "display/verblevel", 4) );
1469 }
1470 else
1471 {
1472 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "display/verblevel", 0) );
1473 }
1474
1475 heurdata->nintegervars = j;
1476
1477 return SCIP_OKAY;
1478}
1479
1480
1481/** free sub-SCIP data structure */
1482static
1484 SCIP* scip, /**< SCIP data structure */
1485 SCIP_HEURDATA* heurdata /**< heuristic data structure */
1486 )
1487{
1488 assert(scip != NULL);
1489 assert(heurdata != NULL);
1490 assert(heurdata->subscip != NULL);
1491
1492 heurdata->nsubvars = 0;
1493 heurdata->nvars = 0;
1494
1495 /* free sub-SCIP */
1496 SCIP_CALL( SCIPfree(&heurdata->subscip) );
1497
1498 return SCIP_OKAY;
1499}
1500
1501
1502/** create a solution from the values of current nonlinear program */
1503static
1505 SCIP* scip, /**< SCIP data structure */
1506 SCIP_HEUR* heur, /**< heuristic data structure */
1507 SCIP_SOL** sol /**< buffer to store solution value; if pointing to NULL a new solution is
1508 * created, otherwise values in the given one are overwritten */
1509 )
1510{
1511 SCIP_HEURDATA* heurdata;
1512 SCIP_VAR** subvars;
1513 SCIP_VAR* subvar;
1514 int i;
1515 int nsubvars;
1516
1517 assert(scip != NULL);
1518 assert(heur != NULL);
1519 assert(sol != NULL);
1520
1521 heurdata = SCIPheurGetData(heur);
1522 assert(heurdata != NULL);
1523
1524 if( *sol == NULL )
1525 {
1526 SCIP_CALL( SCIPcreateSol(scip, sol, heur) );
1527 }
1528
1529 /* sub-SCIP may have more variables than the number of active (transformed) variables in the main SCIP
1530 * since constraint copying may have required the copy of variables that are fixed in the main SCIP */
1531 assert(heurdata->nsubvars <= SCIPgetNOrigVars(heurdata->subscip));
1532
1533 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, NULL, NULL, NULL, NULL) );
1534
1535 /* set solution values */
1536 for( i = 0; i < nsubvars; ++i )
1537 {
1538 subvar = subvars[i];
1539 assert(subvar != NULL);
1540
1541 subvar = SCIPvarGetTransVar(subvar);
1542
1543 if( !SCIPvarIsActive(subvar) )
1544 continue;
1545
1546 assert(SCIPvarGetNLPSol(subvar) != SCIP_INVALID);/*lint !e777*/
1547 SCIP_CALL( SCIPsetSolVal(scip, *sol, subvar, SCIPvarGetNLPSol(subvar)) );
1548 }
1549
1550 return SCIP_OKAY;
1551}
1552
1553#define BIG_VALUE 1E+10
1554
1555/** method to fix the (relaxed) discrete variables */
1556static
1558 SCIP* scip, /**< SCIP data structure */
1559 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
1560 SCIP_SOL* refpoint, /**< point to take fixation of discrete variables from;
1561 * if NULL, then LP solution is used */
1562 SCIP_SOL** transsol /**< pointer to new created solution with fixed values as solution value */
1563 )
1564{
1565 SCIP_Real fixval;
1566 SCIP_VAR* var;
1567 SCIP_VAR* subvar;
1568 SCIP_CONS* rcons;
1569 int i;
1570
1571 SCIP_CALL( SCIPcreateOrigSol(scip, transsol, NULL) );
1572
1573 /* fix discrete variables */
1574 for( i = 0; i < heurdata->nintegervars; i++ )
1575 {
1576 var = heurdata->integervars[i];
1577 assert(var != NULL);
1578
1579 var = SCIPvarGetTransVar(var);
1580 assert(var != NULL);
1581 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1582
1583 if( subvar == NULL )
1584 continue;
1585
1586 if ( SCIPhashmapGetImage(heurdata->indicopymap, subvar) != NULL )
1587 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->indicopymap, subvar);
1588
1589 /* if we do not really have a startpoint, we set to 0.0 here and project on bounds below */
1590 if( refpoint == NULL && SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
1591 fixval = 0.0;
1592 else
1593 {
1594 /* get value of the variables (NULL as refpoint gives the current LP solution, otherwise the start point) */
1595 fixval = SCIPgetSolVal(scip, refpoint, heurdata->integervars[i]);
1596
1597 /* take care that we do not fix variables to very large values (project on bounds below) */
1598 if( REALABS(fixval) > BIG_VALUE )
1599 fixval = 0.0;
1600 else
1601 {
1602 /* round fractional variables to the nearest integer, use exact integral value, if the variable is only
1603 * integral within numerical tolerances */
1604 fixval = SCIPfloor(scip, fixval + 0.5);
1605 }
1606 }
1607
1608 /* adjust value to the global bounds of the corresponding SCIP variable */
1609 fixval = MAX(fixval, SCIPvarGetLbGlobal(heurdata->integervars[i])); /*lint !e666*/
1610 fixval = MIN(fixval, SCIPvarGetUbGlobal(heurdata->integervars[i])); /*lint !e666*/
1611
1612 SCIP_CALL( SCIPsetSolVal(scip, *transsol, heurdata->integervars[i], fixval) );
1613
1614 /* adjust the relaxation constraints to the new fixval */
1615 rcons = (SCIP_CONS*) SCIPhashmapGetImage(heurdata->relaxcons, subvar);
1616
1617 fixval = MAX(fixval, SCIPvarGetLbGlobal(subvar));/*lint !e666*/
1618 fixval = MIN(fixval, SCIPvarGetUbGlobal(subvar));/*lint !e666*/
1619 if( rcons == NULL )
1620 {
1621 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, subvar, fixval) );
1622 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, subvar, fixval) );
1623 continue;
1624 }
1625
1626 SCIP_CALL( SCIPchgLhsLinear(heurdata->subscip, rcons, fixval) );
1627 SCIP_CALL( SCIPchgRhsLinear(heurdata->subscip, rcons, fixval) );
1628 }
1629
1630 return SCIP_OKAY;
1631}
1632
1633/** method to free memory before leaving the heuristic or jumping up in the recursion */
1634static
1636 SCIP* scip, /**< scip data structure */
1637 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
1638 SCIP_SOL* transsol, /**< sol that has to be freed */
1639 SCIP_Real* absranks, /**< array of absolute rank values */
1640 SCIP_Real* ranks, /**< array of rank values */
1641 SCIP_VAR** sortedvars, /**< array of corresponding variables */
1642 SCIP_Bool beforeswitching, /**< did we call this method before or after switching variables? */
1643 SCIP_Bool clearswitchedvars /**< says if we should clear switchedvars or not */
1644 )
1645{
1646 SCIP_VAR** subvars;
1647 SCIP_VAR* subvar;
1648 SCIP_VAR* var;
1649 SCIP_Real* val;
1650 int nsubvars;
1651 int nsubbinvars;
1652 int nsubintvars;
1653 int i;
1654
1655 if( clearswitchedvars )
1656 {
1657 /* free memory of the solution values in the hashmaps */
1658 for( i = 0; i < heurdata->nintegervars; i++ )
1659 {
1660 var = heurdata->integervars[i];
1661
1662 if( SCIPhashmapGetImage(heurdata->slacktoindivarsmap, var) != NULL )
1663 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->slacktoindivarsmap, var);
1664
1665 val = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars, var);
1666 if( val != NULL )
1667 {
1668 SCIPfreeBlockMemoryArray(heurdata->subscip, &val, 1);
1669 }
1670
1671 val = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars2, var);
1672 if( val != NULL )
1673 {
1674 SCIPfreeBlockMemoryArray(heurdata->subscip, &val, 1);
1675 }
1676 }
1677
1678 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->switchedvars) );
1679 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->switchedvars2) );
1680 }
1681
1682 SCIPfreeBufferArrayNull( scip, &ranks );
1683 SCIPfreeBufferArrayNull( scip, &absranks );
1684 SCIPfreeBufferArrayNull( scip, &sortedvars );
1685
1686 if( transsol != NULL )
1687 {
1688 SCIP_CALL( SCIPfreeSol(scip, &transsol) );
1689 }
1690
1691 if( beforeswitching )
1692 {
1693 SCIP_CALL( SCIPfreeTransform(heurdata->subscip) );
1694 }
1695
1696 /* undo fixing of discrete variables in sub-SCIP */
1697 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, &nsubbinvars, &nsubintvars, NULL, NULL) );
1698
1699 /* set bounds of discrete variables to original values */
1700 for( i = nsubbinvars + nsubintvars - 1; i >= 0; --i )
1701 {
1702 subvar = subvars[i];
1703 assert(SCIPvarGetProbindex(subvar) == i);
1704
1705 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, subvar);
1706
1707 if (SCIPhashmapGetImage(heurdata->indicopymapback, subvar) != NULL)
1708 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, SCIPhashmapGetImage(heurdata->indicopymapback, subvar));
1709
1710 assert(var != NULL);
1711
1712 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, subvar, SCIPvarGetLbGlobal(var)) );
1713 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, subvar, SCIPvarGetUbGlobal(var)) );
1714 }
1715
1716 return SCIP_OKAY;
1717}
1718
1719/** computes the ranks, saves them into an array and sorts the variables according to absolute ranks */
1720static
1722 SCIP* scip, /**< scip data structure */
1723 SCIP_HEURDATA* heurdata, /**< heuristic data structure */
1724 SCIP_Real* absranks, /**< array of absolute rank values */
1725 SCIP_Real* ranks, /**< array of rank values */
1726 SCIP_VAR** sortedvars /**< array of corresponding variables */
1727 )
1728{
1729 SCIP_CONSHDLR* conshdlrindicator;
1730 SCIP_CONS* relaxcons;
1731 SCIP_CONS* indicons;
1732 SCIP_CONS* subcons;
1733 SCIP_CONS* transcons;
1734 SCIP_VAR* var;
1735 SCIP_Real* dualvalue;
1736 int nconsindicator;
1737 int j;
1738 int k;
1739
1740 conshdlrindicator = SCIPfindConshdlr(scip, "indicator");
1741 nconsindicator = SCIPconshdlrGetNConss(conshdlrindicator);
1742
1743 /* Now we compute the rank of each variable */
1744 for( j = 0; j < heurdata->nintegervars; j++ )
1745 {
1746 sortedvars[j] = heurdata->integervars[j];
1747 ranks[j] = 0;
1748 absranks[j] = 0;
1749
1750 if( sortedvars[j] == NULL )
1751 break;
1752
1753 var = SCIPvarGetTransVar(sortedvars[j]);
1754 assert(var != NULL);
1755
1756 /* globally fixed variables get rank 0 */
1758 {
1759 ranks[j] = 0;
1760 continue;
1761 }
1762 else
1763 {
1764 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
1765 assert(var != NULL);
1766 relaxcons = (SCIP_CONS*)SCIPhashmapGetImage(heurdata->relaxcons, (void*)(var));
1767
1768 /* get ranks */
1769 if( relaxcons != NULL )
1770 {
1771 SCIP_CALL( SCIPgetTransformedCons(heurdata->subscip, relaxcons, &transcons) );
1772 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)transcons);
1773
1774 if( dualvalue == NULL )
1775 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)(relaxcons));
1776
1777 if( dualvalue == NULL )
1778 continue;
1779
1780 assert(dualvalue != NULL);
1781 ranks[j] = (*dualvalue);
1782 }
1783 else /* if we have an indicator variable */
1784 {
1785 assert(ranks[j] == 0.0);
1786
1787 if (SCIPhashmapGetImage(heurdata->relaxconsindi, (void*)(var)) != NULL)
1788 {
1789 subcons = (SCIP_CONS*)SCIPhashmapGetImage(heurdata->relaxconsindi, (void*)(var));
1790
1791 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)(subcons));
1792
1793 if( dualvalue == NULL )
1794 continue;
1795
1796 assert(dualvalue != NULL);
1797
1798 ranks[j] = (*dualvalue);
1799 }
1800
1801 /* compute the rank of the indicators, we take the highest dualvalue of an indicator constraint */
1802 for( k = 0; k < nconsindicator; k++ )
1803 {
1804 SCIP_CONS** indicatorconss = SCIPconshdlrGetConss(conshdlrindicator);
1805 SCIP_CONS* currcons;
1806 SCIP_VAR* indicatorbinvar;
1807
1808 currcons = indicatorconss[k];
1809 assert(currcons != NULL);
1810
1811 indicatorbinvar = SCIPgetBinaryVarIndicator(currcons);
1812 assert(indicatorbinvar != NULL);
1813
1814 if( indicatorbinvar == (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, var)
1815 || (SCIPvarIsNegated(indicatorbinvar) && indicatorbinvar == SCIPvarGetNegatedVar(var)) )
1816 {
1817 indicons = currcons;
1818 assert(indicons != NULL);
1819
1820 subcons = (SCIP_CONS*)SCIPhashmapGetImage(heurdata->origsubscipConsMap, (void*)(indicons));
1821 assert(subcons != NULL);
1822
1823 subcons = SCIPgetLinearConsIndicator(subcons);
1824 assert(subcons != NULL);
1825
1826 dualvalue = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, (void*)(subcons));
1827
1828 if( dualvalue == NULL )
1829 continue;
1830
1831 assert(dualvalue != NULL);
1832
1833 if( REALABS(ranks[j]) < REALABS(*dualvalue) )
1834 ranks[j] = (*dualvalue);
1835 }
1836 }
1837 }
1838 }
1839
1840 /* take the absolute value of each rank */
1841 absranks[j] = REALABS(ranks[j]);
1842 }
1843
1844 SCIPsortDownRealRealPtr(absranks, ranks, (void**)sortedvars, heurdata->nintegervars);
1845
1846 return SCIP_OKAY;
1847}
1848
1849/** compute maximal slack of a variable */
1850static
1852 SCIP* scip, /**< scip data structure */
1853 SCIP_HEURDATA* heurdata /**< heuristic data structure */
1854 )
1855{
1856 SCIP_VAR* maxvar;
1857 SCIP_VAR* subvar;
1858 SCIP_SOL* bestsol;
1859 SCIP_Real maxslack;
1860 int i;
1861 int nsubvars;
1862 SCIP_Bool maxslackset;
1863
1864 /* compute maximal slack */
1865 nsubvars = SCIPgetNOrigVars(heurdata->subscip);
1866
1867 /* save information about maximal violation */
1868 maxvar = NULL;
1869 maxslack = -SCIPinfinity(heurdata->subscip);
1870 maxslackset = FALSE;
1871
1872 bestsol = SCIPgetBestSol(heurdata->subscip);
1873
1874 /* search for variable with maximal slack */
1875 for( i = 0; i < nsubvars; i++ )
1876 {
1877 subvar = SCIPgetOrigVars(heurdata->subscip)[i];
1878 if( subvar == NULL)
1879 continue;
1880
1881 /* if variable is slack */
1882 if( SCIPhashmapGetImage(heurdata->slack2var, subvar) != NULL )
1883 {
1884 if( heurdata->isnlp )
1885 {
1886 if( maxslack < SCIPvarGetNLPSol(subvar) )
1887 {
1888 maxslack = SCIPvarGetNLPSol(subvar);
1889 maxvar = subvar;
1890 maxslackset = TRUE;
1891 }
1892 }
1893 else
1894 {
1895 assert(bestsol != NULL);
1896 if( maxslack < SCIPgetSolVal(heurdata->subscip, bestsol, subvar) )
1897 {
1898 maxslack = SCIPgetSolVal(heurdata->subscip, bestsol, subvar);
1899 maxvar = subvar;
1900 maxslackset = TRUE;
1901 }
1902 }
1903 }
1904 }
1905
1906 if( ! maxslackset )
1907 {
1908 maxslack = 0;
1909 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "could not find a variable with maximal slack!\n");
1910 }
1911
1912 assert(maxslack >= 0);
1913
1914 if( heurdata->heurverblevel > 0 && maxslackset )
1915 {
1916 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "maximum slack: %f %s\n", maxslack, SCIPvarGetName(maxvar));
1917 }
1918
1919 return maxslack;
1920}
1921
1922/** method called after a solution is found which is feasible in the original problem, stores it and cleans up */
1923static
1925 SCIP* scip, /**< SCIP data structure */
1926 SCIP_HEUR* heur, /**< heuristic data */
1927 SCIP_RESULT* result, /**< pointer to store result of: did not run, solution found,
1928 * no solution found, or fixing is infeasible (cutoff) */
1929 SCIP_SOL* transsol, /**< solution to fix variables */
1930 SCIP_SOL* bestsol /**< solution we create a original scip solution from */
1931 )
1932{
1933 SCIP_HEURDATA* heurdata;
1934 SCIP_SOL* sol = NULL;
1935 SCIP_Bool stored;
1936 SCIP_Real primalobj;
1937
1938 /* get heuristic's data */
1939 heurdata = SCIPheurGetData(heur);
1940 assert(heurdata != NULL);
1941 SCIP_CALL( createSolFromSubScipSol(scip, heur, &sol, bestsol) );
1942
1943 /* if this happens, there was an ipopt error - stop the heuristic for there is no good starting point */
1944 if( heurdata->isnlp && SCIPgetNLPSolstat(heurdata->subscip) > SCIP_NLPSOLSTAT_FEASIBLE )
1945 {
1946 *result = SCIP_DIDNOTFIND;
1947 heurdata->solfound = TRUE;
1948
1949 /* here we can be sure that we are in the nlp case */
1950 assert( heurdata->isnlp );
1951 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) );
1952
1953 SCIP_CALL( freeMemory(scip, heurdata, transsol, NULL, NULL, NULL, TRUE, TRUE) );
1954
1955 /* don't use the heuristic anymore if IPOPT doesn't give proper solution
1956 * (normally then this happens in most ipopt runs that may follow) */
1957 SCIPheurSetFreq(heur, -1);
1958
1959 SCIPdebugMsg(scip, "return10 : turn off heuristic, ipopt error\n");
1960
1961 if( heurdata->heurverblevel > 1 )
1962 {
1963 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "turn off heuristic due to ipopt error");
1964 }
1965
1966 return SCIP_OKAY;
1967 }
1968
1969 primalobj = SCIPinfinity(scip);
1970
1971 /* if there is a solution, try to add solution to storage and free it */
1972 if( sol != NULL )
1973 {
1974 primalobj = SCIPsolGetOrigObj(sol);
1975
1976 if( heurdata->heurverblevel > 0 )
1977 {
1978 SCIP_CALL( SCIPtrySolFree(scip, &sol, TRUE, TRUE, TRUE, FALSE, TRUE, &stored) );
1979 }
1980 else
1981 {
1982 SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, FALSE, TRUE, FALSE, TRUE, &stored) );
1983 }
1984 }
1985 else
1986 stored = FALSE;
1987
1988 if( stored && heurdata->heurverblevel > 1 )
1989 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "accepted solution\n");
1990
1991 if( heurdata->isnlp )
1992 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) );
1993
1994 SCIP_CALL( freeMemory(scip, heurdata, transsol, NULL, NULL, NULL, TRUE, TRUE) );
1995
1996 if( !stored )
1997 {
1998 *result = SCIP_DIDNOTFIND;
1999 heurdata->solfound = TRUE;
2000
2001 if( heurdata->heurverblevel >= 1 )
2002 {
2003 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "return9 : found solution that was not stored, objective %f\n", primalobj);/*lint !e644*/
2004 }
2005
2006 return SCIP_OKAY;
2007 }
2008
2009 heurdata->prevInfeasible = FALSE;
2010 heurdata->solfound = TRUE;
2011 *result = SCIP_FOUNDSOL;
2012
2013 if( heurdata->heurverblevel >= 1 )
2014 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "return 9 : found and stored new solution, objective %lf\n", primalobj);
2015
2016 return SCIP_OKAY;
2017}
2018
2019/** main procedure of the dualval heuristic */
2021 SCIP* scip, /**< original SCIP data structure */
2022 SCIP_HEUR* heur, /**< heuristic data structure */
2023 SCIP_RESULT* result, /**< pointer to store result of: did not run, solution found, no solution
2024 * found, or fixing is infeasible (cutoff) */
2025 SCIP_SOL* refpoint /**< point to take fixation of discrete variables from; if NULL, then LP
2026 * solution is used */
2027 )
2028{
2029 SCIP_HEURDATA* heurdata;
2030 SCIP_NLROW* nlrow;
2031 SCIP_SOL* transsol;
2032 SCIP_SOL* bestsol;
2033 SCIP_CONS** subconss;
2034 SCIP_CONS* rcons;
2035 SCIP_VAR** subvars;
2036 SCIP_VAR** sortedvars;
2037 SCIP_VAR* var;
2038 SCIP_VAR* subvar;
2039 SCIP_VAR* v;
2040 SCIP_RETCODE retcode;
2041 SCIP_Real* absranks;
2042 SCIP_Real* ranks;
2043 SCIP_Real* startpoint;
2044 SCIP_Real* dualval;
2045 SCIP_Real* lastval;
2046 SCIP_Real* seclastval;
2047 SCIP_Real* newval;
2049 SCIP_Real maxslack;
2050 SCIP_Real objvalue;
2051 int i;
2052 int k;
2053 int nsubvars;
2054 int nsubbinvars;
2055 int nsubintvars;
2056 int nsubconss;
2057 int maxequalranks;
2058
2059 assert(scip != NULL);
2060 assert(heur != NULL);
2061
2062 /* dio not run without nlp solver */
2063 if( SCIPgetNNlpis(scip) <= 0 )
2064 return SCIP_OKAY;
2065
2066 /* get heuristic's data */
2067 heurdata = SCIPheurGetData(heur);
2068 assert(heurdata != NULL);
2069
2070 /* don't use the heuristic, if the gap is small so we don't expect to get better solutions than already found */
2071 if( SCIPgetGap(scip) * 100 < heurdata->mingap )
2072 {
2073 SCIPdebugMsg(scip, "return13 : gap is less than mingap\n");
2074 return SCIP_OKAY;
2075 }
2076
2077 /* in the mode 'onlyleaves' don't run the heuristic if we are not in a leaf of the B&B tree */
2078 if( heurdata->onlyleaves && (SCIPgetNLPBranchCands(scip) != 0 || SCIPgetNPseudoBranchCands(scip) != 0) )
2079 return SCIP_OKAY;
2080
2081 /* try to setup subscip if not tried before */
2082 if( heurdata->subscip == NULL && !heurdata->triedsetupsubscip )
2083 {
2084 SCIP_CALL( createSubSCIP(scip, heurdata) );
2085 }
2086
2087 /* quit the recursion if we have found a solution */
2088 if( heurdata->solfound )
2089 {
2090 SCIPdebugMsg(scip, "return1 : already found solution \n");
2091 return SCIP_OKAY;
2092 }
2093
2094 *result = SCIP_DIDNOTRUN;
2095
2096 /* not initialized */
2097 if( heurdata->subscip == NULL )
2098 {
2099 SCIPdebugMsg(scip, "return2 : subscip is NULL\n");
2100 return SCIP_OKAY;
2101 }
2102
2103 assert(heurdata->nsubvars > 0);
2104 assert(heurdata->varsubsciptoscip != NULL);
2105
2106 /* fix discrete variables in sub-SCIP */
2107 SCIP_CALL( fixDiscreteVars(scip, heurdata, refpoint, &transsol) );
2109
2110 if( heurdata->onlycheaper && !SCIPisInfinity(scip, bound) )
2111 {
2112 SCIP_CALL( SCIPchgRhsLinear( heurdata->subscip, heurdata->objbound, bound) );
2113 }
2114
2115 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "presolving/maxrounds", 1) );
2116 SCIP_CALL( SCIPsetIntParam(heurdata->subscip, "propagating/maxroundsroot", 0) );
2117
2118 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 1LL) );
2119 SCIP_CALL( SCIPpresolve(heurdata->subscip) );
2120
2121 if( SCIPgetStatus(heurdata->subscip) == SCIP_STATUS_INFEASIBLE )
2122 {
2123 SCIPdebugMsg(scip, "return 4 : subscip is infeasible\n");
2124
2125 *result = SCIP_DIDNOTFIND;
2126 heurdata->prevInfeasible = TRUE;
2127 SCIP_CALL( freeMemory(scip, heurdata, transsol, NULL, NULL, NULL, TRUE, TRUE) );
2128
2129 return SCIP_OKAY;
2130 }
2131
2132 /* If no NLP was constructed, then there were no nonlinearities after presolve.
2133 * So we increase the nodelimit to 1 and hope that SCIP will find some solution to this probably linear subproblem.
2134 */
2135 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 0LL) );
2136 retcode = SCIPsolve(heurdata->subscip);
2137 heurdata->isnlp = TRUE;
2138
2139 bestsol = NULL;
2140
2141 /* we have no dualvalues, so give up */
2142 if( SCIPgetStatus(heurdata->subscip) == SCIP_STATUS_OPTIMAL)
2143 {
2144 *result = SCIP_DIDNOTFIND;
2145 SCIP_CALL( freeMemory(scip, heurdata, transsol, NULL, NULL, NULL, TRUE, TRUE) );
2146
2147 return SCIP_OKAY;
2148 }
2149
2150 if( ! SCIPisNLPConstructed(heurdata->subscip) && retcode == SCIP_OKAY )
2151 {
2152 SCIP_CALL( SCIPsetLongintParam(heurdata->subscip, "limits/nodes", 1LL) );
2153 SCIP_CALL( SCIPsolve(heurdata->subscip) );
2154 heurdata->isnlp = FALSE;
2155 bestsol = SCIPgetBestSol(heurdata->subscip);
2156 }
2157
2158 if( heurdata->isnlp )
2159 {
2160 /* add non-combinatorial linear constraints from subscip into subNLP */
2161 SCIP_CALL( addLinearConstraintsToNlp(heurdata->subscip, FALSE, TRUE, heurdata) );
2162
2163 SCIP_CALL( SCIPallocBufferArray(scip, &startpoint, SCIPgetNNLPVars(heurdata->subscip)) );
2164
2165 /* set starting values (=refpoint, if not NULL; otherwise LP solution (or pseudo solution)) */
2166 for( i = 0; i < SCIPgetNNLPVars(heurdata->subscip); ++i )
2167 {
2168 SCIP_Real scalar = 1.0;
2169 SCIP_Real constant = 0.0;
2170
2171 subvar = SCIPgetNLPVars(heurdata->subscip)[i];
2172
2173 /* gets corresponding original variable */
2174 SCIP_CALL( SCIPvarGetOrigvarSum(&subvar, &scalar, &constant) );
2175 if( subvar == NULL )
2176 {
2177 startpoint[i] = constant;
2178 continue;
2179 }
2180
2181 var = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsubsciptoscip, subvar);
2182 if( var == NULL || REALABS( SCIPgetSolVal(scip, refpoint, var) ) > 1.0e+12 )
2183 {
2184 SCIP_Real tmpmax;
2185 tmpmax = MAX( 0.0, SCIPvarGetLbGlobal(subvar) );/*lint !e666*/
2186 startpoint[i] = MIN( tmpmax, SCIPvarGetUbGlobal(subvar) );/*lint !e666*/
2187 }
2188 else
2189 /* scalar*subvar+constant corresponds to nlpvar[i], so nlpvar[i] gets value scalar*varval+constant */
2190 startpoint[i] = scalar * SCIPgetSolVal(scip, refpoint, var) + constant;
2191 }
2192
2193 SCIP_CALL( SCIPsetNLPInitialGuess(heurdata->subscip, startpoint) );
2194
2195 /* don't need startpoint array anymore */
2196 SCIPfreeBufferArray( scip, &startpoint );
2197
2198 SCIP_CALL( SCIPsolveNLP(heurdata->subscip, .verblevel = (unsigned short)heurdata->nlpverblevel) ); /*lint !e666*/
2199 assert(SCIPisNLPConstructed(heurdata->subscip));
2200
2201 /* in this case there was an error in ipopt, we try to give another startpoint */
2202 if( SCIPgetNLPSolstat(heurdata->subscip) > SCIP_NLPSOLSTAT_FEASIBLE )
2203 {
2204 SCIP_CALL( SCIPsetNLPInitialGuess(heurdata->subscip, NULL) );
2205 SCIP_CALL( SCIPsolveNLP(heurdata->subscip, .verblevel = (unsigned short)heurdata->nlpverblevel) ); /*lint !e666*/
2206 assert(SCIPisNLPConstructed(heurdata->subscip));
2207 }
2208
2209 nsubconss = SCIPgetNOrigConss(heurdata->subscip);
2210 subconss = SCIPgetOrigConss(heurdata->subscip);
2211
2212 /* free memory of all entries and clear the hashmap before filling it */
2213 for( i = 0; i < nsubconss; i++ )
2214 {
2215 dualval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, subconss[i]);
2216 SCIPfreeBlockMemoryArray(heurdata->subscip, &dualval, 1);
2217 }
2218 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->dualvalues) );
2219
2220 /* save the dualvalues from our nlp solution */
2221 for( i = 0; i < nsubconss; i++ )
2222 {
2223 SCIP_CONS* transcons;
2224
2225 SCIP_CALL( SCIPgetTransformedCons(heurdata->subscip, subconss[i], &transcons) );
2226
2227 if( transcons == NULL )
2228 continue;
2229
2230 if( SCIPconsGetHdlr(transcons) != SCIPfindConshdlr(heurdata->subscip, "linear") )
2231 continue;
2232
2233 nlrow = (SCIP_NLROW*)SCIPhashmapGetImage(heurdata->conss2nlrow, transcons);
2234
2235 if (nlrow != NULL)
2236 {
2237 SCIP_CALL( SCIPallocBlockMemoryArray(heurdata->subscip, &dualval, 1) ); /*lint !e506*/
2238 *dualval = SCIPnlrowGetDualsol(nlrow);
2239 }
2240 else
2241 {
2242 SCIP_CALL( SCIPallocBlockMemoryArray(heurdata->subscip, &dualval, 1) ); /*lint !e506*/
2243 *dualval = 0;
2244 }
2245
2246 SCIP_CALL( SCIPhashmapInsert(heurdata->dualvalues, subconss[i], dualval) );
2247 }
2248
2249 bestsol = NULL;
2250 SCIP_CALL( createSolFromNLP(heurdata->subscip, heur, &bestsol) );
2251 }
2252
2253 /* if we are infeasible, we can't do anything*/
2254 if( SCIPgetStatus(heurdata->subscip) == SCIP_STATUS_INFEASIBLE )
2255 {
2256 SCIPdebugMsg(scip, "return4 : the subscip is infeasible\n");
2257
2258 SCIP_CALL( freeMemory(scip, heurdata, transsol, NULL, NULL, NULL, TRUE, TRUE) );
2259
2260 return SCIP_OKAY;
2261 }
2262
2263 maxslack = maximalslack(scip, heurdata);
2264 SCIPdebugMsg(scip, "origObj: %f\n", SCIPgetSolOrigObj(heurdata->subscip, bestsol));
2265 SCIP_CALL( SCIPgetOrigVarsData(heurdata->subscip, &subvars, &nsubvars, &nsubbinvars, &nsubintvars, NULL, NULL) );
2266 objvalue = 0.0;
2267 assert(bestsol != NULL);
2268
2269 /* save information about maximal violation */
2270 for( i = 0; i < nsubvars; i++ )
2271 {
2272 subvar = SCIPgetOrigVars(heurdata->subscip)[i];
2273
2274 if( SCIPhashmapGetImage(heurdata->slack2var, subvar) == NULL )
2275 objvalue += SCIPvarGetObj(subvar) * SCIPgetSolVal(heurdata->subscip, bestsol, subvar);
2276 }
2277
2278 /* we stop the heuristic if it does not come "closer" to a feasible solution*/
2279 if( heurdata->forceimprovements )
2280 {
2281 if( SCIPisGE(scip, SCIPgetSolOrigObj(heurdata->subscip, bestsol) - objvalue, heurdata->prevobjective) && maxslack > 0 )
2282 {
2283 heurdata->nonimprovingRounds++;
2284 SCIPdebugMsg(scip, "nonimpr rounds %d prevobj %f \n", heurdata->nonimprovingRounds, heurdata->prevobjective);
2285
2286 /* leave, if we have not improved some iterations*/
2287 if( heurdata->nonimprovingRounds > heurdata->maxcalls/8 )
2288 {
2289 *result = SCIP_DIDNOTFIND;
2290
2291 if( heurdata->isnlp )
2292 {
2293 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) );
2294 }
2295
2296 SCIP_CALL( freeMemory(scip, heurdata, transsol, NULL, NULL, NULL, TRUE, TRUE) );
2297
2298 heurdata->solfound = TRUE;
2299 heurdata->switchdifferent = TRUE;
2300
2301 SCIPdebugMsg(scip, "return11 : solution did not improve\n");
2302
2303 return SCIP_OKAY;
2304 }
2305 }
2306 }
2307
2308 heurdata->prevobjective = SCIPgetSolOrigObj(heurdata->subscip, bestsol) - objvalue;
2309
2310 /* in this case we found a feasible solution, store it, clean up and stop the heuristic*/
2311 if( SCIPisFeasLE(heurdata->subscip, maxslack, 0.0) )
2312 return storeSolution(scip, heur, result, transsol, bestsol);
2313
2314 SCIP_CALL( SCIPallocBufferArray(scip, &ranks, heurdata->nintegervars) );
2315 SCIP_CALL( SCIPallocBufferArray(scip, &sortedvars, heurdata->nintegervars) );
2316 SCIP_CALL( SCIPallocBufferArray(scip, &absranks, heurdata->nintegervars) );
2317
2318 /* compute ranks and sort them in non-increasing order */
2319 SCIP_CALL( computeRanks(scip, heurdata, absranks, ranks, sortedvars) );
2320
2321 /* print out the highest ranks */
2322 if( heurdata->heurverblevel > 1 )
2323 {
2324 k = heurdata->rankvalue;
2325
2326 if( heurdata->nintegervars < heurdata->rankvalue )
2327 k = heurdata->nintegervars;
2328
2329 for( i = 0; i < k; i++ )
2330 {
2331 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%i. rank: %f name: %s\n", i, ranks[i], SCIPvarGetName(sortedvars[i]));
2332 }
2333 }
2334
2335 /* free solution */
2336 if( heurdata->isnlp )
2337 SCIP_CALL( SCIPfreeSol(heurdata->subscip, &bestsol) );
2338
2339 /* we don't allow more than a third of the variables to have the same rank */
2340 maxequalranks = MIN(heurdata->maxequalranks, heurdata->nintegervars/3);
2341
2342 if( heurdata->maxequalranks >= 0 && SCIPisFeasEQ(heurdata->subscip, REALABS(ranks[0]), REALABS(ranks[maxequalranks])) )
2343 {
2344 *result = SCIP_DIDNOTFIND;
2345
2346 SCIPdebugMsg(scip, "return12 : equal maxranks\n");
2347
2348 SCIP_CALL( freeMemory(scip, heurdata, transsol, absranks, ranks, sortedvars, TRUE, TRUE ) );
2349 return SCIP_OKAY;
2350 }
2351
2352 /* now we can start switching the variable values */
2353 SCIP_CALL( SCIPfreeTransform(heurdata->subscip) );
2354
2355 /* set bounds of fixed discrete variables to original values so we can switch */
2356 for( k = 0; k < heurdata->nintegervars; ++k )
2357 {
2358 var = heurdata->integervars[k];
2359 if( var == NULL )
2360 break;
2361
2362 var = SCIPvarGetTransVar(var);
2363 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->varsciptosubscip, var);
2364
2365 rcons = (SCIP_CONS*) SCIPhashmapGetImage(heurdata->relaxcons, subvar);
2366 if( rcons != NULL )
2367 continue;
2368
2369 assert(var != NULL);
2370 assert(subvar != NULL);
2371
2372 if ( SCIPhashmapGetImage(heurdata->indicopymap, subvar) != NULL )
2373 subvar = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->indicopymap, subvar);
2374
2375 SCIP_CALL( SCIPchgVarLbGlobal(heurdata->subscip, subvar, SCIPvarGetLbGlobal(heurdata->integervars[k])) );
2376 SCIP_CALL( SCIPchgVarUbGlobal(heurdata->subscip, subvar, SCIPvarGetUbGlobal(heurdata->integervars[k])) );
2377 }
2378
2379 /* switch variable with maximum ranking if possible */
2380 for( i = 0; i < heurdata->nintegervars; i++ )
2381 {
2382 v = sortedvars[i];
2383 SCIP_CALL( SCIPallocBlockMemoryArray(heurdata->subscip, &newval, 1) ); /*lint !e506*/
2384
2385 /* compute the new value of the variable */
2386
2387 /* if we have an indicator constraint, we turn it off */
2388 if( SCIPhashmapGetImage(heurdata->slacktoindivarsmap, v) != NULL )
2389 {
2390 /* get the indicator var of this constraint */
2391 v = (SCIP_VAR*)SCIPhashmapGetImage(heurdata->slacktoindivarsmap, v);
2392
2393 /* set the value to 0 */
2394 SCIP_CALL( SCIPsetSolVal(scip, transsol, v, 0.0) );
2395 if( heurdata->heurverblevel > 1 )
2396 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Setting value of %s%s to 0\n", SCIPvarIsNegated(v) ? "(negated) " : " ", SCIPvarGetName(v));
2397
2398 *newval = 0.0;
2399 SCIP_CALL( SCIPhashmapInsert(heurdata->switchedvars, v, newval) );
2400 }
2401 else
2402 {
2403 if( ranks[i] > 0 )
2404 {
2405 if( SCIPvarIsBinary(v) && SCIPisEQ(scip, 1.0, SCIPgetSolVal(scip, transsol, v)) )
2406 continue;
2407
2408 /* ignore fixed vars in input */
2410 continue;
2411
2412 *newval = SCIPgetSolVal(scip, transsol, v) + 1;
2413 }
2414 else
2415 {
2416 if( SCIPvarIsBinary(v) && SCIPisEQ(scip, 0.0, SCIPgetSolVal(scip, transsol, v)) )
2417 continue;
2418
2420 continue;
2421
2422 *newval = SCIPgetSolVal(scip, transsol, v) - 1;
2423 }
2424 }
2425 lastval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars, v);
2426 seclastval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->switchedvars2, v);
2427
2428 /* we don't want to set a variable to a value it already had,or set a binary variable more than once */
2429 if( (lastval != NULL && (SCIPvarIsBinary(v) || SCIPisFeasEQ(scip, *lastval, *newval))) || (seclastval != NULL && SCIPisFeasEQ(scip, *seclastval, *newval)) )
2430 {
2431 SCIPfreeBlockMemoryArray(heurdata->subscip, &newval, 1);
2432 continue;
2433 }
2434 else /* update the switchedvars values, switchedvars2 is the second last and switchedvars the last value */
2435 {
2436 if( seclastval != NULL )
2437 SCIPfreeBlockMemoryArray(heurdata->subscip, &seclastval, 1);
2438
2439 SCIP_CALL( SCIPhashmapRemove(heurdata->switchedvars2, v) );
2440 SCIP_CALL( SCIPhashmapInsert(heurdata->switchedvars2, v, lastval) );
2441 SCIP_CALL( SCIPhashmapRemove(heurdata->switchedvars, v) );
2442 SCIP_CALL( SCIPhashmapInsert(heurdata->switchedvars, v, newval) );
2443
2444 if( heurdata->heurverblevel > 1 )
2445 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Setting value of %s from %f to %f\n", SCIPvarGetName(v), SCIPgetSolVal(scip, transsol, v), *newval);
2446
2447 SCIP_CALL( SCIPsetSolVal(scip, transsol, v, *newval) );
2448 }
2449
2450 /* if we have exceeded our iterations limit give up without any solution */
2451 if( heurdata->usedcalls >= heurdata->maxcalls )
2452 {
2453 SCIPdebugMsg(scip, "return5 : reached iteration limit\n");
2454
2455 SCIP_CALL( freeMemory(scip, heurdata, transsol, absranks, ranks, sortedvars, FALSE, TRUE) );
2456 *result = SCIP_DIDNOTFIND;
2457 return SCIP_OKAY;
2458 }
2459
2460 heurdata->usedcalls++;
2461
2462 if( heurdata->heurverblevel > 1 )
2463 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "----- Total Calls: %d\n", heurdata->usedcalls);
2464
2465 /* recursive call of the heuristic */
2466 SCIP_CALL( SCIPapplyHeurDualval(scip, heur, result, transsol) );
2467
2468 /* just to go up in the recursion */
2469 if( *result == SCIP_DIDNOTFIND || heurdata->solfound || heurdata->prevInfeasible )
2470 {
2471 SCIPdebugMsg(scip, "return6 : go up\n");
2472
2473 /* here we only go up one step and try another switch (switch the same variables again is forbidden
2474 * since they are contained in switchedvars) */
2475 if( heurdata->switchdifferent )
2476 {
2477 heurdata->switchdifferent = FALSE;
2478 heurdata->solfound = FALSE;
2479 *result = SCIP_DIDNOTRUN;
2480 heurdata->nonimprovingRounds -= 2;
2481 }
2482
2483 if( heurdata->prevInfeasible )
2484 {
2485 heurdata->prevInfeasible = FALSE;
2486 heurdata->solfound = FALSE;
2487 *result = SCIP_DIDNOTRUN;
2488 heurdata->nonimprovingRounds++;
2489 }
2490
2491 SCIP_CALL( freeMemory(scip, heurdata, transsol, absranks, ranks, sortedvars, FALSE, FALSE) );
2492 return SCIP_OKAY;
2493 }
2494 }
2495
2496 if( heurdata->subscip == NULL )
2497 {
2498 /* something horrible must have happened that we decided to give up completely on this heuristic */
2499 *result = SCIP_DIDNOTFIND;
2500 SCIPdebugMsg(scip, "return7 : subscip was set NULL\n");
2501
2502 SCIP_CALL( freeMemory(scip, heurdata, transsol, absranks, ranks, sortedvars, FALSE, TRUE) );
2503 return SCIP_OKAY;
2504 }
2505 assert(!SCIPisTransformed(heurdata->subscip));
2506
2507 SCIPdebugMsg(scip, "return8 : cannot switch any variable\n");
2508
2509 SCIP_CALL( freeMemory(scip, heurdata, transsol, absranks, ranks, sortedvars, FALSE, TRUE) );
2510
2511 *result = SCIP_DIDNOTFIND;
2512 return SCIP_OKAY;
2513}
2514
2515
2516/* Callback methods of primal heuristic */
2517
2518/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
2519static
2520SCIP_DECL_HEURFREE(heurFreeDualval)
2521{
2522 SCIP_HEURDATA* heurdata;
2523
2524 assert(scip != NULL);
2525 assert(heur != NULL);
2526
2527 heurdata = SCIPheurGetData(heur);
2528
2529 SCIPfreeBlockMemory(scip, &heurdata);
2530
2531 return SCIP_OKAY;
2532}
2533
2534
2535/** initialization method of primal heuristic (called after problem was transformed) */
2536static
2537SCIP_DECL_HEURINIT(heurInitDualval)
2538{ /*lint --e{715}*/
2539 SCIP_HEURDATA* heurdata;
2540
2541 assert(scip != NULL);
2542 assert(heur != NULL);
2543
2544 /* skip setting up sub-SCIP if heuristic is disabled or we do not want to run the heuristic */
2545 if( SCIPheurGetFreq(heur) < 0 )
2546 return SCIP_OKAY;
2547
2548 SCIP_CALL( SCIPsetIntParam(scip, "presolving/maxrestarts", 0) );
2549
2550 heurdata = SCIPheurGetData(heur);
2551 assert(heurdata != NULL);
2552 assert(heurdata->subscip == NULL);
2553 assert(!heurdata->triedsetupsubscip);
2554
2555 /* create sub-SCIP for later use */
2556 SCIP_CALL( createSubSCIP(scip, heurdata) );
2557
2558 /* creating sub-SCIP may fail if the solver interfaces did not copy into subscip */
2559 if( heurdata->subscip == NULL )
2560 return SCIP_OKAY;
2561
2562 /* if the heuristic is called at the root node, we want to be called directly after the initial root LP solve */
2563 if( SCIPheurGetFreqofs(heur) == 0 )
2565
2566 SCIP_CALL( SCIPhashmapCreate(&heurdata->dualvalues, SCIPblkmem(scip), 512) );
2567
2568 return SCIP_OKAY;
2569}
2570
2571/** deinitialization method of primal heuristic (called before transformed problem is freed) */
2572static
2573SCIP_DECL_HEUREXIT(heurExitDualval)
2574{ /*lint --e{715}*/
2575 SCIP_HEURDATA* heurdata;
2576 SCIP_CONS** subconss;
2577 SCIP_Real* dualval;
2578 int i;
2579 int nsubconss;
2580
2581 assert(scip != NULL);
2582 assert(heur != NULL);
2583
2584 heurdata = SCIPheurGetData(heur);
2585 assert(heurdata != NULL);
2586
2587 SCIPfreeBlockMemoryArrayNull(scip, &heurdata->integervars, heurdata->integervarssize);
2588
2589 if( heurdata->subscip != NULL)
2590 {
2591 nsubconss = SCIPgetNOrigConss(heurdata->subscip);
2592 subconss = SCIPgetOrigConss(heurdata->subscip);
2593
2594 /* free memory of all entries and clear the hashmap before filling it */
2595 for( i = 0; i < nsubconss; i++ )
2596 {
2597 dualval = (SCIP_Real*)SCIPhashmapGetImage(heurdata->dualvalues, subconss[i]);
2598 SCIPfreeBlockMemoryArrayNull(heurdata->subscip, &dualval, 1);
2599 }
2600 SCIP_CALL( SCIPhashmapRemoveAll(heurdata->dualvalues) );
2601 SCIPhashmapFree(&heurdata->dualvalues);
2602
2603 if( heurdata->varsciptosubscip != NULL )
2604 {
2605 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->varsciptosubscip, TRUE) );
2606
2607 SCIPhashmapFree(&heurdata->varsciptosubscip);
2608 }
2609 if( heurdata->origsubscipConsMap != NULL )
2610 {
2611 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->origsubscipConsMap, FALSE) );
2612
2613 SCIPhashmapFree(&heurdata->origsubscipConsMap);
2614 }
2615 if( heurdata->relaxcons != NULL )
2616 {
2617 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->relaxcons, FALSE) );
2618
2619 SCIPhashmapFree(&heurdata->relaxcons);
2620 }
2621 if( heurdata->conss2nlrow != NULL )
2622 {
2623 SCIP_CALL( releaseHashmapNLPRows(heurdata->subscip, heurdata->conss2nlrow) );
2624
2625 SCIPhashmapFree(&heurdata->conss2nlrow);
2626 }
2627 if( heurdata->slack2var != NULL )
2628 {
2629 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->slack2var, TRUE) );
2630
2631 SCIPhashmapFree(&heurdata->slack2var);
2632 }
2633 if( heurdata->indicopymap != NULL )
2634 {
2635 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->indicopymap, TRUE) );
2636
2637 SCIPhashmapFree(&heurdata->indicopymap);
2638 }
2639 if( heurdata->indicopymapback != NULL )
2640 {
2641 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->indicopymapback, TRUE) );
2642
2643 SCIPhashmapFree(&heurdata->indicopymapback);
2644 }
2645 if( heurdata->relaxconsindi != NULL )
2646 {
2647 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->relaxconsindi, FALSE) );
2648
2649 SCIPhashmapFree(&heurdata->relaxconsindi);
2650 }
2651 if( heurdata->slackvarlbMap != NULL )
2652 {
2653 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->slackvarlbMap, TRUE) );
2654
2655 SCIPhashmapFree(&heurdata->slackvarlbMap);
2656 }
2657 if( heurdata->slackvarubMap != NULL )
2658 {
2659 SCIP_CALL( releaseHashmapEntries(heurdata->subscip, heurdata->slackvarubMap, TRUE) );
2660
2661 SCIPhashmapFree(&heurdata->slackvarubMap);
2662 }
2663
2664 if( heurdata->subscip != NULL )
2665 {
2666 SCIP_CALL( freeSubSCIP(scip, heurdata) );
2667 }
2668 }
2669
2670 if( heurdata->varsubsciptoscip != NULL )
2671 {
2672 SCIP_CALL( releaseHashmapEntries(scip, heurdata->varsubsciptoscip, TRUE) );
2673
2674 SCIPhashmapFree(&heurdata->varsubsciptoscip);
2675 }
2676 if( heurdata->slacktoindivarsmap != NULL )
2677 {
2678 SCIP_CALL( releaseHashmapEntries(scip, heurdata->slacktoindivarsmap, TRUE) );
2679
2680 SCIPhashmapFree(&heurdata->slacktoindivarsmap);
2681 }
2682 if( heurdata->indicators != NULL )
2683 {
2684 SCIP_CALL( releaseHashmapEntries(scip, heurdata->indicators, FALSE) );
2685
2686 SCIPhashmapFree(&heurdata->indicators);
2687 }
2688 if( heurdata->switchedvars != NULL )
2689 {
2690 SCIPhashmapFree(&heurdata->switchedvars);
2691 }
2692 if( heurdata->switchedvars2 != NULL )
2693 {
2694 SCIPhashmapFree(&heurdata->switchedvars2);
2695 }
2696
2697 /* reset some flags and counters */
2698 heurdata->triedsetupsubscip = FALSE;
2699 heurdata->usedcalls = 0;
2700 heurdata->solfound = FALSE;
2701 heurdata->prevInfeasible = FALSE;
2702
2703 assert(heurdata->subscip == NULL);
2704 assert(heurdata->varsubsciptoscip == NULL);
2705 assert(heurdata->varsciptosubscip == NULL);
2706
2707 return SCIP_OKAY;
2708}
2709
2710/** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
2711static
2712SCIP_DECL_HEURINITSOL(heurInitsolDualval)
2713{
2714 SCIP_HEURDATA* heurdata;
2715
2716 assert(scip != NULL);
2717 assert(heur != NULL);
2718
2719 /* skip setting up sub-SCIP if heuristic is disabled or we do not want to run the heuristic */
2720 if( SCIPheurGetFreq(heur) < 0 )
2721 return SCIP_OKAY;
2722
2723 heurdata = SCIPheurGetData(heur);
2724 assert(heurdata != NULL);
2725
2726 /* creating sub-SCIP may fail if the solver interfaces did not copy into subscip */
2727 if( heurdata->subscip == NULL )
2728 return SCIP_OKAY;
2729
2730 /* if the heuristic is called at the root node, we want to be called directly after the initial root LP solve */
2731 if( SCIPheurGetFreqofs(heur) == 0 )
2733
2734 return SCIP_OKAY;
2735}
2736
2737
2738/** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
2739static
2740SCIP_DECL_HEUREXITSOL(heurExitsolDualval)
2741{
2742 assert(scip != NULL);
2743 assert(heur != NULL);
2744
2746
2747 return SCIP_OKAY;
2748}
2749
2750
2751/** execution method of primal heuristic */
2752static
2753SCIP_DECL_HEUREXEC(heurExecDualval)
2754{ /*lint --e{715}*/
2755 SCIP_HEURDATA* heurdata;
2756
2757 assert(scip != NULL);
2758 assert(heur != NULL);
2759 assert(result != NULL);
2760
2761 /* get heuristic's data */
2762 heurdata = SCIPheurGetData(heur);
2763 assert(heurdata != NULL);
2764
2765 /* obviously, we did not do anything yet */
2766 *result = SCIP_DIDNOTRUN;
2767
2768 /* init data */
2769 heurdata->usedcalls = 0;
2770 heurdata->prevInfeasible = FALSE;
2771 heurdata->solfound = FALSE;
2772 heurdata->nonimprovingRounds = 0;
2773 heurdata->prevobjective = INT_MAX;
2774
2775 SCIP_CALL( SCIPapplyHeurDualval(scip, heur, result, NULL) );
2776
2777 /* SCIP does not like cutoff as return, so we say didnotfind, since we did not find a solution */
2778 if( *result == SCIP_CUTOFF )
2779 *result = SCIP_DIDNOTFIND;
2780
2781 /* reset timing, if it was changed temporary (at the root node) */
2782 if( heurtiming != HEUR_TIMING )
2784
2785 return SCIP_OKAY;
2786}
2787
2788
2789/* primal heuristic specific interface methods */
2790
2791/** creates the dualval primal heuristic and includes it in SCIP */
2793 SCIP* scip /**< SCIP data structure */
2794 )
2795{
2796 SCIP_HEURDATA* heurdata = NULL;
2797 SCIP_HEUR* heur = NULL;
2798
2799 /* create dualval primal heuristic data */
2800 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
2801 BMSclearMemory(heurdata);
2802
2803 /* include primal heuristic */
2804
2805 /* use SCIPincludeHeurBasic() plus setter functions if you want to set callbacks one-by-one and your code should
2806 * compile independent of new callbacks being added in future SCIP versions */
2809 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecDualval, heurdata) );
2810
2811 assert(heur != NULL);
2812
2813 /* set non fundamental callbacks via setter functions */
2814 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeDualval) );
2815 SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitDualval) );
2816 SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitDualval) );
2817 SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolDualval) );
2818 SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolDualval) );
2819
2820 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/forceimprovements",
2821 "exit if objective doesn't improve",
2822 &heurdata->forceimprovements, TRUE, DEFAULT_FORCEIMPROVEMENTS, NULL, NULL) );
2823
2824 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlycheaper",
2825 "add constraint to ensure that discrete vars are improving",
2826 &heurdata->onlycheaper, TRUE, DEFAULT_ONLYCHEAPER, NULL, NULL) );
2827
2828 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/onlyleaves",
2829 "disable the heuristic if it was not called at a leaf of the B&B tree",
2830 &heurdata->onlyleaves, FALSE, DEFAULT_ONLYLEAVES, NULL, NULL) );
2831
2832 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/relaxindicators",
2833 "relax the indicator variables by introducing continuous copies",
2834 &heurdata->relaxindicators, FALSE, DEFAULT_RELAXINDICATORS, NULL, NULL) );
2835
2836 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/relaxcontvars",
2837 "relax the continous variables",
2838 &heurdata->relaxcontvars, FALSE, DEFAULT_RELAXCONTVARS, NULL, NULL) );
2839
2840 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/heurverblevel",
2841 "verblevel of the heuristic, default is 0 to display nothing",
2842 &heurdata->heurverblevel, FALSE, DEFAULT_HEURVERBLEVEL, 0, 4, NULL, NULL) );
2843
2844 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/nlpverblevel",
2845 "verblevel of the nlp solver, can be 0 or 1",
2846 &heurdata->nlpverblevel, FALSE, DEFAULT_NLPVERBLEVEL, 0, 1, NULL, NULL) );
2847
2848 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/rankvalue",
2849 "number of ranks that should be displayed when the heuristic is called",
2850 &heurdata->rankvalue, FALSE, DEFAULT_RANKVALUE, 0, INT_MAX, NULL, NULL) );
2851
2852 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxcalls",
2853 "maximal number of recursive calls of the heuristic (if dynamicdepth is off)",
2854 &heurdata->maxcalls, FALSE, DEFAULT_MAXCALLS, 0, INT_MAX, NULL, NULL) );
2855
2856 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/dynamicdepth",
2857 "says if and how the recursion depth is computed at runtime",
2858 &heurdata->dynamicdepth, FALSE, DEFAULT_DYNAMICDEPTH, 0, 1, NULL, NULL) );
2859
2860 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxequalranks",
2861 "maximal number of variables that may have maximal rank, quit if there are more, turn off by setting -1",
2862 &heurdata->maxequalranks, FALSE, DEFAULT_MAXEQUALRANKS, -1, INT_MAX, NULL, NULL) );
2863
2864 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/mingap",
2865 "minimal gap for which we still run the heuristic, if gap is less we return without doing anything",
2866 &heurdata->mingap, FALSE, DEFAULT_MINGAP, 0.0, 100.0, NULL, NULL) );
2867
2868 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lambdaslack",
2869 "value added to objective of slack variables, must not be zero",
2870 &heurdata->lambdaslack, FALSE, DEFAULT_LAMBDASLACK, 0.1, SCIPinfinity(scip), NULL, NULL) );
2871
2872 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/lambdaobj",
2873 "scaling factor for the objective function",
2874 &heurdata->lambdaobj, FALSE, DEFAULT_LAMBDAOBJ, 0.0, 1.0, NULL, NULL) );
2875
2876 return SCIP_OKAY;
2877}
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_Longint
Definition: def.h:158
#define SCIP_INVALID
Definition: def.h:193
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#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)
Definition: cons_setppc.c:9545
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9568
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)
Definition: cons_setppc.c:9591
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)
Definition: scip_general.c:596
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:339
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:307
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:498
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
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,...)
Definition: scip_message.c:225
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPapplyHeurDualval(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_SOL *refpoint)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:545
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:603
SCIP_RETCODE SCIPincludeHeurDualval(SCIP *scip)
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:428
int SCIPgetNPseudoBranchCands(SCIP *scip)
Definition: scip_branch.c:758
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_EVENTHDLRDATA * SCIPeventhdlrGetData(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:334
SCIP_RETCODE SCIPsetEventhdlrExit(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTEXIT((*eventexit)))
Definition: scip_event.c:178
SCIP_RETCODE SCIPsetEventhdlrInit(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_DECL_EVENTINIT((*eventinit)))
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 SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:242
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 SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
Definition: scip_heur.c:210
void SCIPheurSetFreq(SCIP_HEUR *heur, int freq)
Definition: heur.c:1548
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition: heur.c:1493
SCIP_RETCODE SCIPsetHeurInitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINITSOL((*heurinitsol)))
Definition: scip_heur.c:226
int SCIPheurGetFreqofs(SCIP_HEUR *heur)
Definition: heur.c:1559
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:194
int SCIPheurGetFreq(SCIP_HEUR *heur)
Definition: heur.c:1538
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_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
SCIP_Real SCIPsolGetOrigObj(SCIP_SOL *sol)
Definition: sol.c:2741
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
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)
Definition: scip_solve.c:2328
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition: scip_solve.c:3344
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2498
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:1794
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:1248
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4943
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17610
SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible)
Definition: scip_var.c:8176
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1527
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:17574
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:5032
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip_var.c:114
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c: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:4513
SCIP_Real SCIPvarGetNLPSol(SCIP_VAR *var)
Definition: var.c:18465
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1214
void SCIPsortDownRealRealPtr(SCIP_Real *realarray1, SCIP_Real *realarray2, void **ptrarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
static SCIP_DECL_EVENTEXEC(eventExecLPsol)
Definition: heur_dualval.c:194
#define DEFAULT_RANKVALUE
Definition: heur_dualval.c:100
#define DEFAULT_ONLYCHEAPER
Definition: heur_dualval.c:92
static SCIP_RETCODE createSolFromSubScipSol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL **sol, SCIP_SOL *subsol)
Definition: heur_dualval.c:765
static SCIP_RETCODE addSetppcConstraints(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_HEURDATA *heurdata)
Definition: heur_dualval.c:547
static SCIP_DECL_HEUREXIT(heurExitDualval)
#define DEFAULT_LAMBDAOBJ
Definition: heur_dualval.c:108
#define DEFAULT_MINGAP
Definition: heur_dualval.c:106
#define DEFAULT_HEURVERBLEVEL
Definition: heur_dualval.c:98
static SCIP_RETCODE addLogicOrConstraints(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_HEURDATA *heurdata)
Definition: heur_dualval.c:480
#define HEUR_TIMING
Definition: heur_dualval.c:83
static SCIP_RETCODE createSolFromNLP(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL **sol)
#define HEUR_FREQOFS
Definition: heur_dualval.c:81
static SCIP_RETCODE computeRanks(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_Real *absranks, SCIP_Real *ranks, SCIP_VAR **sortedvars)
#define HEUR_DESC
Definition: heur_dualval.c:77
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
Definition: heur_dualval.c:94
static SCIP_DECL_HEUREXEC(heurExecDualval)
static SCIP_RETCODE releaseHashmapNLPRows(SCIP *scip, SCIP_HASHMAP *hashmap)
Definition: heur_dualval.c:313
static SCIP_RETCODE addLinearConstraints(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_Bool addcombconss, SCIP_Bool addcontconss, SCIP_HEURDATA *heurdata)
Definition: heur_dualval.c:345
#define DEFAULT_FORCEIMPROVEMENTS
Definition: heur_dualval.c:91
#define HEUR_DISPCHAR
Definition: heur_dualval.c:78
#define HEUR_MAXDEPTH
Definition: heur_dualval.c:82
#define HEUR_PRIORITY
Definition: heur_dualval.c:79
static SCIP_RETCODE storeSolution(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_SOL *transsol, SCIP_SOL *bestsol)
#define DEFAULT_LAMBDASLACK
Definition: heur_dualval.c:107
static SCIP_DECL_EVENTEXIT(eventExitLPsol)
Definition: heur_dualval.c:181
#define HEUR_NAME
Definition: heur_dualval.c:76
static SCIP_DECL_HEURINIT(heurInitDualval)
#define DEFAULT_RELAXCONTVARS
Definition: heur_dualval.c:95
#define DEFAULT_MAXCALLS
Definition: heur_dualval.c:101
static SCIP_Real maximalslack(SCIP *scip, SCIP_HEURDATA *heurdata)
static SCIP_RETCODE SCIPincludeEventHdlrLPsol(SCIP *scip, SCIP_HEURDATA *heurdata)
Definition: heur_dualval.c:244
static SCIP_RETCODE createSubSCIP(SCIP *scip, SCIP_HEURDATA *heurdata)
Definition: heur_dualval.c:856
static SCIP_DECL_HEUREXITSOL(heurExitsolDualval)
#define BIG_VALUE
static SCIP_DECL_HEURFREE(heurFreeDualval)
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)
Definition: heur_dualval.c:639
#define DEFAULT_DYNAMICDEPTH
Definition: heur_dualval.c:102
static SCIP_DECL_HEURINITSOL(heurInitsolDualval)
#define DEFAULT_ONLYLEAVES
Definition: heur_dualval.c:93
static SCIP_RETCODE freeSubSCIP(SCIP *scip, SCIP_HEURDATA *heurdata)
#define DEFAULT_NLPVERBLEVEL
Definition: heur_dualval.c:99
static SCIP_RETCODE releaseHashmapEntries(SCIP *scip, SCIP_HASHMAP *hashmap, SCIP_Bool isvarmap)
Definition: heur_dualval.c:270
#define EVENTHDLR_DESC
Definition: heur_dualval.c:87
#define DEFAULT_MAXEQUALRANKS
Definition: heur_dualval.c:103
#define HEUR_FREQ
Definition: heur_dualval.c:80
static SCIP_RETCODE addVarboundConstraints(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_Bool addcombconss, SCIP_Bool addcontconss, SCIP_HEURDATA *heurdata)
Definition: heur_dualval.c:422
#define HEUR_USESSUBSCIP
Definition: heur_dualval.c:84
static SCIP_RETCODE addLinearConstraintsToNlp(SCIP *scip, SCIP_Bool addcombconss, SCIP_Bool addcontconss, SCIP_HEURDATA *heurdata)
Definition: heur_dualval.c:711
static SCIP_DECL_EVENTINIT(eventInitLPsol)
Definition: heur_dualval.c:168
#define EVENTHDLR_NAME
Definition: heur_dualval.c:86
primal heuristic that uses dualvalues for successive switching variable values
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
struct SCIP_EventhdlrData SCIP_EVENTHDLRDATA
Definition: type_event.h:155
#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
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_VERBLEVEL_HIGH
Definition: type_message.h:56
@ 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_OKAY
Definition: type_retcode.h:42
@ SCIP_ERROR
Definition: type_retcode.h:43
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ 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