Scippy

GCG

Branch-and-Price & Column Generation for Everyone

heur_xpcrossover.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2021 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
28 /**@file heur_xpcrossover.c
29  * @brief Extreme Point Crossover
30  * @author Christian Puchert
31  */
32 
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 
35 #include <assert.h>
36 #include <string.h>
37 #include <stdio.h>
38 
39 #include "heur_xpcrossover.h"
40 #include "gcg.h"
41 
42 #include "scip/scip.h"
43 #include "scip/misc.h"
44 #include "scip/scipdefplugins.h"
45 
46 
47 #define HEUR_NAME "xpcrossover"
48 #define HEUR_DESC "Extreme Point Crossover"
49 #define HEUR_DISPCHAR 'X'
50 #define HEUR_PRIORITY -1100500
51 #define HEUR_FREQ 0
52 #define HEUR_FREQOFS 0
53 #define HEUR_MAXDEPTH -1
54 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
55 #define HEUR_USESSUBSCIP TRUE
56 
57 #define DEFAULT_MAXNODES 1000LL /**< maximum number of nodes to regard in the subproblem */
58 #define DEFAULT_MINIMPROVE 0.01 /**< factor by which crossover should at least improve the incumbent */
59 #define DEFAULT_MINNODES 200LL /**< minimum number of nodes to regard in the subproblem */
60 #define DEFAULT_MINFIXINGRATE 0.4 /**< minimum percentage of integer variables that have to be fixed */
61 #define DEFAULT_NODESOFS 200LL /**< number of nodes added to the contingent of the total nodes */
62 #define DEFAULT_NODESQUOT 0.1 /**< subproblem nodes in relation to nodes of the original problem */
63 #define DEFAULT_NUSEDPTS 4 /**< number of extreme pts per block that will be taken into account */
64 #define DEFAULT_RANDOMIZATION FALSE /**< should the choice which sols to take be randomized? */
65 #define DEFAULT_COPYCUTS TRUE /**< if DEFAULT_USELPROWS is FALSE, then should all active cuts from the cutpool
66  * of the original scip be copied to constraints of the subscip
67  */
68 #define DEFAULT_RANDSEED 7 /**< initial random seed */
69 
70 #define HASHSIZE_POINTS 11113 /**< size of hash table for extreme point tuples */
71 
72 
73 
74 
75 /*
76  * Data structures
77  */
78 typedef struct PointTuple POINTTUPLE;
79 
80 /** primal heuristic data */
81 struct SCIP_HeurData
82 {
83  SCIP_Longint maxnodes; /**< maximum number of nodes to regard in the subproblem */
84  SCIP_Longint minnodes; /**< minimum number of nodes to regard in the subproblem */
85  SCIP_Longint nodesofs; /**< number of nodes added to the contingent of the total nodes */
86  SCIP_Longint usednodes; /**< nodes already used by crossover in earlier calls */
87  SCIP_Real nodesquot; /**< subproblem nodes in relation to nodes of the original problem */
88 
89  int nusedpts; /**< number of extreme pts per block that will be taken into account */
90  unsigned int nfailures; /**< number of failures since last successful call */
91  SCIP_Longint nextnodenumber; /**< number of BnB nodes at which crossover should be called next */
92  SCIP_Real minfixingrate; /**< minimum percentage of integer variables that have to be fixed */
93  SCIP_Real minimprove; /**< factor by which crossover should at least improve the incumbent */
94  SCIP_Bool randomization; /**< should the choice which sols to take be randomized? */
95  SCIP_Bool copycuts; /**< if uselprows == FALSE, should all active cuts from cutpool be copied
96  * to constraints in subproblem?
97  */
98  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
99  SCIP_HASHTABLE* hashtable; /**< hashtable used to store the extreme point tuples already used */
100  POINTTUPLE* lasttuple; /**< last tuple of extreme points */
101 
102 #ifdef SCIP_STATISTIC
103  SCIP_Longint nfixfails; /**< number of abortions due to a bad fixing rate */
104  SCIP_Real avgfixrate; /**< average rate of variables that are fixed */
105  SCIP_Real avgzerorate; /**< average rate of fixed variables that are zero */
106  SCIP_Longint totalsols; /**< total number of subSCIP solutions (including those which have not
107  * been added)
108  */
109  SCIP_Real subsciptime; /**< total subSCIP solving time in seconds */
110  SCIP_Real bestprimalbd; /**< objective value of best solution found by this heuristic */
111 #endif
112 };
113 
114 /** n-tuple of extreme points and their hashkey */
116 {
117  int* indices; /**< sorted array of master variable indices */
118  int size; /**< size of the array (should be heurdata->nusedpts * nblocks) */
119  unsigned int key; /**< hashkey of the tuple */
120  POINTTUPLE* prev; /**< previous extreme point tuple created */
121 };
122 
123 
124 
125 
126 /*
127  * Local methods
128  */
129 
130 
131 /** gets the hash key of an extreme point tuple */
132 static
133 SCIP_DECL_HASHGETKEY(hashGetKeyPts)
134 { /*lint --e{715}*/
135  return elem;
136 }
137 
138 
139 /** returns TRUE iff both extreme point tuples are identical */
140 static
141 SCIP_DECL_HASHKEYEQ(hashKeyEqPts)
142 { /*lint --e{715}*/
143  int i;
144  int size;
145 
146  int* indices1;
147  int* indices2;
148 
149  indices1 = ((POINTTUPLE*)key1)->indices;
150  indices2 = ((POINTTUPLE*)key2)->indices;
151 
152  /* there should be two nonempty arrays of the same size */
153  assert(indices1 != NULL);
154  assert(indices2 != NULL);
155  assert(((POINTTUPLE*)key1)->size == ((POINTTUPLE*)key2)->size);
156 
157  size = ((POINTTUPLE*)key1)->size;
158 
159  /* compare arrays by components, return TRUE, iff equal */
160  for( i = 0; i < size; i++ )
161  {
162  if( indices1[i] != indices2[i] )
163  return FALSE;
164  }
165 
166  return TRUE;
167 }
168 
169 
170 /** returns hashkey of an extreme point tuple */
171 static
172 SCIP_DECL_HASHKEYVAL(hashKeyValPts)
173 { /*lint --e{715}*/
174  return ((POINTTUPLE*)key)->key;
175 }
176 
177 
178 /** calculates a hash key for a given tuple of master variable indices */
179 static
180 unsigned int calculateHashKey(
181  int* indices, /**< indices of master variables */
182  int size /**< number of master variables */
183  )
184 {
185  int i;
186  unsigned int hashkey;
187 
188  /* haskey should be (x1+2) * (x2+2) * ... * (xn+2) + (x1+1) + (x2+1) + ... + (xn+1) */
189  hashkey = 1;
190  for( i = 0; i < size; i++ )
191  hashkey *= indices[i] + 2;
192  for( i = 0; i < size; i++ )
193  hashkey += indices[i] + 1;
194 
195  return hashkey;
196 }
197 
198 
199 /** creates a new tuple of extreme points (= mastervars) */
200 static
201 SCIP_RETCODE createPtTuple(
202  SCIP* scip, /**< original SCIP data structure */
203  POINTTUPLE** elem, /**< tuple of master variables which should be created */
204  int* indices, /**< indices of master variables */
205  int size, /**< number of master variables */
206  SCIP_HEURDATA* heurdata /**< primal heuristic data */
207  )
208 {
209  /* memory allocation */
210  SCIP_CALL( SCIPallocBlockMemory(scip, elem) );
211  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*elem)->indices,size) );
212  BMScopyMemoryArray((*elem)->indices, indices, size);
213 
214  /* data input */
215  SCIPsortInt((*elem)->indices, size);
216  (*elem)->size = size;
217  (*elem)->key = calculateHashKey((*elem)->indices, (*elem)->size);
218  (*elem)->prev = heurdata->lasttuple;
219 
220  /* update heurdata */
221  heurdata->lasttuple = *elem;
222  return SCIP_OKAY;
223 }
224 
225 
226 /** for each block, select extreme points (represented by mastervars) to be crossed */
227 static
228 SCIP_RETCODE selectExtremePoints(
229  SCIP* scip, /**< original SCIP data structure */
230  SCIP_HEURDATA* heurdata, /**< primal heuristic data */
231  int* selection, /**< indices of selected extreme points */
232  SCIP_Bool* success /**< pointer to store whether the process was successful */
233  )
234 {
235  SCIP* masterprob;
236  int nblocks;
237 
238  SCIP_VAR** mastervars;
239  SCIP_Real* mastervals;
240  int nmastervars;
241 
242  int nusedpts;
243  int block;
244 #ifndef NDEBUG
245  int nidentblocks;
246 #endif
247  int* blocknrs;
248  int* identblock;
249  SCIP_Real* blockvalue;
250  SCIP_Real value;
251  SCIP_Real* selvalue;
252 
253  POINTTUPLE* elem;
254 
255  int i;
256  int j;
257  int k;
258 
259  /* check preconditions */
260  assert(scip != NULL);
261  assert(heurdata != NULL);
262  assert(selection != NULL);
263  assert(success != NULL);
264 
265  /* get master problem */
266  masterprob = GCGgetMasterprob(scip);
267  assert(masterprob != NULL);
268 
269  /* get number of blocks */
270  nblocks = GCGgetNPricingprobs(scip);
271 
272  /* get variables of the master problem */
273  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
274  assert(mastervars != NULL);
275  assert(nmastervars >= 0);
276 
277  /* get master LP solution values */
278  SCIP_CALL( SCIPallocBufferArray(scip, &mastervals, nmastervars) );
279  SCIP_CALL( SCIPgetSolVals(masterprob, NULL, nmastervars, mastervars, mastervals) );
280 
281  /* get number of extreme points per block */
282  nusedpts = heurdata->nusedpts;
283 
284  /* allocate memory */
285  SCIP_CALL( SCIPallocBufferArray(scip, &selvalue, nblocks * nusedpts) );
286  SCIP_CALL( SCIPallocBufferArray(scip, &blocknrs, nblocks) );
287  SCIP_CALL( SCIPallocBufferArray(scip, &blockvalue, nblocks) );
288  SCIP_CALL( SCIPallocBufferArray(scip, &identblock, nblocks) );
289 
290  /* initialize the block values for the pricing problems */
291  for( i = 0; i < nblocks; i++ )
292  {
293  blockvalue[i] = 0.0;
294  blocknrs[i] = 0;
295  identblock[i] = i;
296  }
297 
298  *success = FALSE;
299 
300  /* loop over all given master variables;
301  * this loop treats master variables that have value one or greater
302  * (in particular important if blocks are represented by others)
303  */
304  for( i = 0; i < nmastervars; i++ )
305  {
306  SCIP_VAR* mastervar;
307 
308  mastervar = mastervars[i];
309  assert(GCGvarIsMaster(mastervar));
310 
311  /* get block information and solution value */
312  block = GCGvarGetBlock(mastervar);
313  value = SCIPgetSolVal(masterprob, NULL, mastervar);
314 
315  /** @todo handle infinite master solution values */
316  assert(!SCIPisInfinity(scip, value));
317 
318  /* ignore irrelevant extreme points */
319  if( SCIPisFeasZero(scip, value) )
320  continue;
321 
322  /* ignore rays
323  * @todo do it smarter */
324  if( GCGmasterVarIsRay(mastervar) )
325  continue;
326 
327  /* variables belonging to no block are not treated here */
328  if( block == -1 )
329  continue;
330 
331  /* get number of blocks that are identical to this block */
332  assert(block >= 0);
333 #ifndef NDEBUG
334  nidentblocks = GCGgetNIdenticalBlocks(scip, block);
335 #endif
336 
337  while( SCIPisFeasGE(scip, mastervals[i], 1.0) )
338  {
339  /* insert the extreme point in the selection (should be the only point for this block) */
340  j = identblock[block] * nusedpts;
341  assert(selection[j] == -1);
342 
343  selection[j] = i;
344  selvalue[j] = 1.0;
345 
346  mastervals[i] = mastervals[i] - 1.0;
347  blocknrs[block]++;
348 
349  /* search the next block to be considered */
350  for( j = identblock[block] + 1; j < nblocks; ++j )
351  if( GCGgetBlockRepresentative(scip, j) == block )
352  {
353  identblock[block] = j;
354  break;
355  }
356 
357 #ifndef NDEBUG
358  assert(blocknrs[block] >= nidentblocks || j < nblocks);
359 #endif
360  }
361  }
362 
363  /* loop over all given master variables */
364  for( i = 0; i < nmastervars; i++ )
365  {
366  SCIP_VAR* mastervar;
367 
368  mastervar = mastervars[i];
369  assert(GCGvarIsMaster(mastervar));
370 
371  /* get block information and solution value */
372  block = GCGvarGetBlock(mastervar);
373  value = SCIPgetSolVal(masterprob, NULL, mastervar);
374 
375  /** @todo handle infinite master solution values */
376  assert(!SCIPisInfinity(scip, value));
377 
378  /* ignore irrelevant extreme points */
379  if( SCIPisFeasZero(scip, value) )
380  continue;
381 
382  /* ignore rays */
383  if( GCGmasterVarIsRay(mastervar) )
384  continue;
385 
386  /* variables belonging to no block are not treated here */
387  if( block == -1 )
388  continue;
389 
390  /* get number of blocks that are identical to this block */
391  assert(block >= 0);
392 #ifndef NDEBUG
393  nidentblocks = GCGgetNIdenticalBlocks(scip, block);
394 #endif
395 
396  assert(SCIPisFeasGE(scip, mastervals[i], 0.0) && SCIPisFeasLT(scip, mastervals[i], 1.0));
397 
398  while( SCIPisFeasPositive(scip, mastervals[i]) )
399  {
400  value = MIN(mastervals[i], 1.0 - blockvalue[block]);
401 
402  /* check if the extreme point is good enough to be inserted in the selection */
403  for( j = identblock[block] * nusedpts; j < (identblock[block] + 1) * nusedpts; ++j )
404  {
405  /* if the extreme point is better than a point in the selection
406  * or there are < nusedpts, insert it
407  */
408  if( selection[j] == -1 || SCIPisGT(scip, value, selvalue[j]) )
409  {
410  for( k = (identblock[block] + 1) * nusedpts - 1; k > j; --k )
411  {
412  selection[k] = selection[k-1];
413  selvalue[k] = selvalue[k-1];
414  }
415  selection[j] = i;
416  selvalue[j] = value;
417  break;
418  }
419  }
420 
421  mastervals[i] = mastervals[i] - value;
422  if( SCIPisFeasZero(scip, mastervals[i]) )
423  mastervals[i] = 0.0;
424  blockvalue[block] += value;
425 
426  /* if the value assigned to the block is equal to 1, this block is full and we consider the next block */
427  if( SCIPisFeasGE(scip, blockvalue[block], 1.0) )
428  {
429  blockvalue[block] = 0.0;
430  blocknrs[block]++;
431 
432  /* search the next identical block to be considered */
433  for( j = identblock[block] + 1; j < nblocks; ++j )
434  if( GCGgetBlockRepresentative(scip, j) == block )
435  {
436  identblock[block] = j;
437  break;
438  }
439 
440 #ifndef NDEBUG
441  assert(blocknrs[block] >= nidentblocks || j < nblocks);
442 #endif
443  }
444  }
445  }
446 
447  /* creates an object ready to be inserted into the hashtable */
448  SCIP_CALL( createPtTuple(scip, &elem, selection, nusedpts * nblocks, heurdata) );
449 
450  /* check whether the set is already in the hashtable, if not, insert it */
451  if( !SCIPhashtableExists(heurdata->hashtable, elem) )
452  {
453  SCIP_CALL( SCIPhashtableInsert(heurdata->hashtable, elem) );
454  *success = TRUE;
455  }
456 
457  /* free memory */
458  SCIPfreeBufferArray(scip, &identblock);
459  SCIPfreeBufferArray(scip, &blockvalue);
460  SCIPfreeBufferArray(scip, &blocknrs);
461  SCIPfreeBufferArray(scip, &selvalue);
462  SCIPfreeBufferArray(scip, &mastervals);
463 
464  return SCIP_OKAY;
465 }
466 
467 
468 /** select extreme points (represented by mastervars) to be crossed randomly */
469 static
471  SCIP* scip, /**< original SCIP data structure */
472  SCIP_HEURDATA* heurdata, /**< primal heuristic data */
473  int* selection, /**< indices of selected extreme points */
474  SCIP_Bool* success /**< pointer to store whether the process was successful */
475  )
476 {
477  SCIP* masterprob;
478  int nblocks;
479 
480  SCIP_VAR** mastervars;
481  int nmastervars;
482 
483  int nusedpts; /* number of extreme points per block to be chosen */
484  int* npts; /* for each block, the number of available extreme points */
485  int* blockpts; /* all points of a block which to be considered */
486  SCIP_Real* ptvals; /* solution values of extreme points in master problem */
487  int lastpt; /* the worst extreme point possible to choose */
488  int iters; /* iteration counter */
489 
490  POINTTUPLE* elem;
491 
492  int i;
493  int j;
494  int k;
495 
496  /* check preconditions */
497  assert(scip != NULL);
498  assert(heurdata != NULL);
499  assert(selection != NULL);
500  assert(success != NULL);
501 
502  /* get master problem */
503  masterprob = GCGgetMasterprob(scip);
504  assert(masterprob != NULL);
505 
506  /* get number of blocks */
507  nblocks = GCGgetNPricingprobs(scip);
508 
509  /* get variables of the master problem */
510  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
511  assert(mastervars != NULL);
512  assert(nmastervars >= 0);
513 
514  /* get number of extreme points per block */
515  nusedpts = heurdata->nusedpts;
516 
517  /* allocate memory */
518  SCIP_CALL( SCIPallocBufferArray(scip, &npts, nblocks) );
519 
520  *success = TRUE;
521 
522  /* check whether we have enough points per block to perform a randomization */
523  for( i = 0; i < nblocks; ++i )
524  npts[i] = 0;
525  for( i = 0; i < nmastervars; ++i )
526  {
527  SCIP_VAR* mastervar;
528  SCIP_Real solval;
529  int block;
530 
531  mastervar = mastervars[i];
532  solval = SCIPgetSolVal(masterprob, NULL, mastervar);
533  block = GCGvarGetBlock(mastervar);
534 
535  if( block >= 0 && !SCIPisFeasZero(scip, solval) )
536  ++npts[block];
537  }
538  for( i = 0; i < nblocks; ++i )
539  if( GCGisPricingprobRelevant(scip, i) && npts[i] <= nusedpts )
540  *success = FALSE;
541 
542  /* do not randomize if there are not enough points available */
543  if( !*success )
544  {
545  SCIPdebugMessage(" -> not enough extreme points available for randomization.\n");
546 
547  /* free memory */
548  SCIPfreeBufferArray(scip, &npts);
549 
550  return SCIP_OKAY;
551  }
552 
553  *success = FALSE;
554  iters = 0;
555 
556  /* perform at maximum 10 restarts and stop as soon as a new set of solutions is found */
557  do
558  {
559  for( i = 0; i < nblocks; ++i )
560  {
561  int blockrep;
562 
563  SCIP_CALL( SCIPallocBufferArray(scip, &blockpts, npts[i]) );
564  SCIP_CALL( SCIPallocBufferArray(scip, &ptvals, npts[i]) );
565 
566  /* get representative of this block */
567  blockrep = GCGgetBlockRepresentative(scip, i);
568  assert(blockrep >= 0 && blockrep <= i);
569 
570  /* get all relevant extreme points for this block */
571  k = 0;
572  for( j = 0; j < nmastervars; ++j )
573  {
574  SCIP_VAR* mastervar;
575  SCIP_Real solval;
576  int block;
577 
578  mastervar = mastervars[j];
579  solval = SCIPgetSolVal(masterprob, NULL, mastervar);
580  block = GCGvarGetBlock(mastervar);
581 
582  if( block == blockrep && !SCIPisFeasZero(scip, solval) )
583  {
584  assert(k < npts[blockrep]);
585  blockpts[k] = j;
586  ++k;
587  }
588  }
589  assert(k == npts[blockrep]);
590 
591  /* sort the extreme points */
592  SCIPsortRealInt(ptvals, blockpts, npts[blockrep]);
593  lastpt = npts[blockrep];
594 
595  /* perform a random selection for this block */
596  for( k = 0; k < nusedpts; ++k )
597  {
598  int idx;
599  int selidx;
600 
601  idx = SCIPrandomGetInt(heurdata->randnumgen, nusedpts-k-1, lastpt-1);
602  selidx = i * nusedpts + k;
603  selection[selidx] = blockpts[idx];
604  lastpt = idx;
605  }
606 
607  SCIPfreeBufferArray(scip, &ptvals);
608  SCIPfreeBufferArray(scip, &blockpts);
609  }
610 
611  /* creates an object ready to be inserted into the hashtable */
612  SCIP_CALL( createPtTuple(scip, &elem, selection, nusedpts * nblocks, heurdata) );
613 
614  /* check whether the randomized set is already in the hashtable, if not, insert it */
615  if( !SCIPhashtableExists(heurdata->hashtable, elem) )
616  {
617  SCIP_CALL( SCIPhashtableInsert(heurdata->hashtable, elem) );
618  *success = TRUE;
619  }
620  ++iters;
621  }
622  while( !*success && iters < 10 );
623 
624  /* free memory */
625  SCIPfreeBufferArray(scip, &npts);
626 
627  return SCIP_OKAY;
628 }
629 
630 
631 #ifdef PRINTPOINTS
632 /** prints selected extreme points to standard output */
633 static
634 SCIP_RETCODE printExtremePoints(
635  SCIP* scip,
636  int nusedpts,
637  int* selection
638  )
639 {
640  SCIP* masterprob;
641  int nblocks;
642 
643  SCIP_VAR** mastervars;
644  int nmastervars;
645  SCIP_VAR* mastervar;
646  SCIP_VAR** origvars;
647  SCIP_Real* origvals;
648  int norigvars;
649 
650  int i;
651  int j;
652  int k;
653  int selidx;
654 
655  assert(scip != NULL);
656 
657  /* get master problem, number of blocks and extreme points per block */
658  masterprob = GCGgetMasterprob(scip);
659  assert(masterprob != NULL);
660 
661  nblocks = GCGgetNPricingprobs(scip);
662 
663  /* get variables of the master problem */
664  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, &nmastervars, NULL, NULL, NULL, NULL) );
665  assert(mastervars != NULL);
666  assert(nmastervars >= 0);
667 
668  /* first, print the relaxation solution */
669  SCIPdebugPrintf("------------------------------------------------------------\n");
670  SCIPdebugPrintf("Current relaxation solution:\n");
671  SCIP_CALL( SCIPprintSol(scip, GCGrelaxGetCurrentOrigSol(scip), NULL, FALSE) );
672  SCIPdebugPrintf("------------------------------------------------------------\n");
673 
674  /* then, print the selected extreme points for each block */
675  for( i = 0; i < nblocks; ++i )
676  {
677  SCIPdebugPrintf("Block %i\n", i+1);
678  SCIPdebugPrintf("------------------------------------------------------------\n");
679 
680  for( j = 0; j < nusedpts; ++j )
681  {
682  selidx = i * nusedpts + j;
683  if( selection[selidx] != -1 )
684  {
685  mastervar = mastervars[selection[selidx]];
686  assert(GCGvarIsMaster(mastervar));
687 
688  origvars = GCGmasterVarGetOrigvars(mastervar);
689  origvals = GCGmasterVarGetOrigvals(mastervar);
690  norigvars = GCGmasterVarGetNOrigvars(mastervar);
691 
692  SCIPdebugPrintf("Extreme point %i, mastervar %s, masterval=%g, index=%d:\n",
693  j+1, SCIPvarGetName(mastervar),
694  SCIPgetSolVal(masterprob, NULL, mastervar), SCIPvarGetProbindex(mastervar));
695  for( k = 0; k < norigvars; ++k )
696  {
697  SCIPdebugPrintf("%-32s % 20.15g \t(obj:%.15g)\n",
698  SCIPvarGetName(origvars[k]), origvals[k], SCIPvarGetObj(origvars[k]));
699  }
700  SCIPdebugPrintf("------------------------------------------------------------\n");
701  }
702  }
703  }
704 
705  return SCIP_OKAY;
706 }
707 #endif
708 
709 /** initialize the subSCIP instance: copy SCIP to subSCIP, set the parameters */
710 static
711 SCIP_RETCODE setupSubproblem(
712  SCIP* scip, /**< original SCIP data structure */
713  SCIP* subscip, /**< SCIP data structure for the subproblem */
714  SCIP_VAR** subvars, /**< the variables of the subproblem */
715  SCIP_HEURDATA* heurdata, /**< primal heuristic data */
716  SCIP_Longint nstallnodes, /**< node limit for subproblem */
717  SCIP_Real timelimit, /**< time limit for subproblem */
718  SCIP_Real memorylimit /**< memory limit for subproblem */
719  )
720 {
721  SCIP_VAR** vars;
722  int nvars;
723 
724  int i;
725 
726  char probname[SCIP_MAXSTRLEN];
727  SCIP_HASHMAP* varmapfw; /* mapping of SCIP variables to subSCIP variables */
728  SCIP_Bool valid;
729 
730  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
731  SCIP_CALL( SCIPhashmapCreate(&varmapfw, SCIPblkmem(subscip), nvars) );
732 
733  /* copy the SCIP instance to the subSCIP */
734 
735  /* copy all plugins */
736  SCIP_CALL( SCIPincludeDefaultPlugins(subscip) );
737 
738  /* get name of the original problem and add the string "_extremeptsub" */
739  (void) SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s_extremeptsub", SCIPgetProbName(scip));
740 
741  /* create the subproblem */
742  SCIP_CALL( SCIPcreateProb(subscip, probname, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
743 
744  /* copy all variables */
745  SCIP_CALL( SCIPcopyVars(scip, subscip, varmapfw, NULL, NULL, NULL, 0, TRUE) );
746 
747  /* copy all constraints */
748  valid = FALSE;
749  SCIP_CALL( SCIPcopyConss(scip, subscip, varmapfw, NULL, TRUE, FALSE, &valid) );
750  if( heurdata->copycuts )
751  {
752  /* copies all active cuts from cutpool of sourcescip to linear constraints in targetscip */
753  SCIP_CALL( SCIPcopyCuts(scip, subscip, varmapfw, NULL, TRUE, NULL) );
754  }
755  SCIPdebugMessage("Copying the SCIP constraints was %s complete.\n", valid ? "" : "not ");
756 
757  /* get the subproblem variables */
758  for( i = 0; i < nvars; i++ )
759  subvars[i] = (SCIP_VAR*) SCIPhashmapGetImage(varmapfw, vars[i]);
760 
761  /* free hash map */
762  SCIPhashmapFree(&varmapfw);
763 
764  /* setup parameters of subSCIP */
765  /* do not abort subproblem on CTRL-C */
766  SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
767 
768 #ifdef SCIP_DEBUG
769  /* for debugging RENS, enable MIP output */
770  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
771  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 100000000) );
772 #else
773  /* disable output to console */
774  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
775 #endif
776 
777  /* set limits for the subproblem */
778  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nstallnodes) );
779  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", MAX(10, nstallnodes/10)) );
780  SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
781  SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
782 
783  /* forbid recursive call of heuristics and separators solving subMIPs */
784  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
785 
786  /* disable cutting plane separation */
787  SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_OFF, TRUE) );
788 
789  /* disable expensive presolving */
790  SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
791 
792  /* use best estimate node selection */
793  if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
794  {
795  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
796  }
797 
798  /* use inference branching */
799  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
800  {
801  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
802  }
803 
804  /* disable conflict analysis */
805  if( !SCIPisParamFixed(subscip, "conflict/enable") )
806  {
807  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", FALSE) );
808  }
809 
810  /* if there is already a solution, add an objective cutoff */
811  if( SCIPgetNSols(scip) > 0 )
812  {
813  SCIP_Real cutoff; /* objective cutoff for the subproblem */
814  SCIP_Real upperbound;
815 
816  assert( !SCIPisInfinity(scip,SCIPgetUpperbound(scip)) );
817 
818  upperbound = SCIPgetUpperbound(scip) - SCIPsumepsilon(scip);
819  if( !SCIPisInfinity(scip,-1.0*SCIPgetLowerbound(scip)) )
820  {
821  cutoff = (1-heurdata->minimprove)*SCIPgetUpperbound(scip) + heurdata->minimprove*SCIPgetLowerbound(scip);
822  }
823  else
824  {
825  if( SCIPgetUpperbound ( scip ) >= 0 )
826  cutoff = ( 1 - heurdata->minimprove ) * SCIPgetUpperbound ( scip );
827  else
828  cutoff = ( 1 + heurdata->minimprove ) * SCIPgetUpperbound ( scip );
829  }
830  cutoff = MIN(upperbound, cutoff );
831  SCIP_CALL( SCIPsetObjlimit(subscip, cutoff) );
832  }
833 
834  return SCIP_OKAY;
835 }
836 
837 /** fix those variables which are identical in each extreme point of their blocks */
838 static
839 SCIP_RETCODE fixVariables(
840  SCIP* scip, /**< original SCIP data structure */
841  SCIP* subscip, /**< SCIP data structure for the subproblem */
842  SCIP_VAR** subvars, /**< the variables of the subproblem */
843  int* selection, /**< selected extreme points the heuristic will use */
844  SCIP_HEURDATA* heurdata, /**< primal heuristic data */
845  SCIP_Real* intfixingrate, /**< percentage of integers that get actually fixed */
846  SCIP_Real* zerofixingrate, /**< percentage of variables fixed to zero */
847  SCIP_Bool* success /**< pointer to store whether the problem was created successfully */
848  )
849 {
850  SCIP* masterprob; /* master problem */
851  SCIP_VAR** mastervars; /* master variables */
852  SCIP_VAR** vars; /* original scip variables */
853 
854  int nblocks; /* number of blocks */
855  int nusedpts; /* number of extreme points per block */
856  int nvars; /* number of original variables */
857  int nbinvars; /* number of binary variables in the original problem */
858  int nintvars; /* number of general integer variables */
859 
860  SCIP_Real* fixvals; /* values to which original variables should be fixed */
861  SCIP_Bool* fixable; /* for each original variable, remember if it is fixable */
862  SCIP_Bool* zeroblocks; /* blocks that would be entirely fixed to zero */
863  int* ptcounter; /* for each original variable, count in how many extreme points it appears */
864  int fixingcounter; /* count how many original variables are fixed */
865  int zerocounter; /* count how many variables are fixed to zero */
866 
867  int i;
868  int j;
869  int k;
870  int l;
871  int idx;
872 
873  /* check preconditions */
874  assert(scip != NULL);
875  assert(subscip != NULL);
876  assert(subvars != NULL);
877  assert(selection != NULL);
878  assert(heurdata != NULL);
879  assert(intfixingrate != NULL);
880  assert(zerofixingrate != NULL);
881  assert(success != NULL);
882 
883  /* get master problem and its variables */
884  masterprob = GCGgetMasterprob(scip);
885  assert(masterprob != NULL);
886  SCIP_CALL( SCIPgetVarsData(masterprob, &mastervars, NULL, NULL, NULL, NULL, NULL) );
887  assert(mastervars != NULL);
888 
889  /* get required data of the original problem */
890  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, NULL, NULL) );
891 
892  nblocks = GCGgetNPricingprobs(scip);
893  nusedpts = heurdata->nusedpts;
894  assert(nusedpts >= 2);
895 
896  fixingcounter = 0;
897  zerocounter = 0;
898 
899  *success = FALSE;
900 
901  /* allocate memory */
902  SCIP_CALL( SCIPallocBufferArray(scip, &fixvals, nbinvars + nintvars) );
903  SCIP_CALL( SCIPallocBufferArray(scip, &fixable, nbinvars + nintvars) );
904  SCIP_CALL( SCIPallocBufferArray(scip, &ptcounter, nbinvars + nintvars) );
905  SCIP_CALL( SCIPallocBufferArray(scip, &zeroblocks, nblocks) );
906 
907  /* initialize fixing information for original variables
908  *
909  * @note: Zero values of extreme points are not stored explicitly in the master
910  * variable data; therefore
911  * * we assume for each variable that it can be fixed to zero
912  * * we assume a fixing value different from zero if we find
913  * a nonzero entry in the first extreme point (so the first point serves
914  * as a 'reference point')
915  * * we mark the variable as unfixable if we find a nonzero entry for it which
916  * differs from the current fixing value
917  * It still may happen that a variable is still marked as fixable although it
918  * appears nonzero in only some, but not all extreme points; this will be corrected
919  * later on (this is why we remember the number of points in which a variable appears
920  * nonzero)
921  */
922  for( i = 0; i < nbinvars + nintvars; ++i )
923  {
924  fixable[i] = TRUE;
925  fixvals[i] = 0.0;
926  ptcounter[i] = 0;
927  }
928  /* for each block, compare the selected extreme points */
929  for( i = 0; i < nblocks; ++i )
930  {
931  int blockrep;
932  SCIP_VAR* mastervar;
933  SCIP_VAR** origvars;
934  SCIP_Real* origvals;
935  int norigvars;
936  int selidx;
937 
938  /* get the block that represents this block (in case of aggregation) */
939  blockrep = GCGgetBlockRepresentative(scip, i);
940 
941  /* at least one extreme point must have been selected */
942  selidx = i * nusedpts;
943  assert(selection[selidx] != -1);
944 
945  /* check whether the block would be fixed entirely to zero;
946  * a neccessary condition is that only one extreme pt has been selected
947  * (actual original variable values are checked later)
948  */
949  selidx = i * nusedpts + 1;
950  if( selection[selidx] == -1 )
951  zeroblocks[i] = TRUE;
952  else
953  zeroblocks[i] = FALSE;
954 
955  /* compare the selected extreme points, where the first point is the reference point */
956  for( j = 0; j < nusedpts; ++j )
957  {
958  selidx = i * nusedpts + j;
959  if( selection[selidx] != -1 )
960  {
961  /* get master variable */
962  mastervar = mastervars[selection[selidx]];
963  assert(GCGvarGetBlock(mastervar) == blockrep);
964 
965  /* get extreme point */
966  origvars = GCGmasterVarGetOrigvars(mastervar);
967  origvals = GCGmasterVarGetOrigvals(mastervar);
968  norigvars = GCGmasterVarGetNOrigvars(mastervar);
969 
970  for( k = 0; k < norigvars; ++k )
971  {
972  SCIP_VAR* origvar;
973  SCIP_Bool firstblock;
974 
975  if( SCIPvarGetType(origvars[k]) > SCIP_VARTYPE_INTEGER )
976  continue;
977 
978  if( SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(origvars[k]), SCIPvarGetUbGlobal(origvars[k]) ) )
979  continue;
980 
981  /* get the corresponding pricing variable;
982  * check whether this is the first block in which this variable appears;
983  * search for the right original variable (in case of aggregation)
984  */
985  if( GCGoriginalVarIsLinking(origvars[k]) )
986  {
987 #ifndef NDEBUG
988  SCIP_VAR* pricingvar;
989 #endif
990  SCIP_VAR** linkingpricingvars;
991 
992  linkingpricingvars = GCGlinkingVarGetPricingVars(origvars[k]);
993 #ifndef NDEBUG
994  pricingvar = linkingpricingvars[blockrep];
995  assert(pricingvar != NULL);
996  assert(GCGvarIsPricing(pricingvar));
997 #endif
998 
999  /* for linking variables, also check whether this is
1000  * the first block the variable appears in
1001  */
1002  for( l = 0; l < blockrep; ++l )
1003  if( linkingpricingvars[l] != NULL )
1004  break;
1005  firstblock = (l == blockrep);
1006 
1007  /** @todo can there be aggregated linking variables? */
1008  origvar = origvars[k];
1009  }
1010  else
1011  {
1012  SCIP_VAR* pricingvar;
1013  SCIP_VAR** pricingorigvars;
1014  int npricingorigvars;
1015 
1016  pricingvar = GCGoriginalVarGetPricingVar(origvars[k]);
1017  assert(pricingvar != NULL);
1018  assert(GCGvarIsPricing(pricingvar));
1019 
1020  firstblock = TRUE;
1021 
1022  /* from all original variables corresponding to the current one,
1023  * get the one which belongs to the current block;
1024  * this is necessary since in case of identical, aggregated blocks,
1025  * the extreme point may belong to multiple blocks
1026  */
1027  npricingorigvars = GCGpricingVarGetNOrigvars(pricingvar);
1028  pricingorigvars = GCGpricingVarGetOrigvars(pricingvar);
1029  origvar = NULL;
1030  for( l = 0; l < npricingorigvars; ++l )
1031  if( GCGvarGetBlock(pricingorigvars[l]) == i )
1032  {
1033  origvar = pricingorigvars[l];
1034  break;
1035  }
1036  assert(origvar != NULL);
1037  }
1038 
1039  /* get the variable index */
1040  idx = SCIPvarGetProbindex(origvar);
1041  assert(idx < nbinvars + nintvars);
1042 
1043  /* the first extreme point serves as a reference point */
1044  if( j == 0 && firstblock )
1045  fixvals[idx] = origvals[k];
1046  /* the variable can not be be fixed if its value differs in the extreme points */
1047  else
1048  if( fixable[idx] && !SCIPisEQ(scip, fixvals[idx], origvals[k]) )
1049  fixable[idx] = FALSE;
1050 
1051  if( !SCIPisZero(scip, origvals[k]) )
1052  {
1053  ++ptcounter[idx];
1054  zeroblocks[i] = FALSE;
1055  }
1056  }
1057  }
1058  }
1059  }
1060 
1061  /* try to fix the binary and general integer variables */
1062  for( i = 0; i < nbinvars + nintvars; ++i )
1063  {
1064  SCIP_VAR* var;
1065  int block; /* current block we are working in */
1066  SCIP_Real lb;
1067  SCIP_Real ub;
1068 
1069  var = vars[i];
1070  assert(GCGvarIsOriginal(var));
1071  block = GCGvarGetBlock(var);
1072 
1073  /* Variables which were directly copied from the original problem do not appear in any extreme point;
1074  * they are fixed like in the RENS heuristic
1075  */
1076  if( block == -1 )
1077  {
1078  fixvals[i] = SCIPgetRelaxSolVal(scip, var);
1079  if( SCIPisFeasIntegral(scip, fixvals[i]) )
1080  {
1081  /* fix variable to current relaxation solution if it is integral;
1082  * use exact integral value, if the variable is only integral within numerical tolerances
1083  */
1084  fixvals[i] = SCIPfloor(scip, fixvals[i] + 0.5);
1085  }
1086  else
1087  fixable[i] = FALSE;
1088  }
1089 
1090  /* If the variable is assigned to a block, it is fixed it has the same value
1091  * in all selected extreme points of its blocks
1092  */
1093  else
1094  {
1095  int nlinkblocks;
1096 
1097  assert(block >= 0 || block == -2);
1098  nlinkblocks = GCGoriginalVarIsLinking(var) ? GCGlinkingVarGetNBlocks(var) : 1;
1099  assert(ptcounter[i] <= nusedpts * nlinkblocks);
1100 
1101  /* This case has not been treated yet:
1102  * A variable which has appeared nonzero in only some, but not all points
1103  * is not fixed
1104  */
1105  if( ptcounter[i] > 0 && ptcounter[i] < nusedpts * nlinkblocks )
1106  fixable[i] = FALSE;
1107 
1108  /* If the variable has not appeared in any extreme point, it should be fixed to zero */
1109 #ifdef SCIP_DEBUG
1110  if( ptcounter[i] == 0 )
1111  {
1112  assert(fixable[i]);
1113  assert(SCIPisZero(scip, fixvals[i]));
1114  }
1115 #endif
1116  }
1117 
1118  /* get variable's global bounds */
1119  lb = SCIPvarGetLbGlobal(var);
1120  ub = SCIPvarGetUbGlobal(var);
1121 
1122  /* The fixing value can be outside transformed global bounds */
1123  if( fixable[i] && (lb > fixvals[i] || fixvals[i] > ub) )
1124  fixable[i] = FALSE;
1125 
1126  /* The variable can be fixed if it has not been marked unfixable, which is the case if
1127  * - it was directly transferred to the master problem and has integer value or
1128  * - it appeared zero in all extreme points
1129  * - it did not appear zero in some extreme pts and nonzero in other extreme pts;
1130  * besides, we do not fix entire blocks to zero
1131  */
1132  if( fixable[i] && (block < 0 || !zeroblocks[block]) )
1133  {
1134  SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[i], fixvals[i]) );
1135  SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[i], fixvals[i]) );
1136 
1137  fixingcounter++;
1138 
1139  if( SCIPisZero(scip, fixvals[i]) )
1140  zerocounter++;
1141  }
1142  }
1143 
1144  *intfixingrate = (SCIP_Real)fixingcounter / (SCIP_Real)(MAX(nbinvars + nintvars, 1));
1145  *zerofixingrate = (SCIP_Real)zerocounter / MAX((SCIP_Real)fixingcounter, 1.0);
1146 
1147  /* if not enough variables were fixed, try to fix zero blocks until the minimum fixing rate is reached */
1148  while( *intfixingrate < heurdata->minfixingrate )
1149  {
1150  SCIPdebugMessage(" fixing rate only %5.2f --> trying to fix a zero block\n", *intfixingrate);
1151 
1152  /* get the next zero block */
1153  for( i = 0; i < nblocks; ++i )
1154  if( zeroblocks[i] )
1155  {
1156  /* fix variables */
1157  for( j = 0; j < nbinvars + nintvars; ++j )
1158  if( GCGvarGetBlock(vars[j]) == i && fixable[j] )
1159  {
1160  assert(SCIPisZero(scip, fixvals[j]));
1161  SCIP_CALL( SCIPchgVarLbGlobal(subscip, subvars[j], 0.0) );
1162  SCIP_CALL( SCIPchgVarUbGlobal(subscip, subvars[j], 0.0) );
1163  fixingcounter++;
1164  zerocounter++;
1165  }
1166 
1167  zeroblocks[i] = FALSE;
1168  break;
1169  }
1170 
1171  *intfixingrate = (SCIP_Real)fixingcounter / (SCIP_Real)(MAX(nbinvars + nintvars, 1));
1172  *zerofixingrate = (SCIP_Real)zerocounter / MAX((SCIP_Real)fixingcounter, 1.0);
1173 
1174  if( i == nblocks )
1175  break;
1176  }
1177 
1178  /* if all variables were fixed or amount of fixed variables is insufficient, abort immediately */
1179  if( *intfixingrate < heurdata->minfixingrate )
1180  {
1181  SCIPstatisticPrintf("xpcrossover statistic: fixed only %5.2f ( %5.2f zero) integer variables --> abort \n", *intfixingrate, *zerofixingrate);
1182  }
1183  if( fixingcounter == nbinvars + nintvars )
1184  {
1185  SCIPstatisticPrintf("xpcrossover statistic: fixed all ( %5.2f zero) integer variables --> abort \n", *zerofixingrate);
1186  }
1187 
1188  *success = TRUE;
1189 
1190  /* free memory */
1191  SCIPfreeBufferArray(scip, &zeroblocks);
1192  SCIPfreeBufferArray(scip, &fixvals);
1193  SCIPfreeBufferArray(scip, &fixable);
1194  SCIPfreeBufferArray(scip, &ptcounter);
1195 
1196  return SCIP_OKAY;
1197 }
1198 
1199 
1200 /** creates a new solution for the original problem by copying the solution of the subproblem */
1201 static
1202 SCIP_RETCODE createNewSol(
1203  SCIP* scip, /**< original SCIP data structure */
1204  SCIP* subscip, /**< SCIP structure of the subproblem */
1205  SCIP_VAR** subvars, /**< the variables of the subproblem */
1206  SCIP_HEUR* heur, /**< primal heuristic structure */
1207  SCIP_SOL* subsol, /**< solution of the subproblem */
1208  SCIP_Bool* success /**< used to store whether new solution was found or not */
1209  )
1210 {
1211 #ifdef SCIP_STATISTIC
1212  SCIP_HEURDATA* heurdata;
1213 #endif
1214  SCIP_VAR** vars; /* the original problem's variables */
1215  int nvars;
1216  SCIP_SOL* newsol; /* solution to be created for the original problem */
1217  SCIP_Real* subsolvals; /* solution values of the subproblem */
1218 
1219  assert(scip != NULL);
1220  assert(subscip != NULL);
1221  assert(subvars != NULL);
1222  assert(subsol != NULL);
1223 
1224 #ifdef SCIP_STATISTIC
1225  /* get heuristic data */
1226  heurdata = SCIPheurGetData(heur);
1227  assert( heurdata != NULL );
1228 #endif
1229 
1230  /* get variables' data */
1231  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
1232  assert(nvars <= SCIPgetNOrigVars(subscip));
1233 
1234  SCIP_CALL( SCIPallocBufferArray(scip, &subsolvals, nvars) );
1235 
1236  /* copy the solution */
1237  SCIP_CALL( SCIPgetSolVals(subscip, subsol, nvars, subvars, subsolvals) );
1238 
1239  /* create new solution for the original problem */
1240  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
1241  SCIP_CALL( SCIPsetSolVals(scip, newsol, nvars, vars, subsolvals) );
1242 
1243  /* try to add new solution to scip */
1244 #ifdef SCIP_STATISTIC
1245  if( !*success )
1246 #endif
1247  SCIP_CALL( SCIPtrySol(scip, newsol, FALSE, FALSE, TRUE, TRUE, TRUE, success) );
1248 
1249 #ifdef SCIP_STATISTIC
1250  if( SCIPgetSolTransObj(scip, newsol) < heurdata->bestprimalbd )
1251  heurdata->bestprimalbd = SCIPgetSolTransObj(scip, newsol);
1252 
1253  SCIPstatisticPrintf("xpcrossover statistic: Solution %13.6e found at node %"SCIP_LONGINT_FORMAT"\n",
1254  SCIPgetSolOrigObj(scip, newsol), SCIPsolGetNodenum(subsol));
1255 #endif
1256 
1257  SCIP_CALL( SCIPfreeSol(scip, &newsol) );
1258 
1259  SCIPfreeBufferArray(scip, &subsolvals);
1260 
1261  return SCIP_OKAY;
1262 }
1263 
1264 /** updates heurdata after a run of crossover */
1265 static
1267  SCIP* scip, /**< original SCIP data structure */
1268  SCIP_HEURDATA* heurdata /**< primal heuristic data */
1269  )
1270 {
1271  /* increase number of failures, calculate next node at which crossover should be called and update actual solutions */
1272  heurdata->nfailures++;
1273  heurdata->nextnodenumber = (heurdata->nfailures <= 25
1274  ? SCIPgetNNodes(scip) + 100*(2LL << heurdata->nfailures) /*lint !e703*/
1275  : SCIP_LONGINT_MAX);
1276 }
1277 
1278 
1279 /*
1280  * Callback methods of primal heuristic
1281  */
1282 
1283 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
1284 static
1285 SCIP_DECL_HEURFREE(heurFreeXpcrossover)
1286 { /*lint --e{715}*/
1287  SCIP_HEURDATA* heurdata;
1288 
1289  assert(heur != NULL);
1290  assert(scip != NULL);
1291 
1292  /* get heuristic data */
1293  heurdata = SCIPheurGetData(heur);
1294  assert(heurdata != NULL);
1295 
1296  /* free heuristic data */
1297  SCIPfreeMemory(scip, &heurdata);
1298  SCIPheurSetData(heur, NULL);
1299 
1300  return SCIP_OKAY;
1301 }
1302 
1303 /** initialization method of primal heuristic (called after problem was transformed) */
1304 static
1305 SCIP_DECL_HEURINIT(heurInitXpcrossover)
1306 { /*lint --e{715}*/
1307  SCIP_HEURDATA* heurdata;
1308 
1309  assert(heur != NULL);
1310  assert(scip != NULL);
1311 
1312  /* get heuristic data */
1313  heurdata = SCIPheurGetData(heur);
1314  assert(heurdata != NULL);
1315 
1316  /* initialize data */
1317  heurdata->usednodes = 0;
1318  heurdata->lasttuple = NULL;
1319  heurdata->nfailures = 0;
1320  heurdata->nextnodenumber = 0;
1321 
1322  /* create random number generator */
1323  SCIP_CALL( SCIPcreateRandom(scip, &heurdata->randnumgen,
1324  SCIPinitializeRandomSeed(scip, DEFAULT_RANDSEED), TRUE) );
1325 
1326  /* initialize hash table */
1327  SCIP_CALL( SCIPhashtableCreate(&heurdata->hashtable, SCIPblkmem(scip), HASHSIZE_POINTS,
1328  hashGetKeyPts, hashKeyEqPts, hashKeyValPts, NULL) );
1329  assert(heurdata->hashtable != NULL );
1330 
1331  return SCIP_OKAY;
1332 }
1333 
1334 /** deinitialization method of primal heuristic (called before transformed problem is freed) */
1335 static
1336 SCIP_DECL_HEUREXIT(heurExitXpcrossover)
1337 { /*lint --e{715}*/
1338  SCIP_HEURDATA* heurdata;
1339  POINTTUPLE* pointtuple;
1340 
1341  assert(heur != NULL);
1342  assert(scip != NULL);
1343 
1344  /* get heuristic data */
1345  heurdata = SCIPheurGetData(heur);
1346  assert(heurdata != NULL);
1347  pointtuple = heurdata->lasttuple;
1348 
1349  /* free all pointtuples iteratively */
1350  while( pointtuple != NULL )
1351  {
1352  POINTTUPLE* tmp;
1353  tmp = pointtuple->prev;
1354  SCIPfreeBlockMemoryArray(scip, &pointtuple->indices, pointtuple->size);
1355  SCIPfreeBlockMemory(scip, &pointtuple);
1356  pointtuple = tmp;
1357  }
1358 
1359  /* free hash table */
1360  assert(heurdata->hashtable != NULL );
1361  SCIPhashtableFree(&heurdata->hashtable);
1362 
1363  /* free random number generator */
1364  SCIPfreeRandom(scip, &heurdata->randnumgen);
1365 
1366  return SCIP_OKAY;
1367 }
1368 
1369 
1370 #ifdef SCIP_STATISTIC
1371 /** solving process initialization method of primal heuristic (called when branch and bound process is about to begin) */
1372 static
1373 SCIP_DECL_HEURINITSOL(heurInitsolXpcrossover)
1374 { /*lint --e{715}*/
1375  SCIP_HEURDATA* heurdata;
1376 
1377  assert(heur != NULL);
1378  assert(scip != NULL);
1379 
1380  /* get heuristic data */
1381  heurdata = SCIPheurGetData(heur);
1382  assert(heurdata != NULL);
1383 
1384  /* initialize statistical data */
1385  heurdata->avgfixrate = 0.0;
1386  heurdata->avgzerorate = 0.0;
1387  heurdata->totalsols = 0;
1388  heurdata->subsciptime = 0.0;
1389  heurdata->bestprimalbd = SCIPinfinity(scip);
1390 
1391  return SCIP_OKAY;
1392 }
1393 
1394 
1395 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
1396 static
1397 SCIP_DECL_HEUREXITSOL(heurExitsolXpcrossover)
1398 { /*lint --e{715}*/
1399  SCIP_HEURDATA* heurdata;
1400  SCIP_Longint ncalls;
1401 
1402  assert(heur != NULL);
1403  assert(scip != NULL);
1404 
1405  /* get heuristic data */
1406  heurdata = SCIPheurGetData(heur);
1407  assert(heurdata != NULL);
1408 
1409  ncalls = SCIPheurGetNCalls(heur);
1410  heurdata->avgfixrate /= MAX((SCIP_Real)ncalls, 1.0);
1411  heurdata->avgzerorate /= MAX((SCIP_Real)ncalls, 1.0);
1412 
1413  /* print detailed statistics */
1414  SCIPstatisticPrintf("LNS Statistics -- %s:\n", SCIPheurGetName(heur));
1415  SCIPstatisticPrintf("Calls : %13"SCIP_LONGINT_FORMAT"\n", ncalls);
1416  SCIPstatisticPrintf("Failed Fixings : %13"SCIP_LONGINT_FORMAT"\n", heurdata->nfixfails);
1417  SCIPstatisticPrintf("Sols : %13"SCIP_LONGINT_FORMAT"\n", SCIPheurGetNSolsFound(heur));
1418  SCIPstatisticPrintf("Improving Sols : %13"SCIP_LONGINT_FORMAT"\n", SCIPheurGetNBestSolsFound(heur));
1419  SCIPstatisticPrintf("Total Sols : %13"SCIP_LONGINT_FORMAT"\n", heurdata->totalsols);
1420  SCIPstatisticPrintf("subSCIP time : %13.2f\n", heurdata->subsciptime);
1421  SCIPstatisticPrintf("subSCIP nodes : %13"SCIP_LONGINT_FORMAT"\n", heurdata->usednodes);
1422  SCIPstatisticPrintf("Avg. fixing rate : %13.2f\n", 100.0 * heurdata->avgfixrate);
1423  SCIPstatisticPrintf("Avg. zero rate : %13.2f\n", 100.0 * heurdata->avgzerorate);
1424  SCIPstatisticPrintf("Best primal bd. :");
1425  if( SCIPisInfinity(scip, heurdata->bestprimalbd) )
1426  SCIPstatisticPrintf(" infinity\n");
1427  else
1428  SCIPstatisticPrintf(" %13.6e\n", heurdata->bestprimalbd);
1429  SCIPstatisticPrintf("\n");
1430 
1431  return SCIP_OKAY;
1432 }
1433 #endif
1434 
1435 
1436 /** execution method of primal heuristic */
1437 static
1438 SCIP_DECL_HEUREXEC(heurExecXpcrossover)
1439 { /*lint --e{715}*/
1440 
1441  SCIP* masterprob;
1442  SCIP_HEURDATA* heurdata;
1443 
1444  SCIP* subscip;
1445  SCIP_VAR** subvars;
1446 
1447  SCIP_Real memorylimit; /* memory limit for the subproblem */
1448  SCIP_Real timelimit; /* time limit for the subproblem */
1449  SCIP_Longint nstallnodes; /* node limit for the subproblem */
1450  SCIP_Real allfixingrate; /* percentage of all variables fixed */
1451  SCIP_Real intfixingrate; /* percentage of integer variables fixed */
1452  SCIP_Real zerofixingrate; /* percentage of variables fixed to zero */
1453 
1454  int* selection;
1455  int nblocks;
1456 
1457  SCIP_Bool success;
1458  SCIP_RETCODE retcode;
1459 
1460  int i;
1461 
1462  assert(heur != NULL);
1463  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
1464  assert(scip != NULL);
1465  assert(result != NULL);
1466 
1467  /* get master problem */
1468  masterprob = GCGgetMasterprob(scip);
1469  assert(masterprob != NULL);
1470 
1471  nblocks = GCGgetNPricingprobs(scip);
1472 
1473  /* get heuristic data */
1474  heurdata = SCIPheurGetData(heur);
1475  assert(heurdata != NULL);
1476 
1477  *result = SCIP_DELAYED;
1478 
1479  /* do not execute the heuristic on invalid relaxation solutions
1480  * (which is the case if the node has been cut off)
1481  */
1482  if( !SCIPisRelaxSolValid(scip) )
1483  {
1484  SCIPdebugMessage("skipping Extreme Point Crossover: invalid relaxation solution\n");
1485  return SCIP_OKAY;
1486  }
1487 
1488  /* only call heuristic, if an optimal LP solution is at hand */
1489  if( SCIPgetStage(masterprob) > SCIP_STAGE_SOLVING || SCIPgetLPSolstat(masterprob) != SCIP_LPSOLSTAT_OPTIMAL )
1490  {
1491  SCIPdebugMessage("skipping Extreme Point Crossover: master LP not solved to optimality.\n");
1492  return SCIP_OKAY;
1493  }
1494 
1495  assert(SCIPhasCurrentNodeLP(masterprob));
1496 
1497  /* if heuristic should be delayed, wait until certain number of nodes is reached */
1498  if( SCIPgetNNodes(scip) < heurdata->nextnodenumber )
1499  return SCIP_OKAY;
1500 
1501  *result = SCIP_DIDNOTRUN;
1502 
1503  /* only continue with some fractional variables */
1504  if( SCIPgetNExternBranchCands(scip) == 0 )
1505  return SCIP_OKAY;
1506 
1507  /* check whether there is enough time and memory left */
1508  timelimit = 0.0;
1509  memorylimit = 0.0;
1510  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
1511  if( !SCIPisInfinity(scip, timelimit) )
1512  timelimit -= SCIPgetSolvingTime(scip);
1513  SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
1514 
1515  /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
1516  if( !SCIPisInfinity(scip, memorylimit) )
1517  {
1518  memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
1519  memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
1520  }
1521 
1522  /* abort if no time is left or not enough memory to create a copy of SCIP, including external memory usage */
1523  if( timelimit <= 0.0 || memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
1524  return SCIP_OKAY;
1525 
1526  /* calculate the maximal number of branching nodes until heuristic is aborted */
1527  nstallnodes = (SCIP_Longint)(heurdata->nodesquot * SCIPgetNNodes(scip));
1528 
1529  /* reward Crossover if it succeeded often */
1530  nstallnodes = (SCIP_Longint)
1531  (nstallnodes * (1.0 + 2.0*(SCIPheurGetNBestSolsFound(heur)+1.0)/(SCIPheurGetNCalls(heur)+1.0)));
1532 
1533  /* count the setup costs for the sub-MIP as 100 nodes */
1534  nstallnodes -= 100 * SCIPheurGetNCalls(heur);
1535  nstallnodes += heurdata->nodesofs;
1536 
1537  /* determine the node limit for the current process */
1538  nstallnodes -= heurdata->usednodes;
1539  nstallnodes = MIN(nstallnodes, heurdata->maxnodes);
1540 
1541  /* check whether we have enough nodes left to call subproblem solving */
1542  if( nstallnodes < heurdata->minnodes )
1543  {
1544  SCIPdebugMessage("skipping Extreme Point Crossover: nstallnodes=%"SCIP_LONGINT_FORMAT", minnodes=%"SCIP_LONGINT_FORMAT"\n", nstallnodes, heurdata->minnodes);
1545  return SCIP_OKAY;
1546  }
1547 
1548  if( SCIPisStopped(scip) )
1549  return SCIP_OKAY;
1550 
1551  SCIPdebugMessage("Executing Extreme Point Crossover heuristic ...\n");
1552 
1553  /* allocate memory */
1554  SCIP_CALL( SCIPallocBufferArray(scip, &selection, nblocks * heurdata->nusedpts) );
1555  SCIP_CALL( SCIPallocBufferArray(scip, &subvars, SCIPgetNVars(scip)) );
1556 
1557  /* initialize empty selection */
1558  for( i = 0; i < nblocks * heurdata->nusedpts; ++i )
1559  selection[i] = -1;
1560 
1561  /* for each block, select extreme points (represented by master variables) considered for a crossover */
1562  success = FALSE;
1563  if( heurdata->randomization )
1564  {
1565  SCIPdebugMessage("selecting extreme points randomly...\n");
1566  SCIP_CALL( selectExtremePointsRandomized(scip, heurdata, selection, &success) );
1567  }
1568  if( !heurdata->randomization || !success )
1569  {
1570  SCIPdebugMessage("selecting extreme points...\n");
1571  SCIP_CALL( selectExtremePoints(scip, heurdata, selection, &success) );
1572  }
1573 
1574  /* do not execute heuristic if no new selection of extreme points was found */
1575  if( !success )
1576  {
1577  SCIPdebugMessage("no proper selection could be created - aborting heuristic.\n");
1578 
1579  updateFailureStatistic(scip, heurdata);
1580 
1581  /* free memory */
1582  SCIPfreeBufferArray(scip, &selection);
1583  SCIPfreeBufferArray(scip, &subvars);
1584 
1585  return SCIP_OKAY;
1586  }
1587 
1588 #ifdef PRINTPOINTS
1589  SCIP_CALL( printExtremePoints(scip, heurdata->nusedpts, selection) );
1590 #endif
1591 
1592  /* initialize the subproblem */
1593  SCIP_CALL( SCIPcreate(&subscip) );
1594  SCIP_CALL( setupSubproblem(scip, subscip, subvars, heurdata, nstallnodes, timelimit, memorylimit) );
1595  SCIPdebugMessage("XP Crossover subproblem: %d vars, %d conss\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip));
1596 
1597  SCIPstatisticPrintf("xpcrossover statistic: called at node %"SCIP_LONGINT_FORMAT"\n", SCIPgetNNodes(scip));
1598 
1599  /* fix the variables of the subproblem */
1600  SCIP_CALL( fixVariables(scip, subscip, subvars, selection, heurdata, &intfixingrate, &zerofixingrate, &success) );
1601 
1602 #ifdef SCIP_STATISTIC
1603  /* for final statistics */
1604  heurdata->avgfixrate += intfixingrate;
1605  heurdata->avgzerorate += zerofixingrate;
1606 #endif
1607 
1608  /* if creation of subscip was aborted (e.g. due to number of fixings), free subscip and abort */
1609  if( !success )
1610  {
1611  /* this run will be counted as a failure since the neighborhood of the
1612  * solution was not fruitful in the sense that it was too big
1613  */
1614  updateFailureStatistic(scip, heurdata);
1615 #ifdef SCIP_STATISTIC
1616  ++heurdata->nfixfails;
1617 #endif
1618  goto TERMINATE;
1619  }
1620 
1621  *result = SCIP_DIDNOTFIND;
1622 
1623  /* presolve the subproblem */
1624  retcode = SCIPpresolve(subscip);
1625 
1626  /* errors in solving the subproblem should not kill the overall solving process;
1627  * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop.
1628  */
1629  if( retcode != SCIP_OKAY )
1630  {
1631 #ifndef NDEBUG
1632  SCIP_CALL( retcode );
1633 #endif
1634  SCIPwarningMessage(scip, "Error while presolving subproblem in XP Crossover heuristic; sub-SCIP terminated with code <%d>\n",retcode);
1635  goto TERMINATE;
1636  }
1637 
1638  SCIPdebugMessage("XP Crossover presolved subproblem: %d vars, %d conss, success=%u\n", SCIPgetNVars(subscip), SCIPgetNConss(subscip), success);
1639 
1640  allfixingrate = (SCIPgetNOrigVars(subscip) - SCIPgetNVars(subscip)) / (SCIP_Real)SCIPgetNOrigVars(subscip);
1641 
1642  /* additional variables added in presolving may lead to the subSCIP having more variables than the original */
1643  allfixingrate = MAX(allfixingrate, 0.0);
1644 
1645  /* after presolving, we should have at least reached a certain fixing rate over ALL variables (including continuous)
1646  * to ensure that not only the MIP but also the LP relaxation is easy enough
1647  */
1648  if( allfixingrate >= heurdata->minfixingrate / 2.0 )
1649  {
1650  SCIP_SOL** subsols;
1651  int nsubsols;
1652 
1653  /* solve the subproblem */
1654  SCIPdebugMessage("subSCIP: Solving... (node limit = %lld, time limit = %.2g)\n", nstallnodes, timelimit);
1655 
1656  /* Errors in the LP solver should not kill the overall solving process, if the LP is just needed for a heuristic.
1657  * Hence in optimized mode, the return code is catched and a warning is printed, only in debug mode, SCIP will stop.
1658  */
1659 #ifdef NDEBUG
1660  retcode = SCIPsolve(subscip);
1661  if( retcode != SCIP_OKAY )
1662  {
1663  SCIPwarningMessage(scip, "Error while solving subproblem in XP Crossover heuristic; sub-SCIP terminated with code <%d>\n",
1664  retcode);
1665  }
1666 #else
1667  SCIP_CALL( SCIPsolve(subscip) );
1668 #endif
1669 
1670 #ifdef SCIP_STATISTIC
1671  heurdata->usednodes += SCIPgetNNodes(subscip);
1672  heurdata->subsciptime += SCIPgetTotalTime(subscip);
1673 #endif
1674 
1675  /* check, whether a solution was found;
1676  * due to numerics, it might happen that not all solutions are feasible -> try all solutions until one was accepted
1677  */
1678  nsubsols = SCIPgetNSols(subscip);
1679  subsols = SCIPgetSols(subscip);
1680  success = FALSE;
1681 #ifdef SCIP_STATISTIC
1682  heurdata->totalsols += nsubsols;
1683  for( i = 0; i < nsubsols; ++i )
1684 #else
1685  for( i = 0; i < nsubsols && !success; ++i )
1686 #endif
1687  {
1688  SCIP_CALL( createNewSol(scip, subscip, subvars, heur, subsols[i], &success) );
1689  if( success )
1690  *result = SCIP_FOUNDSOL;
1691  }
1692 
1693  SCIPstatisticPrintf("xpcrossover statistic: fixed %6.3f integer variables ( %6.3f zero), %6.3f all variables, needed %6.1f sec (SCIP time: %6.1f sec), %"SCIP_LONGINT_FORMAT" nodes, found %d solutions, solution %10.4f found at node %"SCIP_LONGINT_FORMAT"\n",
1694  intfixingrate, zerofixingrate, allfixingrate, SCIPgetSolvingTime(subscip), SCIPgetSolvingTime(scip), SCIPgetNNodes(subscip), nsubsols,
1695  success ? SCIPgetPrimalbound(scip) : SCIPinfinity(scip), nsubsols > 0 ? SCIPsolGetNodenum(SCIPgetBestSol(subscip)) : -1 );
1696 
1697  if( !success )
1698  {
1699  /* if no new solution was found, run was a failure */
1700  updateFailureStatistic(scip, heurdata);
1701  SCIPdebugMessage(" -> no subMIP solution found - subSCIP status is %d\n", SCIPgetStatus(subscip));
1702  }
1703  }
1704  else
1705  {
1706  SCIPstatisticPrintf("xpcrossover statistic: fixed only %6.3f integer variables ( %6.3f zero), %6.3f all variables --> abort \n", intfixingrate, zerofixingrate, allfixingrate);
1707  }
1708 
1709 TERMINATE:
1710  /* free memory */
1711  SCIP_CALL( SCIPfree(&subscip) );
1712  SCIPfreeBufferArray(scip, &selection);
1713  SCIPfreeBufferArray(scip, &subvars);
1714 
1715  return SCIP_OKAY;
1716 }
1717 
1718 
1719 
1720 /*
1721  * primal heuristic specific interface methods
1722  */
1723 
1724 /** creates the Extreme Point Crossover primal heuristic and includes it in SCIP */
1726  SCIP* scip /**< SCIP data structure */
1727  )
1728 {
1729  SCIP_HEURDATA* heurdata;
1730  SCIP_HEUR* heur;
1731 
1732  /* create Extreme Point Crossover primal heuristic data */
1733  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
1734 
1735  /* include primal heuristic */
1736  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
1738  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecXpcrossover, heurdata) );
1739 
1740  assert(heur != NULL);
1741 
1742  /* set non-NULL pointers to callback methods */
1743  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeXpcrossover) );
1744  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitXpcrossover) );
1745  SCIP_CALL( SCIPsetHeurExit(scip, heur, heurExitXpcrossover) );
1746 #ifdef SCIP_STATISTIC
1747  SCIP_CALL( SCIPsetHeurInitsol(scip, heur, heurInitsolXpcrossover) );
1748  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolXpcrossover) );
1749 #endif
1750 
1751  /* add Extreme Point Crossover primal heuristic parameters */
1752 
1753  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/nodesofs",
1754  "number of nodes added to the contingent of the total nodes",
1755  &heurdata->nodesofs, FALSE, DEFAULT_NODESOFS, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1756 
1757  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/maxnodes",
1758  "maximum number of nodes to regard in the subproblem",
1759  &heurdata->maxnodes, TRUE, DEFAULT_MAXNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1760 
1761  SCIP_CALL( SCIPaddLongintParam(scip, "heuristics/"HEUR_NAME"/minnodes",
1762  "minimum number of nodes required to start the subproblem",
1763  &heurdata->minnodes, TRUE, DEFAULT_MINNODES, 0LL, SCIP_LONGINT_MAX, NULL, NULL) );
1764 
1765  SCIP_CALL( SCIPaddIntParam(scip, "heuristics/"HEUR_NAME"/nusedpts",
1766  "number of extreme pts per block that will be taken into account",
1767  &heurdata->nusedpts, FALSE, DEFAULT_NUSEDPTS, 2, INT_MAX, NULL, NULL) );
1768 
1769  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/nodesquot",
1770  "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1771  &heurdata->nodesquot, FALSE, DEFAULT_NODESQUOT, 0.0, 1.0, NULL, NULL) );
1772 
1773  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/minfixingrate",
1774  "minimum percentage of integer variables that have to be fixed",
1775  &heurdata->minfixingrate, FALSE, DEFAULT_MINFIXINGRATE, 0.0, 1.0, NULL, NULL) );
1776 
1777  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/"HEUR_NAME"/minimprove",
1778  "factor by which crossover should at least improve the incumbent",
1779  &heurdata->minimprove, TRUE, DEFAULT_MINIMPROVE, 0.0, 1.0, NULL, NULL) );
1780 
1781  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/randomization",
1782  "should the choice which sols to take be randomized?",
1783  &heurdata->randomization, TRUE, DEFAULT_RANDOMIZATION, NULL, NULL) );
1784 
1785  SCIP_CALL( SCIPaddBoolParam(scip, "heuristics/"HEUR_NAME"/copycuts",
1786  "if uselprows == FALSE, should all active cuts from cutpool be copied to constraints in subproblem?",
1787  &heurdata->copycuts, TRUE, DEFAULT_COPYCUTS, NULL, NULL) );
1788 
1789  return SCIP_OKAY;
1790 }
SCIP_HASHTABLE * hashtable
int GCGgetBlockRepresentative(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:4023
#define DEFAULT_RANDOMIZATION
static SCIP_DECL_HEURINITSOL(heurInitsolGcgdins)
Definition: heur_gcgdins.c:485
int GCGmasterVarGetNOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:886
#define DEFAULT_MINIMPROVE
GCG interface methods.
SCIP_Bool GCGvarIsMaster(SCIP_VAR *var)
Definition: gcgvar.c:150
unsigned int key
#define HEUR_MAXDEPTH
#define DEFAULT_NODESOFS
#define HEUR_USESSUBSCIP
SCIP_Real minimprove
Definition: heur_gcgdins.c:80
#define HEUR_FREQOFS
#define DEFAULT_NODESQUOT
#define DEFAULT_RANDSEED
#define DEFAULT_COPYCUTS
SCIP_RETCODE SCIPincludeHeurXpcrossover(SCIP *scip)
static SCIP_DECL_HEURFREE(heurFreeXpcrossover)
static SCIP_RETCODE fixVariables(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, int *selection, SCIP_HEURDATA *heurdata, SCIP_Real *intfixingrate, SCIP_Real *zerofixingrate, SCIP_Bool *success)
POINTTUPLE * prev
SCIP_VAR ** GCGmasterVarGetOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:908
SCIP_Real * GCGmasterVarGetOrigvals(SCIP_VAR *var)
Definition: gcgvar.c:932
int GCGvarGetBlock(SCIP_VAR *var)
Definition: gcgvar.c:1033
int GCGlinkingVarGetNBlocks(SCIP_VAR *var)
Definition: gcgvar.c:493
#define HASHSIZE_POINTS
SCIP_Bool GCGvarIsPricing(SCIP_VAR *var)
Definition: gcgvar.c:134
SCIP_Bool copycuts
Definition: heur_gcgdins.c:89
SCIP_Longint nodesofs
Definition: heur_gcgdins.c:76
SCIP_VAR * GCGoriginalVarGetPricingVar(SCIP_VAR *var)
Definition: gcgvar.c:216
int GCGgetNPricingprobs(SCIP *scip)
Definition: relax_gcg.c:3979
SCIP_RANDNUMGEN * randnumgen
SCIP_Bool GCGvarIsOriginal(SCIP_VAR *var)
Definition: gcgvar.c:166
SCIP_Longint nextnodenumber
#define HEUR_FREQ
#define HEUR_DISPCHAR
SCIP * GCGgetMasterprob(SCIP *scip)
Definition: relax_gcg.c:3920
#define DEFAULT_MAXNODES
int GCGpricingVarGetNOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:997
#define DEFAULT_MINNODES
static SCIP_RETCODE selectExtremePointsRandomized(SCIP *scip, SCIP_HEURDATA *heurdata, int *selection, SCIP_Bool *success)
#define HEUR_NAME
SCIP_Longint maxnodes
Definition: heur_gcgdins.c:77
#define HEUR_TIMING
static SCIP_RETCODE selectExtremePoints(SCIP *scip, SCIP_HEURDATA *heurdata, int *selection, SCIP_Bool *success)
static SCIP_DECL_HEURINIT(heurInitXpcrossover)
int GCGgetNIdenticalBlocks(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:4053
static SCIP_DECL_HASHKEYEQ(hashKeyEqPts)
static SCIP_RETCODE setupSubproblem(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEURDATA *heurdata, SCIP_Longint nstallnodes, SCIP_Real timelimit, SCIP_Real memorylimit)
POINTTUPLE * lasttuple
static SCIP_DECL_HASHGETKEY(hashGetKeyPts)
static SCIP_DECL_HEUREXEC(heurExecXpcrossover)
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success)
SCIP_SOL * GCGrelaxGetCurrentOrigSol(SCIP *scip)
Definition: relax_gcg.c:4183
unsigned int nfailures
static void updateFailureStatistic(SCIP *scip, SCIP_HEURDATA *heurdata)
SCIP_VAR ** GCGpricingVarGetOrigvars(SCIP_VAR *var)
Definition: gcgvar.c:1015
Extreme Point Crossover.
static SCIP_DECL_HEUREXITSOL(heurExitsolGcgdins)
Definition: heur_gcgdins.c:529
static SCIP_DECL_HEUREXIT(heurExitXpcrossover)
#define HEUR_DESC
static unsigned int calculateHashKey(int *indices, int size)
#define DEFAULT_NUSEDPTS
SCIP_Bool GCGmasterVarIsRay(SCIP_VAR *var)
Definition: gcgvar.c:852
#define HEUR_PRIORITY
SCIP_Bool GCGoriginalVarIsLinking(SCIP_VAR *var)
Definition: gcgvar.c:182
static SCIP_RETCODE createPtTuple(SCIP *scip, POINTTUPLE **elem, int *indices, int size, SCIP_HEURDATA *heurdata)
SCIP_Bool GCGisPricingprobRelevant(SCIP *scip, int pricingprobnr)
Definition: relax_gcg.c:4000
SCIP_Longint usednodes
Definition: heur_gcgdins.c:81
SCIP_VAR ** GCGlinkingVarGetPricingVars(SCIP_VAR *var)
Definition: gcgvar.c:409
SCIP_Longint minnodes
Definition: heur_gcgdins.c:78
SCIP_Bool randomization
#define DEFAULT_MINFIXINGRATE
SCIP_Real minfixingrate
Definition: heur_gcgrens.c:84
SCIP_Real nodesquot
Definition: heur_gcgdins.c:82
static SCIP_DECL_HASHKEYVAL(hashKeyValPts)