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