Scippy

SCIP

Solving Constraint Integer Programs

heur_cyckerlin.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_cyckerlin.c
17  * @brief improvement heuristic that exchanges binary variables between clusters.
18  * Similar to the famous kernighan/lin heuristic for graph partitioning
19  * @author Leon Eifler
20  */
21 
22 /*---+---- 1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include "heur_cyckerlin.h"
25 
26 #include <assert.h>
27 #include <string.h>
28 
29 #include "probdata_cyc.h"
30 #include "scip/pub_misc.h"
31 
32 #define HEUR_NAME "cyckerlin"
33 #define HEUR_DESC "switch heuristic that tries to improve solution by trading states betweeen clusters"
34 #define HEUR_DISPCHAR '@'
35 #define HEUR_PRIORITY 500
36 #define HEUR_FREQ 10
37 #define HEUR_FREQOFS 0
38 #define HEUR_MAXDEPTH -1
39 #define MAXPERMUTATIONS 5
40 #define DEFAULT_RANDSEED 177 /**< random seed */
41 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
42 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
43 
44 struct SCIP_HeurData
45 {
46  SCIP_SOL** candidates;
47  int ncandidates;
48  int candlength;
49 };
50 
51 /*
52  * Local methods
53  */
54 
55 /** external method that adds a solution to the list of candidate-solutions that should be improved */
57  SCIP* scip, /**< SCIP data structure */
58  SCIP_SOL* sol /**< the given solution */
59  )
60 {
61  SCIP_HEUR* heur;
62  SCIP_HEURDATA* heurdata;
63 
64  heur = SCIPfindHeur(scip, "cyckerlin");
65 
66  if( heur == NULL )
67  return SCIP_OKAY;
68 
69  heurdata = SCIPheurGetData(heur);
70 
71  assert(heurdata != NULL);
72  assert(sol != NULL);
73 
74  /* realloc candidate array, if necessary */
75  if( heurdata->candlength - 1 <= heurdata->ncandidates )
76  {
77  SCIP_CALL( SCIPreallocMemoryArray(scip, &(heurdata->candidates), (SCIP_Longint) heurdata->candlength * 2) );
78  heurdata->candlength *= 2;
79  }
80 
81  heurdata->candidates[heurdata->ncandidates] = sol;
82  heurdata->ncandidates++;
83 
84  return SCIP_OKAY;
85 }
86 
87 
88 /** get the bin-var assignment from scip and save it as a matrix */
89 static
91  SCIP* scip, /**< SCIP data structure */
92  SCIP_SOL* bestsol, /**< the solution */
93  SCIP_Real** solclustering, /**< matrix to save the bin-vars*/
94  SCIP_Bool** binfixed, /**< matrix to save if a bin is fixed in scip */
95  int* clusterofbin, /**< array containing the cluster of each bin */
96  int* nbinsincluster /**< number of bins in each cluster */
97  )
98 {
99  SCIP_VAR*** binvars;
100  int nbins;
101  int ncluster;
102  int i;
103  int c;
104 
105  assert(bestsol != NULL);
106 
107  nbins = SCIPcycGetNBins(scip);
108  ncluster = SCIPcycGetNCluster(scip);
109  binvars = SCIPcycGetBinvars(scip);
110 
111  assert(nbins > 0 && ncluster > 0 && nbins > ncluster);
112  assert(binvars != NULL);
113 
114  /* get the bin-variable values from the solution */
115  for( i = 0; i < nbins; ++i )
116  {
117  for( c = 0; c < ncluster; ++c )
118  {
119  binfixed[i][c] = FALSE;
120 
121  if( binvars[i][c] != NULL)
122  {
123  if( (SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(binvars[i][c]), SCIPvarGetLbGlobal(binvars[i][c]))) )
124  binfixed[i][c] = TRUE;
125 
126  solclustering[i][c] = SCIPgetSolVal(scip, bestsol, binvars[i][c]);
127 
128  if( SCIPisFeasEQ(scip, solclustering[i][c], 1.0) )
129  {
130  clusterofbin[i] = c;
131  nbinsincluster[c]++;
132  }
133  }
134  }
135  }
136 
137  return SCIP_OKAY;
138 }
139 
140 /** Set a bin to a new cluster, update the qmatrix. */
141 static
143  SCIP_Real** solclustering, /**< the matrix with the clustering of the bins */
144  SCIP_Real** cmatrix, /**< the transition matrix*/
145  SCIP_Real** qmatrix, /**< the matrix containing the transition probabilities between clusters*/
146  int newbin, /**< the bin to be changed*/
147  int newcluster, /**< the cluster where the bin is changed*/
148  SCIP_Bool setone, /**< TRUE if the assignment is switched from 0 to 1, FALSE if 1 to 0*/
149  int nbins, /**< the number of bins*/
150  int ncluster /**< the number of clusters*/
151  )
152 {
153  int bin;
154  int cluster;
155  SCIP_Real sign = setone ? 1.0 : -1.0;
156 
157  for( cluster = 0; cluster < ncluster; ++cluster )
158  {
159  for( bin = 0; bin < nbins; ++bin )
160  {
161  if( cluster != newcluster )
162  {
163  qmatrix[newcluster][cluster] += sign * solclustering[bin][cluster] * cmatrix[newbin][bin];
164  qmatrix[cluster][newcluster] += sign * solclustering[bin][cluster] * cmatrix[bin][newbin];
165  }
166  else
167  {
168  if( bin != newbin )
169  {
170  qmatrix[newcluster][newcluster] += sign * (cmatrix[newbin][bin] + cmatrix[bin][newbin])
171  * solclustering[bin][cluster];
172  }
173  }
174  }
175  }
176 
177  solclustering[newbin][newcluster] = (sign + 1.0) / 2.0;
178 }
179 
180 /** initialize the q-matrix from a given (possibly incomplete) clusterassignment */
181 static
183  SCIP_Real** clustering, /**< the matrix containing the clusterassignment */
184  SCIP_Real** qmatrix, /**< the returned matrix the transition probability between clusters */
185  SCIP_Real** cmatrix, /**< the transition-matrix containg the probability-data */
186  int nbins, /**< the number of bins */
187  int ncluster /**< the number of possible clusters */
188  )
189 {
190  int i;
191  int j;
192  int k;
193  int l;
194 
195  for( k = 0; k < ncluster; ++k )
196  {
197  for( l = 0; l < ncluster; ++l )
198  {
199  qmatrix[k][l] = 0;
200  for( i = 0; i < nbins; ++i )
201  {
202  for( j = 0; j < nbins; ++j )
203  {
204  /* as -1 and 0 are both interpreted as 0, this check is necessary. Compute x_ik*x_jl*c_ij */
205  if( i == j )
206  continue;
207 
208  qmatrix[k][l] += cmatrix[i][j] * clustering[i][k] * clustering[j][l];
209  }
210  }
211  }
212  }
213 }
214 
215 /** calculate the current objective value for a q-matrix */
216 static
218  SCIP* scip, /**< SCIP data structure */
219  SCIP_Real** qmatrix, /**< the irreversibility matrix*/
220  SCIP_Real scale, /**< the scaling parameter in the objective function */
221  int ncluster /**< the number of cluster*/
222  )
223 {
224  SCIP_Real objective = 0.0;
225  int c;
226  int c2;
227 
228  for( c = 0; c < ncluster; ++c )
229  {
230  c2 = ( c + 1 ) % ncluster;
231  objective += ( qmatrix[c][c2] - qmatrix[c2][c]);
232  objective += scale * qmatrix[c][c];
233  }
234 
235  /* if we have no transitions at all then irreversibility should be set to 0 */
236  return objective;
237 }
238 
239 /** exchange another bin to a different cluster. No bin may be changed twice */
240 static
242  SCIP* scip, /**< SCIP data structure */
243  SCIP_Real** cmatrix, /**< the transition matrix */
244  SCIP_Real** qmatrix, /**< the irreversibility matrix */
245  SCIP_Real** clustering, /**< the clusterassignement */
246  SCIP_Bool** binfixed, /**< array containing information about fixedbins */
247  SCIP_Bool* binprocessed, /**< has the bin already been switched? */
248  int* clusterofbin, /**< contains the cluster each bin is in at the moment */
249  int* nbinsincluster, /**< number of bins in each cluster */
250  int* switchedbin, /**< the bins swithced in each iteration */
251  int* switchedcluster, /**< the cluster to witch the bin was assigned in each iteration */
252  SCIP_Real* switchbound, /**< the objective achieved in each iteration */
253  SCIP_Real* maxbound, /**< the best objective value so far */
254  int* bestlength, /**< the amount of switches with the best objective value so far */
255  int iteration /**< which iteration are we in */
256  )
257 {
258  SCIP_Real irrevchg;
259  SCIP_Real cohchg;
260  SCIP_Real maxboundlocal;
261  SCIP_Real scale;
262  SCIP_Real oldobjective;
263  int bin;
264  int k;
265  int i;
266  int l;
267  int indkmin;
268  int indlmin;
269  int maxbin;
270  int maxcluster;
271  int nbins = SCIPcycGetNBins(scip);
272  int ncluster = SCIPcycGetNCluster(scip);
273 
274  scale = SCIPcycGetScale(scip);
275  maxboundlocal = -SCIPinfinity(scip);
276  oldobjective = getObjective(scip, qmatrix, scale, ncluster);
277  maxbin = -1;
278  maxcluster = -1;
279 
280  assert(isPartition(scip, clustering, nbins, ncluster));
281 
282  for( bin = 0; bin < nbins; ++bin )
283  {
284  if( binprocessed[bin] || nbinsincluster[clusterofbin[bin]] == 1 )
285  continue;
286  k = clusterofbin[bin];
287 
288  assert(SCIPisFeasEQ(scip, clustering[bin][k], 1.0));
289 
290  /* calculate the irreversibility and coherence after bin was moved from k to l */
291  for( l = 0; l < ncluster; ++l )
292  {
293  if( binfixed[bin][k] || binfixed[bin][l] )
294  continue;
295 
296  if( k == l )
297  continue;
298 
299  if( k == 0 )
300  indkmin = ncluster - 1;
301  else
302  indkmin = k - 1;
303 
304  if( l == 0 )
305  indlmin = ncluster - 1;
306  else
307  indlmin = l - 1;
308 
309  irrevchg = 0;
310  cohchg = 0;
311 
312  assert(SCIPisZero(scip, clustering[bin][l]));
313 
314  for( i = 0; i < nbins; ++i )
315  {
316  /*irreversibility change */
317  irrevchg -= clustering[i][indkmin] * (cmatrix[i][bin] - cmatrix[bin][i]);
318  irrevchg -= clustering[i][(k+1) % ncluster] * (cmatrix[bin][i] - cmatrix[i][bin]);
319 
320  clustering[bin][k] = 0;
321  clustering[bin][l] = 1;
322 
323  irrevchg += clustering[i][indlmin] * (cmatrix[i][bin] - cmatrix[bin][i]);
324  irrevchg += clustering[i][(l+1) % ncluster] * (cmatrix[bin][i] - cmatrix[i][bin]);
325 
326  clustering[bin][k] = 1;
327  clustering[bin][l] = 0;
328 
329  /*coherence change */
330  if( i != bin )
331  {
332  cohchg -= clustering[i][k] * (cmatrix[bin][i]+ cmatrix[i][bin]);
333  cohchg += clustering[i][l] * (cmatrix[bin][i]+ cmatrix[i][bin]);
334  }
335  }
336 
337  if( oldobjective + irrevchg + scale * cohchg > maxboundlocal )
338  {
339  maxboundlocal = oldobjective + irrevchg + scale * cohchg;
340  maxbin = bin;
341  maxcluster = l;
342  }
343  }
344  }
345 
346  if( maxbin == -1 )
347  return FALSE;
348 
349  assert(maxbin >= 0 && maxcluster >= 0);
350  assert(maxbin < nbins && maxcluster < ncluster);\
351 
352  /* assign the exchange and update all saving-structures */
353  setBinToCluster(clustering, cmatrix, qmatrix, maxbin, clusterofbin[maxbin], FALSE, nbins, ncluster);
354  setBinToCluster(clustering, cmatrix, qmatrix, maxbin, maxcluster, TRUE, nbins, ncluster);
355 
356  nbinsincluster[clusterofbin[maxbin]]--;
357  nbinsincluster[maxcluster]++;
358 
359  clusterofbin[maxbin] = maxcluster;
360  binprocessed[maxbin] = TRUE;
361 
362  switchedbin[iteration] = maxbin;
363  switchedcluster[iteration] = maxcluster;
364  switchbound[iteration] = getObjective(scip, qmatrix, scale, ncluster);
365 
366  if( switchbound[iteration] > *maxbound )
367  {
368  *maxbound = switchbound[iteration];
369  *bestlength = iteration;
370  }
371 
372  return TRUE;
373 }
374 
375 /** Create a solution in scip from the clustering */
376 static
378  SCIP* scip, /**< SCIP data structure */
379  SCIP_HEUR* heur, /**< heuristic pointer */
380  SCIP_Real** cmatrix, /**< the transition matrix */
381  SCIP_Real** qmatrix, /**< the projected transition matrix using the clustering */
382  SCIP_Bool** binfixed, /**< matrix that tells which bin-variables cannot be changed */
383  SCIP_Real** startclustering, /**< the start-assignment */
384  SCIP_RESULT* result, /**< result pointer */
385  int nbins, /**< the number of states */
386  int ncluster /**< the number of clusters */
387  )
388 {
389  SCIP_SOL* bestsol;
390  SCIP_SOL* worksol;
391  SCIP_Real** clustering;
392  SCIP_Real** solclustering;
393  SCIP_Bool* binprocessed;
394  SCIP_Real max;
395  SCIP_Real objective;
396  SCIP_Real* switchbound;
397  SCIP_Real maxbound;
398  SCIP_Bool heurpossible = TRUE;
399  SCIP_Bool feasible;
400  int c;
401  int i;
402  int* nbinsincluster; /*lint !e771*/
403  int* switchedbin;
404  int* switchedcluster;
405  int* clusterofbin;
406  int bestlength;
407  int nrswitches;
408 
409  /* allocate memory */
410  SCIP_CALL( SCIPallocBufferArray(scip, &binprocessed, nbins) );
411  SCIP_CALL( SCIPallocBufferArray(scip, &switchbound, nbins) );
412  SCIP_CALL( SCIPallocBufferArray(scip, &nbinsincluster, ncluster) );
413  SCIP_CALL( SCIPallocBufferArray(scip, &switchedbin, nbins) );
414  SCIP_CALL( SCIPallocBufferArray(scip, &switchedcluster, nbins) );
415  SCIP_CALL( SCIPallocBufferArray(scip, &clusterofbin, nbins) );
416  SCIP_CALL( SCIPallocClearBufferArray(scip, &clustering, nbins) );
417  SCIP_CALL( SCIPallocClearBufferArray(scip, &solclustering, nbins) );
418 
419  for( i = 0; i < nbins; ++i )
420  {
421  SCIP_CALL( SCIPallocClearBufferArray(scip, &clustering[i], ncluster) ); /*lint !e866*/
422  SCIP_CALL( SCIPallocClearBufferArray(scip, &solclustering[i], ncluster) ); /*lint !e866*/
423  }
424 
425  /* copy the solution so that we may change it and still keep the original one*/
426  for( c = 0; c < ncluster; ++c )
427  {
428  nbinsincluster[c] = 0;
429  }
430 
431  for( i = 0; i < nbins; ++i )
432  {
433  for( c = 0; c < ncluster; ++c )
434  {
435  solclustering[i][c] = startclustering[i][c];
436 
437  if( SCIPisFeasEQ(scip, startclustering[i][c], 1.0) )
438  {
439  clusterofbin[i] = c;
440  nbinsincluster[c]++; /*lint !e771*/
441  }
442  }
443 
444  binprocessed[i] = FALSE;
445  }
446 
447  bestsol = SCIPgetBestSol(scip);
448 
449  while( heurpossible )
450  {
451  /* we run the heuristic until we cannot find any more improvement */
452  for( c = 0; c < ncluster; ++c )
453  {
454  nbinsincluster[c] = 0;
455  }
456 
457  for( i = 0; i < nbins; ++i )
458  {
459  for( c = 0; c < ncluster; ++c )
460  {
461  clustering[i][c] = solclustering[i][c];
462 
463  if( SCIPisFeasEQ(scip, solclustering[i][c], 1.0) )
464  {
465  clusterofbin[i] = c;
466  nbinsincluster[c]++;
467  }
468  }
469 
470  binprocessed[i] = FALSE;
471  }
472 
473  bestlength = -1;
474  nrswitches = nbins;
475 
476  /* initialize qmatrix */
477  computeIrrevMat(solclustering, qmatrix, cmatrix, nbins, ncluster);
478  maxbound = SCIPgetSolOrigObj(scip, bestsol);
479 
480  /* main part of the heuristic. States are switched until every state has been exchanged exactly once */
481  for( i = 0; i < nrswitches; ++i )
482  {
483  if( !switchNext(scip, cmatrix, qmatrix, clustering, binfixed, binprocessed, clusterofbin,
484  nbinsincluster, switchedbin, switchedcluster, switchbound, &maxbound, &bestlength, i) )
485  {
486  nrswitches = i;
487  break;
488  }
489  }
490 
491  /* select the clustering with the best objective and reconstruct it from the start clustering */
492  for( i = 0; i <= bestlength; ++i )
493  {
494  for( c = 0; c < ncluster; ++c )
495  {
496  solclustering[switchedbin[i]][c] = 0; /*lint !e771*/
497  }
498 
499  solclustering[switchedbin[i]][switchedcluster[i]] = 1; /*lint !e771*/
500  clusterofbin[switchedbin[i]] = switchedcluster[i];
501  }
502 
503  computeIrrevMat(solclustering, qmatrix, cmatrix, nbins, ncluster);
504  max = getObjective(scip, qmatrix, SCIPcycGetScale(scip), ncluster);
505  objective = SCIPgetSolOrigObj(scip, bestsol);
506  feasible = FALSE;
507 
508  /* if the solution is an improvement we add it to scip */
509  if( max > objective )
510  {
511  SCIP_CALL( SCIPcreateSol(scip, &worksol, heur) );
512 
513  assert(isPartition(scip, solclustering, nbins, ncluster));
514 
515  SCIP_CALL( assignVars(scip, worksol, solclustering, nbins, ncluster) );
516  SCIP_CALL( SCIPtrySolFree(scip, &worksol, FALSE, TRUE, TRUE, TRUE, TRUE, &feasible) );
517  }
518 
519  if( feasible )
520  {
521  *result = SCIP_FOUNDSOL;
522  objective = max;
523  }
524  else
525  {
526  *result = SCIP_DIDNOTFIND;
527  heurpossible = FALSE;
528  }
529  }
530 
531  /* free memory */
532  for( i = 0; i < nbins; ++i )
533  {
534  SCIPfreeBufferArray(scip, &solclustering[i]);
535  SCIPfreeBufferArray(scip, &clustering[i]);
536  }
537 
538  SCIPfreeBufferArray(scip, &solclustering);
539  SCIPfreeBufferArray(scip, &clustering);
540  SCIPfreeBufferArray(scip, &clusterofbin);
541  SCIPfreeBufferArray(scip, &switchedcluster);
542  SCIPfreeBufferArray(scip, &switchedbin);
543  SCIPfreeBufferArray(scip, &nbinsincluster);
544  SCIPfreeBufferArray(scip, &switchbound);
545  SCIPfreeBufferArray(scip, &binprocessed);
546 
547  return SCIP_OKAY;
548 }
549 
550 /** method that randomly creates a different solution from a given solution. From each cluster, half the states are
551  * randomly selected and added to the next cluster. */
552 static
554  SCIP* scip, /**< SCIP data structure */
555  SCIP_Real** startclustering, /**< the solution to be permuted */
556  SCIP_RANDNUMGEN* rnd, /**< a random number generator */
557  int nbins, /**< the number of states */
558  int ncluster /**< the number of clusters */
559  )
560 {
561  int i;
562  int t;
563  int c;
564  int rndcluster;
565  int pushed;
566  int* binsincluster;
567  int **bins;
568 
569  SCIP_CALL( SCIPallocBufferArray(scip, &binsincluster, ncluster) );
570  SCIP_CALL( SCIPallocBufferArray(scip, &bins, ncluster) );
571 
572  for( t = 0; t < ncluster; ++t )
573  {
574  binsincluster[t] = 0;
575 
576  for( i = 0; i < nbins; ++i )
577  {
578  if( SCIPisPositive(scip, startclustering[i][t]) )
579  binsincluster[t]++;
580  }
581 
582  SCIP_CALL( SCIPallocClearBufferArray(scip, &bins[t], binsincluster[t]) ); /*lint !e866*/
583 
584  c = 0;
585 
586  for( i = 0; i < nbins; ++i )
587  {
588  if( SCIPisPositive(scip, startclustering[i][t]) )
589  {
590  bins[t][c] = i;
591  c++;
592  }
593  }
594  }
595 
596  for( t = 0; t < ncluster; ++t )
597  {
598  pushed = 0;
599 
600  while(pushed < binsincluster[t] / 2) /*lint !e771*/
601  {
602  rndcluster = bins[t][SCIPrandomGetInt(rnd, 0, binsincluster[t] - 1)];
603 
604  if( rndcluster == nbins -1 )
605  continue;
606  if( SCIPisZero(scip, startclustering[rndcluster][t]) )
607  continue;
608 
609  startclustering[rndcluster][t] = 0;
610  startclustering[rndcluster][phi(t,ncluster)] = 1;
611  pushed++;
612  }
613 
614  SCIPfreeBufferArray(scip, &bins[t]);
615  }
616 
617  SCIPfreeBufferArray(scip, &bins);
618  SCIPfreeBufferArray(scip, &binsincluster);
619 
620  return SCIP_OKAY;
621 }
622 
623 /** executes the exchange heuristic for a given solution */
624 static
626  SCIP* scip, /**< SCIP data structure */
627  SCIP_HEUR* heur, /**< heuristic pointer */
628  SCIP_SOL* sol, /**< given solution */
629  SCIP_RESULT* result /**< result pointer */
630  )
631 {
632  SCIP_Real** startclustering;
633  SCIP_Bool** binfixed;
634  SCIP_Real** cmatrix;
635  SCIP_Real** qmatrix;
636  SCIP_RANDNUMGEN* rnd;
637  int* clusterofbin;
638  int* nbinsincluster;
639  int nbins;
640  int ncluster;
641  int i;
642  int c;
643 
644  /* get problem variables */
645  nbins = SCIPcycGetNBins(scip);
646  ncluster = SCIPcycGetNCluster(scip);
647  cmatrix = SCIPcycGetCmatrix(scip);
649 
650  assert(nbins >= 0);
651  assert(ncluster >= 0);
652 
653  /* allocate Memory */
654  SCIP_CALL( SCIPallocClearBufferArray(scip, &startclustering, nbins) );
655  SCIP_CALL( SCIPallocClearBufferArray(scip, &clusterofbin, nbins) );
656  SCIP_CALL( SCIPallocClearBufferArray(scip, &binfixed, nbins) );
657  SCIP_CALL( SCIPallocClearBufferArray(scip, &qmatrix, ncluster) );
658  SCIP_CALL( SCIPallocClearBufferArray(scip, &nbinsincluster, ncluster) );
659 
660  for( c = 0; c < ncluster; ++c )
661  {
662  SCIP_CALL( SCIPallocBufferArray(scip, &qmatrix[c], ncluster) ); /*lint !e866*/
663  }
664  for( i = 0; i < nbins; ++i )
665  {
666  SCIP_CALL( SCIPallocClearBufferArray(scip, &startclustering[i], ncluster) ); /*lint !e866*/
667  SCIP_CALL( SCIPallocClearBufferArray(scip, &binfixed[i], ncluster) ); /*lint !e866*/
668  }
669 
670  /* get the solution values from scip */
671  SCIP_CALL( getSolutionValues(scip, sol, startclustering, binfixed, clusterofbin, nbinsincluster) );
672 
673  if( isPartition(scip, startclustering, nbins, ncluster) )
674  {
675  SCIP_CALL( createSwitchSolution(scip, heur, cmatrix, qmatrix, binfixed, startclustering, result, nbins, ncluster) );
676  for( i = 0; i < MAXPERMUTATIONS; ++i )
677  {
678  SCIP_CALL( permuteStartSolution(scip, startclustering, rnd, nbins, ncluster) );
679 
680  assert(isPartition(scip, startclustering, nbins, ncluster));
681 
682  SCIP_CALL( createSwitchSolution(scip, heur, cmatrix, qmatrix, binfixed, startclustering, result, nbins, ncluster) );
683  }
684  }
685 
686  /* free all data-structures */
687  for( i = 0; i < nbins; ++i )
688  {
689  SCIPfreeBufferArray(scip, &binfixed[i]);
690  SCIPfreeBufferArray(scip, &startclustering[i]);
691  }
692 
693  for( c = 0; c < ncluster; ++c )
694  {
695  SCIPfreeBufferArray(scip, &qmatrix[c]);
696  }
697 
698  SCIPfreeBufferArray(scip, &nbinsincluster);
699  SCIPfreeBufferArray(scip, &qmatrix);
700  SCIPfreeBufferArray(scip, &binfixed);
701  SCIPfreeBufferArray(scip, &clusterofbin);
702  SCIPfreeBufferArray(scip, &startclustering);
703 
704  SCIPfreeRandom(scip, &rnd);
705 
706  return SCIP_OKAY;
707 }
708 
709 /*
710  * Callback methods of primal heuristic
711  */
712 
713 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
714 static
715 SCIP_DECL_HEURCOPY(heurCopyCyckerlin)
716 { /*lint --e{715}*/
717  assert(scip != NULL);
718  assert(heur != NULL);
719 
720  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
721 
722  /* call inclusion method of primal heuristic */
724 
725  return SCIP_OKAY;
726 }
727 
728 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
729 static
730 SCIP_DECL_HEURFREE(heurFreeCyckerlin)
731 { /*lint --e{715}*/
732  SCIP_HEURDATA* heurdata;
733 
734  assert(heur != NULL);
735  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
736  assert(scip != NULL);
737 
738  /* get heuristic data */
739  heurdata = SCIPheurGetData(heur);
740 
741  assert(heurdata != NULL);
742 
743  SCIPfreeMemoryArray(scip, &(heurdata->candidates));
744 
745  /* free heuristic data */
746  SCIPfreeBlockMemory(scip, &heurdata);
747  SCIPheurSetData(heur, NULL);
748 
749  return SCIP_OKAY;
750 }
751 
752 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
753 static
754 SCIP_DECL_HEUREXITSOL(heurExitsolCyckerlin)
755 { /*lint --e{715}*/
756  SCIP_HEURDATA* heurdata;
757 
758  assert(heur != NULL);
759  assert(scip != NULL);
760  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
761 
762  /* reset the timing mask to its default value */
764 
765  /* get heuristic data */
766  heurdata = SCIPheurGetData(heur);
767 
768  assert(heurdata != NULL);
769 
770  heurdata->candlength = 0;
771 
772  return SCIP_OKAY;
773 }
774 
775 /** initialization method of primal heuristic (called after problem was transformed) */
776 static
777 SCIP_DECL_HEURINIT(heurInitCyckerlin)
778 { /*lint --e{715}*/
779  SCIP_HEURDATA* heurdata;
780 
781  assert(heur != NULL);
782  assert(scip != NULL);
783 
784  /* get heuristic's data */
785  heurdata = SCIPheurGetData(heur);
786 
787  assert(heurdata != NULL);
788 
789  heurdata->ncandidates = 0;
790  heurdata->candlength = 10;
791 
792  SCIP_CALL( SCIPallocMemoryArray(scip, &(heurdata->candidates), heurdata->candlength) );
793 
794  return SCIP_OKAY;
795 }
796 
797 
798 /** execution method of primal heuristic */
799 static
800 SCIP_DECL_HEUREXEC(heurExecCyckerlin)
801 { /*lint --e{715}*/
802  SCIP_Real objective;
803  SCIP_HEURDATA* heurdata;
804  int i;
805 
806  assert(heur != NULL);
807  assert(scip != NULL);
808  assert(result != NULL);
809 
810  *result = SCIP_DIDNOTRUN;
811  heurdata = SCIPheurGetData(heur);
812 
813  assert(NULL != heurdata);
814 
815  /* reset the timing mask to its default value (at the root node it could be different) */
816  if( SCIPgetNNodes(scip) > 1 )
818  for( i = 0; i < heurdata->ncandidates; i++ )
819  {
820  objective = SCIPgetSolOrigObj(scip, heurdata->candidates[i]);
821 
822  if( !SCIPisZero(scip, objective) )
823  {
824  SCIP_CALL( runCyckerlin(scip, heur, heurdata->candidates[i], result) );
825  }
826 
827  heurdata->candidates[i] = NULL;
828  }
829 
830  heurdata->ncandidates = 0;
831  return SCIP_OKAY;
832 }
833 
834 /*
835  * primal heuristic specific interface methods
836  */
837 
838 /** creates the oneopt primal heuristic and includes it in SCIP */
840  SCIP* scip /**< SCIP data structure */
841  )
842 {
843  SCIP_HEUR* heur;
844  SCIP_HEURDATA* heurdata;
845 
846  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
847 
848  /* include primal heuristic */
849  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
851  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecCyckerlin, heurdata) );
852 
853  assert(heur != NULL);
854 
855  /* set non-NULL pointers to callback methods */
856  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyCyckerlin) );
857  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeCyckerlin) );
858  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolCyckerlin) );
859  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitCyckerlin) );
860 
861  return SCIP_OKAY;
862 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define HEUR_DISPCHAR
static SCIP_Real getObjective(SCIP *scip, SCIP_Real **qmatrix, SCIP_Real scale, int ncluster)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1429
#define HEUR_FREQOFS
void SCIPfreeRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen)
#define HEUR_FREQ
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:233
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1340
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:113
static SCIP_DECL_HEUREXITSOL(heurExitsolCyckerlin)
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:69
static SCIP_RETCODE createSwitchSolution(SCIP *scip, SCIP_HEUR *heur, SCIP_Real **cmatrix, SCIP_Real **qmatrix, SCIP_Bool **binfixed, SCIP_Real **startclustering, SCIP_RESULT *result, int nbins, int ncluster)
static SCIP_RETCODE runCyckerlin(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol, SCIP_RESULT *result)
static SCIP_RETCODE getSolutionValues(SCIP *scip, SCIP_SOL *bestsol, SCIP_Real **solclustering, SCIP_Bool **binfixed, int *clusterofbin, int *nbinsincluster)
SCIP_RETCODE assignVars(SCIP *scip, SCIP_SOL *sol, SCIP_Real **clustering, int nbins, int ncluster)
Definition: probdata_cyc.c:79
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:53
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
#define HEUR_DESC
static SCIP_RETCODE permuteStartSolution(SCIP *scip, SCIP_Real **startclustering, SCIP_RANDNUMGEN *rnd, int nbins, int ncluster)
#define FALSE
Definition: def.h:73
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_Real SCIPcycGetScale(SCIP *scip)
#define HEUR_PRIORITY
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
static SCIP_DECL_HEUREXEC(heurExecCyckerlin)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:185
static SCIP_DECL_HEURCOPY(heurCopyCyckerlin)
SCIP_RETCODE SCIPcreateRandom(SCIP *scip, SCIP_RANDNUMGEN **randnumgen, unsigned int initialseed, SCIP_Bool useglobalseed)
SCIP_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition: scip_heur.c:249
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:320
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
Definition: scip_heur.c:108
#define HEUR_TIMING
SCIP_Longint SCIPgetNNodes(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPreallocMemoryArray(scip, ptr, newnum)
Definition: scip_mem.h:59
SCIPInterval sign(const SCIPInterval &x)
static SCIP_Real phi(SCIP *scip, SCIP_Real val, SCIP_Real lb, SCIP_Real ub)
Definition: sepa_eccuts.c:747
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
#define HEUR_USESSUBSCIP
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1350
#define NULL
Definition: lpi_spx1.cpp:155
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition: heur.c:1469
#define SCIP_CALL(x)
Definition: def.h:364
int SCIPcycGetNBins(SCIP *scip)
#define MAXPERMUTATIONS
static void setBinToCluster(SCIP_Real **solclustering, SCIP_Real **cmatrix, SCIP_Real **qmatrix, int newbin, int newcluster, SCIP_Bool setone, int nbins, int ncluster)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Real SCIPinfinity(SCIP *scip)
public data structures and miscellaneous methods
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
Definition: misc.c:9959
#define SCIP_Bool
Definition: def.h:70
#define DEFAULT_RANDSEED
SCIP_RETCODE SCIPincludeHeurCycKerlin(SCIP *scip)
#define HEUR_MAXDEPTH
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17677
#define HEUR_NAME
static void computeIrrevMat(SCIP_Real **clustering, SCIP_Real **qmatrix, SCIP_Real **cmatrix, int nbins, int ncluster)
problem data for cycle clustering problem
static SCIP_DECL_HEURINIT(heurInitCyckerlin)
int SCIPcycGetNCluster(SCIP *scip)
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17667
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
SCIP_RETCODE addCandSolCyckerlin(SCIP *scip, SCIP_SOL *sol)
#define SCIP_Real
Definition: def.h:163
#define SCIP_Longint
Definition: def.h:148
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
static SCIP_DECL_HEURFREE(heurFreeCyckerlin)
Improvement heuristic that trades bin-variables between clusters.
SCIP_Bool isPartition(SCIP *scip, SCIP_Real **solclustering, int nbins, int ncluster)
Definition: probdata_cyc.c:48
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:3232
static SCIP_Bool switchNext(SCIP *scip, SCIP_Real **cmatrix, SCIP_Real **qmatrix, SCIP_Real **clustering, SCIP_Bool **binfixed, SCIP_Bool *binprocessed, int *clusterofbin, int *nbinsincluster, int *switchedbin, int *switchedcluster, SCIP_Real *switchbound, SCIP_Real *maxbound, int *bestlength, int iteration)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2305
SCIP_VAR *** SCIPcycGetBinvars(SCIP *scip)
SCIP_Real ** SCIPcycGetCmatrix(SCIP *scip)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
Definition: scip_sol.c:1436