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