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 */
84 struct 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 };
111 typedef struct Blockproblem BLOCKPROBLEM;
112 
113 /** data related to one linking constraint */
114 struct Linking
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 };
131 typedef 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  */
142 static
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) );
180  SCIP_CALL( SCIPcomputeDecompStats(scip, newdecomp, TRUE) );
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) );
203  SCIP_CALL( SCIPcomputeDecompStats(scip, newdecomp, TRUE) );
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 */
216 static
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 */
269 static
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 */
348 static
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,
545  0.0, SCIPinfinity(scip), 1.0, SCIP_VARTYPE_CONTINUOUS) );
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,
565  0.0, SCIPinfinity(scip), 1.0, SCIP_VARTYPE_CONTINUOUS) );
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 */
659 static
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  */
712 static
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 */
873 static
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 */
1063 static
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 */
1226 static
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  */
1317 static
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 */
1383 static
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 */
1503 static
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  */
1687 static
1688 SCIP_DECL_EVENTEXEC(eventExecDps)
1689 {
1690  assert(eventhdlr != NULL);
1691  assert(eventdata != NULL);
1692  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
1693  assert(event != NULL);
1694  assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_LPSOLVED);
1695 
1696  SCIPdebugMsg(scip, "dual bound: %.2f\n", SCIPgetDualbound(scip));
1697 
1698  if( SCIPisFeasGT(scip, SCIPgetDualbound(scip), 0.0) && SCIPgetNSols(scip) >= 1 )
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) */
1713 static
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) */
1727 static
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 */
1746 static
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 */
1863  SCIP_CALL( SCIPdecompCreate(&assigneddecomp, SCIPblkmem(scip), nblocks, SCIPdecompIsOriginal(decomp), SCIPdecompUseBendersLabels(decomp)) );
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 */
2183 TERMINATE:
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 */
2261  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
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 }
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_VAR ** slackvars
Definition: heur_dps.c:103
SCIP_Real * currentrhs
Definition: heur_dps.c:121
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetActivityLinear(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
#define SCIP_EVENTTYPE_LPSOLVED
Definition: type_event.h:101
SCIP_Real SCIPconsGetLhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: misc_linear.c:112
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:979
#define NULL
Definition: def.h:267
static SCIP_DECL_EVENTEXEC(eventExecDps)
Definition: heur_dps.c:1688
public methods for SCIP parameter handling
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 HEUR_NAME
Definition: heur_dps.c:62
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8475
SCIP_VAR ** slacks
Definition: heur_dps.c:118
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)
void SCIPdecompGetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:198
public methods for memory management
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
SCIP_Real SCIPgetPrimalbound(SCIP *scip)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18079
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:307
#define SCIP_MAXSTRLEN
Definition: def.h:288
SCIP_Real * minactivity
Definition: heur_dps.c:119
SCIP_RETCODE SCIPaddSolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool *stored)
Definition: scip_sol.c:2855
SCIP_CONS ** linkingconss
Definition: heur_dps.c:104
unsigned int SCIP_HEURTIMING
Definition: type_timing.h:106
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
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPcomputeDecompStats(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Bool uselimits)
Definition: scip_dcmp.c:1136
SCIP_Real SCIPconsGetRhs(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: misc_linear.c:48
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2432
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
int nslacks
Definition: heur_dps.c:125
#define SCIP_HEURTIMING_BEFORENODE
Definition: type_timing.h:79
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int * blocknumbers
Definition: heur_dps.c:123
#define HEUR_DESC
Definition: heur_dps.c:63
SCIP_Real * origobj
Definition: heur_dps.c:109
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:104
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1247
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_HEURFREE(heurFreeDps)
Definition: heur_dps.c:1728
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2119
#define FALSE
Definition: def.h:94
static SCIP_RETCODE reuseSolution(LINKING **linkings, BLOCKPROBLEM **blockproblem, int nblocks)
Definition: heur_dps.c:1384
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3296
SCIP_RETCODE SCIPcomputeDecompConsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition: scip_dcmp.c:345
static SCIP_RETCODE createSubscip(SCIP *scip, SCIP **subscip)
Definition: heur_dps.c:217
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
#define TRUE
Definition: def.h:93
int SCIPdecompGetNBorderVars(SCIP_DECOMP *decomp)
Definition: dcmp.c:379
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
#define SCIP_HEURTIMING_AFTERNODE
Definition: type_timing.h:101
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:953
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_VAR ** SCIPgetOrigVars(SCIP *scip)
Definition: scip_prob.c:2405
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:77
void SCIPdecompGetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:149
SCIP_RETCODE SCIPdecompSetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:124
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
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
#define SCIP_DECOMP_LINKCONS
Definition: type_dcmp.h:45
void SCIPsortIntIntReal(int *intarray1, int *intarray2, SCIP_Real *realarray, int len)
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip_prob.c:3088
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4675
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:307
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1374
SCIP_Bool SCIPdecompIsOriginal(SCIP_DECOMP *decomp)
Definition: dcmp.c:246
int nslackvars
Definition: heur_dps.c:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:102
SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
Definition: var.c:17905
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:603
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8485
static SCIP_RETCODE initCurrent(SCIP *scip, LINKING **linkings, BLOCKPROBLEM **blockproblem, SCIP_HEURTIMING heurtiming, int nlinking, SCIP_Bool *success)
Definition: heur_dps.c:874
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
#define SCIPdebugMsg
Definition: scip_message.h:78
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_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8277
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:421
#define HEUR_USESSUBSCIP
Definition: heur_dps.c:70
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1067
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
void SCIPgetDecomps(SCIP *scip, SCIP_DECOMP ***decomps, int *ndecomps, SCIP_Bool original)
Definition: scip_dcmp.c:263
SCIP_VAR * SCIPfindVar(SCIP *scip, const char *name)
Definition: scip_prob.c:2685
static SCIP_DECL_HEURCOPY(heurCopyDps)
Definition: heur_dps.c:1714
SCIP_Bool hasrhs
Definition: heur_dps.c:128
public methods for decompositions
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18089
SCIP_RETCODE SCIPdecompGetVarsSize(SCIP_DECOMP *decomp, int *varssize, int nlabels)
Definition: dcmp.c:316
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2498
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1453
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
SCIP_Real * currentlhs
Definition: heur_dps.c:122
#define SCIPerrorMessage
Definition: pub_message.h:64
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4199
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:219
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2622
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2770
SCIP_Real * maxactivity
Definition: heur_dps.c:120
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:178
int nblocks
Definition: heur_dps.c:124
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1254
SCIP_Real SCIPgetDualbound(SCIP *scip)
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:429
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:498
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
SCIP * blockscip
Definition: heur_dps.c:102
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8216
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4765
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8435
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:173
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17420
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
int SCIPdecompGetNBlocks(SCIP_DECOMP *decomp)
Definition: dcmp.c:279
#define EVENTHDLR_DESC
Definition: heur_dps.c:77
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:269
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18453
#define HEUR_FREQOFS
Definition: heur_dps.c:67
#define SCIP_CALL(x)
Definition: def.h:380
SCIP_CONS * linkingcons
Definition: heur_dps.c:116
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int lastviolations
Definition: heur_dps.c:127
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
Definition: heur.c:1579
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip_cons.c:2578
public methods for primal heuristic plugins and divesets
public methods for constraint handler plugins and constraints
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 SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_var.c:4512
#define SCIP_DECOMP_LINKVAR
Definition: type_dcmp.h:44
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 SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
public data structures and miscellaneous methods
SCIP_RETCODE SCIPdecompSetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:173
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition: scip_solve.c:3344
#define SCIP_Bool
Definition: def.h:91
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:286
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1030
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:67
#define HEUR_TIMING
Definition: heur_dps.c:69
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_CONS ** blockconss
Definition: heur_dps.c:117
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8236
#define MIN(x, y)
Definition: def.h:243
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:487
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
Definition: cons.c:8345
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:320
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8415
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8385
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17927
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2070
SCIP_RETCODE SCIPdecompCreate(SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition: dcmp.c:57
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1300
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define HEUR_PRIORITY
Definition: heur_dps.c:65
static SCIP_DECL_HEUREXEC(heurExecDps)
Definition: heur_dps.c:1747
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
#define SCIP_REAL_MAX
Definition: def.h:174
SCIP_VAR ** b
Definition: circlepacking.c:65
general public methods
#define MAX(x, y)
Definition: def.h:239
#define HEUR_FREQ
Definition: heur_dps.c:66
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2169
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
char * SCIPdecompPrintStats(SCIP_DECOMP *decomp, char *strbuf)
Definition: dcmp.c:455
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
#define DEFAULT_PENALTY
Definition: heur_dps.c:73
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip_mem.c:100
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 SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1668
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3042
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
int nblockvars
Definition: heur_dps.c:107
#define HEUR_DISPCHAR
Definition: heur_dps.c:64
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip_mem.c:126
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1947
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17539
#define SCIP_Real
Definition: def.h:173
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8465
SCIP_RETCODE SCIPgetConsVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int varssize, SCIP_Bool *success)
Definition: misc_linear.c:179
#define DEFAULT_MAXIT
Definition: heur_dps.c:72
public methods for message handling
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8405
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8395
SCIP_Real SCIPgetTotalTime(SCIP *scip)
Definition: scip_timing.c:351
#define HEUR_MAXDEPTH
Definition: heur_dps.c:68
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17585
#define EVENTHDLR_NAME
Definition: heur_dps.c:76
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1119
SCIP_Bool haslhs
Definition: heur_dps.c:129
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:222
void SCIPdecompFree(SCIP_DECOMP **decomp, BMS_BLKMEM *blkmem)
Definition: dcmp.c:99
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int nlinking
Definition: heur_dps.c:106
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
SCIP_Bool SCIPdecompUseBendersLabels(SCIP_DECOMP *decomp)
Definition: dcmp.c:269
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:162
int * linkingindices
Definition: heur_dps.c:105
SCIP_RETCODE SCIPinterruptSolve(SCIP *scip)
Definition: scip_solve.c:3430
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
public methods for primal heuristics
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
SCIP_RETCODE SCIPdecompGetConssSize(SCIP_DECOMP *decomp, int *consssize, int nlabels)
Definition: dcmp.c:349
dynamic partition search
#define SCIP_CALL_ABORT(x)
Definition: def.h:359
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1364
public methods for decompositions
SCIP_RETCODE SCIPincludeHeurDps(SCIP *scip)
Definition: heur_dps.c:2248
int nslacksperblock
Definition: heur_dps.c:126
int SCIPdecompGetNBorderConss(SCIP_DECOMP *decomp)
Definition: dcmp.c:394
#define SCIPABORT()
Definition: def.h:352
public methods for global and local (sub)problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
default SCIP plugins
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
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
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
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:904
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:545
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1526
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
void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
static SCIP_RETCODE roundPartition(SCIP *scip, LINKING *linking, BLOCKPROBLEM **blockproblem, SCIP_Bool roundbyrhs)
Definition: heur_dps.c:713
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:339
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128