Scippy

SCIP

Solving Constraint Integer Programs

heur_dps.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_dps.c
26 * @ingroup DEFPLUGINS_HEUR
27 * @brief dynamic partition search
28 * @author Katrin Halbig
29 *
30 * The dynamic partition search (DPS) is a construction heuristic which additionally needs a
31 * user decomposition with linking constraints only.
32 *
33 * This heuristic splits the problem into several sub-SCIPs according to the given decomposition. Thereby the linking constraints
34 * with their right-hand and left-hand sides are also split. DPS searches for a partition of the sides on the blocks
35 * so that a feasible solution is obtained.
36 * For each block the parts of the original linking constraints are extended by slack variables. Moreover, the objective function
37 * is replaced by the sum of these additional variables weighted by penalty parameters lambda. If all blocks have an optimal solution
38 * of zero, the algorithm terminates with a feasible solution for the main problem. Otherwise, the partition and the penalty parameters
39 * are updated, and the sub-SCIPs are solved again.
40 *
41 * A detailed description can be found in
42 * K. Halbig, A. Göß and D. Weninger (2023). Exploiting user-supplied Decompositions inside Heuristics. https://optimization-online.org/?p=23386
43 */
44
45/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
46
47#include "scip/heur_dps.h"
48#include "scip/pub_dcmp.h"
49#include "scip/pub_heur.h"
50#include "scip/pub_misc.h"
51#include "scip/scipdefplugins.h"
52#include "scip/scip_cons.h"
53#include "scip/scip_dcmp.h"
54#include "scip/scip_general.h"
55#include "scip/scip_heur.h"
56#include "scip/scip_mem.h"
57#include "scip/scip_message.h"
58#include "scip/scip_param.h"
59#include "scip/scip_prob.h"
60
61
62#define HEUR_NAME "dps"
63#define HEUR_DESC "primal heuristic for decomposable MIPs"
64#define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
65#define HEUR_PRIORITY 75000
66#define HEUR_FREQ -1
67#define HEUR_FREQOFS 0
68#define HEUR_MAXDEPTH -1
69#define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_AFTERNODE
70#define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
71
72#define DEFAULT_MAXIT 50 /**< maximum number of iterations */
73#define DEFAULT_PENALTY 100.0 /**< multiplier for absolute increase of penalty parameters */
74
75/* event handler properties */
76#define EVENTHDLR_NAME "Dps"
77#define EVENTHDLR_DESC "event handler for " HEUR_NAME " heuristic"
78
79/*
80 * Data structures
81 */
82
83/** primal heuristic data */
84struct SCIP_HeurData
85{
86 SCIP_CONS** linkingconss; /**< linking constraints */
87 int nlinking; /**< number of linking constraints */
88 int nblocks; /**< number of blocks */
89 int maxit; /**< maximal number of iterations */
90 int timing; /**< should the heuristic run before or after the processing of the node?
91 (0: before, 1: after, 2: both)*/
92 SCIP_Real maxlinkscore; /**< maximal linking score of used decomposition (equivalent to percentage of linking constraints) */
93 SCIP_Real penalty; /**< multiplier for absolute increase of penalty parameters */
94 SCIP_Bool reoptimize; /**< should the problem get reoptimized with the original objective function? */
95 SCIP_Bool reuse; /**< should solutions get reused in subproblems? */
96 SCIP_Bool reoptlimits; /**< should strict limits for reoptimization be set? */
97};
98
99/** data related to one block */
101{
102 SCIP* blockscip; /**< SCIP data structure */
103 SCIP_VAR** slackvars; /**< slack variables */
104 SCIP_CONS** linkingconss; /**< linking constraints */
105 int* linkingindices; /**< indices of linking constraints in original problem */
106 int nlinking; /**< number of linking constraints */
107 int nblockvars; /**< number of block variables */
108 int nslackvars; /**< number of slack variables */
109 SCIP_Real* origobj; /**< original objective coefficients */
110};
112
113/** data related to one linking constraint */
115{
116 SCIP_CONS* linkingcons; /**< corresponding linking constraint of original problem */
117 SCIP_CONS** blockconss; /**< linking constraints of the blocks */
118 SCIP_VAR** slacks; /**< slackvars of the blocks */
119 SCIP_Real* minactivity; /**< minimal activity of constraint for each block */
120 SCIP_Real* maxactivity; /**< maximal activity of constraint for each block */
121 SCIP_Real* currentrhs; /**< current partition of rhs */
122 SCIP_Real* currentlhs; /**< current partition of lhs */
123 int* blocknumbers; /**< number of the blocks */
124 int nblocks; /**< number of blocks in which this linking constraint participates; dimension of arrays */
125 int nslacks; /**< number of slack variables */
126 int nslacksperblock; /**< 2, if ranged constraint; 1, if only rhs or lhs */
127 int lastviolations; /**< number of iterations in which the constraint was violated in succession */
128 SCIP_Bool hasrhs; /**< has linking constraint finite right-hand side? */
129 SCIP_Bool haslhs; /**< has linking constraint finite left-hand side? */
130};
131typedef struct Linking LINKING;
132
133/*
134 * Local methods
135 */
136
137/** assigns linking variables to last block
138 *
139 * The labels are copied to newdecomp and the linking variables are assigned to the last block (i.e., highest block label).
140 * Constraint labels and statistics are recomputed.
141 */
142static
144 SCIP* scip, /**< SCIP data structure */
145 SCIP_DECOMP* newdecomp, /**< decomposition with assigned linking variables */
146 SCIP_VAR** vars, /**< sorted array of variables */
147 SCIP_CONS** conss, /**< sorted array of constraints */
148 int* varlabels, /**< sorted array of variable labels */
149 int* conslabels, /**< sorted array of constraint labels */
150 int nvars, /**< number of variables */
151 int nconss, /**< number of constraints */
152 int nlinkvars /**< number of linking variables */
153 )
154{
155 int newlabel;
156 int v;
157
158 assert(scip != NULL);
159 assert(newdecomp != NULL);
160 assert(vars != NULL);
161 assert(conss != NULL);
162 assert(varlabels != NULL);
163 assert(conslabels != NULL);
164
165 /* copy the labels */
166 SCIP_CALL( SCIPdecompSetVarsLabels(newdecomp, vars, varlabels, nvars) );
167 SCIP_CALL( SCIPdecompSetConsLabels(newdecomp, conss, conslabels, nconss) );
168
169 /* assign linking variables */
170 newlabel = varlabels[nvars - 1]; /* take always label of last block */
171 assert(newlabel >= 0);
172 for( v = 0; v < nlinkvars; v++ )
173 {
174 SCIP_CALL( SCIPdecompSetVarsLabels(newdecomp, &vars[v], &newlabel, 1) );
175 }
176 SCIPdebugMsg(scip, "assigned %d linking variables\n", nlinkvars);
177
178 /* recompute constraint labels and statistics */
179 SCIP_CALL( SCIPcomputeDecompConsLabels(scip, newdecomp, conss, nconss) );
181 nlinkvars = SCIPdecompGetNBorderVars(newdecomp);
182
183 /* get new labels and sort */
184 SCIPdecompGetConsLabels(newdecomp, conss, conslabels, nconss);
185 SCIPdecompGetVarsLabels(newdecomp, vars, varlabels, nvars);
186 SCIPsortIntPtr(conslabels, (void**)conss, nconss);
187 SCIPsortIntPtr(varlabels, (void**)vars, nvars);
188
189 /* After assigning the linking variables, blocks can have zero constraints.
190 * So the remaining variables are labeled as linking in SCIPcomputeDecompStats().
191 * We assign this variables to the same label as above.
192 */
193 if( nlinkvars >= 1 )
194 {
195 assert(varlabels[0] == SCIP_DECOMP_LINKVAR);
196 SCIPdebugMsg(scip, "assign again %d linking variables\n", nlinkvars);
197
198 for( v = 0; v < nlinkvars; v++ )
199 {
200 SCIP_CALL( SCIPdecompSetVarsLabels(newdecomp, &vars[v], &newlabel, 1) );
201 }
202 SCIP_CALL( SCIPcomputeDecompConsLabels(scip, newdecomp, conss, nconss) );
204
205 SCIPdecompGetConsLabels(newdecomp, conss, conslabels, nconss);
206 SCIPdecompGetVarsLabels(newdecomp, vars, varlabels, nvars);
207 SCIPsortIntPtr(conslabels, (void**)conss, nconss);
208 SCIPsortIntPtr(varlabels, (void**)vars, nvars);
209 }
210 assert(varlabels[0] != SCIP_DECOMP_LINKVAR);
211
212 return SCIP_OKAY;
213}
214
215/** creates a sub-SCIP and sets parameters */
216static
218 SCIP* scip, /**< main SCIP data structure */
219 SCIP** subscip /**< pointer to store created sub-SCIP */
220 )
221{
222 SCIP_Real infvalue;
223
224 assert(scip != NULL);
225 assert(subscip != NULL);
226
227 /* create a new SCIP instance */
228 SCIP_CALL( SCIPcreate(subscip) );
230
231 /* copy value for infinity */
232 SCIP_CALL( SCIPgetRealParam(scip, "numerics/infinity", &infvalue) );
233 SCIP_CALL( SCIPsetRealParam(*subscip, "numerics/infinity", infvalue) );
234
235 SCIP_CALL( SCIPcopyLimits(scip, *subscip) );
236
237 /* avoid recursive calls */
238 SCIP_CALL( SCIPsetSubscipsOff(*subscip, TRUE) );
239
240 /* disable cutting plane separation */
242
243 /* disable expensive presolving */
245
246 /* disable expensive techniques */
247 SCIP_CALL( SCIPsetIntParam(*subscip, "misc/usesymmetry", 0) );
248
249 /* do not abort subproblem on CTRL-C */
250 SCIP_CALL( SCIPsetBoolParam(*subscip, "misc/catchctrlc", FALSE) );
251
252#ifdef SCIP_DEBUG
253 /* for debugging, enable full output */
254 SCIP_CALL( SCIPsetIntParam(*subscip, "display/verblevel", 5) );
255 SCIP_CALL( SCIPsetIntParam(*subscip, "display/freq", 100000000) );
256#else
257 /* disable statistic timing inside sub SCIP and output to console */
258 SCIP_CALL( SCIPsetIntParam(*subscip, "display/verblevel", 0) );
259 SCIP_CALL( SCIPsetBoolParam(*subscip, "timing/statistictiming", FALSE) );
260#endif
261
262 /* speed up sub-SCIP by not checking dual LP feasibility */
263 SCIP_CALL( SCIPsetBoolParam(*subscip, "lp/checkdualfeas", FALSE) );
264
265 return SCIP_OKAY;
266}
267
268/** copies the given variables and constraints to the given sub-SCIP */
269static
271 SCIP* scip, /**< source SCIP */
272 SCIP* subscip, /**< target SCIP */
273 const char* name, /**< name for copied problem */
274 SCIP_VAR** vars, /**< array of variables to copy */
275 SCIP_CONS** conss, /**< array of constraints to copy */
276 SCIP_HASHMAP* varsmap, /**< hashmap for copied variables */
277 SCIP_HASHMAP* conssmap, /**< hashmap for copied constraints */
278 int nvars, /**< number of variables to copy */
279 int nconss, /**< number of constraints to copy */
280 SCIP_Bool* success /**< was copying successful? */
281 )
282{
283 SCIP_CONS* newcons;
284 SCIP_VAR* newvar;
285 int i;
286
287 assert(scip != NULL);
288 assert(subscip != NULL);
289 assert(vars != NULL);
290 assert(conss != NULL);
291 assert(varsmap != NULL);
292 assert(conssmap != NULL);
293 assert(success != NULL);
294
295 SCIPdebugMsg(scip, "copyToSubscip\n");
296
297 /* create problem in sub-SCIP */
298 SCIP_CALL( SCIPcreateProb(subscip, name, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
299
300 /* copy variables */
301 for( i = 0; i < nvars; ++i )
302 {
303 SCIP_CALL( SCIPgetVarCopy(scip, subscip, vars[i], &newvar, varsmap, conssmap, FALSE, success) );
304
305 /* abort if variable was not successfully copied */
306 if( !(*success) )
307 {
308 SCIPwarningMessage(scip, "Abort heuristic dps since not all variables were successfully copied.\n");
309 SCIPABORT();
310 return SCIP_OKAY;
311 }
312 }
313 assert(nvars == SCIPgetNOrigVars(subscip));
314
315 /* copy constraints */
316 for( i = 0; i < nconss; ++i )
317 {
318 assert(conss[i] != NULL);
319 assert(!SCIPconsIsModifiable(conss[i]));
320 assert(SCIPconsIsActive(conss[i]));
321 assert(!SCIPconsIsDeleted(conss[i]));
322
323 /* copy the constraint */
324 SCIP_CALL( SCIPgetConsCopy(scip, subscip, conss[i], &newcons, SCIPconsGetHdlr(conss[i]), varsmap, conssmap, NULL,
325 SCIPconsIsInitial(conss[i]), SCIPconsIsSeparated(conss[i]), SCIPconsIsEnforced(conss[i]),
326 SCIPconsIsChecked(conss[i]), SCIPconsIsPropagated(conss[i]), FALSE, FALSE,
327 SCIPconsIsDynamic(conss[i]), SCIPconsIsRemovable(conss[i]), FALSE, FALSE, success) );
328
329 /* abort if constraint was not successfully copied */
330 if( !(*success) )
331 return SCIP_OKAY;
332
333 SCIP_CALL( SCIPaddCons(subscip, newcons) );
334 SCIP_CALL( SCIPreleaseCons(subscip, &newcons) );
335 }
336
337 /* block constraint contains variables which are not part of this block
338 *
339 * todo: maybe they are part of the block, but it is not recognized, because they are, for example, negated or aggregated.
340 */
341 if( nvars != SCIPgetNOrigVars(subscip) )
342 *success = FALSE;
343
344 return SCIP_OKAY;
345}
346
347/** creates the subscip for a given block */
348static
350 SCIP* scip, /**< SCIP data structure */
351 BLOCKPROBLEM* blockproblem, /**< blockproblem that should be created */
352 LINKING** linkings, /**< linkings that will be (partially) initialized */
353 SCIP_CONS** conss, /**< sorted array of constraints of this block */
354 SCIP_VAR** vars, /**< sorted array of variables of this block */
355 int nconss, /**< number of constraints of this block */
356 int nvars, /**< number of variables of this block */
357 SCIP_CONS** linkingconss, /**< linking constraints in the original problem */
358 int nlinking, /**< number of linking constraints in the original problem */
359 int blocknumber, /**< number of block that should be created */
360 SCIP_Bool* success /**< pointer to store whether creation was successful */
361 )
362{
363 char name[SCIP_MAXSTRLEN];
364 SCIP_HASHMAP* varsmap;
365 SCIP_HASHMAP* conssmap;
366 SCIP_VAR** consvars; /* all vars in original linking cons */
367 SCIP_Real* consvals;
368 int nconsvars;
369 SCIP_VAR** blockvars; /* vars of current linking cons of current block */
370 SCIP_Real* blockvals;
371 int nblockvars;
372 SCIP_VAR** subvars; /* all vars of subscip */
373 int maxnconsvars; /* current size of arrays */
374 int c;
375 int v;
376
377 assert(scip != NULL);
378 assert(blockproblem != NULL);
379 assert(conss != NULL);
380 assert(vars != NULL);
381 assert(blockproblem->blockscip != NULL);
382
383 maxnconsvars = 20; /* start size; increase size if necessary */
384
385 SCIPdebugMsg(scip, "Create blockproblem %d\n", blocknumber);
386
387 /* create the variable/constraint mapping hash map */
388 SCIP_CALL( SCIPhashmapCreate(&varsmap, SCIPblkmem(scip), nvars) );
389 SCIP_CALL( SCIPhashmapCreate(&conssmap, SCIPblkmem(scip), nconss) );
390
391 /* get name of the original problem and add "comp_nr" */
392 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_comp_%d", SCIPgetProbName(scip), blocknumber);
393
394 SCIP_CALL( copyToSubscip(scip, blockproblem->blockscip, name, vars, conss, varsmap, conssmap,
395 nvars, nconss, success) );
396 if( !(*success) )
397 {
398 SCIPdebugMsg(scip, "Copy to subscip failed\n");
399 SCIPhashmapFree(&conssmap);
400 SCIPhashmapFree(&varsmap);
401
402 return SCIP_OKAY;
403 }
404
405 /* save number of variables that have a corresponding variable in original problem*/
406 blockproblem->nblockvars = SCIPgetNVars(blockproblem->blockscip);
407
408 /* save original objective and set objective to zero */
409 subvars = SCIPgetVars(blockproblem->blockscip);
410 for( v = 0; v < nvars; v++ )
411 {
412 blockproblem->origobj[v] = SCIPvarGetObj(subvars[v]);
413 SCIP_CALL( SCIPchgVarObj(blockproblem->blockscip, subvars[v], 0.0) );
414 }
415
416 /* allocate memory */
417 SCIP_CALL( SCIPallocBufferArray(blockproblem->blockscip, &blockvars, nvars + 2) ); /* two entries for the slack variables */
418 SCIP_CALL( SCIPallocBufferArray(blockproblem->blockscip, &blockvals, nvars + 2) );
419 SCIP_CALL( SCIPallocBufferArray(blockproblem->blockscip, &consvars, maxnconsvars) );
420 SCIP_CALL( SCIPallocBufferArray(blockproblem->blockscip, &consvals, maxnconsvars) );
421
422 /* find and add parts of linking constraints */
423 SCIPdebugMsg(scip, "add parts of linking constraints\n");
424 for( c = 0; c < nlinking; c++ )
425 {
426 const char* conshdlrname;
427 char consname[SCIP_MAXSTRLEN];
428 SCIP_CONS* newcons;
429 SCIP_Real rhs;
430 SCIP_Real lhs;
431 SCIP_Real minact;
432 SCIP_Real maxact;
433 SCIP_Bool mininfinite;
434 SCIP_Bool maxinfinite;
435
436 assert(linkingconss[c] != NULL);
437
438 newcons = NULL;
439
440#ifdef SCIP_MORE_DEBUG
441 SCIPdebugMsg(scip, "consider constraint %s\n", SCIPconsGetName(linkingconss[c]));
442 SCIPdebugPrintCons(scip, linkingconss[c], NULL);
443#endif
444
445 nblockvars = 0;
446
447 /* every constraint with linear representation is allowed */
448 conshdlrname = SCIPconshdlrGetName(SCIPconsGetHdlr(linkingconss[c]));
449 if( !( (strcmp(conshdlrname, "linear") == 0) || (strcmp(conshdlrname, "setppc") == 0)
450 || (strcmp(conshdlrname, "logicor") == 0) || (strcmp(conshdlrname, "knapsack") == 0)
451 || (strcmp(conshdlrname, "varbound") == 0) ) )
452 {
453 SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "Heuristic %s cannot handle linking constraints of type %s\n", HEUR_NAME, conshdlrname);
454 /* TODO which other types can we handle/transform in a linear constraint? */
455
456 *success = FALSE;
457 break; /* releases memory and breaks heuristic */
458 }
459
460 SCIP_CALL( SCIPgetConsNVars(scip, linkingconss[c], &nconsvars, success) );
461
462 /* reallocate memory if we have more variables than maxnconsvars */
463 if( nconsvars > maxnconsvars )
464 {
465 int newsize;
466
467 /* calculate new size */
468 newsize = SCIPcalcMemGrowSize(scip, MAX(2 * maxnconsvars, nconsvars)); /* at least double size */
469
470 SCIP_CALL( SCIPreallocBufferArray(blockproblem->blockscip, &consvars, newsize) );
471 SCIP_CALL( SCIPreallocBufferArray(blockproblem->blockscip, &consvals, newsize) );
472 maxnconsvars = newsize;
473 }
474
475 SCIP_CALL( SCIPgetConsVars(scip, linkingconss[c], consvars, nconsvars, success) );
476 SCIP_CALL( SCIPgetConsVals(scip, linkingconss[c], consvals, nconsvars, success) );
477
478 if( !(*success) )
479 {
480 SCIPdebugMsg(scip, "Create blockproblem failed\n");
481 break; /* releases memory and breaks heuristic */
482 }
483
484 /* check if constraint contains variables of this block */
485 for( v = 0; v < nconsvars; v++ )
486 {
487 if( SCIPhashmapExists(varsmap, (void*)consvars[v]) )
488 {
489 blockvars[nblockvars] = (SCIP_VAR*) SCIPhashmapGetImage(varsmap, (void*)consvars[v]);
490 blockvals[nblockvars] = consvals[v];
491 ++nblockvars;
492 }
493 /* handle negated variables*/
494 else if( SCIPvarGetStatus(consvars[v]) == SCIP_VARSTATUS_NEGATED)
495 {
496 if( SCIPhashmapExists(varsmap, (void*)SCIPvarGetNegationVar(consvars[v])) ) /* negation exists in this block */
497 {
498 /* save negated variable */
499 SCIP_VAR* origblockvar = (SCIP_VAR*) SCIPhashmapGetImage(varsmap, (void*)SCIPvarGetNegationVar(consvars[v]));
500 SCIP_VAR* negblockvar = NULL;
501 SCIP_CALL( SCIPgetNegatedVar(blockproblem->blockscip, origblockvar, &negblockvar) );
502 blockvars[nblockvars] = negblockvar;
503 blockvals[nblockvars] = consvals[v];
504 ++nblockvars;
505 }
506 }
507 }
508
509 /* continue with next linking constraint if it has no part in current block */
510 if( nblockvars == 0 )
511 continue;
512
513 /* get rhs and/or lhs */
514 rhs = SCIPconsGetRhs(scip, linkingconss[c], success);
515 if( !(*success) )
516 {
517 SCIPdebugMsg(scip, "Create blockproblem failed\n");
518 return SCIP_OKAY;
519 }
520 lhs = SCIPconsGetLhs(scip, linkingconss[c], success);
521 if( !(*success) )
522 {
523 SCIPdebugMsg(scip, "Create blockproblem failed\n");
524 return SCIP_OKAY;
525 }
526 assert(!SCIPisInfinity(scip, rhs) || !SCIPisInfinity(scip, -lhs)); /* at least one side bounded */
527 assert(SCIPisLE(scip, lhs, rhs));
528
529 if( !SCIPisInfinity(scip, rhs) )
530 linkings[c]->hasrhs = TRUE;
531 if( !SCIPisInfinity(scip, -lhs) )
532 linkings[c]->haslhs = TRUE;
533 if( !SCIPisInfinity(scip, rhs) && !SCIPisInfinity(scip, -lhs))
534 linkings[c]->nslacksperblock = 2;
535 else
536 linkings[c]->nslacksperblock = 1;
537
538 /* add slack variable for rhs */
539 if( linkings[c]->hasrhs )
540 {
541 /* slack variable z_r >= 0 */
542 char varname[SCIP_MAXSTRLEN];
543 (void)SCIPsnprintf(varname, SCIP_MAXSTRLEN, "z_r_%s", SCIPconsGetName(linkingconss[c]));
544 SCIP_CALL( SCIPcreateVarBasic(blockproblem->blockscip, &blockvars[nblockvars], varname,
546 blockvals[nblockvars] = -1.0;
547 SCIP_CALL( SCIPaddVar(blockproblem->blockscip, blockvars[nblockvars]) );
548#ifdef SCIP_MORE_DEBUG
549 SCIPdebugMsg(scip, "Add variable %s\n", SCIPvarGetName(blockvars[nblockvars]));
550#endif
551 linkings[c]->slacks[linkings[c]->nslacks] = blockvars[nblockvars];
552 blockproblem->slackvars[blockproblem->nslackvars] = blockvars[nblockvars];
553 ++blockproblem->nslackvars;
554 ++linkings[c]->nslacks;
555 ++nblockvars;
556 }
557
558 /* add slack variable for lhs */
559 if( linkings[c]->haslhs )
560 {
561 /* slack variable z_l >= 0 */
562 char varname[SCIP_MAXSTRLEN];
563 (void)SCIPsnprintf(varname, SCIP_MAXSTRLEN, "z_l_%s", SCIPconsGetName(linkingconss[c]));
564 SCIP_CALL( SCIPcreateVarBasic(blockproblem->blockscip, &blockvars[nblockvars], varname,
566 blockvals[nblockvars] = 1.0;
567 SCIP_CALL( SCIPaddVar(blockproblem->blockscip, blockvars[nblockvars]) );
568#ifdef SCIP_MORE_DEBUG
569 SCIPdebugMsg(scip, "Add variable %s\n", SCIPvarGetName(blockvars[nblockvars]));
570#endif
571 linkings[c]->slacks[linkings[c]->nslacks] = blockvars[nblockvars];
572 blockproblem->slackvars[blockproblem->nslackvars] = blockvars[nblockvars];
573 ++blockproblem->nslackvars;
574 ++linkings[c]->nslacks;
575 ++nblockvars;
576 }
577
578 /* add linking constraint with slack variable */
579 (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s", SCIPconsGetName(linkingconss[c]));
580 SCIP_CALL( SCIPcreateConsBasicLinear(blockproblem->blockscip, &newcons, consname, nblockvars, blockvars, blockvals, lhs, rhs) );
581 SCIP_CALL( SCIPaddCons(blockproblem->blockscip, newcons) );
582#ifdef SCIP_MORE_DEBUG
583 SCIPdebugMsg(blockproblem->blockscip, "add constraint %s\n", SCIPconsGetName(newcons));
584 SCIPdebugPrintCons(blockproblem->blockscip, newcons, NULL);
585#endif
586
587 blockproblem->linkingconss[blockproblem->nlinking] = newcons;
588 linkings[c]->blockconss[linkings[c]->nblocks] = newcons;
589 linkings[c]->blocknumbers[linkings[c]->nblocks] = blocknumber;
590 blockproblem->linkingindices[blockproblem->nlinking] = c;
591
592 /* calculate minimal und maximal activity (exclude slack variables) */
593 minact = 0;
594 maxact = 0;
595 mininfinite = FALSE;
596 maxinfinite = FALSE;
597 for( v = 0; v < nblockvars - linkings[c]->nslacksperblock && (!mininfinite || !maxinfinite); v++ )
598 {
599 SCIP_Real lb;
600 SCIP_Real ub;
601 lb = SCIPvarGetLbGlobal(blockvars[v]);
602 ub = SCIPvarGetUbGlobal(blockvars[v]);
603
604 if( blockvals[v] >= 0.0 )
605 {
606 mininfinite = (mininfinite || SCIPisInfinity(scip, -lb));
607 maxinfinite = (maxinfinite || SCIPisInfinity(scip, ub));
608 if( !mininfinite )
609 minact += blockvals[v] * lb;
610 if( !maxinfinite )
611 maxact += blockvals[v] * ub;
612 }
613 else
614 {
615 mininfinite = (mininfinite || SCIPisInfinity(scip, ub));
616 maxinfinite = (maxinfinite || SCIPisInfinity(scip, -lb));
617 if( !mininfinite )
618 minact += blockvals[v] * ub;
619 if( !maxinfinite )
620 maxact += blockvals[v] * lb;
621 }
622 }
623
624 if( mininfinite )
625 linkings[c]->minactivity[linkings[c]->nblocks] = -SCIPinfinity(scip);
626 else
627 linkings[c]->minactivity[linkings[c]->nblocks] = minact;
628 if( maxinfinite )
629 linkings[c]->maxactivity[linkings[c]->nblocks] = SCIPinfinity(scip);
630 else
631 linkings[c]->maxactivity[linkings[c]->nblocks] = maxact;
632 assert(SCIPisLE(scip, linkings[c]->minactivity[linkings[c]->nblocks], linkings[c]->maxactivity[linkings[c]->nblocks]));
633
634 linkings[c]->nblocks++;
635 blockproblem->nlinking++;
636
637 for( v = 1; v <= linkings[c]->nslacksperblock; v++ )
638 {
639 SCIP_CALL( SCIPreleaseVar(blockproblem->blockscip, &blockvars[nblockvars - v]) );
640 }
641
642 SCIP_CALL( SCIPreleaseCons(blockproblem->blockscip, &newcons) );
643 }
644 assert(blockproblem->nlinking <= nlinking);
645
646 /* free memory */
647 SCIPfreeBufferArray(blockproblem->blockscip, &consvals);
648 SCIPfreeBufferArray(blockproblem->blockscip, &consvars);
649 SCIPfreeBufferArray(blockproblem->blockscip, &blockvals);
650 SCIPfreeBufferArray(blockproblem->blockscip, &blockvars);
651
652 SCIPhashmapFree(&conssmap);
653 SCIPhashmapFree(&varsmap);
654
655 return SCIP_OKAY;
656}
657
658/** creates data structures and splits problem into blocks */
659static
661 SCIP* scip, /**< SCIP data structure */
662 SCIP_HEURDATA* heurdata, /**< heuristic data */
663 SCIP_DECOMP* decomp, /**< decomposition data structure */
664 BLOCKPROBLEM** blockproblem, /**< array of blockproblem data structures */
665 LINKING** linkings, /**< array of linking data structures */
666 SCIP_VAR** vars, /**< sorted array of variables */
667 SCIP_CONS** conss, /**< sorted array of constraints */
668 SCIP_Bool* success /**< pointer to store whether splitting was successful */
669 )
670{
671 int* nconssblock;
672 int* nvarsblock;
673 int conssoffset;
674 int varsoffset;
675 int i; /* blocknumber */
676
677 assert(scip != NULL);
678 assert(heurdata != NULL);
679 assert(vars != NULL);
680 assert(conss != NULL);
681
682 SCIP_CALL( SCIPallocBufferArray(scip, &nvarsblock, heurdata->nblocks + 1) );
683 SCIP_CALL( SCIPallocBufferArray(scip, &nconssblock, heurdata->nblocks + 1) );
684 SCIP_CALL( SCIPdecompGetVarsSize(decomp, nvarsblock, heurdata->nblocks + 1) );
685 SCIP_CALL( SCIPdecompGetConssSize(decomp, nconssblock, heurdata->nblocks + 1) );
686 assert(0 == nvarsblock[0]);
687
688 varsoffset = 0;
689 conssoffset = 0;
690
691 for( i = 0; i < heurdata->nblocks; i++)
692 {
693 conssoffset += nconssblock[i];
694 varsoffset += nvarsblock[i];
695
696 SCIP_CALL( createBlockproblem(scip, blockproblem[i], linkings, &conss[conssoffset], &vars[varsoffset], nconssblock[i+1], nvarsblock[i+1],
697 heurdata->linkingconss, heurdata->nlinking, i, success) );
698 if( !(*success) )
699 break;
700 }
701
702 SCIPfreeBufferArray(scip, &nconssblock);
703 SCIPfreeBufferArray(scip, &nvarsblock);
704
705 return SCIP_OKAY;
706}
707
708/** rounds partition for one linking constraint to integer value if variables and coefficients are integer
709 *
710 * changes only currentrhs/currentlhs
711 */
712static
714 SCIP* scip, /**< SCIP data structure */
715 LINKING* linking, /**< one linking data structure */
716 BLOCKPROBLEM** blockproblem, /**< array of blockproblem data structures */
717 SCIP_Bool roundbyrhs /**< round by right hand side? */
718 )
719{
720 SCIP_Real* fracPart;
721 int* sorting;
722 int* isinteger;
723 SCIP_Real sumbefor; /* includes value at idx */
724 SCIP_Real sumafter;
725 SCIP_Real diff;
726 int nnonintblocks; /* number of non integer blocks */
727 int idx;
728 int b;
729 int i;
730 int k;
731
732 assert(scip != NULL);
733 assert(linking != NULL);
734 assert(blockproblem != NULL);
735
736 nnonintblocks = 0;
737 idx = 0;
738
739 SCIP_CALL( SCIPallocBufferArray(scip, &fracPart, linking->nblocks) );
740 SCIP_CALL( SCIPallocBufferArray(scip, &sorting, linking->nblocks) );
741 SCIP_CALL( SCIPallocBufferArray(scip, &isinteger, linking->nblocks) );
742
743 /* get integer blocks and fractional parts */
744 for( b = 0; b < linking->nblocks; b++ )
745 {
746 SCIP* subscip;
747 SCIP_CONS* blockcons;
748 SCIP_VAR** blockvars;
749 SCIP_Real* blockvals;
750 int nblockvars;
751 int length; /* number of block variables without slack variables */
752 SCIP_Bool success;
753
754 subscip = blockproblem[linking->blocknumbers[b]]->blockscip;
755 blockcons = linking->blockconss[b];
756 sorting[b] = b; /* store current sorting to sort back */
757
758 SCIP_CALL( SCIPgetConsNVars(subscip, blockcons, &nblockvars, &success) );
759 assert(success);
760 SCIP_CALL( SCIPallocBufferArray(scip, &blockvars, nblockvars) );
761 SCIP_CALL( SCIPallocBufferArray(scip, &blockvals, nblockvars) );
762
763 SCIP_CALL( SCIPgetConsVars(subscip, blockcons, blockvars, nblockvars, &success) );
764 assert(success);
765 SCIP_CALL( SCIPgetConsVals(subscip, blockcons, blockvals, nblockvars, &success) );
766 assert(success);
767
768 /* get number of block variables in this constraint without slack variables */
769 length = nblockvars - linking->nslacksperblock;
770
771 /* get blocks with integer value */
772 isinteger[b] = 1;
773 for( i = 0; i < length; i++ )
774 {
775 if( SCIPvarGetType(blockvars[i]) == SCIP_VARTYPE_CONTINUOUS || !SCIPisIntegral(scip, blockvals[i]) )
776 {
777 isinteger[b] = 0;
778 nnonintblocks++;
779 break;
780 }
781 }
782
783 /* get fractional part of blockconstraints */
784 if( roundbyrhs )
785 fracPart[b] = linking->currentrhs[b] - floor(linking->currentrhs[b]); /* do not use SCIPfrac()! */
786 else
787 fracPart[b] = linking->currentlhs[b] - floor(linking->currentlhs[b]);
788
789 SCIPfreeBufferArray(scip, &blockvals);
790 SCIPfreeBufferArray(scip, &blockvars);
791 }
792
793 /* sort non-integer blocks to the front */
794 SCIPsortIntIntReal(isinteger, sorting, fracPart, linking->nblocks);
795
796 /* sort by fractional part */
797 SCIPsortRealInt(fracPart, sorting, nnonintblocks);
798 SCIPsortRealInt(&fracPart[nnonintblocks], &sorting[nnonintblocks], linking->nblocks - nnonintblocks);
799
800 /* detect blocks for rounding down and rounding up:
801 * integer blocks with small fractional parts are rounded down
802 * integer blocks with big fractional parts are rounded up
803 */
804
805 sumbefor = 0.0;
806 sumafter = 0.0;
807
808 for( i = 0; i < linking->nblocks - nnonintblocks; i++ )
809 sumafter += 1 - fracPart[nnonintblocks + i];
810
811 for( i = 0; i < linking->nblocks - nnonintblocks; i++ )
812 {
813 sumbefor += fracPart[nnonintblocks + i];
814 sumafter -= 1 - fracPart[nnonintblocks + i];
815
816 if( sumbefor >= sumafter )
817 {
818 for( k = 0; k <= i; k++ )
819 fracPart[nnonintblocks + k] = -fracPart[nnonintblocks + k];
820
821 for( k = i + 1; k < linking->nblocks - nnonintblocks; k++ )
822 fracPart[nnonintblocks + k] = 1 - fracPart[nnonintblocks + k];
823
824 idx = i;
825 break;
826 }
827 }
828 diff = sumbefor - sumafter;
829 assert(SCIPisGE(scip, diff, 0.0));
830
831 /* add difference to last non integer block */
832 for( i = nnonintblocks - 1; i >= 0; i-- )
833 {
834 if( SCIPisGT(scip, diff, 0.0) )
835 {
836 fracPart[i] = diff;
837 diff = 0;
838 }
839 else
840 fracPart[i] = 0;
841 }
842
843 /* add difference to last rounded down block if no non integer block exists */
844 if( SCIPisGT(scip, diff, 0.0))
845 {
846 assert(nnonintblocks == 0);
847 fracPart[idx] += diff;
848 }
849
850 /* sort back */
851 SCIPsortIntReal(sorting, fracPart, linking->nblocks);
852
853 /* round partition
854 * if we have a ranged constraint, both sides get rounded in the same way
855 */
856 for( b = 0; b < linking->nblocks; b++ )
857 {
858 if( linking->hasrhs )
859 linking->currentrhs[b] += fracPart[b];
860
861 if( linking->haslhs )
862 linking->currentlhs[b] += fracPart[b];
863 }
864
865 SCIPfreeBufferArray(scip, &isinteger);
866 SCIPfreeBufferArray(scip, &sorting);
867 SCIPfreeBufferArray(scip, &fracPart);
868
869 return SCIP_OKAY;
870}
871
872/** calculates initial partition and sets rhs/lhs in blockproblems */
873static
875 SCIP* scip, /**< SCIP data structure of main scip */
876 LINKING** linkings, /**< array of linking data structures */
877 BLOCKPROBLEM** blockproblem, /**< array of blockproblem data structures */
878 SCIP_HEURTIMING heurtiming, /**< current point in the node solving process */
879 int nlinking, /**< number of linking constraints */
880 SCIP_Bool* success /**< pointer to store whether initialization was successful */
881 )
882{
883 LINKING* linking;
884 SCIP_Real rhs;
885 SCIP_Real lhs;
886 SCIP_Real residualrhs;
887 SCIP_Real residuallhs;
888 SCIP_Real goalvalue;
889 int c;
890 int b;
891
892 assert(scip != NULL);
893 assert(linkings != NULL);
894 assert(blockproblem != NULL);
895 assert(nlinking > 0);
896
897 SCIPdebugMsg(scip, "initialize partition\n");
898
899 /* for each linking constraint the rhs/lhs is split between the blocks */
900 for( c = 0; c < nlinking; c++ )
901 {
902 linking = linkings[c];
903 rhs = SCIPconsGetRhs(scip, linking->linkingcons, success);
904 assert(*success);
905 lhs = SCIPconsGetLhs(scip, linking->linkingcons, success);
906 assert(*success);
907 residualrhs = rhs;
908 residuallhs = lhs;
909
910 /* LP value for each block plus part of remaining amount if sum is not equal to rhs/lhs */
911 if( (heurtiming & SCIP_HEURTIMING_AFTERNODE) && (linking->hasrhs || linking->haslhs) )
912 {
913 SCIP_Real sumrhs = 0.0;
914 SCIP_Real sumlhs = 0.0;
915 for( b = 0; b < linking->nblocks; b++ )
916 {
917 SCIP_VAR** consvars;
918 SCIP_Real* consvals;
919 SCIP_CONS* cons;
920 int nconsvars;
921 SCIP_Real lpvalue;
922 int i;
923
924 /* get variables of linking constraint of one block */
925 cons = linking->blockconss[b];
926 SCIP_CALL( SCIPgetConsNVars(blockproblem[linking->blocknumbers[b]]->blockscip, cons, &nconsvars, success) );
927 SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nconsvars) );
928 SCIP_CALL( SCIPallocBufferArray(scip, &consvals, nconsvars) );
929 SCIP_CALL( SCIPgetConsVars(blockproblem[linking->blocknumbers[b]]->blockscip, cons, consvars, nconsvars, success) );
930 SCIP_CALL( SCIPgetConsVals(blockproblem[linking->blocknumbers[b]]->blockscip, cons, consvals, nconsvars, success) );
931 assert(success);
932
933 /* calculate value of partition variable in lp solution */
934 lpvalue = 0.0;
935 for( i = 0; i < nconsvars - linking->nslacksperblock; i++ )
936 {
937 SCIP_VAR* origvar;
938 SCIP_Real varlpvalue;
939
940 origvar = SCIPfindVar(scip, SCIPvarGetName(consvars[i]));
941 if( origvar == NULL ) /* e.g. variable is negated */
942 {
943 *success = FALSE;
944 return SCIP_OKAY;
945 }
946 varlpvalue = SCIPvarGetLPSol(origvar);
947 lpvalue += varlpvalue * consvals[i];
948 }
949 sumrhs += lpvalue;
950 sumlhs += lpvalue;
951
952 /* set currentrhs/lhs at lp value */
953 if( linking->hasrhs )
954 linking->currentrhs[b] = lpvalue;
955 if( linking->haslhs )
956 linking->currentlhs[b] = lpvalue;
957
958 SCIPfreeBufferArray(scip, &consvars);
959 SCIPfreeBufferArray(scip, &consvals);
960 }
961 assert(SCIPisLE(scip, sumrhs, rhs));
962 assert(SCIPisGE(scip, sumlhs, lhs));
963
964 /* distribute remaining amount */
965 if( !SCIPisEQ(scip, rhs, sumrhs) && linking->hasrhs )
966 {
967 SCIP_Real diff;
968 SCIP_Real part;
969 SCIP_Real residual;
970 diff = rhs - sumrhs;
971 residual = 0.0;
972
973 for( b = 0; b < linking->nblocks; b++ )
974 {
975 goalvalue = linking->currentrhs[b] + ( diff / linking->nblocks ) + residual;
976 part = MIN(goalvalue, linking->maxactivity[b]);
977 residual = goalvalue - part;
978 linking->currentrhs[b] = part;
979 }
980 if( !SCIPisZero(scip, residual) )
981 linking->currentrhs[0] += residual;
982 }
983 if( !SCIPisEQ(scip, lhs, sumlhs) && linking->haslhs )
984 {
985 SCIP_Real diff;
986 SCIP_Real part;
987 SCIP_Real residual;
988 diff = sumlhs - lhs; /* always positive*/
989 residual = 0.0;
990
991 for( b = 0; b < linking->nblocks; b++ )
992 {
993 goalvalue = linking->currentlhs[b] - ( diff / linking->nblocks ) + residual;
994 part = MAX(goalvalue, linking->minactivity[b]);
995 residual = goalvalue - part;
996 linking->currentlhs[b] = part;
997 }
998 if( !SCIPisZero(scip, residual) )
999 linking->currentlhs[0] += residual;
1000 }
1001 }
1002 /* equal parts for each block with respect to minimal/maximal activity */
1003 else if( linking->hasrhs || linking->haslhs )
1004 {
1005 if( linking->hasrhs )
1006 {
1007 for( b = 0; b < linking->nblocks; b++ )
1008 {
1009 goalvalue = residualrhs / (linking->nblocks - b);
1010 linking->currentrhs[b] = MIN(MAX(goalvalue, linking->minactivity[b]), linking->maxactivity[b]);
1011 residualrhs -= linking->currentrhs[b];
1012 }
1013 /* add residual partition to first block */
1014 linking->currentrhs[0] += residualrhs;
1015 }
1016 if( linking->haslhs )
1017 {
1018 for( b = 0; b < linking->nblocks; b++ )
1019 {
1020 goalvalue = residuallhs / (linking->nblocks - b);
1021 linking->currentlhs[b] = MIN(MAX(goalvalue, linking->minactivity[b]), linking->maxactivity[b]);
1022 residuallhs -= linking->currentlhs[b];
1023 }
1024 /* add residual partition to first block */
1025 linking->currentlhs[0] += residuallhs;
1026 }
1027 }
1028 else
1029 {
1030 assert(linking->nblocks == 0 && !SCIPconsIsChecked(linking->linkingcons));
1031 }
1032
1033 SCIP_CALL( roundPartition(scip, linking, blockproblem, linking->hasrhs) );
1034
1035 /* set sides in blockproblem at initial partition */
1036 for( b = 0; b < linking->nblocks; b++ )
1037 {
1038 if( linking->hasrhs )
1039 {
1040 SCIP_CALL( SCIPchgRhsLinear(blockproblem[linking->blocknumbers[b]]->blockscip,
1041 linking->blockconss[b], linking->currentrhs[b]) );
1042#ifdef SCIP_MORE_DEBUG
1043 SCIPdebugMsg(scip, "change rhs of %s in block %d to %f\n",
1044 SCIPconsGetName(linking->linkingcons), linking->blocknumbers[b], linking->currentrhs[b]);
1045#endif
1046 }
1047 if( linking->haslhs )
1048 {
1049 SCIP_CALL( SCIPchgLhsLinear(blockproblem[linking->blocknumbers[b]]->blockscip,
1050 linking->blockconss[b], linking->currentlhs[b]) );
1051#ifdef SCIP_MORE_DEBUG
1052 SCIPdebugMsg(scip, "change lhs of %s in block %d to %f\n",
1053 SCIPconsGetName(linking->linkingcons), linking->blocknumbers[b], linking->currentlhs[b]);
1054#endif
1055 }
1056 }
1057 }
1058
1059 return SCIP_OKAY;
1060}
1061
1062/** calculates shift */
1063static
1065 SCIP* scip, /**< SCIP data structure of main scip */
1066 BLOCKPROBLEM** blockproblem, /**< array of blockproblem data structures */
1067 LINKING* linking, /**< one linking data structure */
1068 SCIP_Real** shift, /**< pointer to store direction vector */
1069 int* nviolatedblocksrhs, /**< pointer to store number of blocks which violate rhs */
1070 int* nviolatedblockslhs, /**< pointer to store number of blocks which violate lhs */
1071 SCIP_Bool* update /**< should we update the partition? */
1072 )
1073{
1074 int* nonviolatedblocksrhs;
1075 int* nonviolatedblockslhs;
1076 SCIP_Real sumviols = 0.0;
1077 int v;
1078
1079 if( linking->hasrhs )
1080 {
1081 SCIP_CALL( SCIPallocBufferArray(scip, &nonviolatedblocksrhs, linking->nblocks) );
1082 }
1083 if( linking->haslhs )
1084 {
1085 SCIP_CALL( SCIPallocBufferArray(scip, &nonviolatedblockslhs, linking->nblocks) );
1086 }
1087
1088 /* get violated blocks and calculate shift */
1089 for( v = 0; v < linking->nblocks; v++ )
1090 {
1091 SCIP* subscip;
1092 SCIP_SOL* subsol;
1093 SCIP_Real slackval;
1094
1095 subscip = blockproblem[linking->blocknumbers[v]]->blockscip;
1096 subsol = SCIPgetBestSol(subscip);
1097
1098 /* if we have ranged constraints, the slack variables of the rhs are in front;
1099 * get slack variable of block; save violated blocks
1100 */
1101 if( linking->hasrhs )
1102 {
1103 slackval = SCIPgetSolVal(subscip, subsol, linking->slacks[v * linking->nslacksperblock]);
1104
1105 /* block is violated */
1106 if( SCIPisPositive(scip, slackval) )
1107 {
1108 (*nviolatedblocksrhs)++;
1109
1110 (*shift)[v] += slackval;
1111 sumviols += slackval;
1112 }
1113 else
1114 {
1115 nonviolatedblocksrhs[v - *nviolatedblocksrhs] = v; /*lint !e644*/
1116 }
1117 }
1118 if( linking->haslhs )
1119 {
1120 slackval = SCIPgetSolVal(subscip, subsol, linking->slacks[(v * linking->nslacksperblock) + linking->nslacksperblock - 1]);
1121
1122 /* block is violated */
1123 if( SCIPisPositive(scip, slackval) )
1124 {
1125 (*nviolatedblockslhs)++;
1126
1127 (*shift)[v] -= slackval;
1128 sumviols -= slackval;
1129 }
1130 else
1131 {
1132 nonviolatedblockslhs[v - *nviolatedblockslhs] = v; /*lint !e644*/
1133 }
1134 }
1135 }
1136
1137 /* linking constraint is in no block violated or always violated -> do not update partition */
1138 if( *nviolatedblocksrhs + *nviolatedblockslhs == 0 ||
1139 linking->nblocks == *nviolatedblocksrhs || linking->nblocks == *nviolatedblockslhs )
1140 {
1141 *update = FALSE;
1142 /* free memory */
1143 if( linking->haslhs )
1144 SCIPfreeBufferArray(scip, &nonviolatedblockslhs);
1145 if( linking->hasrhs )
1146 SCIPfreeBufferArray(scip, &nonviolatedblocksrhs);
1147 return SCIP_OKAY;
1148 }
1149
1150 /* set values of non violated blocks */
1151 if( SCIPisPositive(scip, sumviols) )
1152 {
1153 /* rhs of original linking constraint is violated */
1154 SCIP_Real residual = sumviols;
1155 SCIP_Real part;
1156 SCIP_Real shift_tmp;
1157
1158 assert(linking->hasrhs);
1159 assert(*nviolatedblocksrhs != 0);
1160
1161 /* substract from each non violated block the same amount with respect to minimal/maximal activity,
1162 * so that the shift is zero in sum
1163 */
1164 for( v = 0; v < linking->nblocks - *nviolatedblocksrhs; v++ )
1165 {
1166 /* coverity[uninit_use] */
1167 part = linking->currentrhs[nonviolatedblocksrhs[v]] - residual/(linking->nblocks - *nviolatedblocksrhs - v);
1168 part = MIN(MAX(part, linking->minactivity[nonviolatedblocksrhs[v]]), linking->maxactivity[nonviolatedblocksrhs[v]]);
1169 shift_tmp = part - linking->currentrhs[nonviolatedblocksrhs[v]];
1170 residual += shift_tmp;
1171 (*shift)[nonviolatedblocksrhs[v]] += shift_tmp;
1172 }
1173 if( !SCIPisZero(scip, residual) )
1174 {
1175 /* assign residual to ... */
1176 if( linking->nblocks - *nviolatedblocksrhs == 1 )
1177 (*shift)[nonviolatedblocksrhs[0] == 0 ? 1 : 0] -= residual; /* first violated block */
1178 else
1179 (*shift)[nonviolatedblocksrhs[0]] -= residual; /* first nonviolated block */
1180 }
1181 }
1182 if( SCIPisNegative(scip, sumviols) )
1183 {
1184 /* lhs of original linking constraint is violated */
1185 SCIP_Real residual = sumviols;
1186 SCIP_Real part;
1187 SCIP_Real shift_tmp;
1188
1189 assert(linking->haslhs);
1190 assert(*nviolatedblockslhs != 0);
1191
1192 /* add to each non violated block the same amount with respect to minimal/maximal activity,
1193 * so that the shift is zero in sum
1194 */
1195 for( v = 0; v < linking->nblocks - *nviolatedblockslhs; v++ )
1196 {
1197 /* coverity[uninit_use] */
1198 part = linking->currentlhs[nonviolatedblockslhs[v]] - residual/(linking->nblocks - *nviolatedblockslhs - v);
1199 part = MIN(MAX(part, linking->minactivity[nonviolatedblockslhs[v]]), linking->maxactivity[nonviolatedblockslhs[v]]);
1200 shift_tmp = part - linking->currentlhs[nonviolatedblockslhs[v]];
1201 residual += shift_tmp;
1202 (*shift)[nonviolatedblockslhs[v]] += shift_tmp;
1203 }
1204 if( !SCIPisZero(scip, residual) )
1205 {
1206 /* assign residual to ... */
1207 if( linking->nblocks - *nviolatedblockslhs == 1 )
1208 (*shift)[nonviolatedblockslhs[0] == 0 ? 1 : 0] -= residual; /* first violated block */
1209 else
1210 (*shift)[nonviolatedblockslhs[0]] -= residual; /* first nonviolated block */
1211 }
1212 }
1213
1214 *update = TRUE;
1215
1216 /* free memory */
1217 if( linking->haslhs )
1218 SCIPfreeBufferArray(scip, &nonviolatedblockslhs);
1219 if( linking->hasrhs )
1220 SCIPfreeBufferArray(scip, &nonviolatedblocksrhs);
1221
1222 return SCIP_OKAY;
1223}
1224
1225/** update partition */
1226static
1228 SCIP* scip, /**< SCIP data structure of main scip */
1229 LINKING** linkings, /**< linking data structure */
1230 BLOCKPROBLEM** blockproblem, /**< array of blockproblem data structures */
1231 int** nviolatedblocksrhs, /**< pointer to store number of blocks which violate rhs */
1232 int** nviolatedblockslhs, /**< pointer to store number of blocks which violate lhs */
1233 int nlinking, /**< number of linking constraints */
1234 int nblocks, /**< number of blocks */
1235 int iteration, /**< number of iteration */
1236 SCIP_Bool* oneupdate /**< is at least partition of one constraint updated? */
1237 )
1238{
1239 SCIP_Real* shift; /* direction vector */
1240 int v;
1241 int c;
1242 SCIP_Bool update; /* is partition of current constraint updated? */
1243
1244 assert(scip != NULL);
1245 assert(linkings != NULL);
1246 assert(blockproblem != NULL);
1247 assert(iteration >= 0);
1248 assert(!*oneupdate);
1249
1250 SCIP_CALL( SCIPallocBufferArray(scip, &shift, nblocks) ); /* allocate memory only once */
1251
1252 for( c = 0; c < nlinking; c++ )
1253 {
1254 LINKING* linking; /* one linking data structure */
1255
1256 linking = linkings[c];
1257 (*nviolatedblocksrhs)[c] = 0;
1258 (*nviolatedblockslhs)[c] = 0;
1259 update = TRUE;
1260 BMSclearMemoryArray(shift, linking->nblocks);
1261 assert(nblocks >= linking->nblocks);
1262
1263 SCIP_CALL( calculateShift(scip, blockproblem, linking, &shift, &(*nviolatedblocksrhs)[c], &(*nviolatedblockslhs)[c], &update) );
1264
1265 if( !update )
1266 continue;
1267
1268 *oneupdate = TRUE;
1269
1270#ifdef SCIP_DEBUG
1271 SCIP_Real sum = 0.0;
1272 /* check sum of shift; must be zero */
1273 for( v = 0; v < linking->nblocks; v++ )
1274 sum += shift[v];
1275 assert(SCIPisFeasZero(scip, sum));
1276#endif
1277
1278 /* add shift to both sides */
1279 for( v = 0; v < linking->nblocks; v++)
1280 {
1281 if( linking->hasrhs )
1282 linking->currentrhs[v] += shift[v];
1283
1284 if( linking->haslhs )
1285 linking->currentlhs[v] += shift[v];
1286 }
1287
1288 SCIP_CALL( roundPartition(scip, linking, blockproblem, ((linking->hasrhs && ((*nviolatedblocksrhs)[c] != 0)) || !linking->haslhs)) );
1289
1290 /* set sides in blockproblems to new partition */
1291 for( v = 0; v < linking->nblocks; v++ )
1292 {
1293 SCIP* subscip;
1294 subscip = blockproblem[linking->blocknumbers[v]]->blockscip;
1295
1296 if( linking->hasrhs )
1297 {
1298 SCIP_CALL( SCIPchgRhsLinear(subscip, linking->blockconss[v], linking->currentrhs[v]) );
1299 }
1300 if( linking->haslhs )
1301 {
1302 SCIP_CALL( SCIPchgLhsLinear(subscip, linking->blockconss[v], linking->currentlhs[v]) );
1303 }
1304 }
1305 }
1306
1307 /* free memory */
1308 SCIPfreeBufferArray(scip, &shift);
1309
1310 return SCIP_OKAY;
1311}
1312
1313/** update penalty parameters lambda
1314 *
1315 * if a linking constraint is violated two times in succession, the corresponding penalty parameter is increased in each block
1316 */
1317static
1319 SCIP* scip, /**< SCIP data structure */
1320 SCIP_HEURDATA* heurdata, /**< heuristic data */
1321 LINKING** linkings, /**< array of linking data structures */
1322 BLOCKPROBLEM** blockproblem, /**< array of blockproblem data structures */
1323 int* nviolatedblocksrhs, /**< number of blocks which violate rhs */
1324 int* nviolatedblockslhs, /**< number of blocks which violate lhs */
1325 int nlinking /**< number of linking constraints */
1326 )
1327{
1328 SCIP_VAR* slackvar;
1329 SCIP_Real old_obj;
1330 SCIP_Real new_obj;
1331 int c;
1332 int b;
1333
1334 assert(scip != NULL);
1335 assert(linkings != NULL);
1336 assert(blockproblem != NULL);
1337
1338 for( c = 0; c < nlinking; c++ )
1339 {
1340 assert(nviolatedblocksrhs[c] >= 0);
1341 assert(nviolatedblockslhs[c] >= 0);
1342
1343 /* skip constraint if it is not violated */
1344 if( nviolatedblocksrhs[c] + nviolatedblockslhs[c] == 0 )
1345 {
1346 linkings[c]->lastviolations = 0; /* reset flag */
1347 continue;
1348 }
1349
1350 /* add number of violated blocks multiplied with parameter "penalty" to lambda (initial value is 1) */
1351 for( b = 0; b < linkings[c]->nblocks; b++ )
1352 {
1353 SCIP* subscip;
1354 subscip = blockproblem[linkings[c]->blocknumbers[b]]->blockscip;
1355 assert(subscip != NULL);
1356
1357 if( linkings[c]->hasrhs && (nviolatedblocksrhs[c] >= 1) && (linkings[c]->lastviolations >= 1) )
1358 {
1359 slackvar = linkings[c]->slacks[b * linkings[c]->nslacksperblock];
1360 old_obj = SCIPvarGetObj(slackvar);
1361 new_obj = old_obj + heurdata->penalty * nviolatedblocksrhs[c];
1362
1363 SCIP_CALL( SCIPchgVarObj(subscip, slackvar, new_obj) );
1364 }
1365 if( linkings[c]->haslhs && (nviolatedblockslhs[c] >= 1) && (linkings[c]->lastviolations >= 1) )
1366 {
1367 slackvar = linkings[c]->slacks[b * linkings[c]->nslacksperblock + linkings[c]->nslacksperblock - 1];
1368 old_obj = SCIPvarGetObj(slackvar);
1369 new_obj = old_obj + heurdata->penalty * nviolatedblockslhs[c];
1370
1371 SCIP_CALL( SCIPchgVarObj(subscip, slackvar, new_obj) );
1372 }
1373 }
1374
1375 /* update number of violations in the last iterations */
1376 linkings[c]->lastviolations += 1;
1377 }
1378
1379 return SCIP_OKAY;
1380}
1381
1382/** computes feasible solution from last stored solution for each block and adds it to the solution storage */
1383static
1385 LINKING** linkings, /**< array of linking data structures */
1386 BLOCKPROBLEM** blockproblem, /**< array of blockproblem data structures */
1387 int nblocks /**< number of blocks */
1388 )
1389{
1390 SCIP_SOL** sols;
1391 SCIP_SOL* sol; /* solution of block that will be repaired */
1392 SCIP_SOL* newsol;
1393 SCIP_VAR** blockvars;
1394 SCIP_Real* blockvals;
1395 int nsols;
1396 int nvars;
1397 int b;
1398 int c;
1399 int i;
1400 SCIP_Bool success;
1401
1402 assert(linkings != NULL);
1403 assert(blockproblem != NULL);
1404
1405 for( b = 0; b < nblocks; b++ )
1406 {
1407 SCIP* subscip;
1408
1409 subscip = blockproblem[b]->blockscip;
1410 nsols = SCIPgetNSols(subscip);
1411
1412 /* no solution in solution candidate storage found */
1413 if( nsols == 0 )
1414 return SCIP_OKAY;
1415
1416 /* take last solution */
1417 sols = SCIPgetSols(subscip);
1418 sol = sols[nsols - 1];
1419
1420 /* copy the solution */
1421 nvars = SCIPgetNVars(subscip);
1422 blockvars = SCIPgetVars(subscip);
1423 SCIP_CALL( SCIPallocBufferArray(subscip, &blockvals, nvars) );
1424 SCIP_CALL( SCIPgetSolVals(subscip, sol, nvars, blockvars, blockvals) );
1425 SCIP_CALL( SCIPcreateOrigSol(subscip, &newsol, NULL) );
1426 SCIP_CALL( SCIPsetSolVals(subscip, newsol, nvars, blockvars, blockvals) );
1427
1428 /* correct each coupling constraint:
1429 * lhs <= orig_var - z_r + z_l <= rhs
1430 * adapt slack variables so that constraint is feasible
1431 */
1432 for( c = 0; c < blockproblem[b]->nlinking; c++ )
1433 {
1434 LINKING* linking; /* linking data structure of this constraint */
1435 SCIP_VAR* rvar; /* slack variable z_r */
1436 SCIP_VAR* lvar; /* slack variable z_l */
1437 SCIP_Real rval; /* value of slack variable z_r */
1438 SCIP_Real lval; /* value of slack variable z_l */
1439 SCIP_Real activitycons; /* activity of constraint*/
1440 SCIP_Real activity; /* activity of constraint without slack variables */
1441 SCIP_Real rhs; /* current right hand side */
1442 SCIP_Real lhs; /* current left hand side */
1443
1444 linking = linkings[blockproblem[b]->linkingindices[c]];
1445 rhs = SCIPgetRhsLinear(subscip, blockproblem[b]->linkingconss[c]);
1446 lhs = SCIPgetLhsLinear(subscip, blockproblem[b]->linkingconss[c]);
1447 assert(SCIPisGE(subscip, rhs, lhs));
1448
1449 activitycons = SCIPgetActivityLinear(subscip, blockproblem[b]->linkingconss[c], sol);
1450
1451 /* get slack variables and subtract their value from the activity;
1452 * calculate and set values of slack variables
1453 */
1454 for( i = 0; i < linking->nblocks; i++ )
1455 {
1456 if( linking->blocknumbers[i] == b )
1457 {
1458 if( linking->hasrhs && linking->haslhs )
1459 {
1460 rvar = linking->slacks[2 * i];
1461 lvar = linking->slacks[2 * i + 1];
1462 rval = SCIPgetSolVal(subscip, sol, rvar);
1463 lval = SCIPgetSolVal(subscip, sol, lvar);
1464 activity = activitycons + rval - lval;
1465 SCIP_CALL( SCIPsetSolVal(subscip, newsol, rvar, MAX(0.0, activity - rhs)) );
1466 SCIP_CALL( SCIPsetSolVal(subscip, newsol, lvar, MAX(0.0, lhs - activity)) );
1467 }
1468 else if( linking->hasrhs )
1469 {
1470 rvar = linking->slacks[i];
1471 rval = SCIPgetSolVal(subscip, sol, rvar);
1472 activity = activitycons + rval;
1473 SCIP_CALL( SCIPsetSolVal(subscip, newsol, rvar, MAX(0.0, activity - rhs)) );
1474 }
1475 else /* linking->haslhs */
1476 {
1477 assert(linking->haslhs);
1478 lvar = linking->slacks[i];
1479 lval = SCIPgetSolVal(subscip, sol, lvar);
1480 activity = activitycons - lval;
1481 SCIP_CALL( SCIPsetSolVal(subscip, newsol, lvar, MAX(0.0, lhs - activity)) );
1482 }
1483 break;
1484 }
1485 }
1486 }
1487
1488 SCIPdebugMsg(subscip, "Try adding solution with objective value %.2f\n", SCIPgetSolOrigObj(subscip, newsol));
1489 SCIP_CALL( SCIPaddSolFree(subscip, &newsol, &success) );
1490
1491 if( !success )
1492 SCIPdebugMsg(subscip, "Correcting solution failed\n"); /* maybe not better than old solutions */
1493 else
1494 SCIPdebugMsg(subscip, "Correcting solution successful\n");
1495
1496 SCIPfreeBufferArray(subscip, &blockvals);
1497 }
1498
1499 return SCIP_OKAY;
1500}
1501
1502/** reoptimizes the heuristic solution with original objective function */
1503static
1505 SCIP* scip, /**< SCIP data structure */
1506 SCIP_HEUR* heur, /**< pointer to heuristic */
1507 SCIP_SOL* sol, /**< heuristic solution */
1508 BLOCKPROBLEM** blockproblem, /**< array of blockproblem data structures */
1509 int nblocks, /**< number of blockproblems */
1510 SCIP_Bool limits, /**< should strict limits be set? */
1511 SCIP_SOL** newsol, /**< pointer to store improved solution */
1512 SCIP_Bool* success /**< pointer to store whether reoptimization was successful */
1513 )
1514{
1515 SCIP_Real time;
1516 SCIP_Real timesubscip;
1517 SCIP_Bool check;
1518 int b;
1519 int v;
1520
1521 assert(scip != NULL);
1522 assert(heur != NULL);
1523 assert(sol != NULL);
1524 assert(blockproblem != NULL);
1525
1526 *success = FALSE;
1527 check = FALSE;
1528
1529 /* get used time */
1530 timesubscip = SCIPgetTotalTime(blockproblem[0]->blockscip);
1531
1532 /* for each blockproblem:
1533 * - change back to original objective function
1534 * - fix slack variables to zero
1535 * - set limits and solve problem
1536 */
1537 for( b = 0; b < nblocks; b++ )
1538 {
1539 SCIP* subscip;
1540 SCIP_VAR** blockvars;
1541 SCIP_Real infvalue;
1542 int nvars;
1543 int nsols;
1544
1545 subscip = blockproblem[b]->blockscip;
1546 blockvars = SCIPgetOrigVars(subscip);
1547 nvars = SCIPgetNOrigVars(subscip);
1548 nsols = 0;
1549
1550 /* in order to change objective function */
1551 SCIP_CALL( SCIPfreeTransform(subscip) );
1552
1553 /* change back to original objective function */
1554 for( v = 0; v < blockproblem[b]->nblockvars; v++ )
1555 {
1556 SCIP_CALL( SCIPchgVarObj(subscip, blockvars[v], blockproblem[b]->origobj[v]) );
1557 }
1558
1559 /* fix slack variables to zero */
1560 for( v = blockproblem[b]->nblockvars; v < nvars; v++ )
1561 {
1562 SCIP_CALL( SCIPchgVarUb(subscip, blockvars[v], 0.0) );
1563 SCIP_CALL( SCIPchgVarLb(subscip, blockvars[v], 0.0) );
1564 }
1565
1566 /* do not abort subproblem on CTRL-C */
1567 SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
1568
1569 /* forbid recursive call of heuristics and separators solving sub-SCIPs */
1570 SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
1571
1572#ifdef SCIP_DEBUG
1573 /* for debugging, enable full output */
1574 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
1575 SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
1576#else
1577 /* disable statistic timing inside sub SCIP and output to console */
1578 SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
1579 SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
1580#endif
1581
1582 /* disable cutting plane separation */
1584
1585 /* disable expensive presolving */
1587
1588 /* disable expensive techniques */
1589 SCIP_CALL( SCIPsetIntParam(subscip, "misc/usesymmetry", 0) );
1590
1591 /* speed up sub-SCIP by not checking dual LP feasibility */
1592 SCIP_CALL( SCIPsetBoolParam(subscip, "lp/checkdualfeas", FALSE) );
1593
1594 /* copy value for infinity */
1595 SCIP_CALL( SCIPgetRealParam(scip, "numerics/infinity", &infvalue) );
1596 SCIP_CALL( SCIPsetRealParam(subscip, "numerics/infinity", infvalue) );
1597
1598 /* set limits; do not use more time in each subproblem than the heuristic has already used for first solution */
1599 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
1600 if( limits )
1601 {
1602 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", 1LL) );
1603 SCIP_CALL( SCIPgetRealParam(subscip, "limits/time", &time) );
1604 if( timesubscip < time - 1.0 )
1605 {
1606 SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timesubscip + 1.0) );
1607 }
1608 SCIP_CALL( SCIPtransformProb(subscip) );
1609 nsols = SCIPgetNSols(subscip);
1610 /* one improving solution */
1611 SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", nsols + 1) );
1612 }
1613 else
1614 {
1615 /* only 50% of remaining time */
1616 SCIP_CALL( SCIPgetRealParam(subscip, "limits/time", &time) );
1617 SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", time * 0.5) );
1618 /* set big node limits */
1619 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", 1000LL) );
1620 SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", 100LL) );
1621 }
1622
1623 /* reoptimize problem */
1624 SCIP_CALL_ABORT( SCIPsolve(subscip) );
1625
1626 if( SCIPgetNSols(subscip) == 0 )
1627 {
1628 /* we found no solution */
1629 return SCIP_OKAY;
1630 }
1631 else if( SCIPgetStatus(subscip) == SCIP_STATUS_BESTSOLLIMIT ||
1632 SCIPgetStatus(subscip) == SCIP_STATUS_OPTIMAL ||
1633 SCIPgetNSols(subscip) > nsols )
1634 {
1635 check = TRUE;
1636 }
1637 }
1638
1639 if( !check )
1640 {
1641 /* we have no better solution */
1642 return SCIP_OKAY;
1643 }
1644
1645 /* create sol of main scip */
1646 SCIP_CALL( SCIPcreateSol(scip, newsol, heur) );
1647
1648 /* copy solution to main scip */
1649 for( b = 0; b < nblocks; b++ )
1650 {
1651 SCIP_SOL* blocksol;
1652 SCIP_VAR** blockvars;
1653 SCIP_Real* blocksolvals;
1654 int nblockvars;
1655
1656 /* get solution of block variables (without slack variables) */
1657 blocksol = SCIPgetBestSol(blockproblem[b]->blockscip);
1658 blockvars = SCIPgetOrigVars(blockproblem[b]->blockscip);
1659 nblockvars = blockproblem[b]->nblockvars;
1660
1661 SCIP_CALL( SCIPallocBufferArray(scip, &blocksolvals, nblockvars) );
1662 SCIP_CALL( SCIPgetSolVals(blockproblem[b]->blockscip, blocksol, nblockvars, blockvars, blocksolvals) );
1663
1664 for( v = 0; v < nblockvars; v++ )
1665 {
1666 SCIP_VAR* origvar;
1667
1668 origvar = SCIPfindVar(scip, SCIPvarGetName(blockvars[v]));
1669 SCIP_CALL( SCIPsetSolVal(scip, *newsol, origvar, blocksolvals[v]) );
1670 }
1671
1672 SCIPfreeBufferArray(scip, &blocksolvals);
1673 }
1674
1675 *success = TRUE;
1676
1677 return SCIP_OKAY;
1678}
1679
1680
1681/* ---------------- Callback methods of event handler ---------------- */
1682
1683/* exec the event handler
1684 *
1685 * interrupt solution process of sub-SCIP if dual bound is greater than zero and a solution is available
1686 */
1687static
1689{
1690 assert(eventhdlr != NULL);
1691 assert(eventdata != NULL);
1692 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
1693 assert(event != NULL);
1695
1696 SCIPdebugMsg(scip, "dual bound: %.2f\n", SCIPgetDualbound(scip));
1697
1699 {
1700 SCIPdebugMsg(scip, "DPS: interrupt subscip\n");
1702 }
1703
1704 return SCIP_OKAY;
1705}
1706
1707
1708/*
1709 * Callback methods of primal heuristic
1710 */
1711
1712/** copy method for primal heuristic plugins (called when SCIP copies plugins) */
1713static
1715{ /*lint --e{715}*/
1716 assert(scip != NULL);
1717 assert(heur != NULL);
1718 assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1719
1720 /* call inclusion method of primal heuristic */
1722
1723 return SCIP_OKAY;
1724}
1725
1726/** destructor of primal heuristic to free user data (called when SCIP is exiting) */
1727static
1729{ /*lint --e{715}*/
1730 SCIP_HEURDATA* heurdata;
1731
1732 assert(heur != NULL);
1733 assert(scip != NULL);
1734
1735 /* free heuristic data */
1736 heurdata = SCIPheurGetData(heur);
1737 assert(heurdata != NULL);
1738
1739 SCIPfreeBlockMemory(scip, &heurdata);
1740 SCIPheurSetData(heur, NULL);
1741
1742 return SCIP_OKAY;
1743}
1744
1745/** execution method of primal heuristic */
1746static
1748{ /*lint --e{715}*/
1749 SCIP_DECOMP** alldecomps;
1750 SCIP_DECOMP* decomp;
1751 SCIP_DECOMP* assigneddecomp;
1752 SCIP_VAR** vars;
1753 SCIP_CONS** conss;
1754 SCIP_VAR** sortedvars;
1755 SCIP_CONS** sortedconss;
1756 SCIP_HEURDATA* heurdata;
1757 BLOCKPROBLEM** blockproblem;
1758 LINKING** linkings;
1759 int* sortedvarlabels;
1760 int* sortedconslabels;
1761 SCIP_EVENTHDLR* eventhdlr; /* event handler */
1762 SCIP_Real memory; /* in MB */
1763 SCIP_Real timelimit;
1764 SCIP_Real allslacksval;
1765 SCIP_Real blocksolval;
1766 SCIP_STATUS status;
1767 SCIP_Bool avoidmemout;
1768 SCIP_Bool disablemeasures;
1769 int maxgraphedge;
1770 int ndecomps;
1771 int nvars;
1772 int nconss;
1773 int nblocks;
1774 SCIP_Bool success;
1775 int b;
1776 int c;
1777 int k;
1778
1779 assert( heur != NULL );
1780 assert( scip != NULL );
1781 assert( result != NULL );
1782
1783 heurdata = SCIPheurGetData(heur);
1784 assert(heurdata != NULL);
1785
1786 assigneddecomp = NULL;
1787 blockproblem = NULL;
1788 linkings = NULL;
1789 eventhdlr = NULL;
1790
1791 *result = SCIP_DIDNOTRUN;
1792
1793 if( !((heurtiming & SCIP_HEURTIMING_BEFORENODE) && (heurdata->timing == 0 || heurdata->timing == 2))
1794 && !((heurtiming & SCIP_HEURTIMING_AFTERNODE) && (heurdata->timing == 1 || heurdata->timing == 2)) )
1795 {
1796 return SCIP_OKAY;
1797 }
1798
1799 /* call heuristic only once */
1800 if( SCIPheurGetNCalls(heur) > 0 )
1801 return SCIP_OKAY;
1802
1803 /* -------------------------------------------------------------------- */
1804 SCIPdebugMsg(scip, "initialize dps heuristic\n");
1805
1806 /* take the first transformed decomposition */
1807 SCIPgetDecomps(scip, &alldecomps, &ndecomps, FALSE);
1808 if( ndecomps == 0 )
1809 return SCIP_OKAY;
1810
1811 decomp = alldecomps[0];
1812 assert(decomp != NULL);
1813 SCIPdebugMsg(scip, "First transformed decomposition is selected\n");
1814
1815 nblocks = SCIPdecompGetNBlocks(decomp);
1816 nconss = SCIPgetNConss(scip);
1817 nvars = SCIPgetNVars(scip);
1818
1819 /* if problem has no constraints, no variables or less than two blocks, return */
1820 if( nconss == 0 || nvars == 0 || nblocks <= 1 )
1821 {
1822 SCIPdebugMsg(scip, "problem has no constraints, no variables or less than two blocks\n");
1823 return SCIP_OKAY;
1824 }
1825
1826 /* estimate required memory for all blocks and terminate if not enough memory is available */
1827 SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memory) );
1828 SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) );
1829 if( avoidmemout && (((SCIPgetMemUsed(scip) + SCIPgetMemExternEstim(scip))/1048576.0) * (nblocks/4.0 + 2) >= memory) )
1830 {
1831 SCIPdebugMsg(scip, "The estimated memory usage for %d blocks is too large.\n", nblocks);
1832 return SCIP_OKAY;
1833 }
1834
1835 /* we do not need the block decomposition graph and expensive measures of the decomposition statistics */
1836 SCIP_CALL( SCIPgetIntParam(scip, "decomposition/maxgraphedge", &maxgraphedge) );
1837 if( !SCIPisParamFixed(scip, "decomposition/maxgraphedge") )
1838 {
1839 SCIP_CALL( SCIPsetIntParam(scip, "decomposition/maxgraphedge", 0) );
1840 }
1841 SCIP_CALL( SCIPgetBoolParam(scip, "decomposition/disablemeasures", &disablemeasures) );
1842 if( !SCIPisParamFixed(scip, "decomposition/disablemeasures") )
1843 {
1844 SCIP_CALL( SCIPsetBoolParam(scip, "decomposition/disablemeasures", TRUE) );
1845 }
1846
1847 vars = SCIPgetVars(scip);
1848 conss = SCIPgetConss(scip);
1849 SCIP_CALL( SCIPduplicateBufferArray(scip, &sortedvars, vars, nvars) );
1850 SCIP_CALL( SCIPduplicateBufferArray(scip, &sortedconss, conss, nconss) );
1851 SCIP_CALL( SCIPallocBufferArray(scip, &sortedvarlabels, nvars) );
1852 SCIP_CALL( SCIPallocBufferArray(scip, &sortedconslabels, nconss) );
1853
1854 /* get labels and sort in increasing order */
1855 SCIPdecompGetVarsLabels(decomp, sortedvars, sortedvarlabels, nvars);
1856 SCIPdecompGetConsLabels(decomp, sortedconss, sortedconslabels, nconss);
1857 SCIPsortIntPtr(sortedvarlabels, (void**)sortedvars, nvars);
1858 SCIPsortIntPtr(sortedconslabels, (void**)sortedconss, nconss);
1859
1860 if( sortedvarlabels[0] == SCIP_DECOMP_LINKVAR )
1861 {
1862 /* create new decomposition; don't change the decompositions in the decompstore */
1864
1865 SCIP_CALL( assignLinking(scip, assigneddecomp, sortedvars, sortedconss, sortedvarlabels, sortedconslabels, nvars, nconss, SCIPdecompGetNBorderVars(decomp)) );
1866 assert(SCIPdecompGetNBlocks(decomp) >= SCIPdecompGetNBlocks(assigneddecomp));
1867 decomp = assigneddecomp;
1868
1869 /* number of blocks can get smaller */
1870 nblocks = SCIPdecompGetNBlocks(decomp);
1871 }
1872 else
1873 {
1874 /* The decomposition statistics were computed during transformation of the decomposition store.
1875 * Since propagators can have changed the number of constraints/variables,
1876 * the statistics are no longer up-to-date and have to be recomputed.
1877 */
1879 nblocks = SCIPdecompGetNBlocks(decomp);
1880 }
1881
1882 /* reset parameters */
1883 SCIP_CALL( SCIPsetIntParam(scip, "decomposition/maxgraphedge", maxgraphedge) );
1884 SCIP_CALL( SCIPsetBoolParam(scip, "decomposition/disablemeasures", disablemeasures) );
1885
1886#ifdef SCIP_DEBUG
1887 char buffer[SCIP_MAXSTRLEN];
1888 SCIPdebugMsg(scip, "DPS used decomposition:\n%s\n", SCIPdecompPrintStats(decomp, buffer));
1889#endif
1890
1891 /* check properties of used decomposition */
1892 if( heurdata->maxlinkscore != 1.0 )
1893 {
1894 SCIP_Real linkscore;
1895 int nlinkconss;
1896
1897 nlinkconss = SCIPdecompGetNBorderConss(decomp);
1898
1899 linkscore = (SCIP_Real)nlinkconss / (SCIP_Real)nconss;
1900
1901 if( linkscore > heurdata->maxlinkscore )
1902 {
1903 SCIPdebugMsg(scip, "decomposition has not the required properties\n");
1904 goto TERMINATE;
1905 }
1906 }
1907
1908 if( sortedvarlabels[0] == SCIP_DECOMP_LINKVAR ||
1909 sortedconslabels[0] != SCIP_DECOMP_LINKCONS ||
1910 nblocks <= 1 )
1911 {
1912 SCIPdebugMsg(scip, "Problem has linking variables or no linking constraints or less than two blocks\n");
1913 goto TERMINATE;
1914 }
1915
1916 /* initialize heurdata */
1917 heurdata->linkingconss = sortedconss;
1918 heurdata->nlinking = SCIPdecompGetNBorderConss(decomp);
1919 heurdata->nblocks = nblocks;
1920
1921 /* allocate memory for blockproblems and initialize partially */
1922 SCIP_CALL( SCIPallocBufferArray(scip, &blockproblem, nblocks) );
1923 for( b = 0; b < nblocks; b++ )
1924 {
1925 SCIP_CALL( SCIPallocBlockMemory(scip, &(blockproblem[b])) ); /*lint !e866*/
1926 SCIP_CALL( createSubscip(scip, &blockproblem[b]->blockscip) );
1927
1928 SCIP_CALL( SCIPallocBufferArray(scip, &blockproblem[b]->linkingconss, heurdata->nlinking) );
1929 SCIP_CALL( SCIPallocBufferArray(scip, &blockproblem[b]->linkingindices, heurdata->nlinking) );
1930 SCIP_CALL( SCIPallocBufferArray(scip, &blockproblem[b]->slackvars, heurdata->nlinking * 2) ); /* maximum two slacks per linking constraint */
1931 SCIP_CALL( SCIPallocBufferArray(scip, &blockproblem[b]->origobj, nvars) );
1932 blockproblem[b]->nblockvars = 0;
1933 blockproblem[b]->nlinking = 0;
1934 blockproblem[b]->nslackvars = 0;
1935 }
1936
1937 /* allocate memory for linkings and initialize partially */
1938 SCIP_CALL( SCIPallocBufferArray(scip, &linkings, heurdata->nlinking) );
1939 for( c = 0; c < heurdata->nlinking; c++ )
1940 {
1941 SCIP_CALL( SCIPallocBlockMemory(scip, &(linkings[c])) ); /*lint !e866*/
1942 SCIP_CALL( SCIPallocBufferArray(scip, &(linkings[c])->blockconss, heurdata->nblocks) );
1943 SCIP_CALL( SCIPallocBufferArray(scip, &(linkings[c])->slacks, heurdata->nblocks*2) ); /* maximum two slacks per block */
1944 SCIP_CALL( SCIPallocBufferArray(scip, &(linkings[c])->blocknumbers, heurdata->nblocks) );
1945 SCIP_CALL( SCIPallocBufferArray(scip, &(linkings[c])->minactivity, heurdata->nblocks) );
1946 SCIP_CALL( SCIPallocBufferArray(scip, &(linkings[c])->maxactivity, heurdata->nblocks) );
1947
1948 linkings[c]->linkingcons = heurdata->linkingconss[c];
1949 linkings[c]->currentrhs = NULL;
1950 linkings[c]->currentlhs = NULL;
1951 linkings[c]->nblocks = 0;
1952 linkings[c]->nslacks = 0;
1953 linkings[c]->nslacksperblock = 0;
1954 linkings[c]->lastviolations = 0;
1955 linkings[c]->hasrhs = FALSE;
1956 linkings[c]->haslhs = FALSE;
1957 }
1958
1959 SCIP_CALL( createAndSplitProblem(scip, heurdata, decomp, blockproblem, linkings, sortedvars, sortedconss, &success) );
1960 if( !success )
1961 {
1962 SCIPdebugMsg(scip, "Create and split problem failed\n");
1963 goto TERMINATE;
1964 }
1965
1966 /* allocate memory for current partition*/
1967 for( c = 0; c < heurdata->nlinking; c++ )
1968 {
1969 if( linkings[c]->hasrhs )
1970 {
1971 SCIP_CALL( SCIPallocBufferArray(scip, &(linkings[c])->currentrhs, linkings[c]->nblocks ) );
1972 }
1973
1974 if( linkings[c]->haslhs )
1975 {
1976 SCIP_CALL( SCIPallocBufferArray(scip, &(linkings[c])->currentlhs, linkings[c]->nblocks ) );
1977 }
1978 }
1979
1980 /* initialize partition */
1981 SCIP_CALL( initCurrent(scip, linkings, blockproblem, heurtiming, heurdata->nlinking, &success) );
1982 if( !success )
1983 {
1984 SCIPdebugMsg(scip, "Initialization of partition failed\n");
1985 goto TERMINATE;
1986 }
1987
1988 /* ------------------------------------------------------------------------ */
1989 SCIPdebugMsg(scip, "Start heuristik DPS\n");
1990 *result = SCIP_DIDNOTFIND;
1991
1992 for( k = 0; k < heurdata->maxit; k++ )
1993 {
1994 /* do not exceed the timelimit */
1995 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
1996 if( (timelimit - SCIPgetSolvingTime(scip)) <= 0 )
1997 goto TERMINATE;
1998
1999 /* solve the subproblems */
2000 allslacksval = 0.0;
2001 for( b = 0; b < heurdata->nblocks; b++ )
2002 {
2003 SCIP* subscip;
2004 subscip = blockproblem[b]->blockscip;
2005
2006 /* update time and memory limit of subproblem */
2007 SCIP_CALL( SCIPcopyLimits(scip, subscip) );
2008
2009 /* create event handler for LP events */
2010 if( k == 0 )
2011 {
2012 SCIP_CALL( SCIPincludeEventhdlrBasic(subscip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC, eventExecDps, NULL) );
2013 if( eventhdlr == NULL )
2014 {
2015 SCIPerrorMessage("event handler for " HEUR_NAME " heuristic not found.\n");
2016 return SCIP_PLUGINNOTFOUND;
2017 }
2018 }
2019
2020 /* catch LP events of sub-SCIP */
2021 SCIP_CALL( SCIPtransformProb(subscip) );
2022 SCIP_CALL( SCIPcatchEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, NULL) );
2023
2024 SCIPdebugMsg(scip, "Solve blockproblem %d\n", b);
2025 SCIP_CALL_ABORT( SCIPsolve(subscip) );
2026
2027 /* drop LP events of sub-SCIP */
2028 SCIP_CALL( SCIPdropEvent(subscip, SCIP_EVENTTYPE_LPSOLVED, eventhdlr, (SCIP_EVENTDATA*) heurdata, -1) );
2029
2030 /* get status and objective value if available */
2031 status = SCIPgetStatus(subscip);
2032 if( status == SCIP_STATUS_INFEASIBLE )
2033 {
2034 SCIPdebugMsg(scip, "Subproblem is infeasible\n");
2035 goto TERMINATE;
2036 }
2037 else if( status == SCIP_STATUS_UNBOUNDED )
2038 {
2039 SCIPdebugMsg(scip, "Subproblem is unbounded\n");
2040 goto TERMINATE;
2041 }
2042 else if( SCIPgetNSols(subscip) >= 1 )
2043 {
2044 blocksolval = SCIPgetPrimalbound(subscip);
2045
2046 if( status == SCIP_STATUS_TIMELIMIT && !SCIPisZero(scip, blocksolval) )
2047 {
2048 SCIPdebugMsg(scip, "Subproblem reached timelimit without optimal solution\n");
2049 goto TERMINATE;
2050 }
2051 SCIPdebugMsg(scip, "Solution value: %f\n", blocksolval);
2052 allslacksval += blocksolval;
2053 }
2054 else
2055 {
2056 SCIPdebugMsg(scip, "No subproblem solution available\n");
2057 goto TERMINATE;
2058 }
2059 }
2060
2061 /* all slack variables are zero -> we found a feasible solution */
2062 if( SCIPisZero(scip, allslacksval) )
2063 {
2064 SCIP_SOL* newsol;
2065
2066 SCIPdebugMsg(scip, "Feasible solution found after %i iterations\n", k);
2067
2068 /* create new solution */
2069 SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
2070 for( b = 0; b < heurdata->nblocks; b++ )
2071 {
2072 SCIP_SOL* blocksol;
2073 SCIP_VAR** blockvars;
2074 SCIP_Real* blocksolvals;
2075 int nblockvars;
2076
2077 /* get solution of block variables (without slack variables) */
2078 blocksol = SCIPgetBestSol(blockproblem[b]->blockscip);
2079 blockvars = SCIPgetOrigVars(blockproblem[b]->blockscip);
2080 nblockvars = blockproblem[b]->nblockvars;
2081
2082 SCIP_CALL( SCIPallocBufferArray(scip, &blocksolvals, nblockvars) );
2083 SCIP_CALL( SCIPgetSolVals(blockproblem[b]->blockscip, blocksol, nblockvars, blockvars, blocksolvals) );
2084
2085 for( c = 0; c < nblockvars; c++ )
2086 {
2087 SCIP_VAR* origvar;
2088
2089 origvar = SCIPfindVar(scip, SCIPvarGetName(blockvars[c]));
2090 SCIP_CALL( SCIPsetSolVal(scip, newsol, origvar, blocksolvals[c]) );
2091 }
2092
2093 SCIPfreeBufferArray(scip, &blocksolvals);
2094 }
2095
2096 /* if reoptimization is activated, fix partition and reoptimize with original objective function */
2097 if( heurdata->reoptimize )
2098 {
2099 SCIP_SOL* improvedsol = NULL;
2100 SCIP_CALL( reoptimize(scip, heur, newsol, blockproblem, heurdata->nblocks, heurdata->reoptlimits, &improvedsol, &success) );
2101 assert(improvedsol != NULL || success == FALSE);
2102
2103 if( success )
2104 {
2105 SCIP_CALL( SCIPtrySolFree(scip, &improvedsol, TRUE, FALSE, TRUE, TRUE, TRUE, &success) );
2106 if( success )
2107 {
2108 SCIPdebugMsg(scip, "Reoptimizing solution successful\n");
2109 *result = SCIP_FOUNDSOL;
2110 }
2111 }
2112 }
2113
2114 /* if reoptimization is turned off or reoptimization found no solution, try initial solution */
2115 if( *result != SCIP_FOUNDSOL )
2116 {
2117 SCIPdebugMsg(scip, "Solution has value: %.2f\n", SCIPgetSolOrigObj(scip, newsol));
2118 SCIP_CALL( SCIPtrySolFree(scip, &newsol, TRUE, FALSE, TRUE, TRUE, TRUE, &success) );
2119 if( success )
2120 {
2121 SCIPdebugMsg(scip, "Solution copy successful\n");
2122 *result = SCIP_FOUNDSOL;
2123 }
2124 }
2125 else
2126 {
2127 SCIP_CALL( SCIPfreeSol(scip, &newsol) );
2128 }
2129
2130 goto TERMINATE;
2131 }
2132 /* current partition is not feasible:
2133 * - update partition
2134 * - update penalty parameters lambda
2135 * - reuse last solution
2136 */
2137 else
2138 {
2139 int* nviolatedblocksrhs; /* number of blocks which violate rhs for each linking constraint */
2140 int* nviolatedblockslhs; /* number of blocks which violate lhs for each linking constraint */
2141 SCIP_Bool update = FALSE;
2142
2143 SCIP_CALL( SCIPallocBufferArray(scip, &nviolatedblocksrhs, heurdata->nlinking) );
2144 SCIP_CALL( SCIPallocBufferArray(scip, &nviolatedblockslhs, heurdata->nlinking) );
2145 BMSclearMemoryArray(nviolatedblocksrhs, heurdata->nlinking);
2146 BMSclearMemoryArray(nviolatedblockslhs, heurdata->nlinking);
2147
2148 SCIPdebugMsg(scip, "update partition\n");
2149 SCIP_CALL( updatePartition(scip, linkings, blockproblem, &nviolatedblocksrhs, &nviolatedblockslhs,
2150 heurdata->nlinking, nblocks, k, &update) );
2151
2152 /* terminate if partition is not updated */
2153 if( !update )
2154 {
2155 SCIPfreeBufferArray(scip, &nviolatedblockslhs);
2156 SCIPfreeBufferArray(scip, &nviolatedblocksrhs);
2157 goto TERMINATE;
2158 }
2159
2160 /* in order to change objective function */
2161 for( b = 0; b < heurdata->nblocks; b++ )
2162 {
2163 SCIP_CALL( SCIPfreeTransform(blockproblem[b]->blockscip) );
2164 }
2165
2166 SCIPdebugMsg(scip, "update lambda\n");
2167 SCIP_CALL( updateLambda(scip, heurdata, linkings, blockproblem, nviolatedblocksrhs, nviolatedblockslhs, heurdata->nlinking) );
2168
2169 if( heurdata->reuse )
2170 {
2171 /* reuse old solution in each block if available */
2172 SCIP_CALL( reuseSolution(linkings, blockproblem, nblocks) );
2173 }
2174
2175 SCIPfreeBufferArray(scip, &nviolatedblockslhs);
2176 SCIPfreeBufferArray(scip, &nviolatedblocksrhs);
2177 }
2178 }
2179 SCIPdebugMsg(scip, "maximum number of iterations reached\n");
2180
2181 /* ------------------------------------------------------------------------ */
2182 /* free memory */
2183TERMINATE:
2184 if( linkings != NULL )
2185 {
2186 for( c = heurdata->nlinking - 1; c >= 0; c-- )
2187 {
2188 if( linkings[c]->currentlhs != NULL )
2189 SCIPfreeBufferArray(scip, &(linkings[c])->currentlhs);
2190
2191 if( linkings[c]->currentrhs != NULL )
2192 SCIPfreeBufferArray(scip, &(linkings[c])->currentrhs);
2193 }
2194
2195 for( c = heurdata->nlinking - 1; c >= 0; c-- )
2196 {
2197 linkings[c]->linkingcons = NULL;
2198 SCIPfreeBufferArray(scip, &(linkings[c])->maxactivity);
2199 SCIPfreeBufferArray(scip, &(linkings[c])->minactivity);
2200 SCIPfreeBufferArray(scip, &(linkings[c])->blocknumbers);
2201 SCIPfreeBufferArray(scip, &(linkings[c])->slacks);
2202 SCIPfreeBufferArray(scip, &(linkings[c])->blockconss);
2203 SCIPfreeBlockMemory(scip, &(linkings[c])); /*lint !e866*/
2204 }
2205 SCIPfreeBufferArray(scip, &linkings);
2206 }
2207
2208 if( blockproblem != NULL )
2209 {
2210 for( b = nblocks - 1; b >= 0; b-- )
2211 {
2212 SCIPfreeBufferArray(scip, &(blockproblem[b])->origobj);
2213 SCIPfreeBufferArray(scip, &(blockproblem[b])->slackvars);
2214 SCIPfreeBufferArray(scip, &(blockproblem[b])->linkingindices);
2215 SCIPfreeBufferArray(scip, &(blockproblem[b])->linkingconss);
2216 SCIP_CALL( SCIPfree(&blockproblem[b]->blockscip) );
2217 SCIPfreeBlockMemory(scip, &(blockproblem[b])); /*lint !e866*/
2218 }
2219 SCIPfreeBufferArray(scip, &blockproblem);
2220 }
2221
2222 if( assigneddecomp != NULL )
2223 SCIPdecompFree(&assigneddecomp, SCIPblkmem(scip));
2224
2225 if( sortedconslabels != NULL )
2226 SCIPfreeBufferArray(scip, &sortedconslabels);
2227
2228 if( sortedvarlabels != NULL )
2229 SCIPfreeBufferArray(scip, &sortedvarlabels);
2230
2231 if( sortedconss != NULL )
2232 SCIPfreeBufferArray(scip, &sortedconss);
2233
2234 if( sortedvars != NULL )
2235 SCIPfreeBufferArray(scip, &sortedvars);
2236
2237 SCIPdebugMsg(scip, "Leave DPS heuristic\n");
2238
2239 return SCIP_OKAY;
2240}
2241
2242
2243/*
2244 * primal heuristic specific interface methods
2245 */
2246
2247/** creates the dps primal heuristic and includes it in SCIP */
2249 SCIP* scip /**< SCIP data structure */
2250 )
2251{
2252 SCIP_HEURDATA* heurdata;
2253 SCIP_HEUR* heur;
2254
2255 /* create dps primal heuristic data */
2256 SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
2257
2258 heur = NULL;
2259
2260 /* include primal heuristic */
2263 HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecDps, heurdata) );
2264
2265 assert(heur != NULL);
2266
2267 /* set non fundamental callbacks via setter functions */
2268 SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyDps) );
2269 SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeDps) );
2270
2271 /* add dps primal heuristic parameters */
2272 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/maxiterations",
2273 "maximal number of iterations", &heurdata->maxit, FALSE, DEFAULT_MAXIT, 1, INT_MAX, NULL, NULL) );
2274
2275 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/maxlinkscore",
2276 "maximal linking score of used decomposition (equivalent to percentage of linking constraints)",
2277 &heurdata->maxlinkscore, FALSE, 1.0, 0.0, 1.0, NULL, NULL) );
2278
2279 SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/penalty",
2280 "multiplier for absolute increase of penalty parameters (0: no increase)",
2281 &heurdata->penalty, FALSE, DEFAULT_PENALTY, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2282
2283 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/reoptimize",
2284 "should the problem get reoptimized with the original objective function?", &heurdata->reoptimize, FALSE, FALSE, NULL, NULL) );
2285
2286 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/reuse",
2287 "should solutions get reused in subproblems?", &heurdata->reuse, FALSE, FALSE, NULL, NULL) );
2288
2289 SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/reoptlimits",
2290 "should strict limits for reoptimization be set?", &heurdata->reoptlimits, FALSE, TRUE, NULL, NULL) );
2291
2292 SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/timing",
2293 "should the heuristic run before or after the processing of the node? (0: before, 1: after, 2: both)",
2294 &heurdata->timing, FALSE, 0, 0, 2, NULL, NULL) );
2295
2296 return SCIP_OKAY;
2297}
SCIP_VAR ** b
Definition: circlepacking.c:65
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_REAL_MAX
Definition: def.h:174
#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 SCIP_CALL_ABORT(x)
Definition: def.h:353
#define SCIPABORT()
Definition: def.h:346
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_Real SCIPgetActivityLinear(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
SCIP_RETCODE SCIPgetConsCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_CONS *sourcecons, SCIP_CONS **targetcons, SCIP_CONSHDLR *sourceconshdlr, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *name, 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_Bool global, SCIP_Bool *valid)
Definition: scip_copy.c:1591
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3296
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:711
SCIP_RETCODE SCIPcomputeDecompConsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition: scip_dcmp.c:345
void SCIPgetDecomps(SCIP *scip, SCIP_DECOMP ***decomps, int *ndecomps, SCIP_Bool original)
Definition: scip_dcmp.c:263
SCIP_RETCODE SCIPdecompSetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:124
int SCIPdecompGetNBlocks(SCIP_DECOMP *decomp)
Definition: dcmp.c:279
SCIP_RETCODE SCIPdecompSetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:173
SCIP_RETCODE SCIPdecompCreate(SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition: dcmp.c:57
SCIP_RETCODE SCIPdecompGetVarsSize(SCIP_DECOMP *decomp, int *varssize, int nlabels)
Definition: dcmp.c:316
SCIP_RETCODE SCIPcomputeDecompStats(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Bool uselimits)
Definition: scip_dcmp.c:1136
char * SCIPdecompPrintStats(SCIP_DECOMP *decomp, char *strbuf)
Definition: dcmp.c:455
SCIP_RETCODE SCIPdecompGetConssSize(SCIP_DECOMP *decomp, int *consssize, int nlabels)
Definition: dcmp.c:349
void SCIPdecompGetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:198
void SCIPdecompFree(SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem)
Definition: dcmp.c:99
int SCIPdecompGetNBorderVars(SCIP_DECOMP *decomp)
Definition: dcmp.c:379
void SCIPdecompGetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:149
SCIP_Bool SCIPdecompUseBendersLabels(SCIP_DECOMP *decomp)
Definition: dcmp.c:269
int SCIPdecompGetNBorderConss(SCIP_DECOMP *decomp)
Definition: dcmp.c:394
SCIP_Bool SCIPdecompIsOriginal(SCIP_DECOMP *decomp)
Definition: dcmp.c:246
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_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1668
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1067
SCIP_VAR ** SCIPgetOrigVars(SCIP *scip)
Definition: scip_prob.c:2405
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip_prob.c:3088
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2770
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3042
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2432
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
Definition: scip_prob.c:117
SCIP_VAR * SCIPfindVar(SCIP *scip, const char *name)
Definition: scip_prob.c:2685
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
#define SCIPdebugMsg
Definition: scip_message.h:78
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:219
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 SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:904
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:307
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:953
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:269
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:429
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:603
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:979
SCIP_RETCODE SCIPincludeHeurDps(SCIP *scip)
Definition: heur_dps.c:2248
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4197
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2622
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 SCIPconsIsDeleted(SCIP_CONS *cons)
Definition: cons.c:8343
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip_cons.c:2578
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8403
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8275
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8433
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8214
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8463
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8393
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
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1030
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 SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
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_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1579
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip_mem.c:126
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip_mem.c:100
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
#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 SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
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_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
SCIP_RETCODE SCIPaddSolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool *stored)
Definition: scip_sol.c:2855
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2070
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:421
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1254
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1119
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2119
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 SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:222
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition: scip_solve.c:3344
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip_solve.c:3430
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2498
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
SCIP_Real SCIPgetDualbound(SCIP *scip)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
SCIP_Real SCIPgetTotalTime(SCIP *scip)
Definition: scip_timing.c:351
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4676
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4766
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18452
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1527
SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
Definition: var.c:17904
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:194
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_var.c:4513
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
void SCIPsortIntIntReal(int *intarray1, int *intarray2, SCIP_Real *realarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
static SCIP_RETCODE updateLambda(SCIP *scip, SCIP_HEURDATA *heurdata, LINKING **linkings, BLOCKPROBLEM **blockproblem, int *nviolatedblocksrhs, int *nviolatedblockslhs, int nlinking)
Definition: heur_dps.c:1318
static SCIP_DECL_HEURCOPY(heurCopyDps)
Definition: heur_dps.c:1714
static SCIP_RETCODE assignLinking(SCIP *scip, SCIP_DECOMP *newdecomp, SCIP_VAR **vars, SCIP_CONS **conss, int *varlabels, int *conslabels, int nvars, int nconss, int nlinkvars)
Definition: heur_dps.c:143
static SCIP_RETCODE roundPartition(SCIP *scip, LINKING *linking, BLOCKPROBLEM **blockproblem, SCIP_Bool roundbyrhs)
Definition: heur_dps.c:713
#define HEUR_TIMING
Definition: heur_dps.c:69
#define HEUR_FREQOFS
Definition: heur_dps.c:67
static SCIP_RETCODE updatePartition(SCIP *scip, LINKING **linkings, BLOCKPROBLEM **blockproblem, int **nviolatedblocksrhs, int **nviolatedblockslhs, int nlinking, int nblocks, int iteration, SCIP_Bool *oneupdate)
Definition: heur_dps.c:1227
#define HEUR_DESC
Definition: heur_dps.c:63
static SCIP_RETCODE createSubscip(SCIP *scip, SCIP **subscip)
Definition: heur_dps.c:217
#define DEFAULT_MAXIT
Definition: heur_dps.c:72
static SCIP_RETCODE initCurrent(SCIP *scip, LINKING **linkings, BLOCKPROBLEM **blockproblem, SCIP_HEURTIMING heurtiming, int nlinking, SCIP_Bool *success)
Definition: heur_dps.c:874
#define HEUR_DISPCHAR
Definition: heur_dps.c:64
#define HEUR_MAXDEPTH
Definition: heur_dps.c:68
#define HEUR_PRIORITY
Definition: heur_dps.c:65
static SCIP_DECL_EVENTEXEC(eventExecDps)
Definition: heur_dps.c:1688
static SCIP_RETCODE reuseSolution(LINKING **linkings, BLOCKPROBLEM **blockproblem, int nblocks)
Definition: heur_dps.c:1384
#define HEUR_NAME
Definition: heur_dps.c:62
static SCIP_RETCODE createBlockproblem(SCIP *scip, BLOCKPROBLEM *blockproblem, LINKING **linkings, SCIP_CONS **conss, SCIP_VAR **vars, int nconss, int nvars, SCIP_CONS **linkingconss, int nlinking, int blocknumber, SCIP_Bool *success)
Definition: heur_dps.c:349
static SCIP_RETCODE reoptimize(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol, BLOCKPROBLEM **blockproblem, int nblocks, SCIP_Bool limits, SCIP_SOL **newsol, SCIP_Bool *success)
Definition: heur_dps.c:1504
#define DEFAULT_PENALTY
Definition: heur_dps.c:73
#define EVENTHDLR_DESC
Definition: heur_dps.c:77
static SCIP_RETCODE createAndSplitProblem(SCIP *scip, SCIP_HEURDATA *heurdata, SCIP_DECOMP *decomp, BLOCKPROBLEM **blockproblem, LINKING **linkings, SCIP_VAR **vars, SCIP_CONS **conss, SCIP_Bool *success)
Definition: heur_dps.c:660
#define HEUR_FREQ
Definition: heur_dps.c:66
#define HEUR_USESSUBSCIP
Definition: heur_dps.c:70
static SCIP_DECL_HEUREXEC(heurExecDps)
Definition: heur_dps.c:1747
static SCIP_RETCODE calculateShift(SCIP *scip, BLOCKPROBLEM **blockproblem, LINKING *linking, SCIP_Real **shift, int *nviolatedblocksrhs, int *nviolatedblockslhs, SCIP_Bool *update)
Definition: heur_dps.c:1064
#define EVENTHDLR_NAME
Definition: heur_dps.c:76
static SCIP_RETCODE copyToSubscip(SCIP *scip, SCIP *subscip, const char *name, SCIP_VAR **vars, SCIP_CONS **conss, SCIP_HASHMAP *varsmap, SCIP_HASHMAP *conssmap, int nvars, int nconss, SCIP_Bool *success)
Definition: heur_dps.c:270
static SCIP_DECL_HEURFREE(heurFreeDps)
Definition: heur_dps.c:1728
dynamic partition search
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
SCIP_Real SCIPconsGetLhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: misc_linear.c:112
SCIP_RETCODE SCIPgetConsVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int varssize, SCIP_Bool *success)
Definition: misc_linear.c:179
SCIP_Real SCIPconsGetRhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: misc_linear.c:48
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
public methods for decompositions
public methods for primal heuristics
#define SCIPerrorMessage
Definition: pub_message.h:64
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:102
public data structures and miscellaneous methods
public methods for constraint handler plugins and constraints
public methods for decompositions
general public methods
public methods for primal heuristic plugins and divesets
public methods for memory management
public methods for message handling
public methods for SCIP parameter handling
public methods for global and local (sub)problems
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
default SCIP plugins
SCIP * blockscip
Definition: heur_dps.c:102
int nlinking
Definition: heur_dps.c:106
int * linkingindices
Definition: heur_dps.c:105
int nblockvars
Definition: heur_dps.c:107
SCIP_CONS ** linkingconss
Definition: heur_dps.c:104
int nslackvars
Definition: heur_dps.c:108
SCIP_VAR ** slackvars
Definition: heur_dps.c:103
SCIP_Real * origobj
Definition: heur_dps.c:109
SCIP_CONS * linkingcons
Definition: heur_dps.c:116
int nslacksperblock
Definition: heur_dps.c:126
SCIP_Bool haslhs
Definition: heur_dps.c:129
SCIP_Real * maxactivity
Definition: heur_dps.c:120
SCIP_Bool hasrhs
Definition: heur_dps.c:128
SCIP_Real * currentrhs
Definition: heur_dps.c:121
SCIP_VAR ** slacks
Definition: heur_dps.c:118
SCIP_Real * minactivity
Definition: heur_dps.c:119
int * blocknumbers
Definition: heur_dps.c:123
SCIP_Real * currentlhs
Definition: heur_dps.c:122
int nslacks
Definition: heur_dps.c:125
int lastviolations
Definition: heur_dps.c:127
int nblocks
Definition: heur_dps.c:124
SCIP_CONS ** blockconss
Definition: heur_dps.c:117
#define SCIP_DECOMP_LINKVAR
Definition: type_dcmp.h:44
#define SCIP_DECOMP_LINKCONS
Definition: type_dcmp.h:45
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:173
#define SCIP_EVENTTYPE_LPSOLVED
Definition: type_event.h:101
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
@ SCIP_VERBLEVEL_FULL
Definition: type_message.h:57
@ SCIP_PARAMSETTING_OFF
Definition: type_paramset.h:63
@ SCIP_PARAMSETTING_FAST
Definition: type_paramset.h:62
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_FOUNDSOL
Definition: type_result.h:56
@ SCIP_PLUGINNOTFOUND
Definition: type_retcode.h:54
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_STATUS_OPTIMAL
Definition: type_stat.h:61
@ SCIP_STATUS_BESTSOLLIMIT
Definition: type_stat.h:57
@ SCIP_STATUS_UNBOUNDED
Definition: type_stat.h:63
@ SCIP_STATUS_TIMELIMIT
Definition: type_stat.h:51
@ SCIP_STATUS_INFEASIBLE
Definition: type_stat.h:62
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:67
unsigned int SCIP_HEURTIMING
Definition: type_timing.h:101
#define SCIP_HEURTIMING_AFTERNODE
Definition: type_timing.h:96
#define SCIP_HEURTIMING_BEFORENODE
Definition: type_timing.h:78
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71
@ SCIP_VARSTATUS_NEGATED
Definition: type_var.h:55