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