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