Scippy

SCIP

Solving Constraint Integer Programs

heur_padm.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_padm.c
17  * @brief PADM primal heuristic based on ideas published in the paper
18  * "A Decomposition Heuristic for Mixed-Integer Supply Chain Problems"
19  * by Martin Schmidt, Lars Schewe, and Dieter Weninger
20  * @author Dieter Weninger
21  * @author Katrin Halbig
22  *
23  * The penalty alternating direction method (PADM) heuristic is a construction heuristic which additionally needs a
24  * user decomposition with linking variables only.
25  *
26  * PADM splits the problem into several sub-SCIPs according to the decomposition, whereby the linking variables get
27  * copied and the difference is penalized. Then the sub-SCIPs are solved on an alternating basis until they arrive at
28  * the same values of the linking variables (ADM-loop). If they don't reconcile after a couple of iterations,
29  * the penalty parameters are increased (penalty-loop) and the sub-SCIPs are solved again on an alternating basis.
30  */
31 
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33 
34 #include <assert.h>
35 #include <string.h>
36 
37 #include "blockmemshell/memory.h"
38 #include "scip/cons_linear.h"
39 #include "scip/debug.h"
40 #include "scip/heur_padm.h"
41 #include "scip/heuristics.h"
42 #include "scip/pub_cons.h"
43 #include "scip/pub_tree.h"
44 #include "scip/pub_heur.h"
45 #include "scip/pub_message.h"
46 #include "scip/pub_misc.h"
47 #include "scip/pub_misc_select.h"
48 #include "scip/pub_sol.h"
49 #include "scip/pub_var.h"
50 #include "scip/scipdefplugins.h"
51 #include "scip/scip_branch.h"
52 #include "scip/scip_cons.h"
53 #include "scip/scip_copy.h"
54 #include "scip/scip_dcmp.h"
55 #include "scip/scip_general.h"
56 #include "scip/scip_heur.h"
57 #include "scip/scip_lp.h"
58 #include "scip/scip_mem.h"
59 #include "scip/scip_message.h"
60 #include "scip/scip_nodesel.h"
61 #include "scip/scip_numerics.h"
62 #include "scip/scip_param.h"
63 #include "scip/scip_prob.h"
64 #include "scip/scip_randnumgen.h"
65 #include "scip/scip_sol.h"
66 #include "scip/scip_solve.h"
67 #include "scip/scip_solvingstats.h"
68 #include "scip/scip_table.h"
69 #include "scip/scip_timing.h"
70 #include "scip/scip_tree.h"
71 #include "scip/scip_var.h"
72 
73 #define HEUR_NAME "padm"
74 #define HEUR_DESC "penalty alternating direction method primal heuristic"
75 #define HEUR_DISPCHAR SCIP_HEURDISPCHAR_LNS
76 #define HEUR_PRIORITY 70000
77 #define HEUR_FREQ 0
78 #define HEUR_FREQOFS 0
79 #define HEUR_MAXDEPTH -1
80 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE | SCIP_HEURTIMING_AFTERNODE
81 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
82 
83 #define COUPLINGSIZE 3
84 #define DEFAULT_MINNODES 50LL
85 #define DEFAULT_MAXNODES 5000LL
86 #define DEFAULT_NODEFAC 0.8
87 #define DEFAULT_ADMIT 4
88 #define DEFAULT_PENALTYIT 100
89 #define DEFAULT_GAP 2.0
90 
91 /*
92  * Data structures
93  */
94 
95 /** data related to one problem (see below) */
96 typedef struct Problem PROBLEM;
97 
98 /** data related to one block */
99 typedef struct Block
100 {
101  PROBLEM* problem; /**< the problem this block belongs to */
102  SCIP* subscip; /**< sub-SCIP representing this block */
103  int number; /**< component number */
104  SCIP_VAR** subvars; /**< variables belonging to this block (without slack variables) */
105  int nsubvars; /**< number of variables belonging to this block (without slack variables) */
106  SCIP_VAR** slackspos; /**< positive slack variables */
107  SCIP_VAR** slacksneg; /**< negative slack variables */
108  SCIP_CONS** couplingcons; /**< coupling contraints */
109  int ncoupling; /**< number of coupling contraints (equal to positive/negative slack variables) */
110  SCIP_Real size; /**< share of total problem */
111 } BLOCK;
112 
113 /** data related to one problem */
114 struct Problem
115 {
116  SCIP* scip; /**< the SCIP instance this problem belongs to */
117  char* name; /**< name of the problem */
118  BLOCK* blocks; /**< blocks into which the problem will be divided */
119  int nblocks; /**< number of blocks */
120 };
121 
122 /** set data structure */
123 typedef struct set
124 {
125  int size; /**< size of the set */
126  int* indexes; /**< set of indexes */
127 } SET;
128 
129 /** data of one linking variable related to one block */
130 typedef struct blockinfo
131 {
132  int block; /**< index of this block */
133  int otherblock; /**< index of the other connected block */
134  int linkvaridx; /**< linking variable index */
135  SCIP_Real linkvarval; /**< value of linking variable */
136  SCIP_VAR* linkvar; /**< linking variable */
137  SCIP_Real slackposobjcoeff; /**< penalty coefficient of positive slack variable */
138  SCIP_VAR* slackposvar; /**< positive slack variable */
139  SCIP_Real slacknegobjcoeff; /**< penalty coefficient of negative slack variable */
140  SCIP_VAR* slacknegvar; /**< negative slack variable */
141  SCIP_CONS* couplingCons; /**< coupling contraint (equation) */
142 } BLOCKINFO;
143 
144 /** returns TRUE iff both keys are equal */
145 static
146 SCIP_DECL_HASHKEYEQ(indexesEqual)
147 { /*lint --e{715}*/
148  BLOCKINFO* binfo1;
149  BLOCKINFO* binfo2;
150 
151  binfo1 = (BLOCKINFO*) key1;
152  binfo2 = (BLOCKINFO*) key2;
153 
154  if( binfo1->block != binfo2->block || binfo1->otherblock != binfo2->otherblock ||
155  binfo1->linkvaridx != binfo2->linkvaridx )
156  return FALSE;
157 
158  return TRUE;
159 }
160 
161 /** returns the hash value of the key */
162 static
163 SCIP_DECL_HASHKEYVAL(indexesHashval)
164 { /*lint --e{715}*/
165  BLOCKINFO* binfo;
166  binfo = (BLOCKINFO*) key;
167 
168  return SCIPhashFour(SCIPrealHashCode((double)binfo->block), SCIPrealHashCode((double)binfo->otherblock),
169  SCIPrealHashCode((double)binfo->linkvaridx), SCIPrealHashCode((double)binfo->linkvaridx));
170 }
171 
172 /** primal heuristic data */
173 struct SCIP_HeurData
174 {
175  SCIP_Longint maxnodes; /**< maximum number of nodes to regard in all subproblems */
176  SCIP_Longint minnodes; /**< minimum number of nodes to regard in one subproblem */
177  int admiterations; /**< maximal number of ADM iterations in each penalty loop */
178  int penaltyiterations; /**< maximal number of penalty iterations */
179  int timing; /**< should the heuristic run before or after the processing of the node?
180  (0: before, 1: after, 2: both) */
181  SCIP_Real nodefac; /**< factor to control nodelimits of subproblems */
182  SCIP_Real gap; /**< mipgap at start */
183  SCIP_Bool reoptimize; /**< should the problem get reoptimized with the original objective function? */
184  SCIP_Bool scaling; /**< enable sigmoid rescaling of penalty parameters */
185  SCIP_Bool assignlinking; /**< should linking constraints be assigned? */
186  SCIP_Bool original; /**< should the original problem be used? */
187 };
188 
189 /*
190  * Local methods
191  */
192 
193 /** initializes one block */
194 static
196  PROBLEM* problem /**< problem structure */
197  )
198 {
199  BLOCK* block;
200 
201  assert(problem != NULL);
202  assert(problem->scip != NULL);
203 
204  block = &problem->blocks[problem->nblocks];
205 
206  block->problem = problem;
207  block->subscip = NULL;
208  block->subvars = NULL;
209  block->nsubvars = 0;
210  block->number = problem->nblocks;
211  block->slackspos = NULL;
212  block->slacksneg = NULL;
213  block->couplingcons = NULL;
214  block->ncoupling = 0;
215  block->size = 0;
216 
217  ++problem->nblocks;
218 
219  return SCIP_OKAY;
220 }
221 
222 /** frees component structure */
223 static
225  BLOCK* block /**< block structure */
226  )
227 {
228  assert(block != NULL);
229 
230  block->ncoupling = 0;
231 
232  if( block->subvars != NULL )
233  {
234  SCIPfreeBufferArray(block->problem->scip, &(block->subvars));
235  }
236 
237  if( block->subscip != NULL )
238  {
239  SCIP_CALL( SCIPfree(&block->subscip) );
240  }
241 
242  return SCIP_OKAY;
243 }
244 
245 /** initializes subproblem structure */
246 static
248  SCIP* scip, /**< SCIP data structure */
249  PROBLEM** problem, /**< pointer to problem structure */
250  int nblocks /**< number of blocks */
251  )
252 {
253  char name[SCIP_MAXSTRLEN];
254 
255  assert(scip != NULL);
256  assert(problem != NULL);
257 
258  SCIP_CALL( SCIPallocBlockMemory(scip, problem) );
259  assert(*problem != NULL);
260 
261  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s", SCIPgetProbName(scip));
262 
263  SCIP_CALL( SCIPduplicateMemoryArray(scip, &(*problem)->name, name, strlen(name) + 1) );
264 
265  SCIPdebugMessage("initialized problem <%s>\n", (*problem)->name);
266 
267  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*problem)->blocks, nblocks) );
268 
269  (*problem)->scip = scip;
270  (*problem)->nblocks = 0;
271 
272  return SCIP_OKAY;
273 }
274 
275 /** frees subproblem structure */
276 static
278  PROBLEM** problem, /**< pointer to problem to free */
279  int nblocks /**< number of blocks in decomposition */
280  )
281 {
282  SCIP* scip;
283  int c;
284 
285  assert(problem != NULL);
286  assert(*problem != NULL);
287 
288  scip = (*problem)->scip;
289  assert(scip != NULL);
290 
291  /* free all blocks */
292  for( c = nblocks - 1; c >= 0; --c )
293  {
294  SCIP_CALL( freeBlock(&(*problem)->blocks[c]) );
295  }
296  if( (*problem)->blocks != NULL )
297  {
298  SCIPfreeBlockMemoryArray(scip, &(*problem)->blocks, nblocks);
299  }
300 
301  /* free problem name */
302  SCIPfreeMemoryArray(scip, &(*problem)->name);
303 
304  /* free PROBLEM struct and set the pointer to NULL */
305  SCIPfreeBlockMemory(scip, problem);
306  *problem = NULL;
307 
308  return SCIP_OKAY;
309 }
310 
311 /** creates a sub-SCIP for the given variables and constraints */
312 static
314  SCIP* scip, /**< main SCIP data structure */
315  SCIP** subscip /**< pointer to store created sub-SCIP */
316  )
317 {
318  SCIP_Real infvalue;
319 
320  /* create a new SCIP instance */
321  SCIP_CALL( SCIPcreate(subscip) );
322 
324 
325  /* copy value for infinity */
326  SCIP_CALL( SCIPgetRealParam(scip, "numerics/infinity", &infvalue) );
327  SCIP_CALL( SCIPsetRealParam(*subscip, "numerics/infinity", infvalue) );
328 
329  SCIP_CALL( SCIPcopyLimits(scip, *subscip) );
330 
331  /* avoid recursive calls */
332  SCIP_CALL( SCIPsetSubscipsOff(*subscip, TRUE) );
333 
334  /* disable cutting plane separation */
336 
337  /* disable expensive presolving */
339 
340  /* disable expensive techniques */
341  SCIP_CALL( SCIPsetIntParam(*subscip, "misc/usesymmetry", 0) );
342 
343  /* do not abort subproblem on CTRL-C */
344  SCIP_CALL( SCIPsetBoolParam(*subscip, "misc/catchctrlc", FALSE) );
345 
346 #ifdef SCIP_DEBUG
347  /* for debugging, enable full output */
348  SCIP_CALL( SCIPsetIntParam(*subscip, "display/verblevel", 5) );
349  SCIP_CALL( SCIPsetIntParam(*subscip, "display/freq", 100000000) );
350 #else
351  /* disable statistic timing inside sub SCIP and output to console */
352  SCIP_CALL( SCIPsetIntParam(*subscip, "display/verblevel", 0) );
353  SCIP_CALL( SCIPsetBoolParam(*subscip, "timing/statistictiming", FALSE) );
354 #endif
355 
356  return SCIP_OKAY;
357 }
358 
359 /** copies the given constraints and the corresponding variables to the given sub-SCIP */
360 static
362  SCIP* scip, /**< source SCIP */
363  SCIP* subscip, /**< target SCIP */
364  const char* name, /**< name for copied problem */
365  SCIP_CONS** conss, /**< constraints to copy */
366  SCIP_HASHMAP* varmap, /**< hashmap used for the copy process of variables */
367  SCIP_HASHMAP* consmap, /**< hashmap used for the copy process of constraints */
368  int nconss, /**< number of constraints to copy */
369  SCIP_Bool useorigprob, /**< do we use the original problem? */
370  SCIP_Bool* success /**< pointer to store whether copying was successful */
371  )
372 {
373  SCIP_CONS* newcons;
374  int i;
375 
376  assert(scip != NULL);
377  assert(subscip != NULL);
378  assert(conss != NULL);
379  assert(consmap != NULL);
380  assert(success != NULL);
381 
382  *success = TRUE;
383  newcons = NULL;
384 
385  /* create problem in sub-SCIP */
386  SCIP_CALL( SCIPcopyProb(scip, subscip, varmap, consmap, FALSE, name) );
387 
388  /* copy constraints */
389  for( i = 0; i < nconss; ++i )
390  {
391  assert(conss[i] != NULL);
392 
393  /* do not check this if we use the original problem
394  * Since constraints can be deleted etc. during presolving, these assertions would fail.
395  */
396  if( !useorigprob )
397  {
398  assert(!SCIPconsIsModifiable(conss[i]));
399  assert(SCIPconsIsActive(conss[i]));
400  assert(!SCIPconsIsDeleted(conss[i]));
401  }
402 
403  /* copy the constraint */
404  SCIP_CALL( SCIPgetConsCopy(scip, subscip, conss[i], &newcons, SCIPconsGetHdlr(conss[i]), varmap, consmap, NULL,
405  SCIPconsIsInitial(conss[i]), SCIPconsIsSeparated(conss[i]), SCIPconsIsEnforced(conss[i]),
406  SCIPconsIsChecked(conss[i]), SCIPconsIsPropagated(conss[i]), FALSE, FALSE,
407  SCIPconsIsDynamic(conss[i]), SCIPconsIsRemovable(conss[i]), FALSE, FALSE, success) );
408 
409  /* abort if constraint was not successfully copied */
410  if( !(*success) || newcons == NULL)
411  return SCIP_OKAY;
412 
413  SCIP_CALL( SCIPaddCons(subscip, newcons) );
414  SCIP_CALL( SCIPreleaseCons(subscip, &newcons) );
415  }
416 
417  return SCIP_OKAY;
418 }
419 
420 /** creates the subscip for a given block */
421 static
423  BLOCK* block, /**< block structure */
424  SCIP_HASHMAP* varmap, /**< variable hashmap used to improve performance */
425  SCIP_HASHMAP* consmap, /**< constraint hashmap used to improve performance */
426  SCIP_CONS** conss, /**< constraints contained in this block */
427  int nconss, /**< number of constraints contained in this block */
428  SCIP_Bool useorigprob, /**< do we use the original problem? */
429  SCIP_Bool* success /**< pointer to store whether the copying process was successful */
430  )
431 {
432  char name[SCIP_MAXSTRLEN];
433  PROBLEM* problem;
434  SCIP* scip;
435  SCIP_VAR** subscipvars;
436  int nsubscipvars;
437  int i;
438 
439  assert(block != NULL);
440  assert(varmap != NULL);
441  assert(consmap != NULL);
442  assert(conss != NULL);
443  assert(success != NULL);
444 
445  problem = block->problem;
446  assert(problem != NULL);
447 
448  scip = problem->scip;
449  assert(scip != NULL);
450 
451  (*success) = TRUE;
452 
453  SCIP_CALL( createSubscip(scip, &block->subscip) );
454 
455  if( block->subscip != NULL )
456  {
457  /* get name of the original problem and add "comp_nr" */
458  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_comp_%d", problem->name, block->number);
459 
460  SCIP_CALL( copyToSubscip(scip, block->subscip, name, conss, varmap, consmap, nconss, useorigprob, success) );
461 
462  if( !(*success) )
463  {
464  SCIP_CALL( SCIPfree(&block->subscip) );
465  block->subscip = NULL;
466  }
467  else
468  {
469  /* save variables of subscip (without slack variables) */
470  nsubscipvars = SCIPgetNOrigVars(block->subscip);
471  subscipvars = SCIPgetOrigVars(block->subscip);
472  SCIP_CALL( SCIPallocBufferArray(scip, &(block->subvars), nsubscipvars) );
473  block->nsubvars = nsubscipvars;
474  for( i = 0; i < nsubscipvars; i++ )
475  block->subvars[i] = subscipvars[i];
476 
477  /* calculate size of sub-SCIP with focus on the number of integer variables
478  * we use this value to determine the nodelimit
479  */
481  (SCIPgetNVars(scip) + SCIPgetNIntVars(scip) + SCIPgetNBinVars(scip));
482  }
483  }
484  else
485  (*success) = FALSE;
486 
487  SCIPdebugMsg(scip, "created subscip of block %d\n", block->number);
488 
489  return SCIP_OKAY;
490 }
491 
492 /** creates problem structure and split it into blocks */
493 static
495  SCIP* scip, /**< SCIP data structure */
496  SCIP_CONS** sortedconss, /**< array of (checked) constraints sorted by blocks */
497  int nconss, /**< number of constraints */
498  int* consssize, /**< number of constraints per block (and border at index 0) */
499  int nblocks, /**< number of blocks */
500  PROBLEM** problem, /**< pointer to store problem structure */
501  SCIP_Bool useorigprob, /**< do we use the original problem? */
502  SCIP_Bool* success /**< pointer to store whether the process was successful */
503  )
504 {
505  BLOCK* block;
506  SCIP_HASHMAP* varmap;
507  SCIP_HASHMAP* consmap;
508  SCIP_CONS** blockconss;
509  int nhandledconss;
510  int nblockconss;
511  int b;
512 
513  (*success) = TRUE;
514 
515  /* init subproblem data structure */
516  SCIP_CALL( initProblem(scip, problem, nblocks) );
517  assert((*problem)->blocks != NULL);
518 
519  /* hashmap mapping from original constraints to constraints in the sub-SCIPs (for performance reasons) */
520  SCIP_CALL( SCIPhashmapCreate(&consmap, SCIPblkmem(scip), nconss) );
521 
522  for( b = 0; b < nblocks; b++ )
523  {
524  SCIP_CALL( initBlock(*problem) );
525  }
526 
527  /* loop over all blocks and create subscips */
528  nhandledconss = 0;
529  for( b = 0; b < nblocks; b++ )
530  {
531  block = &(*problem)->blocks[b];
532 
533  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scip), SCIPgetNVars(scip)) );
534 
535  /* get block constraints */
536  blockconss = &(sortedconss[nhandledconss]);
537  nblockconss = consssize[b + 1];
538 
539  /* build subscip for block */
540  SCIP_CALL( blockCreateSubscip(block, varmap, consmap, blockconss, nblockconss, useorigprob, success) );
541 
542  SCIPhashmapFree(&varmap);
543  nhandledconss += nblockconss;
544 
545  if( !(*success) )
546  break;
547  }
548 
549  SCIPhashmapFree(&consmap);
550 
551  if( !(*success) )
552  {
553  /* free subproblem data structure since not all blocks could be copied */
554  SCIP_CALL( freeProblem(problem, nblocks) );
555  }
556 
557  return SCIP_OKAY;
558 }
559 
560 /** copies labels to newdecomp and assigns linking constraints if possible*/
561 static
563  SCIP* scip, /**< SCIP data structure */
564  SCIP_DECOMP* newdecomp, /**< decomposition with (partially) assigned linking constraints */
565  SCIP_VAR** vars, /**< array of variables */
566  SCIP_CONS** sortedconss, /**< sorted array of constraints */
567  int* varlabels, /**< array of variable labels */
568  int* conslabels, /**< sorted array of constraint labels */
569  int nvars, /**< number of variables */
570  int nconss, /**< number of constraints */
571  int nlinkconss /**< number of linking constraints */
572  )
573 {
574  assert(scip != NULL);
575  assert(vars != NULL);
576  assert(sortedconss != NULL);
577  assert(varlabels != NULL);
578  assert(conslabels != NULL);
579 
580  /* copy the labels */
581  SCIP_CALL( SCIPdecompSetVarsLabels(newdecomp, vars, varlabels, nvars) );
582  SCIP_CALL( SCIPdecompSetConsLabels(newdecomp, sortedconss, conslabels, nconss) );
583 
584  SCIPdebugMsg(scip, "try to assign %d linking constraints\n", nlinkconss);
585 
586  /* reassign linking constraints */
587  SCIP_CALL( SCIPassignDecompLinkConss(scip, newdecomp, &sortedconss[0], nlinkconss, NULL) );
588 
589  SCIP_CALL( SCIPcomputeDecompVarsLabels(scip, newdecomp, sortedconss, nconss) );
590 
591  SCIP_CALL( SCIPcomputeDecompStats(scip, newdecomp, TRUE) );
592 
593  SCIPdecompGetConsLabels(newdecomp, sortedconss, conslabels, nconss);
594  SCIPdecompGetVarsLabels(newdecomp, vars, varlabels, nvars);
595 
596  SCIPsortIntPtr(conslabels, (void**)sortedconss, nconss);
597 
598  return SCIP_OKAY;
599 }
600 
601 /** computes feasible solution from last stored solution of the block*/
602 static
604  SCIP* subscip, /**< SCIP data structure */
605  BLOCK* block /**< block structure*/
606  )
607 {
608  SCIP_SOL** sols;
609  SCIP_SOL* sol; /* solution of block that will be repaired */
610  SCIP_SOL* newsol;
611  SCIP_VAR** blockvars;
612  SCIP_VAR** consvars;
613  SCIP_Real* blockvals;
614  int nsols;
615  int nvars;
616  int c;
617  SCIP_Bool success;
618 
619  assert(subscip != NULL);
620  assert(block != NULL);
621 
622  nsols = SCIPgetNSols(subscip);
623 
624  /* no solution in solution candidate storage found */
625  if( nsols == 0 )
626  return SCIP_OKAY;
627 
628  SCIP_CALL( SCIPallocBufferArray(subscip, &consvars, COUPLINGSIZE) );
629 
630  sols = SCIPgetSols(subscip);
631  sol = sols[nsols - 1];
632 
633  /* copy the solution */
634  nvars = SCIPgetNVars(subscip);
635  blockvars = SCIPgetVars(subscip);
636  SCIP_CALL( SCIPallocBufferArray(subscip, &blockvals, nvars) );
637  SCIP_CALL( SCIPgetSolVals(subscip, sol, nvars, blockvars, blockvals) );
638  SCIP_CALL( SCIPcreateOrigSol(subscip, &newsol, NULL) );
639  SCIP_CALL( SCIPsetSolVals(subscip, newsol, nvars, blockvars, blockvals) );
640 
641  /* correct each coupling constraint;
642  * orig_var + slackpos - slackneg == side
643  * adapt slack variables so that constraint is feasible */
644  for( c = 0; c < block->ncoupling; c++ )
645  {
646  SCIP_Real solval; /* old solution values of variables; [0] original variable, [1] slackpos, [2] slackneg */
647  SCIP_Real side; /* current right hand side */
648  SCIP_Real diff;
649 
650  SCIP_CALL( SCIPgetConsVars(subscip, block->couplingcons[c], consvars, COUPLINGSIZE, &success) );
651  solval = SCIPgetSolVal(subscip, sol, consvars[0]);
652 
653  side = SCIPgetRhsLinear(subscip, block->couplingcons[c]);
654  assert(SCIPisEQ(subscip, SCIPgetRhsLinear(subscip, block->couplingcons[c]), SCIPgetLhsLinear(subscip, block->couplingcons[c])));
655 
656  diff = side - solval;
657 
658  /* slackpos is strict positiv */
659  if( diff > 0 )
660  {
661  SCIP_CALL( SCIPsetSolVal(subscip, newsol, block->slackspos[c], diff) );
662  SCIP_CALL( SCIPsetSolVal(subscip, newsol, block->slacksneg[c], 0.0) );
663  }
664  /* slackneg is strict positiv */
665  else if( diff < 0 )
666  {
667  SCIP_CALL( SCIPsetSolVal(subscip, newsol, block->slacksneg[c], -diff) );
668  SCIP_CALL( SCIPsetSolVal(subscip, newsol, block->slackspos[c], 0.0) );
669  }
670  /* no slack variable necessary */
671  else
672  {
673  SCIP_CALL( SCIPsetSolVal(subscip, newsol, block->slackspos[c], 0.0) );
674  SCIP_CALL( SCIPsetSolVal(subscip, newsol, block->slacksneg[c], 0.0) );
675  }
676  }
677 
678  SCIPdebugMsg(subscip, "Try adding solution with objective value %.2f\n", SCIPgetSolOrigObj(subscip, newsol));
679  SCIP_CALL( SCIPaddSolFree(subscip, &newsol, &success) );
680 
681  if( !success )
682  SCIPdebugMsg(subscip, "Correcting solution failed\n"); /* maybe not better than old solutions */
683  else
684  {
685  SCIPdebugMsg(subscip, "Correcting solution successful\n");
686  }
687 
688  SCIPfreeBufferArray(subscip, &blockvals);
689  SCIPfreeBufferArray(subscip, &consvars);
690 
691  return SCIP_OKAY;
692 }
693 
694 /** reoptimizes the heuristic solution with original objective function
695  *
696  * Since the main algorithm of padm ignores the objective function, this method can be called to obtain better solutions.
697  * It copies the main scip, fixes the linking variables at the values of the already found solution
698  * and solves the new problem with small limits.
699  */
700 static
702  SCIP* scip, /**< SCIP data structure */
703  SCIP_HEUR* heur, /**< pointer to heuristic*/
704  SCIP_SOL* sol, /**< heuristic solution */
705  SCIP_VAR** vars, /**< pointer to variables */
706  int nvars, /**< number of variables */
707  SCIP_VAR** linkvars, /**< pointer to linking variables */
708  int nlinkvars, /**< number of linking variables */
709  SCIP_SOL** newsol, /**< pointer to store improved solution */
710  SCIP_Bool* success /**< pointer to store whether reoptimization was successful */
711  )
712 {
713  SCIP* scipcopy;
714  SCIP_SOL* startsol;
715  SCIP_HASHMAP* varmap;
716  SCIP_VAR** subvars;
717  SCIP_STATUS status;
718  SCIP_Real* linkvals;
719  SCIP_Real time;
720  int v;
721 
722  assert(scip != NULL);
723  assert(heur != NULL);
724  assert(sol != NULL);
725  assert(vars != NULL);
726  assert(linkvars != NULL);
727 
728  SCIP_CALL( SCIPallocBufferArray(scip, &linkvals, nlinkvars) );
729  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, nvars) );
730 
731  SCIP_CALL( SCIPgetSolVals(scip, sol, nlinkvars, linkvars, linkvals) );
732 
733  /* initializing the problem copy*/
734  SCIP_CALL( SCIPcreate(&scipcopy) );
735 
736  /* - create the variable mapping hash map
737  * - create a problem copy of main SCIP
738  */
739  if( SCIPheurGetData(heur)->original )
740  {
741  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scipcopy), SCIPgetNOrigVars(scip)) );
742  SCIP_CALL( SCIPcopyOrigConsCompression(scip, scipcopy, varmap, NULL, "reopt_padm", linkvars, linkvals, nlinkvars,
743  FALSE, FALSE, TRUE, success) );
744  }
745  else
746  {
747  SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scipcopy), SCIPgetNVars(scip)) );
748  SCIP_CALL( SCIPcopyConsCompression(scip, scipcopy, varmap, NULL, "reopt_padm", linkvars, linkvals, nlinkvars,
749  TRUE, FALSE, FALSE, TRUE, success) );
750  }
751  for( v = 0; v < nvars; v++ )
752  {
753  subvars[v] = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[v]);
754  }
755 
756  /* do not abort subproblem on CTRL-C */
757  SCIP_CALL( SCIPsetBoolParam(scipcopy, "misc/catchctrlc", FALSE) );
758 
759  /* forbid recursive call of heuristics and separators solving sub-SCIPs */
760  SCIP_CALL( SCIPsetSubscipsOff(scipcopy, TRUE) );
761 
762 #ifdef SCIP_DEBUG
763  /* for debugging, enable full output */
764  SCIP_CALL( SCIPsetIntParam(scipcopy, "display/verblevel", 5) );
765  SCIP_CALL( SCIPsetIntParam(scipcopy, "display/freq", 100000000) );
766 #else
767  /* disable statistic timing inside sub SCIP and output to console */
768  SCIP_CALL( SCIPsetIntParam(scipcopy, "display/verblevel", 0) );
769  SCIP_CALL( SCIPsetBoolParam(scipcopy, "timing/statistictiming", FALSE) );
770 #endif
771 
772  /* disable cutting plane separation */
774 
775  /* disable expensive presolving but enable components presolver */
777  SCIP_CALL( SCIPsetIntParam(scipcopy, "constraints/components/maxprerounds", 1) );
778  SCIP_CALL( SCIPsetLongintParam(scipcopy, "constraints/components/nodelimit", 0LL) );
779 
780  /* disable expensive techniques */
781  SCIP_CALL( SCIPsetIntParam(scipcopy, "misc/usesymmetry", 0) );
782 
783  /* speed up sub-SCIP by not checking dual LP feasibility */
784  SCIP_CALL( SCIPsetBoolParam(scipcopy, "lp/checkdualfeas", FALSE) );
785 
786  /* add heuristic solution as start solution */
787  SCIP_CALL( SCIPtransformProb(scipcopy) );
788  *success = FALSE;
789  if( SCIPisLT(scip, SCIPgetSolOrigObj(scip, sol), SCIPinfinity(scip)) )
790  {
791  SCIP_CALL( SCIPcreateSol(scipcopy, &startsol, heur) );
792  for( v = 0; v < nvars; v++ )
793  {
794  SCIP_VAR* subvar;
795  subvar = (SCIP_VAR*) SCIPhashmapGetImage(varmap, vars[v]);
796  if( subvar != NULL )
797  {
798  SCIP_CALL( SCIPsetSolVal(scipcopy, startsol, subvar, SCIPgetSolVal(scip, sol, vars[v])) );
799  }
800  }
801 
802  SCIP_CALL( SCIPtrySolFree(scipcopy, &startsol, FALSE, FALSE, FALSE, FALSE, FALSE, success) );
803  if( *success )
804  SCIPdebugMsg(scip, "set start solution\n");
805  else
806  SCIPdebugMsg(scip, "start solution for reoptimizing is not feasible\n");
807  }
808 
809  /* set limits; do not use more time than the heuristic has already used */
810  SCIP_CALL( SCIPcopyLimits(scip, scipcopy) );
811  SCIP_CALL( SCIPsetLongintParam(scipcopy, "limits/nodes", 1LL) );
812  SCIP_CALL( SCIPgetRealParam(scipcopy, "limits/time", &time) );
813  if( SCIPheurGetTime(heur) < time - 1.0 )
814  {
815  SCIP_CALL( SCIPsetRealParam(scipcopy, "limits/time", SCIPheurGetTime(heur) + 1.0) );
816  }
817  if( *success )
818  {
819  SCIP_CALL( SCIPsetIntParam(scipcopy, "limits/bestsol", 2) ); /* first solution is start solution */
820  }
821  else
822  {
823  SCIP_CALL( SCIPsetIntParam(scipcopy, "limits/bestsol", 1) );
824  }
825 
826  /* reoptimize problem */
827  SCIP_CALL_ABORT( SCIPsolve(scipcopy) );
828  status = SCIPgetStatus(scipcopy);
829 
830  /* copy solution to main scip */
831  if( status == SCIP_STATUS_BESTSOLLIMIT || status == SCIP_STATUS_OPTIMAL )
832  {
833  SCIP_SOL* solcopy;
834 
835  solcopy = SCIPgetBestSol(scipcopy);
836  SCIP_CALL( SCIPtranslateSubSol(scip, scipcopy, solcopy, heur, subvars, newsol) );
837 
838  SCIPdebugMsg(scip, "Objective value of reoptimized solution %.2f\n", SCIPgetSolOrigObj(scip, *newsol));
839  *success = TRUE;
840  }
841  else
842  {
843  *success = FALSE;
844  }
845 
846  /* free data */
847  SCIPhashmapFree(&varmap);
848  SCIP_CALL( SCIPfree(&scipcopy) );
849  SCIPfreeBufferArray(scip, &subvars);
850  SCIPfreeBufferArray(scip, &linkvals);
851 
852  return SCIP_OKAY;
853 }
854 
855 /** rescales the penalty parameters
856  *
857  * A sigmoid function is a function with an "S"-shaped graph, e.g. S(x) = x/(1+|x|).
858  * In order to avoid numerical instabilities due to large penalty parameters we rescale them
859  * using the sigmoid function
860  * S(x) = (x - shift)/(flatness + |x - shift|) * (range/2) + offset.
861  * The parameters are mapped into the more controllable interval [lowestslack, range + lowestslack].
862  */
863 static
865  PROBLEM* problem, /**< block structure */
866  SET* linkvartoblocks, /**< linking variable to blocks set */
867  SET* blocktolinkvars, /**< block to linking variable set */
868  SCIP_HASHTABLE* htable, /**< hashtable containing blockinfo*/
869  SCIP_Real maxpenalty /**< maximum penalty parameter */
870  )
871 {
872  SCIP_Real shift;
873  SCIP_Real lowestslack;
874  SCIP_Real range;
875  SCIP_Real offset;
876  SCIP_Real flatness;
877  int b;
878  int i;
879  int k;
880 
881  shift = maxpenalty / 2.0;
882  lowestslack = 0.1;
883  range = 10.0;
884  offset = range / 2.0 + lowestslack;
885  flatness = maxpenalty / 10.0;
886 
887  for( b = 0; b < problem->nblocks; b++ )
888  {
889  for( i = 0; i < blocktolinkvars[b].size; i++ )
890  {
891  int linkvaridx;
892  linkvaridx = blocktolinkvars[b].indexes[i];
893 
894  for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
895  {
896  int b2;
897  b2 = linkvartoblocks[linkvaridx].indexes[k];
898 
899  if( b2 != b )
900  {
901  BLOCKINFO binfo;
902  BLOCKINFO* binfoout;
903  SCIP_Real oldcoeff;
904 
905  binfo.block = b;
906  binfo.otherblock = b2;
907  binfo.linkvaridx = linkvaridx;
908  binfoout = (BLOCKINFO*) SCIPhashtableRetrieve(htable, (void*) &binfo);
909  assert(binfoout != NULL);
910 
911  /* scale coefficient of positive slack variable */
912  oldcoeff = binfoout->slackposobjcoeff;
913  binfoout->slackposobjcoeff = ((oldcoeff - shift) / (flatness + REALABS(oldcoeff - shift))) * range / 2.0 + offset;
914 
915  /* scale coefficient of negative slack variable */
916  oldcoeff = binfoout->slacknegobjcoeff;
917  binfoout->slacknegobjcoeff = ((oldcoeff - shift) / (flatness + REALABS(oldcoeff - shift))) * range / 2.0 + offset;
918  }
919  }
920  }
921  }
922  return SCIP_OKAY;
923 }
924 
925 /** returns the available time limit that is left */
926 static
928  SCIP* scip, /**< SCIP data structure */
929  SCIP_Real* time /**< pointer to store remaining time */
930  )
931 {
932  SCIP_Real timelim;
933  SCIP_Real solvingtime;
934 
935  assert(scip != NULL);
936 
937  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelim) );
938  solvingtime = SCIPgetSolvingTime(scip);
939 
940  if( !SCIPisInfinity(scip, timelim) )
941  *time = MAX(0.0, (timelim - solvingtime));
942  else
943  *time = SCIPinfinity(scip);
944 
945  return SCIP_OKAY;
946 }
947 
948 /*
949  * Callback methods of primal heuristic
950  */
951 
952 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
953 static
954 SCIP_DECL_HEURCOPY(heurCopyPADM)
955 { /*lint --e{715}*/
956  assert(scip != NULL);
957  assert(heur != NULL);
958  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
959 
960  /* call inclusion method of primal heuristic */
962 
963  return SCIP_OKAY;
964 }
965 
966 
967 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
968 static
969 SCIP_DECL_HEURFREE(heurFreePADM)
970 { /*lint --e{715}*/
971  SCIP_HEURDATA* heurdata;
972 
973  heurdata = SCIPheurGetData(heur);
974  SCIPheurSetData(heur, NULL);
975 
976  assert(heurdata != NULL);
977 
978  SCIPfreeBlockMemory(scip, &heurdata);
979 
980  return SCIP_OKAY;
981 }
982 
983 
984 /** execution method of primal heuristic */
985 static SCIP_DECL_HEUREXEC(heurExecPADM)
986 { /*lint --e{715}*/
987  char name[SCIP_MAXSTRLEN];
988  char info[SCIP_MAXSTRLEN];
989  SCIP_HEURDATA* heurdata;
990  PROBLEM* problem;
991  SCIP_DECOMP** alldecomps;
992  SCIP_DECOMP* decomp;
993  SCIP_DECOMP* assigneddecomp;
994  SCIP_VAR** vars;
995  SCIP_VAR** linkvars;
996  SCIP_VAR** tmpcouplingvars;
997  SCIP_CONS** conss;
998  SCIP_CONS** sortedconss;
999  SET* linkvartoblocks;
1000  SET* blocktolinkvars;
1001  BLOCKINFO* blockinfolist;
1002  SCIP_HASHTABLE* htable;
1003  int* varlabels;
1004  int* conslabels;
1005  int* consssize;
1006  int* alllinkvartoblocks; /* for efficient memory allocation */
1007  SCIP_Bool* varonlyobj;
1008  SCIP_Real* tmpcouplingcoef;
1009  SCIP_Real gap;
1010  SCIP_Real maxpenalty;
1011  SCIP_Real slackthreshold;
1012  SCIP_Real memory; /* in MB */
1013  SCIP_Real timeleft;
1014  SCIP_STATUS status;
1015  SCIP_Bool solutionsdiffer;
1016  SCIP_Bool solved;
1017  SCIP_Bool doscaling;
1018  SCIP_Bool istimeleft;
1019  SCIP_Bool success;
1020  SCIP_Bool avoidmemout;
1021  SCIP_Bool disablemeasures;
1022  int maxgraphedge;
1023  int ndecomps;
1024  int nconss;
1025  int nvars;
1026  int nblocks;
1027  int numlinkvars;
1028  int nentries;
1029  int aiter;
1030  int piter;
1031  int increasedslacks;
1032  int blockinfolistfill;
1033  SCIP_Longint nodesleft;
1034  int i;
1035  int b;
1036  int k;
1037  int j;
1038 
1039  assert(scip != NULL);
1040  assert(heur != NULL);
1041  assert(result != NULL);
1042 
1043  heurdata = SCIPheurGetData(heur);
1044  assert(heurdata != NULL);
1045 
1046  *result = SCIP_DIDNOTRUN;
1047 
1048  problem = NULL;
1049  assigneddecomp = NULL;
1050  sortedconss = NULL;
1051  varlabels = NULL;
1052  conslabels = NULL;
1053  consssize = NULL;
1054  alllinkvartoblocks = NULL;
1055  linkvars = NULL;
1056  linkvartoblocks = NULL;
1057  blocktolinkvars = NULL;
1058  tmpcouplingvars = NULL;
1059  tmpcouplingcoef = NULL;
1060  varonlyobj = NULL;
1061  blockinfolist = NULL;
1062  htable = NULL;
1063 
1064  nodesleft = heurdata->maxnodes;
1065  gap = heurdata->gap;
1066 
1067  if( (heurtiming & SCIP_HEURTIMING_BEFORENODE) && heurdata->timing !=1 )
1068  {
1069  SCIPdebugMsg(scip, "Initialize padm heuristic before node\n");
1070  }
1071  else if( (heurtiming & SCIP_HEURTIMING_AFTERNODE) && heurdata->timing >=1 )
1072  {
1073  SCIPdebugMsg(scip, "Initialize padm heuristic after node\n");
1074  }
1075  else
1076  {
1077  return SCIP_OKAY;
1078  }
1079 
1080 #ifdef PADM_WRITE_PROBLEMS
1081  SCIP_CALL( SCIPwriteOrigProblem(scip, "orig_problem", NULL, FALSE) );
1082  SCIP_CALL( SCIPwriteTransProblem(scip, "trans_problem", NULL, FALSE) );
1083 #endif
1084 
1085  /* take original problem (This is only for testing and not recommended!) */
1086  if( heurdata->original )
1087  {
1088  /* multiaggregation of variables has to be switched off */
1089  if( !SCIPdoNotMultaggr(scip) )
1090  {
1091  SCIPwarningMessage(scip, "Heuristic %s does not support multiaggregation when the original problem is used.\nPlease turn multiaggregation off to use this feature.\n", HEUR_NAME);
1092  return SCIP_OKAY;
1093  }
1094 
1095  SCIPgetDecomps(scip, &alldecomps, &ndecomps, TRUE);
1096  if( ndecomps == 0)
1097  return SCIP_OKAY;
1098 
1099  /* it takes the first decomposition */
1100  decomp = alldecomps[0];
1101  SCIPdebugMsg(scip, "First original decomposition is selected\n");
1102  assert(decomp != NULL);
1103 
1104  nconss = SCIPgetNOrigConss(scip);
1105  conss = SCIPgetOrigConss(scip);
1106  nvars = SCIPgetNOrigVars(scip);
1107  vars = SCIPgetOrigVars(scip);
1108  }
1109  /* take transformed problem */
1110  else
1111  {
1112  SCIPgetDecomps(scip, &alldecomps, &ndecomps, FALSE);
1113  if( ndecomps == 0)
1114  return SCIP_OKAY;
1115 
1116  /* it takes the first decomposition */
1117  decomp = alldecomps[0];
1118  SCIPdebugMsg(scip, "First transformed decomposition is selected\n");
1119  assert(decomp != NULL);
1120 
1121  nconss = SCIPgetNConss(scip);
1122  conss = SCIPgetConss(scip);
1123  nvars = SCIPgetNVars(scip);
1124  vars = SCIPgetVars(scip);
1125  }
1126 
1127  nblocks = SCIPdecompGetNBlocks(decomp);
1128 
1129  /* if problem has no constraints, no variables or less than two blocks, return */
1130  if( nconss == 0 || nvars == 0 || nblocks <= 1 )
1131  {
1132  SCIPdebugMsg(scip, "problem has no constraints, no variables or less than two blocks\n");
1133  goto TERMINATE;
1134  }
1135 
1136  /* estimate required memory for all blocks and terminate if not enough memory is available */
1137  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memory) );
1138  SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) );
1139  if( avoidmemout && (((SCIPgetMemUsed(scip) + SCIPgetMemExternEstim(scip))/1048576.0) * nblocks >= memory) )
1140  {
1141  SCIPdebugMsg(scip, "The estimated memory usage for %d blocks is too large.\n", nblocks);
1142  goto TERMINATE;
1143  }
1144 
1145  /* we do not need the block decomposition graph and expensive measures of the decomposition statistics */
1146  SCIP_CALL( SCIPgetIntParam(scip, "decomposition/maxgraphedge", &maxgraphedge) );
1147  if( !SCIPisParamFixed(scip, "decomposition/maxgraphedge") )
1148  {
1149  SCIP_CALL( SCIPsetIntParam(scip, "decomposition/maxgraphedge", 0) );
1150  }
1151  SCIP_CALL( SCIPgetBoolParam(scip, "decomposition/disablemeasures", &disablemeasures) );
1152  if( !SCIPisParamFixed(scip, "decomposition/disablemeasures") )
1153  {
1154  SCIP_CALL( SCIPsetBoolParam(scip, "decomposition/disablemeasures", TRUE) );
1155  }
1156 
1157  /* don't change problem by sorting constraints */
1158  SCIP_CALL( SCIPduplicateBufferArray(scip, &sortedconss, conss, nconss) );
1159 
1160  SCIP_CALL( SCIPallocBufferArray(scip, &varlabels, nvars) );
1161  SCIP_CALL( SCIPallocBufferArray(scip, &conslabels, nconss) );
1162  SCIP_CALL( SCIPallocBufferArray(scip, &consssize, nblocks + 1) );
1163 
1164  SCIPdecompGetConsLabels(decomp, conss, conslabels, nconss);
1165  SCIPdecompGetVarsLabels(decomp, vars, varlabels, nvars);
1166 
1167  /* sort constraints by blocks */
1168  SCIPsortIntPtr(conslabels, (void**)sortedconss, nconss);
1169 
1170  /* try to assign linking constraints */
1171  if( heurdata->assignlinking && conslabels[0] == SCIP_DECOMP_LINKCONS )
1172  {
1173  /* create new decomposition; don't change the decompositions in the decompstore */
1174  SCIP_CALL( SCIPcreateDecomp(scip, &assigneddecomp, nblocks, heurdata->original, SCIPdecompUseBendersLabels(decomp)) );
1175 
1176  SCIP_CALL( assignLinking(scip, assigneddecomp, vars, sortedconss, varlabels, conslabels, nvars, nconss, SCIPdecompGetNBorderConss(decomp)) );
1177  assert(SCIPdecompGetNBlocks(decomp) >= SCIPdecompGetNBlocks(assigneddecomp));
1178  decomp = assigneddecomp;
1179 
1180  /* number of blocks can get smaller (since assigning constraints can lead to empty blocks) */
1181  nblocks = SCIPdecompGetNBlocks(decomp);
1182  }
1183  else
1184  {
1185  /* The decomposition statistics were computed during transformation of the decomposition store.
1186  * Since propagators can have changed the number of constraints/variables,
1187  * the statistics are no longer up-to-date and have to be recomputed.
1188  */
1190  nblocks = SCIPdecompGetNBlocks(decomp);
1191  }
1192 
1193  /* reset parameters */
1194  SCIP_CALL( SCIPsetIntParam(scip, "decomposition/maxgraphedge", maxgraphedge) );
1195  SCIP_CALL( SCIPsetBoolParam(scip, "decomposition/disablemeasures", disablemeasures) );
1196 
1197  /* @note the terms 'linking' and 'border' (constraints/variables) are used interchangeably */
1198 
1199  if( SCIPdecompGetNBorderConss(decomp) != 0 )
1200  {
1201  SCIPdebugMsg(scip, "No support for linking contraints\n");
1202  goto TERMINATE;
1203  }
1204 
1205  /* get number of linking variables */
1206  numlinkvars = SCIPdecompGetNBorderVars(decomp);
1207  SCIPdebugMsg(scip, "%d linking variables\n", numlinkvars);
1208 
1209  if( numlinkvars == 0 )
1210  {
1211  SCIPdebugMsg(scip, "No linking variables\n");
1212  goto TERMINATE;
1213  }
1214 
1215  *result = SCIP_DIDNOTFIND;
1216 
1217  /* get for every block the number of constraints (first entry belongs to border) */
1218  SCIP_CALL( SCIPdecompGetConssSize(decomp, consssize, nblocks + 1) );
1219 
1220  /* create blockproblems */
1221  SCIP_CALL( createAndSplitProblem(scip, sortedconss, nconss, consssize, nblocks, &problem, heurdata->original, &success) );
1222 
1223  if( !success )
1224  {
1225  SCIPdebugMsg(scip, "Some subscips could not be created successfully.\n");
1226  goto TERMINATE;
1227  }
1228 
1229  SCIP_CALL( SCIPallocBufferArray(scip, &linkvartoblocks, numlinkvars) );
1230  SCIP_CALL( SCIPallocBufferArray(scip, &blocktolinkvars, problem->nblocks) );
1231 
1232  /* set pointer to NULL for safe memory release */
1233  for( i = 0; i < numlinkvars; i++ )
1234  linkvartoblocks[i].indexes = NULL;
1235  for( i = 0; i < problem->nblocks; i++ )
1236  blocktolinkvars[i].indexes = NULL;
1237 
1238  /* extract linking variables and init linking variable to blocks set */
1239  SCIP_CALL( SCIPallocBufferArray(scip, &alllinkvartoblocks, problem->nblocks * numlinkvars) );
1240  SCIP_CALL( SCIPallocBufferArray(scip, &linkvars, numlinkvars) );
1241 
1242  b = 0;
1243  for( i = 0; i < nvars; i++ )
1244  {
1245  if( varlabels[i] == SCIP_DECOMP_LINKVAR )
1246  {
1247  linkvars[b] = vars[i];
1248  linkvartoblocks[b].indexes = &alllinkvartoblocks[b * problem->nblocks];
1249  linkvartoblocks[b].size = 0;
1250  b++;
1251  }
1252  }
1253 
1254  /* fill linking variable to blocks set */
1255  for( i = 0; i < numlinkvars; i++ )
1256  {
1257  SCIP_VAR* var;
1258  const char* vname;
1259 
1260  vname = SCIPvarGetName(linkvars[i]);
1261  k = 0;
1262  for( b = 0; b < problem->nblocks; b++ )
1263  {
1264  var = SCIPfindVar((problem->blocks[b]).subscip, vname);
1265  if( var != NULL )
1266  {
1267  linkvartoblocks[i].indexes[k] = b;
1268  linkvartoblocks[i].size = k + 1;
1269  k++;
1270  }
1271  }
1272  }
1273 
1274  /* check whether there is enough time left */
1275  SCIP_CALL( getTimeLeft(scip, &timeleft) );
1276  if( timeleft <= 0 )
1277  {
1278  SCIPdebugMsg(scip, "no time left\n");
1279  goto TERMINATE;
1280  }
1281 
1282  /* init varonlyobj; true if variable is only part of the objective function */
1283  SCIP_CALL( SCIPallocBufferArray(scip, &varonlyobj, numlinkvars) );
1284  for( i = 0; i < numlinkvars; ++i)
1285  varonlyobj[i] = TRUE;
1286 
1287  /* init and fill block to linking variables set */
1288  for( b = 0; b < problem->nblocks; b++ )
1289  {
1290  SCIP_CALL( SCIPallocBufferArray(scip, &(blocktolinkvars[b].indexes), numlinkvars) );
1291  blocktolinkvars[b].size = 0;
1292 
1293  k = 0;
1294  for( i = 0; i < numlinkvars; i++ )
1295  {
1296  SCIP_VAR* var;
1297  const char* vname;
1298 
1299  vname = SCIPvarGetName(linkvars[i]);
1300  var = SCIPfindVar((problem->blocks[b]).subscip, vname);
1301  if( var != NULL )
1302  {
1303  varonlyobj[i] = FALSE;
1304  blocktolinkvars[b].indexes[k] = i;
1305  blocktolinkvars[b].size = k + 1;
1306  k++;
1307  }
1308  }
1309  }
1310 
1311  /* init arrays for slack variables and coupling constraints */
1312  for( b = 0; b < problem->nblocks; b++ )
1313  {
1314  SCIP_CALL( SCIPallocBufferArray(scip, &((problem->blocks[b]).slackspos), blocktolinkvars[b].size * (nblocks - 1)) );
1315  SCIP_CALL( SCIPallocBufferArray(scip, &((problem->blocks[b]).slacksneg), blocktolinkvars[b].size * (nblocks - 1)) );
1316  SCIP_CALL( SCIPallocBufferArray(scip, &((problem->blocks[b]).couplingcons), blocktolinkvars[b].size * (nblocks - 1)) );
1317  }
1318 
1319  SCIP_CALL( SCIPallocBufferArray(scip, &tmpcouplingvars, COUPLINGSIZE) );
1320  SCIP_CALL( SCIPallocBufferArray(scip, &tmpcouplingcoef, COUPLINGSIZE) );
1321  tmpcouplingcoef[0] = 1.0;
1322  tmpcouplingcoef[1] = 1.0;
1323  tmpcouplingcoef[2] = -1.0;
1324 
1325  /* count hashtable entries */
1326  nentries = 0;
1327  for( b = 0; b < problem->nblocks; b++ )
1328  {
1329  for( i = 0; i < blocktolinkvars[b].size; i++ )
1330  {
1331  int linkvaridx = blocktolinkvars[b].indexes[i];
1332  for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
1333  {
1334  if( linkvartoblocks[linkvaridx].indexes[k] != b )
1335  nentries++;
1336  }
1337  }
1338  }
1339 
1340  SCIP_CALL( SCIPallocBufferArray(scip, &blockinfolist, nentries) );
1341  SCIP_CALL( SCIPhashtableCreate(&htable, SCIPblkmem(scip), 1, SCIPhashGetKeyStandard, indexesEqual, indexesHashval, (void*) scip) );
1342  blockinfolistfill = 0;
1343 
1344  /* extend submips */
1345  SCIPdebugMsg(scip, "Extending %d block models\n", problem->nblocks);
1346  for( b = 0; b < problem->nblocks; b++ )
1347  {
1348  SCIP_VAR** blockvars;
1349  int nblockvars;
1350 
1351  blockvars = SCIPgetVars((problem->blocks[b]).subscip);
1352  nblockvars = SCIPgetNVars((problem->blocks[b]).subscip);
1353 
1354  /* set objective function of each block to zero */
1355  for( i = 0; i < nblockvars; i++ )
1356  {
1357  SCIP_CALL( SCIPchgVarObj((problem->blocks[b]).subscip, blockvars[i], 0.0) );
1358  }
1359 
1360  /* add two slack variables for each linking variable in block */
1361  for( i = 0; i < blocktolinkvars[b].size; i++ )
1362  {
1363  int linkvaridx;
1364  linkvaridx = blocktolinkvars[b].indexes[i];
1365 
1366  for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
1367  {
1368  int b2;
1369  b2 = linkvartoblocks[linkvaridx].indexes[k];
1370 
1371  /* handle different blocks with common linking variable */
1372  if( b2 != b )
1373  {
1374  BLOCKINFO* binfo;
1375  binfo = &blockinfolist[blockinfolistfill];
1376  blockinfolistfill++;
1377  binfo->block = b;
1378  binfo->otherblock = b2;
1379  binfo->linkvaridx = linkvaridx;
1380  binfo->linkvar = SCIPfindVar((problem->blocks[b]).subscip, SCIPvarGetName(linkvars[linkvaridx]));
1381  j = (problem->blocks[b]).ncoupling;
1382 
1383  /* create positive slack variable */
1384  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_slackpos_block_%d", SCIPvarGetName(linkvars[linkvaridx]), b2);
1385  (problem->blocks[b]).slackspos[j] = NULL;
1386  SCIP_CALL( SCIPcreateVarBasic((problem->blocks[b]).subscip,
1387  &((problem->blocks[b]).slackspos[j]), name,
1388  0.0, SCIPinfinity(scip), 1.0, SCIP_VARTYPE_CONTINUOUS) );
1389  SCIP_CALL( SCIPaddVar((problem->blocks[b]).subscip, (problem->blocks[b]).slackspos[j]) );
1390  assert((problem->blocks[b]).slackspos[j] != NULL);
1391  binfo->slackposobjcoeff = 1.0;
1392  binfo->slackposvar = (problem->blocks[b]).slackspos[j];
1393 
1394  /* create negative slack variable */
1395  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_slackneg_block_%d", SCIPvarGetName(linkvars[linkvaridx]), b2);
1396  (problem->blocks[b]).slacksneg[j] = NULL;
1397  SCIP_CALL( SCIPcreateVarBasic((problem->blocks[b]).subscip,
1398  &((problem->blocks[b]).slacksneg[j]), name,
1399  0.0, SCIPinfinity(scip), 1.0, SCIP_VARTYPE_CONTINUOUS) );
1400  SCIP_CALL( SCIPaddVar((problem->blocks[b]).subscip, (problem->blocks[b]).slacksneg[j]) );
1401  assert((problem->blocks[b]).slacksneg[j] != NULL);
1402  binfo->slacknegobjcoeff = 1.0;
1403  binfo->slacknegvar = (problem->blocks[b]).slacksneg[j];
1404 
1405  /* fill variables for linking constraint */
1406  tmpcouplingvars[0] = binfo->linkvar;
1407  tmpcouplingvars[1] = binfo->slackposvar;
1408  tmpcouplingvars[2] = binfo->slacknegvar;
1409 
1410  /* create linking constraint */
1411  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_coupling_block_%d",
1412  SCIPvarGetName(linkvars[linkvaridx]), b2);
1413  (problem->blocks[b]).couplingcons[j] = NULL;
1414 
1415  /* create linking constraint with initial side equal to zero (or lower bound of linking variable) */
1416  if( heurtiming & SCIP_HEURTIMING_BEFORENODE )
1417  {
1418  SCIP_Real initval;
1419  SCIP_Real lb;
1420 
1421  lb = SCIPvarGetLbOriginal(binfo->linkvar);
1422  initval = MAX(lb, 0.0);
1423 
1424  SCIP_CALL( SCIPcreateConsBasicLinear((problem->blocks[b]).subscip, &((problem->blocks[b]).couplingcons[j]),
1425  name, COUPLINGSIZE, tmpcouplingvars, tmpcouplingcoef, initval, initval) );
1426 
1427  /* set initial value of linking variable */
1428  binfo->linkvarval = initval;
1429  }
1430 
1431  /* create linking constraint with initial side equal to LP solution (rounded if variable is integer) */
1432  if( heurtiming & SCIP_HEURTIMING_AFTERNODE )
1433  {
1434  SCIP_Real initval;
1435 
1436  initval = SCIPvarGetLPSol(linkvars[linkvaridx]);
1438  initval = SCIPround(scip, initval);
1439 
1440  SCIP_CALL( SCIPcreateConsBasicLinear((problem->blocks[b]).subscip, &((problem->blocks[b]).couplingcons[j]),
1441  name, COUPLINGSIZE, tmpcouplingvars, tmpcouplingcoef, initval, initval) );
1442 
1443  /* set initial value of linking variable */
1444  binfo->linkvarval = initval;
1445  }
1446 
1447  SCIP_CALL( SCIPaddCons((problem->blocks[b]).subscip, (problem->blocks[b]).couplingcons[j]) );
1448  assert((problem->blocks[b]).couplingcons[j] != NULL);
1449  binfo->couplingCons = (problem->blocks[b]).couplingcons[j];
1450 
1451  (problem->blocks[b]).ncoupling++;
1452 
1453  /* feed hashtable */
1454  SCIP_CALL( SCIPhashtableSafeInsert(htable, (void*) binfo) );
1455  }
1456  }
1457  }
1458  }
1459  assert(nentries == SCIPhashtableGetNElements(htable));
1460 
1461 #ifdef PADM_WRITE_PROBLEMS
1462  /* write extended submips */
1463  for( b = 0; b < problem->nblocks; b++ )
1464  {
1465  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "extended_block_%d.lp", b);
1466  SCIP_CALL( SCIPwriteOrigProblem((problem->blocks[b]).subscip, name, NULL, FALSE) );
1467  }
1468 #endif
1469 
1470  /* determine threshold for penalty coefficients via maximum norm */
1471  slackthreshold = SCIP_REAL_MIN;
1472  for( i = 0; i < nvars; i++ )
1473  {
1474  SCIP_Real obj;
1475 
1476  obj = REALABS(SCIPvarGetObj(vars[i]));
1477  if( obj > slackthreshold )
1478  slackthreshold = obj;
1479  }
1480 
1481  /* ------------------------------------------------------------------------------------------------- */
1482 
1483  /* check whether there is enough time left */
1484  SCIP_CALL( getTimeLeft(scip, &timeleft) );
1485  if( timeleft <= 0 )
1486  {
1487  SCIPdebugMsg(scip, "no time left\n");
1488  goto TERMINATE;
1489  }
1490 
1491  SCIPdebugMsg(scip, "Starting iterations\n");
1492  SCIPdebugMsg(scip, "PIt\tADMIt\tSlacks\tInfo\n");
1493 
1494  piter = 0;
1495  increasedslacks = 0;
1496  (void) SCIPsnprintf(info, SCIP_MAXSTRLEN, "-");
1497  solved = FALSE;
1498  istimeleft = TRUE;
1499 
1500  /* Penalty loop */
1501  while( !solved && piter < heurdata->penaltyiterations && istimeleft )
1502  {
1503  piter++;
1504  solutionsdiffer = TRUE;
1505  aiter = 0;
1506 
1507  /* Alternating direction method loop */
1508  while( solutionsdiffer && aiter < heurdata->admiterations && istimeleft )
1509  {
1510  aiter++;
1511  solutionsdiffer = FALSE;
1512  SCIPdebugMsg(scip, "%d\t%d\t%d\t%s\n", piter, aiter, increasedslacks, info);
1513 
1514  /* Loop through the blocks and solve each sub-SCIP, potentially multiple times */
1515  for( b = 0; b < problem->nblocks; b++ )
1516  {
1517  for( i = 0; i < blocktolinkvars[b].size; i++ )
1518  {
1519  int linkvaridx;
1520  linkvaridx = blocktolinkvars[b].indexes[i];
1521 
1522  for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
1523  {
1524  int b2;
1525  b2 = linkvartoblocks[linkvaridx].indexes[k];
1526 
1527  if( b2 != b )
1528  {
1529  BLOCKINFO binfo;
1530  BLOCKINFO* binfoout;
1531  BLOCKINFO binfo2;
1532  BLOCKINFO* binfo2out;
1533 
1535  SCIP_Real newrhs;
1536 
1537  binfo.block = b;
1538  binfo.otherblock = b2;
1539  binfo.linkvaridx = linkvaridx;
1540 
1541  binfoout = (BLOCKINFO*) SCIPhashtableRetrieve(htable, (void *)&binfo);
1542  assert(binfoout != NULL);
1543  couplingcons = binfoout->couplingCons;
1544 
1545  /* interchange blocks b and b2 for getting new right hand side */
1546  binfo2.block = b2;
1547  binfo2.otherblock = b;
1548  binfo2.linkvaridx = linkvaridx;
1549  binfo2out = (BLOCKINFO*) SCIPhashtableRetrieve(htable, (void*) &binfo2);
1550  assert(binfo2out != NULL);
1551  newrhs = binfo2out->linkvarval;
1552 
1553  /* change side of coupling constraint equation with linking variable value of the other block */
1554  SCIP_CALL( SCIPchgLhsLinear((problem->blocks[b]).subscip, couplingcons, newrhs) );
1555  SCIP_CALL( SCIPchgRhsLinear((problem->blocks[b]).subscip, couplingcons, newrhs) );
1556 
1557  /* change penalty coefficients of slack variables */
1558  SCIP_CALL( SCIPchgVarObj((problem->blocks[b]).subscip, binfoout->slackposvar, binfoout->slackposobjcoeff) );
1559  SCIP_CALL( SCIPchgVarObj((problem->blocks[b]).subscip, binfoout->slacknegvar, binfoout->slacknegobjcoeff) );
1560  }
1561  }
1562  }
1563 
1564  /* increase slack penalty coeffs until each subproblem can be solved to optimality */
1565  do
1566  {
1568  int iteration;
1569 
1570 #ifdef PADM_WRITE_PROBLEMS
1571  SCIPdebugMsg(scip, "write subscip of block %d in piter=%d and aiter=%d\n", b, piter, aiter);
1572  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "blockproblem_%d_%d_%d.lp", b, piter, aiter);
1573  SCIP_CALL( SCIPwriteOrigProblem((problem->blocks[b]).subscip, name, NULL, FALSE) );
1574 #endif
1575 
1576  SCIP_CALL( SCIPsetRealParam((problem->blocks[b]).subscip, "limits/gap", gap) );
1577 
1578  /* reuse old solution if available */
1579  SCIP_CALL( reuseSolution((problem->blocks[b]).subscip, &problem->blocks[b]) );
1580 
1581  /* update time and memory limit of subproblem */
1582  SCIP_CALL( SCIPcopyLimits(scip, (problem->blocks[b]).subscip) );
1583 
1584  /* stop if there are not enough nodes left */
1585  if( nodesleft < heurdata->minnodes )
1586  {
1587  SCIPdebugMsg(scip, "Node limit reached.\n");
1588  goto TERMINATE;
1589  }
1590 
1591  /* update node limit of subproblem
1592  * in the first iterations we have a smaller node limit
1593  */
1594  iteration = ((piter - 1) * heurdata->admiterations) + aiter;
1595  nnodes = (SCIP_Longint)SCIPceil(scip, (problem->blocks[b]).size * nodesleft * ( 1 - pow(heurdata->nodefac, (double)iteration) ));
1596  nnodes = MAX( heurdata->minnodes, nnodes );
1597  SCIP_CALL( SCIPsetLongintParam((problem->blocks[b]).subscip, "limits/nodes", nnodes) );
1598 
1599  /* solve block
1600  *
1601  * errors in solving the subproblem should not kill the overall solving process;
1602  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
1603  */
1604  SCIP_CALL_ABORT( SCIPsolve((problem->blocks[b]).subscip) );
1605  status = SCIPgetStatus((problem->blocks[b]).subscip);
1606 
1607  /* subtract used nodes from the total nodelimit */
1608  nodesleft -= (SCIP_Longint)SCIPceil(scip, SCIPgetNNodes((problem->blocks[b]).subscip) * (problem->blocks[b]).size);
1609 
1610  /* check solution if one of the four cases occurs
1611  * - solution is optimal
1612  * - solution reached gaplimit
1613  * - node limit reached with at least one feasible solution
1614  * - time limit is reached but best solution needs no slack variables (no dual solution available)
1615  */
1616  if( status == SCIP_STATUS_OPTIMAL || status == SCIP_STATUS_GAPLIMIT ||
1617  (status == SCIP_STATUS_NODELIMIT && SCIPgetNSols((problem->blocks[b]).subscip) > 0) ||
1618  (status == SCIP_STATUS_TIMELIMIT && SCIPgetNSols((problem->blocks[b]).subscip) > 0 &&
1619  SCIPisEQ(scip, SCIPgetSolOrigObj((problem->blocks[b]).subscip, SCIPgetBestSol((problem->blocks[b]).subscip)), 0.0) ) )
1620  {
1621  SCIPdebugMsg(scip, "Block is optimal or reached gaplimit or nodelimit.\n");
1622 
1623  if( status == SCIP_STATUS_TIMELIMIT )
1624  {
1625  SCIPdebugMsg(scip, "Block reached time limit with at least one feasible solution.\n");
1626  istimeleft = FALSE;
1627  }
1628 
1629  for( i = 0; i < blocktolinkvars[b].size; i++ )
1630  {
1631  int linkvaridx;
1632  linkvaridx = blocktolinkvars[b].indexes[i];
1633 
1634  for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
1635  {
1636  int b2;
1637  b2 = linkvartoblocks[linkvaridx].indexes[k];
1638 
1639  if( b2 != b )
1640  {
1641  SCIP_SOL* sol;
1642  BLOCKINFO binfo;
1643  BLOCKINFO* binfoout;
1644  SCIP_VAR* var;
1645  SCIP_Real val;
1646 
1647  binfo.block = b;
1648  binfo.otherblock = b2;
1649  binfo.linkvaridx = linkvaridx;
1650  binfoout = (BLOCKINFO *)SCIPhashtableRetrieve(htable, (void *)&binfo);
1651  assert(binfoout != NULL);
1652 
1653  sol = SCIPgetBestSol((problem->blocks[b]).subscip);
1654  assert(sol != NULL);
1655  var = binfoout->linkvar;
1656  val = SCIPgetSolVal((problem->blocks[b]).subscip, sol, var);
1657 
1658  if( !EPSEQ(binfoout->linkvarval, val, SCIP_DEFAULT_EPSILON) )
1659  solutionsdiffer = TRUE;
1660 
1661  binfoout->linkvarval = val;
1662  }
1663  }
1664  }
1665  }
1666  else if( status == SCIP_STATUS_UNBOUNDED )
1667  {
1668  SCIPdebugMsg(scip, "Block is unbounded.\n");
1669  for( i = 0; i < blocktolinkvars[b].size; i++ )
1670  {
1671  int linkvaridx;
1672  linkvaridx = blocktolinkvars[b].indexes[i];
1673 
1674  for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
1675  {
1676  int b2;
1677  b2 = linkvartoblocks[linkvaridx].indexes[k];
1678 
1679  if( b2 != b )
1680  {
1681  BLOCKINFO binfo;
1682  BLOCKINFO* binfoout;
1683 
1684  binfo.block = b;
1685  binfo.otherblock = b2;
1686  binfo.linkvaridx = linkvaridx;
1687  binfoout = (BLOCKINFO*) SCIPhashtableRetrieve(htable, (void*) &binfo);
1688  assert(binfoout != NULL);
1689 
1690  /* increase penalty coefficients to obtain a bounded subproblem */
1691  binfoout->slackposobjcoeff *= 10.0;
1692  binfoout->slacknegobjcoeff *= 10.0;
1693  SCIP_CALL( SCIPchgVarObj((problem->blocks[b]).subscip, binfoout->slackposvar, binfoout->slackposobjcoeff) );
1694  SCIP_CALL( SCIPchgVarObj((problem->blocks[b]).subscip, binfoout->slacknegvar, binfoout->slacknegobjcoeff) );
1695  }
1696  }
1697  }
1698  }
1699  else if( status == SCIP_STATUS_TIMELIMIT )
1700  {
1701  SCIPdebugMsg(scip, "Block reached time limit. No optimal solution available.\n");
1702  goto TERMINATE;
1703  }
1704  else
1705  {
1706  SCIPdebugMsg(scip, "Block solving status %d not supported\n", status);
1707  goto TERMINATE;
1708  }
1709 
1710  /* free solving data in order to change problem */
1711  SCIP_CALL( SCIPfreeTransform((problem->blocks[b]).subscip) );
1712  }
1713  while( status != SCIP_STATUS_OPTIMAL && status != SCIP_STATUS_GAPLIMIT &&
1714  !(status == SCIP_STATUS_NODELIMIT && SCIPgetNSols((problem->blocks[b]).subscip) > 0) &&
1715  !(status == SCIP_STATUS_TIMELIMIT && SCIPgetNSols((problem->blocks[b]).subscip) > 0 &&
1716  SCIPisEQ(scip, SCIPgetSolOrigObj((problem->blocks[b]).subscip, SCIPgetBestSol((problem->blocks[b]).subscip)), 0.0) ) );
1717  }
1718  }
1719 
1720  /* check wether problem has been solved and if not update penalty coeffs */
1721  doscaling = FALSE;
1722  solved = TRUE;
1723  increasedslacks = 0;
1724  maxpenalty = SCIP_REAL_MIN;
1725  for( b = 0; b < problem->nblocks; b++ )
1726  {
1727  for( i = 0; i < blocktolinkvars[b].size; i++ )
1728  {
1729  int linkvaridx;
1730  linkvaridx = blocktolinkvars[b].indexes[i];
1731 
1732  for( k = 0; k < linkvartoblocks[linkvaridx].size; k++ )
1733  {
1734  int b2;
1735  b2 = linkvartoblocks[linkvaridx].indexes[k];
1736 
1737  if( b2 != b )
1738  {
1739  SCIP_SOL* sol;
1740  BLOCKINFO binfo;
1741  BLOCKINFO* binfoout;
1742  SCIP_Real slackposval;
1743  SCIP_Real slacknegval;
1744 
1745  binfo.block = b;
1746  binfo.otherblock = b2;
1747  binfo.linkvaridx = linkvaridx;
1748  binfoout = (BLOCKINFO*) SCIPhashtableRetrieve(htable, (void*) &binfo);
1749  assert(binfoout != NULL);
1750 
1751  sol = SCIPgetBestSol((problem->blocks[b]).subscip);
1752  slackposval = SCIPgetSolVal((problem->blocks[b]).subscip, sol, binfoout->slackposvar);
1753  slacknegval = SCIPgetSolVal((problem->blocks[b]).subscip, sol, binfoout->slacknegvar);
1754 
1755  /* increase penalty coefficient of positive slack variable */
1756  if( SCIPisGT(scip, slackposval, 0.0) )
1757  {
1758  binfoout->slackposobjcoeff *= 10.0;
1759 
1760  if( binfoout->slackposobjcoeff > slackthreshold )
1761  doscaling = TRUE;
1762 
1763  if( binfoout->slackposobjcoeff > maxpenalty )
1764  maxpenalty = binfoout->slackposobjcoeff;
1765 
1766  solved = FALSE;
1767  increasedslacks++;
1768  }
1769 
1770  /* increase penalty coefficient of negative slack variable */
1771  if( SCIPisGT(scip, slacknegval, 0.0) )
1772  {
1773  binfoout->slacknegobjcoeff *= 10.0;
1774 
1775  if( binfoout->slacknegobjcoeff > slackthreshold )
1776  doscaling = TRUE;
1777 
1778  if( binfoout->slacknegobjcoeff > maxpenalty )
1779  maxpenalty = binfoout->slacknegobjcoeff;
1780 
1781  solved = FALSE;
1782  increasedslacks++;
1783  }
1784  }
1785  }
1786  }
1787  }
1788 
1789  /* should sigmoid scaling be applied to the penalty parameters? */
1790  if( doscaling && heurdata->scaling )
1791  {
1792  SCIPdebugMsg(scip, "rescale penalty parameters\n");
1793 
1794  /* reset counter */
1795  increasedslacks = 0;
1796 
1797  /* rescale penalty parameters */
1798  SCIP_CALL( scalePenalties(problem, linkvartoblocks, blocktolinkvars, htable, maxpenalty) );
1799  }
1800 
1801  /* adapt in some cases the gap parameter */
1802  if( (aiter == 1 && solutionsdiffer == FALSE) || (doscaling && heurdata->scaling) )
1803  {
1804  SCIP_Real mingap = 0.001; //todo
1805  SCIP_Real newgap = MAX(gap * 0.5, mingap);
1806 
1807  if( newgap >= mingap )
1808  {
1809  if( doscaling && heurdata->scaling )
1810  (void) SCIPsnprintf(info, SCIP_MAXSTRLEN, "scale, %f", newgap);
1811  else
1812  (void) SCIPsnprintf(info, SCIP_MAXSTRLEN, "%f", newgap);
1813 
1814  gap = newgap;
1815  }
1816  }
1817 
1818  /* free solution process data */
1819  if( !solved )
1820  for( b = 0; b < problem->nblocks; b++ )
1821  {
1822  SCIP_CALL( SCIPfreeTransform((problem->blocks[b]).subscip) );
1823  }
1824  }
1825 
1826  /* copy solution if present */
1827  if( solved )
1828  {
1829  SCIP_SOL* newsol;
1830  SCIP_Real* blocksolvals;
1831 
1832  assert(increasedslacks == 0);
1833 
1834  SCIP_CALL( SCIPallocBufferArray(scip, &blocksolvals, nvars) );
1835  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
1836 
1837  for( b = 0; b < problem->nblocks; b++ )
1838  {
1839  SCIP_SOL* blocksol;
1840  SCIP_VAR** blockvars;
1841  int nblockvars;
1842 
1843  /* get solution of block variables (without slack variables) */
1844  blocksol = SCIPgetBestSol((problem->blocks[b]).subscip);
1845  assert(blocksol != NULL);
1846  blockvars = (problem->blocks[b]).subvars;
1847  nblockvars = (problem->blocks[b]).nsubvars;
1848  SCIP_CALL( SCIPgetSolVals((problem->blocks[b]).subscip, blocksol, nblockvars, blockvars, blocksolvals) );
1849 
1850  for( i = 0; i < nblockvars; i++ )
1851  {
1852  SCIP_VAR* origvar;
1853  SCIP_Real solval;
1854 
1855  origvar = SCIPfindVar(scip, SCIPvarGetName(blockvars[i]));
1856  solval = blocksolvals[i];
1857  SCIP_CALL_ABORT( SCIPsetSolVal(scip, newsol, origvar, solval) );
1858  }
1859  }
1860 
1861  /* treat variables with no constraints; set value of variable to bound */
1862  for( i = 0; i < numlinkvars; i++ )
1863  {
1864  if( varonlyobj[i] )
1865  {
1866  SCIP_Real fixedvalue;
1867  if( SCIPvarGetObj(linkvars[i]) < 0 )
1868  {
1869  fixedvalue = SCIPvarGetUbLocal(linkvars[i]);
1870  if( SCIPisInfinity(scip, fixedvalue) )
1871  break; // todo: maybe we should return the status UNBOUNDED instead
1872  }
1873  else
1874  {
1875  fixedvalue = SCIPvarGetLbLocal(linkvars[i]);
1876  if( SCIPisInfinity(scip, fixedvalue) )
1877  break; // todo: maybe we should return the status UNBOUNDED instead
1878  }
1879  SCIP_CALL_ABORT( SCIPsetSolVal(scip, newsol, linkvars[i], fixedvalue) );
1880  }
1881  }
1882 
1883  SCIPdebugMsg(scip, "Objective value %.2f\n", SCIPgetSolOrigObj(scip, newsol));
1884 
1885  /* fix linking variables and reoptimize with original objective function */
1886  if( heurdata->reoptimize )
1887  {
1888  SCIP_SOL* improvedsol = NULL;
1889  SCIP_CALL( reoptimize(scip, heur, newsol, vars, nvars, linkvars, numlinkvars, &improvedsol, &success) );
1890  assert(improvedsol != NULL || success == FALSE);
1891 
1892  if( success )
1893  {
1894  SCIP_CALL( SCIPtrySolFree(scip, &improvedsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
1895  if( !success )
1896  {
1897  SCIPdebugMsg(scip, "Reoptimizing solution failed\n");
1898  }
1899  else
1900  {
1901  SCIPdebugMsg(scip, "Reoptimizing solution successful\n");
1902  *result = SCIP_FOUNDSOL;
1903  }
1904  }
1905  }
1906 
1907  /* if reoptimization is turned off or reoptimization found no solution, try initial solution */
1908  if( *result != SCIP_FOUNDSOL )
1909  {
1910  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
1911  if( !success )
1912  {
1913  SCIPdebugMsg(scip, "Solution copy failed\n");
1914  }
1915  else
1916  {
1917  SCIPdebugMsg(scip, "Solution copy successful\n");
1918  *result = SCIP_FOUNDSOL;
1919  }
1920  }
1921  else
1922  {
1923  SCIP_CALL( SCIPfreeSol(scip, &newsol) );
1924  }
1925 
1926  SCIPfreeBufferArray(scip, &blocksolvals);
1927  }
1928  else
1929  {
1930  SCIPdebugMsg(scip, "maximum number of penalty loops reached\n");
1931  *result = SCIP_DIDNOTFIND;
1932  }
1933 
1934 TERMINATE:
1935  /* release variables, constraints and free memory */
1936  if( problem != NULL )
1937  {
1938  for( b = 0; b < problem->nblocks; b++ )
1939  {
1940  BLOCK curr_block = problem->blocks[b];
1941  for( i = 0; i < (problem->blocks[b]).ncoupling; i++ )
1942  {
1943  SCIP_CALL( SCIPreleaseCons(curr_block.subscip, &curr_block.couplingcons[i]) );
1944  SCIP_CALL( SCIPreleaseVar(curr_block.subscip, &curr_block.slackspos[i]) );
1945  SCIP_CALL( SCIPreleaseVar(curr_block.subscip, &curr_block.slacksneg[i]) );
1946  }
1947  }
1948  }
1949 
1950  if( htable != NULL )
1951  SCIPhashtableFree(&htable);
1952 
1953  if( blockinfolist != NULL )
1954  SCIPfreeBufferArray(scip, &blockinfolist);
1955 
1956  if( tmpcouplingcoef != NULL )
1957  SCIPfreeBufferArray(scip, &tmpcouplingcoef);
1958 
1959  if( tmpcouplingvars != NULL )
1960  SCIPfreeBufferArray(scip, &tmpcouplingvars);
1961 
1962  if( problem != NULL )
1963  {
1964  for( b = problem->nblocks - 1; b >= 0; b-- )
1965  {
1966  if( problem->blocks[b].couplingcons != NULL )
1967  {
1968  SCIPfreeBufferArray(scip, &problem->blocks[b].couplingcons);
1969  SCIPfreeBufferArray(scip, &problem->blocks[b].slacksneg);
1970  SCIPfreeBufferArray(scip, &problem->blocks[b].slackspos);
1971  }
1972  }
1973  }
1974 
1975  if( varonlyobj != NULL )
1976  SCIPfreeBufferArray(scip, &varonlyobj);
1977 
1978  if( problem != NULL && blocktolinkvars != NULL )
1979  {
1980  for( b = problem->nblocks -1; b >= 0; b-- )
1981  {
1982  if( blocktolinkvars[b].indexes != NULL )
1983  SCIPfreeBufferArray(scip, &(blocktolinkvars[b].indexes));
1984  }
1985  }
1986 
1987  if( linkvars != NULL )
1988  SCIPfreeBufferArray(scip, &linkvars);
1989 
1990  if( alllinkvartoblocks != NULL )
1991  SCIPfreeBufferArray(scip, &alllinkvartoblocks);
1992 
1993  if( blocktolinkvars != NULL )
1994  SCIPfreeBufferArray(scip, &blocktolinkvars);
1995 
1996  if( linkvartoblocks != NULL )
1997  SCIPfreeBufferArray(scip, &linkvartoblocks);
1998 
1999  if( assigneddecomp != NULL )
2000  SCIPfreeDecomp(scip, &assigneddecomp);
2001 
2002  if( consssize != NULL )
2003  SCIPfreeBufferArray(scip, &consssize);
2004 
2005  if( conslabels != NULL )
2006  SCIPfreeBufferArray(scip, &conslabels);
2007 
2008  if( varlabels != NULL )
2009  SCIPfreeBufferArray(scip, &varlabels);
2010 
2011  if( sortedconss != NULL )
2012  SCIPfreeBufferArray(scip, &sortedconss);
2013 
2014  if( problem != NULL )
2015  {
2016  SCIP_CALL( freeProblem(&problem, nblocks) );
2017  }
2018 
2019  SCIPdebugMsg(scip, "Leave padm heuristic\n");
2020  return SCIP_OKAY;
2021 }
2022 
2023 /*
2024  * primal heuristic specific interface methods
2025  */
2026 
2027 /** creates the PADM primal heuristic and includes it in SCIP */
2029  SCIP* scip /**< SCIP data structure */
2030  )
2031 {
2032  SCIP_HEURDATA* heurdata;
2033  SCIP_HEUR* heur = NULL;
2034 
2035  /* create PADM primal heuristic data */
2036  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
2037 
2038  /* include primal heuristic */
2039 
2040  /* use SCIPincludeHeurBasic() plus setter functions if you want to set callbacks one-by-one and your code should
2041  * compile independent of new callbacks being added in future SCIP versions
2042  */
2043  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
2045  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecPADM, heurdata) );
2046 
2047  assert(heur != NULL);
2048 
2049  /* set non fundamental callbacks via setter functions */
2050  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyPADM) );
2051  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreePADM) );
2052 
2053  /* add padm primal heuristic parameters */
2054  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/maxnodes",
2055  "maximum number of nodes to regard in all subproblems",
2056  &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
2057 
2058  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/" HEUR_NAME "/minnodes",
2059  "minimum number of nodes to regard in one subproblem",
2060  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
2061 
2062  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/nodefac",
2063  "factor to control nodelimits of subproblems", &heurdata->nodefac, TRUE, DEFAULT_NODEFAC, 0.0, 0.99, NULL, NULL) );
2064 
2065  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/admiterations",
2066  "maximal number of ADM iterations in each penalty loop", &heurdata->admiterations, TRUE, DEFAULT_ADMIT, 1, 100, NULL, NULL) );
2067 
2068  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/penaltyiterations",
2069  "maximal number of penalty iterations", &heurdata->penaltyiterations, TRUE, DEFAULT_PENALTYIT, 1, 100000, NULL, NULL) );
2070 
2071  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/gap",
2072  "mipgap at start", &heurdata->gap, TRUE, DEFAULT_GAP, 0.0, 16.0, NULL, NULL) );
2073 
2074  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/reoptimize",
2075  "should the problem get reoptimized with the original objective function?", &heurdata->reoptimize, FALSE, TRUE, NULL, NULL) );
2076 
2077  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/scaling",
2078  "enable sigmoid rescaling of penalty parameters", &heurdata->scaling, TRUE, TRUE, NULL, NULL) );
2079 
2080  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/assignlinking",
2081  "should linking constraints be assigned?", &heurdata->assignlinking, FALSE, TRUE, NULL, NULL) );
2082 
2083  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/" HEUR_NAME "/original",
2084  "should the original problem be used? This is only for testing and not recommended!", &heurdata->original, TRUE, FALSE, NULL, NULL) );
2085 
2086  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/" HEUR_NAME "/timing",
2087  "should the heuristic run before or after the processing of the node? (0: before, 1: after, 2: both)",
2088  &heurdata->timing, FALSE, 0, 0, 2, NULL, NULL) );
2089 
2090  return SCIP_OKAY;
2091 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
int SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2080
#define DEFAULT_ADMIT
Definition: heur_padm.c:87
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:369
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:949
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
public methods for SCIP parameter handling
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8344
public methods for branch and bound tree
SCIP_VAR * slackposvar
Definition: heur_padm.c:138
#define SCIPduplicateMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:67
struct Block BLOCK
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)
public methods for node selector plugins
SCIP_Real size
Definition: heur_padm.c:110
void SCIPdecompGetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:188
SCIP_RETCODE SCIPcomputeDecompVarsLabels(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss)
Definition: scip_dcmp.c:444
public methods for memory management
SCIP_RETCODE SCIPassignDecompLinkConss(SCIP *scip, SCIP_DECOMP *decomp, SCIP_CONS **conss, int nconss, int *nskipconss)
Definition: scip_dcmp.c:539
#define HEUR_USESSUBSCIP
Definition: heur_padm.c:81
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
#define HEUR_NAME
Definition: heur_padm.c:73
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
#define SCIP_MAXSTRLEN
Definition: def.h:293
SCIP_RETCODE SCIPaddSolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool *stored)
Definition: scip_sol.c:3015
#define HEUR_DISPCHAR
Definition: heur_padm.c:75
static SCIP_DECL_HASHKEYVAL(indexesHashval)
Definition: heur_padm.c:163
SCIP_RETCODE SCIPcomputeDecompStats(SCIP *scip, SCIP_DECOMP *decomp, SCIP_Bool uselimits)
Definition: scip_dcmp.c:1125
int SCIPgetNOrigVars(SCIP *scip)
Definition: scip_prob.c:2430
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
#define SCIP_HEURTIMING_BEFORENODE
Definition: type_timing.h:70
public solving methods
public methods for timing
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1245
#define HEUR_PRIORITY
Definition: heur_padm.c:76
SCIP_Real slackposobjcoeff
Definition: heur_padm.c:137
static SCIP_RETCODE blockCreateSubscip(BLOCK *block, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_CONS **conss, int nconss, SCIP_Bool useorigprob, SCIP_Bool *success)
Definition: heur_padm.c:422
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2254
#define FALSE
Definition: def.h:87
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
#define EPSEQ(x, y, eps)
Definition: def.h:202
SCIP_RETCODE SCIPaddLongintParam(SCIP *scip, const char *name, const char *desc, SCIP_Longint *valueptr, SCIP_Bool isadvanced, SCIP_Longint defaultvalue, SCIP_Longint minvalue, SCIP_Longint maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:102
SCIP_VAR * slacknegvar
Definition: heur_padm.c:140
SCIP_RETCODE SCIPcopyLimits(SCIP *sourcescip, SCIP *targetscip)
Definition: scip_copy.c:3278
SCIP_Bool original
Definition: struct_dcmp.h:53
int ncoupling
Definition: heur_padm.c:109
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
int SCIPdecompGetNBorderVars(SCIP_DECOMP *decomp)
Definition: dcmp.c:369
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define SCIP_HEURTIMING_AFTERNODE
Definition: type_timing.h:92
static SCIP_RETCODE scalePenalties(PROBLEM *problem, SET *linkvartoblocks, SET *blocktolinkvars, SCIP_HASHTABLE *htable, SCIP_Real maxpenalty)
Definition: heur_padm.c:864
methods commonly used by primal heuristics
static SCIP_RETCODE reoptimize(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol, SCIP_VAR **vars, int nvars, SCIP_VAR **linkvars, int nlinkvars, SCIP_SOL **newsol, SCIP_Bool *success)
Definition: heur_padm.c:701
SCIP_RETCODE SCIPwriteOrigProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
Definition: scip_prob.c:599
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:923
SCIP_RETCODE SCIPtranslateSubSol(SCIP *scip, SCIP *subscip, SCIP_SOL *subsol, SCIP_HEUR *heur, SCIP_VAR **subvars, SCIP_SOL **newsol)
Definition: scip_copy.c:1399
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:185
SCIP_VAR ** SCIPgetOrigVars(SCIP *scip)
Definition: scip_prob.c:2403
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
void SCIPdecompGetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:139
SCIP_RETCODE SCIPdecompSetVarsLabels(SCIP_DECOMP *decomp, SCIP_VAR **vars, int *labels, int nvars)
Definition: dcmp.c:114
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:108
#define SCIP_DECOMP_LINKCONS
Definition: type_dcmp.h:36
void SCIPfreeDecomp(SCIP *scip, SCIP_DECOMP **decomp)
Definition: scip_dcmp.c:224
#define SCIPdebugMessage
Definition: pub_message.h:87
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:123
SCIP_CONS ** SCIPgetConss(SCIP *scip)
Definition: scip_prob.c:3086
static SCIP_RETCODE reuseSolution(SCIP *subscip, BLOCK *block)
Definition: heur_padm.c:603
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3201
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIP_LONGINT_MAX
Definition: def.h:163
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:283
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1362
public methods for SCIP variables
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
Definition: scip_param.c:594
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8354
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:111
#define SCIPdebugMsg
Definition: scip_message.h:69
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8146
Definition: heur_padm.c:123
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:556
public methods for numerical tolerances
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2236
int block
Definition: heur_padm.c:132
#define SCIP_DEFAULT_EPSILON
Definition: def.h:183
public methods for querying solving statistics
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1065
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
public methods for the branch-and-bound tree
static SCIP_RETCODE assignLinking(SCIP *scip, SCIP_DECOMP *newdecomp, SCIP_VAR **vars, SCIP_CONS **sortedconss, int *varlabels, int *conslabels, int nvars, int nconss, int nlinkconss)
Definition: heur_padm.c:562
void SCIPgetDecomps(SCIP *scip, SCIP_DECOMP ***decomps, int *ndecomps, SCIP_Bool original)
Definition: scip_dcmp.c:253
SCIP_VAR * SCIPfindVar(SCIP *scip, const char *name)
Definition: scip_prob.c:2683
static SCIP_RETCODE initProblem(SCIP *scip, PROBLEM **problem, int nblocks)
Definition: heur_padm.c:247
public methods for decompositions
public methods for managing constraints
#define DEFAULT_NODEFAC
Definition: heur_padm.c:86
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2613
struct blockinfo BLOCKINFO
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1441
PROBLEM * problem
Definition: heur_padm.c:101
#define HEUR_MAXDEPTH
Definition: heur_padm.c:79
#define SCIPhashFour(a, b, c, d)
Definition: pub_misc.h:515
static SCIP_RETCODE freeProblem(PROBLEM **problem, int nblocks)
Definition: heur_padm.c:277
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:210
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2768
SCIP_Real SCIPvarGetLbOriginal(SCIP_VAR *var)
Definition: var.c:17856
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1389
static SCIP_RETCODE initBlock(PROBLEM *problem)
Definition: heur_padm.c:195
static SCIP_DECL_HEURFREE(heurFreePADM)
Definition: heur_padm.c:969
static INLINE uint32_t SCIPrealHashCode(double x)
Definition: pub_misc.h:535
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:420
SCIP_STATUS SCIPgetStatus(SCIP *scip)
Definition: scip_general.c:474
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:48
PADM primal heuristic based on ideas published in the paper "A Decomposition Heuristic for Mixed-Inte...
int nsubvars
Definition: heur_padm.c:105
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8304
SCIP_CONS ** SCIPgetOrigConss(SCIP *scip)
Definition: scip_prob.c:3159
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
SCIP_VAR ** slacksneg
Definition: heur_padm.c:107
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3048
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
int SCIPdecompGetNBlocks(SCIP_DECOMP *decomp)
Definition: dcmp.c:269
#define NULL
Definition: lpi_spx1.cpp:155
#define REALABS(x)
Definition: def.h:201
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:260
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18284
public methods for problem copies
public methods for primal CIP solutions
#define SCIP_CALL(x)
Definition: def.h:384
int SCIPgetNOrigConss(SCIP *scip)
Definition: scip_prob.c:3132
#define DEFAULT_MAXNODES
Definition: heur_padm.c:85
Definition: graph_load.c:93
static SCIP_RETCODE createSubscip(SCIP *scip, SCIP **subscip)
Definition: heur_padm.c:313
static SCIP_DECL_HEUREXEC(heurExecPADM)
Definition: heur_padm.c:985
#define HEUR_FREQ
Definition: heur_padm.c:77
#define HEUR_FREQOFS
Definition: heur_padm.c:78
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip_cons.c:2514
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:1577
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_var.c:4510
#define SCIP_DECOMP_LINKVAR
Definition: type_dcmp.h:35
SCIP_RETCODE SCIPcopyConsCompression(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool global, SCIP_Bool enablepricing, SCIP_Bool threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:2951
static SCIP_RETCODE freeBlock(BLOCK *block)
Definition: heur_padm.c:224
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1212
public data structures and miscellaneous methods
SCIP_RETCODE SCIPdecompSetConsLabels(SCIP_DECOMP *decomp, SCIP_CONS **conss, int *labels, int nconss)
Definition: dcmp.c:163
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
Definition: scip_solve.c:3432
SCIP_Real linkvarval
Definition: heur_padm.c:135
SCIP_CONS ** couplingcons
Definition: heur_padm.c:108
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
SCIP_RETCODE SCIPwriteTransProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
Definition: scip_prob.c:646
#define HEUR_DESC
Definition: heur_padm.c:74
enum SCIP_Status SCIP_STATUS
Definition: type_stat.h:58
public methods for statistics table plugins
struct Problem PROBLEM
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip_sol.c:3231
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8105
SCIP * subscip
Definition: heur_padm.c:102
methods for debugging
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:478
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
Definition: cons.c:8214
SCIP_RETCODE SCIPhashtableSafeInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2519
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:976
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8284
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8254
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17758
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2205
int otherblock
Definition: heur_padm.c:133
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1435
int number
Definition: heur_padm.c:103
Constraint handler for linear constraints in their most general form, .
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2548
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2035
int linkvaridx
Definition: heur_padm.c:134
public methods for the LP relaxation, rows and columns
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2286
#define DEFAULT_MINNODES
Definition: heur_padm.c:84
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1990
#define SCIP_REAL_MIN
Definition: def.h:179
public methods for branching rule plugins and branching
SCIP_VAR ** b
Definition: circlepacking.c:56
SCIP_RETCODE SCIPcopyProb(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, const char *name)
Definition: scip_copy.c:518
SCIP_RETCODE SCIPcopyOrigConsCompression(SCIP *sourcescip, SCIP *targetscip, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *suffix, SCIP_VAR **fixedvars, SCIP_Real *fixedvals, int nfixedvars, SCIP_Bool enablepricing, SCIP_Bool threadsafe, SCIP_Bool passmessagehdlr, SCIP_Bool *valid)
Definition: scip_copy.c:3119
general public methods
int SCIPgetNOrigIntVars(SCIP *scip)
Definition: scip_prob.c:2484
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2304
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
public methods for solutions
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
Definition: scip_mem.c:91
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1666
public methods for random numbers
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3040
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIP_VAR ** subvars
Definition: heur_padm.c:104
public methods for message output
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
Definition: scip_mem.c:117
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition: scip_prob.c:1945
#define SCIP_Real
Definition: def.h:177
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8334
static SCIP_RETCODE getTimeLeft(SCIP *scip, SCIP_Real *time)
Definition: heur_padm.c:927
public methods for message handling
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8274
#define DEFAULT_GAP
Definition: heur_padm.c:89
static SCIP_RETCODE copyToSubscip(SCIP *scip, SCIP *subscip, const char *name, SCIP_CONS **conss, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, int nconss, SCIP_Bool useorigprob, SCIP_Bool *success)
Definition: heur_padm.c:361
SCIP_RETCODE SCIPcreateDecomp(SCIP *scip, SCIP_DECOMP **decomp, int nblocks, SCIP_Bool original, SCIP_Bool benderslabels)
Definition: scip_dcmp.c:208
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8264
SCIP_CONS * couplingCons
Definition: heur_padm.c:141
#define SCIP_Longint
Definition: def.h:162
SCIP_Real slacknegobjcoeff
Definition: heur_padm.c:139
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17416
#define DEFAULT_PENALTYIT
Definition: heur_padm.c:88
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1254
SCIP_RETCODE SCIPtransformProb(SCIP *scip)
Definition: scip_solve.c:358
SCIP_Bool SCIPdoNotMultaggr(SCIP *scip)
Definition: scip_var.c:8572
static SCIP_DECL_HEURCOPY(heurCopyPADM)
Definition: heur_padm.c:954
SCIP_VAR * linkvar
Definition: heur_padm.c:136
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
SCIP_Bool SCIPdecompUseBendersLabels(SCIP_DECOMP *decomp)
Definition: dcmp.c:259
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
#define nnodes
Definition: gastrans.c:65
SCIP_VAR ** slackspos
Definition: heur_padm.c:106
public methods for primal heuristics
int SCIPgetNOrigBinVars(SCIP *scip)
Definition: scip_prob.c:2457
#define COUPLINGSIZE
Definition: heur_padm.c:83
SCIPallocBlockMemory(scip, subsol))
SCIP_RETCODE SCIPdecompGetConssSize(SCIP_DECOMP *decomp, int *consssize, int nlabels)
Definition: dcmp.c:339
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1352
int SCIPdecompGetNBorderConss(SCIP_DECOMP *decomp)
Definition: dcmp.c:384
SCIP_Real SCIPheurGetTime(SCIP_HEUR *heur)
Definition: heur.c:1629
SCIP_Longint SCIPgetNNodes(SCIP *scip)
struct set SET
public methods for global and local (sub)problems
SCIP_Real SCIPround(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPincludeHeurPADM(SCIP *scip)
Definition: heur_padm.c:2028
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
default SCIP plugins
int * indexes
Definition: heur_padm.c:126
SCIP_Longint SCIPhashtableGetNElements(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2707
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:130
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:874
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:536
static SCIP_DECL_HASHKEYEQ(indexesEqual)
Definition: heur_padm.c:146
static SCIP_RETCODE createAndSplitProblem(SCIP *scip, SCIP_CONS **sortedconss, int nconss, int *consssize, int nblocks, PROBLEM **problem, SCIP_Bool useorigprob, SCIP_Bool *success)
Definition: heur_padm.c:494
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
#define HEUR_TIMING
Definition: heur_padm.c:80
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:315
methods for selecting (weighted) k-medians
int size
Definition: heur_padm.c:125
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:319
memory allocation routines