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