Scippy

SCIP

Solving Constraint Integer Programs

heur_cycgreedy.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-2018 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 scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file heur_cycgreedy.c
17  * @brief Greedy primal heuristic. States are assigned to clusters iteratively. At each iteration all possible
18  * assignments are computed and the one with the best change in objective value is selected.
19  * @author Leon Eifler
20  */
21 
22 #include "heur_cycgreedy.h"
23 
24 #include <assert.h>
25 #include <string.h>
26 #include <time.h>
27 #include <stdlib.h>
28 #include "scip/misc.h"
29 #include "probdata_cyc.h"
30 #include "scip/cons_and.h"
31 
32 #define HEUR_NAME "cycgreedy"
33 #define HEUR_DESC "primal heuristic template"
34 #define HEUR_DISPCHAR 'h'
35 #define HEUR_PRIORITY 536870911
36 #define HEUR_FREQ 1
37 #define HEUR_FREQOFS 0
38 #define HEUR_MAXDEPTH -1
39 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
40 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
41 
42 /** primal heuristic data */
43 struct SCIP_HeurData
44 {
45  int lasteffectrootdepth;/**< index of the last solution for which oneopt was performed */
46  SCIP_Bool local; /**< the heuristic only computes assignments until any improvement is found */
47 };
48 
49 /** calculate the current objective value for a q-matrix */
50 static
52  SCIP* scip, /**< SCIP data structure */
53  SCIP_Real** qmatrix, /**< the irreversibility matrix*/
54  SCIP_Real scale, /**< the scaling parameter in the objective function */
55  int ncluster /**< the number of cluster*/
56  )
57 {
58  SCIP_Real objective = 0.0;
59  int c;
60  int c2;
61 
62  for( c = 0; c < ncluster; ++c )
63  {
64  c2 = ( c + 1 ) % ncluster;
65  objective += qmatrix[c][c2] - qmatrix[c2][c];
66  objective += scale * qmatrix[c][c];
67  }
68 
69  /* if we have no transitions at all then irreversibility should be set to 0 */
70  return objective;
71 }
72 
73 /** initialize the q-matrix from a given (possibly incomplete) clusterassignment */
74 static
76  SCIP_Real** clusterassignment, /**< the matrix containing the (incomplete) clusterassignment */
77  SCIP_Real** qmatrix, /**< the returned matrix with the irreversibility between two clusters */
78  SCIP_Real** cmatrix, /**< the transition-matrix containg the probability-data */
79  int nbins, /**< the number of bins */
80  int ncluster /**< the number of possible clusters */
81  )
82 {
83  int i;
84  int j;
85  int k;
86  int l;
87 
88  for( k = 0; k < ncluster; ++k )
89  {
90  for( l = 0; l < ncluster; ++l )
91  {
92  qmatrix[k][l] = 0;
93 
94  for( i = 0; i < nbins; ++i )
95  {
96  for( j = 0; j < nbins; ++j )
97  {
98  /* as -1 and 0 are both interpreted as 0, this check is necessary. Compute x_ik*x_jl*c_ij */
99  if( clusterassignment[i][k] < 1 || clusterassignment[j][l] < 1 )
100  continue;
101 
102  qmatrix[k][l] += cmatrix[i][j];
103  }
104  }
105  }
106  }
107 }
108 
109 /** update the irreversibility matrix, after the clusterassignment[newcluster][newbin] was either set
110  * from 0 to 1 or from 1 to 0
111  */
112 static
114  SCIP_Real** clusterassignment, /**< the matrix containing the (incomplete) clusterassignment */
115  SCIP_Real** qmatrix, /**< the returned matrix with the irreversibility between two clusters */
116  SCIP_Real** cmatrix, /**< the transition-matrix containg the probability-data */
117  int newbin, /**< the bin to be added to the assignment */
118  int newcluster, /**< the bluster in which the bin was changed */
119  int nbins, /**< the number of bins */
120  int ncluster /**< the number of clusters */
121  )
122 {
123  int bin;
124  int cluster;
125 
126  for( cluster = 0; cluster < ncluster; ++cluster )
127  {
128  for( bin = 0; bin < nbins; ++bin )
129  {
130  /* multiplier is 1 if clusterassignment is 1, and 0 if it is 0 (set to 0) or -1 (unassigned) */
131  int temp = 0;
132  if( clusterassignment[bin][cluster] == 1 )
133  temp = 1;
134 
135  if( cluster != newcluster )
136  {
137  qmatrix[newcluster][cluster] += temp * cmatrix[newbin][bin];
138  qmatrix[cluster][newcluster] += temp * cmatrix[bin][newbin];
139  }
140  else
141  {
142  if( bin == newbin )
143  qmatrix[newcluster][newcluster] += cmatrix[newbin][bin];
144  else
145  qmatrix[newcluster][newcluster] += (cmatrix[newbin][bin] + cmatrix[bin][newbin]) * temp;
146  }
147  }
148  }
149 }
150 
151 /** get the temporary objective value bound after newbin would be added to newcluster
152  * but dont not change anything with the clustering
153  */
154 static
156  SCIP* scip, /**< SCIP data structure */
157  SCIP_Real** qmatrix, /**< the irreversibility matrix */
158  SCIP_Real** cmatrix, /**< the transition matrix */
159  SCIP_Real** clusterassignment, /**< the clusterassignment */
160  int newbin, /**< the bin that would be added to cluster */
161  int newcluster, /**< the cluster the bin would be added to */
162  int nbins, /**< the number of bins */
163  int ncluster /**< the number of cluster */
164  )
165 {
166  SCIP_Real obj;
167  SCIP_Real temp;
168  int i;
169 
170  obj = getObjective(scip, qmatrix, SCIPcycGetScale(scip), ncluster);
171 
172  /* the coh in cluster changes as well as the flow to the next and the previous cluster */
173  for( i = 0; i < nbins; ++i )
174  {
175  temp = (clusterassignment[i][phiinv(newcluster, ncluster)] < 1 ? 0 : 1);
176  obj += (cmatrix[i][newbin] - cmatrix[newbin][i]) * temp;
177  temp = (clusterassignment[i][phi(newcluster, ncluster)] < 1 ? 0 : 1);
178  obj -= (cmatrix[i][newbin] - cmatrix[newbin][i]) * temp;
179  temp = (clusterassignment[i][newcluster] < 1 ? 0 : 1);
180  obj += (cmatrix[i][newbin] + cmatrix[newbin][i]) * temp;
181  }
182 
183  return obj;
184 }
185 
186 /* find and assign the next unassigned bin to an appropriate cluster */
187 static
189  SCIP* scip, /**< SCIP data structure */
190  SCIP_Bool localheur, /**< should the heuristic only compute local optimal assignment */
191  SCIP_Real** clusterassignment, /**< the matrix with the Clusterassignment */
192  SCIP_Real** cmatrix, /**< the transition matrix */
193  SCIP_Real** qmatrix, /**< the irreversibility matrix */
194  SCIP_Bool* isassigned, /**< TRUE, if the bin i was already assigned to a cluster*/
195  int nbins, /**< the number of bins*/
196  int ncluster, /**< the number of cluster*/
197  int* amountassigned, /**< the total amount of bins already assigned*/
198  int* binsincluster, /**< the number of bins currently in a cluster*/
199  SCIP_Real* objective /**< the objective */
200  )
201 {
202  SCIP_Real* binobjective;
203  SCIP_Bool** clusterispossible;
204  int* bestcluster;
205  SCIP_Real tempobj;
206  SCIP_Real max = -SCIPinfinity(scip);
207  int i;
208  int c;
209  int c1;
210  int c2;
211  int save = -1;
212  int ind = -1;
213 
214  /* allocate memory */
215  SCIP_CALL( SCIPallocClearBufferArray(scip, &binobjective, nbins) );
216  SCIP_CALL( SCIPallocClearBufferArray(scip, &bestcluster, nbins) );
217  SCIP_CALL( SCIPallocClearBufferArray(scip, &clusterispossible, nbins) );
218 
219  for( i = 0; i < nbins; ++i )
220  {
221  SCIP_CALL( SCIPallocClearBufferArray(scip, &clusterispossible[i], ncluster) ); /*lint !e866*/
222  }
223 
224  /* make ceratin that each cluster is non-empty*/
225  for( c = 0; c < ncluster; ++c )
226  {
227  tempobj = 0;
228 
229  if( binsincluster[c] == 0 )
230  {
231  for( i = 0; i < nbins; ++i )
232  {
233  /* if already assigned do nothing */
234  if( isassigned[i] )
235  continue;
236 
237  /* check if assigning this state is better than the previous best state */
238  binobjective[i] = getTempObj(scip, qmatrix, cmatrix, clusterassignment, i, c, nbins, ncluster);
239 
240  if( binobjective[i] > tempobj )
241  {
242  save = i;
243  tempobj = binobjective[i];
244  }
245 
246  /* ensure that a state is assigned */
247  if( save == -1 )
248  save = i;
249  }
250 
251  /* assign the found state to the cluster */
252  for( c1 = 0; c1 < ncluster; ++c1 )
253  {
254  clusterassignment[save][c1] = 0;
255  }
256 
257  clusterassignment[save][c] = 1;
258  binsincluster[c]++;
259 
260  assert(binsincluster[c] == 1);
261 
262  isassigned[save] = TRUE;
263  *amountassigned += 1;
264 
265  /* update the q-matrix */
266  updateIrrevMat(clusterassignment, qmatrix, cmatrix, save, c, nbins, ncluster);
267  }
268  }
269 
270  /*phase 2: iteratively assign states such that at each iteration the highest objective improvement is achieved */
271  for( i = 0; i < nbins; ++i )
272  {
273  bestcluster[i] = 0;
274  binobjective[i] = -SCIPinfinity(scip);
275  }
276 
277  for( i = 0; i < nbins; ++i )
278  {
279  if( isassigned[i] )
280  continue;
281 
282  /* check which clusters the bin can be assigned to. -1 means unassigned, 0 means fixed to 0. */
283  for( c1 = 0; c1 < ncluster; ++c1 )
284  {
285  /* if assignment to i would violate abs-var assignment then set clusterpossible to FALSE */
286  if( 0 != clusterassignment[i][c1] )
287  clusterispossible[i][c1] = TRUE;
288  else
289  clusterispossible[i][c1] = FALSE;
290  }
291 
292  /* calculate the irrevbound for all possible clusterassignments */
293  for( c2 = 0; c2 < ncluster; ++c2 )
294  {
295  if( !clusterispossible[i][c2] || clusterassignment[i][c2] == 0 )
296  continue;
297 
298  /* temporarily assign i to c2 */
299  save = (int) clusterassignment[i][c2];
300  clusterassignment[i][c2] = 1;
301 
302  /* save the best possible irrevbound for each bin */
303  tempobj = getTempObj(scip, qmatrix, cmatrix, clusterassignment, i, c2, nbins, ncluster);
304 
305  /* check if this is an improvement compared to the best known assignment */
306  if( SCIPisGT(scip, tempobj, binobjective[i]) )
307  {
308  binobjective[i] = tempobj;
309  bestcluster[i] = c2;
310  }
311 
312  clusterassignment[i][c2] = save;
313  }
314 
315  /* if localheur is true, then the heuristic assigns a state as soon as any improvement is found */
316  if( localheur && SCIPisGT(scip, binobjective[i], *objective) )
317  break;
318  }
319 
320  /* take the bin with the highest increase in irrev-bound */
321  for( i = 0; i < nbins; ++i )
322  {
323  if( SCIPisLT(scip, max, binobjective[i]) )
324  {
325  max = binobjective[i];
326  ind = i;
327  }
328  }
329 
330  assert(!isassigned[ind] && ind > -1 && ind < nbins);
331 
332  /* assign this bin to the found cluster */
333  for( c1 = 0; c1 < ncluster; ++c1 )
334  {
335  clusterassignment[ind][c1] = 0;
336  }
337 
338  clusterassignment[ind][bestcluster[ind]] = 1;
339  binsincluster[bestcluster[ind]]++;
340  *amountassigned += 1;
341  isassigned[ind] = TRUE;
342 
343  /* update the Irreversibility matrix */
344  updateIrrevMat(clusterassignment, qmatrix, cmatrix, ind, bestcluster[ind], nbins, ncluster);
345  *objective = getObjective(scip, qmatrix, SCIPcycGetScale(scip), ncluster);
346 
347  /* free the allocated memory */
348  for( i = 0; i < nbins; ++i )
349  {
350  SCIPfreeBufferArray(scip, &(clusterispossible[i]));
351  }
352  SCIPfreeBufferArray(scip, &clusterispossible);
353  SCIPfreeBufferArray(scip, &bestcluster);
354  SCIPfreeBufferArray(scip, &binobjective);
355 
356  return SCIP_OKAY;
357 }
358 
359 /*
360  * Callback methods of primal heuristic
361  */
362 
363 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
364 static
365 SCIP_DECL_HEURCOPY(heurCopyCycGreedy)
366 { /*lint --e{715}*/
367  assert(scip != NULL);
368  assert(heur != NULL);
369  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
370 
371  /* call inclusion method of primal heuristic */
373 
374  return SCIP_OKAY;
375 }
376 
377 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
378 static
379 SCIP_DECL_HEURFREE(heurFreeCycGreedy)
380 { /*lint --e{715}*/
381  SCIP_HEURDATA* heurdata;
382 
383  assert(heur != NULL);
384  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
385  assert(scip != NULL);
386 
387  /* free heuristic data */
388  heurdata = SCIPheurGetData(heur);
389 
390  assert(heurdata != NULL);
391 
392  SCIPfreeMemory(scip, &heurdata);
393  SCIPheurSetData(heur, NULL);
394 
395  return SCIP_OKAY;
396 }
397 
398 /** solving process deinitialization method of primal heuristic (called before branch and bound process data is freed) */
399 static
400 SCIP_DECL_HEUREXITSOL(heurExitsolCycGreedy)
401 { /*lint --e{715}*/
402  assert(heur != NULL);
403  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
404 
405  /* reset the timing mask to its default value */
407 
408  return SCIP_OKAY;
409 }
410 
411 /** initialization method of primal heuristic (called after problem was transformed) */
412 static
413 SCIP_DECL_HEURINIT(heurInitCycGreedy)
414 { /*lint --e{715}*/
415  SCIP_HEURDATA* heurdata;
416 
417  assert(heur != NULL);
418  assert(scip != NULL);
419 
420  /* get heuristic data */
421  heurdata = SCIPheurGetData(heur);
422  assert(heurdata != NULL);
423 
424  /* initialize last solution index */
425  heurdata->lasteffectrootdepth = -1;
426 
427  return SCIP_OKAY;
428 }
429 
430 /** execution method of primal heuristic */
431 static
432 SCIP_DECL_HEUREXEC(heurExecCycGreedy)
433 { /*lint --e{715}*/
434  SCIP_Real** cmatrix; /* the transition matrixx */
435  SCIP_Real** qmatrix; /* the low-dimensional transition matrix between clusters */
436  SCIP_VAR*** binvars; /* SCIP variables */
437  SCIP_Real** clustering; /* matrix for the assignment of the binary variables */
438  int* binsincluster; /* amount of bins in a given cluster */
439  SCIP_Bool* isassigned; /* TRUE if a bin has already bin assigned to a cluster */
440  SCIP_HEURDATA* heurdata; /* the heurdata */
441  SCIP_SOL* sol; /* pointer to solution */
442  SCIP_Bool possible = TRUE; /* can the heuristic be run */
443  SCIP_Bool feasible = FALSE; /* is the solution feasible */
444  SCIP_Real obj = 0.0; /* objective value */
445  int amountassigned; /* total amount of bins assigned */
446  int nbins; /* number of bins */
447  int ncluster; /* number of cluster */
448  int i; /* running indices */
449  int j;
450  int c;
451 
452  *result = SCIP_DIDNOTRUN;
453  amountassigned = 0;
454 
455  /* for now: do not use heurisitc if weighted objective is used */
456  heurdata = SCIPheurGetData(heur);
457  if( SCIPgetEffectiveRootDepth(scip) == heurdata->lasteffectrootdepth )
458  return SCIP_OKAY;
459 
460  heurdata->lasteffectrootdepth = SCIPgetEffectiveRootDepth(scip);
461 
462  /* get the problem data from scip */
463  cmatrix = SCIPcycGetCmatrix(scip);
464  nbins = SCIPcycGetNBins(scip);
465  ncluster = SCIPcycGetNCluster(scip);
466  binvars = SCIPcycGetBinvars(scip);
467 
468  assert(nbins > 0 && ncluster > 0);
469 
470  /* allocate memory for the assignment */
471  SCIP_CALL( SCIPallocClearBufferArray(scip, &clustering, nbins) );
472  SCIP_CALL( SCIPallocClearBufferArray(scip, &binsincluster, ncluster) );
473  SCIP_CALL( SCIPallocClearBufferArray(scip, &qmatrix, ncluster) );
474  SCIP_CALL( SCIPallocClearBufferArray(scip, &isassigned, nbins) );
475 
476  for ( i = 0; i < nbins; ++i )
477  {
478  if( i < ncluster )
479  {
480  SCIP_CALL( SCIPallocClearBufferArray(scip, &qmatrix[i], ncluster) ); /*lint !e866*/
481  }
482 
483  SCIP_CALL( SCIPallocClearBufferArray(scip, &clustering[i], ncluster) ); /*lint !e866*/
484 
485  for( j = 0; j < ncluster; ++j )
486  {
487  /* unassigned is set to -1 so we can differentiate unassigned and fixed in the branch and bound tree */
488  clustering[i][j] = -1;
489  }
490  }
491 
492  /* get the already fixed bin-variables from scip. An assignment of -1 one means unassigned.
493  * 0 is fixed to 0, 1 is fixed to 1
494  */
495  for( i = 0; i < nbins; ++i )
496  {
497  for( j = 0; j < ncluster; ++j )
498  {
499  if( NULL == binvars[i][j] )
500  {
501  possible = FALSE;
502  break;
503  }
504 
505  /* if the bounds determine a fixed binary variable, then fix the variable in the clusterassignment */
506  if( SCIPisEQ(scip, SCIPvarGetLbGlobal(binvars[i][j]), SCIPvarGetUbGlobal(binvars[i][j])) )
507  {
508  clustering[i][j] = SCIPvarGetLbGlobal(binvars[i][j]);
509 
510  if( SCIPisEQ(scip, 1.0, clustering[i][j]) )
511  {
512  binsincluster[j]++;
513  isassigned[i] = TRUE;
514  amountassigned += 1;
515 
516  for( c = 0; c < ncluster; ++c )
517  {
518  if( clustering[i][c] == -1 )
519  clustering[i][c] = 0;
520  }
521  }
522  }
523  }
524  }
525 
526  /* check if the assignment violates paritioning, e.g. because we are in a subscip */
527  for( i = 0; i < nbins; ++i )
528  {
529  int amountzeros = 0;
530  int sum = 0;
531 
532  for( j = 0; j < ncluster; ++j )
533  {
534  if( 0 == clustering[i][j] )
535  amountzeros++;
536  if( 1 == clustering[i][j] )
537  sum++;
538  }
539 
540  if( ncluster == amountzeros || sum > 1 )
541  possible = FALSE;
542  }
543 
544  if( amountassigned < nbins && possible )
545  {
546  /* initialize the qmatrix and the lower irreversibility bound */
547  computeIrrevMat(clustering, qmatrix, cmatrix, nbins, ncluster);
548  obj = getObjective(scip, qmatrix, SCIPcycGetScale(scip), ncluster);
549 
550  /* assign bins iteratively until all bins are assigned */
551  while( amountassigned < nbins )
552  {
553  SCIP_CALL( assignNextBin(scip, heurdata->local, clustering, cmatrix, qmatrix,
554  isassigned, nbins, ncluster, &amountassigned, binsincluster, &obj ) );
555  }
556 
557  /* assert that the assignment is valid in the sense that it is a partition of the bins.
558  * Feasibility is not checked in this method
559  */
560  assert(isPartition(scip,clustering, nbins, ncluster));
561 
562  /* update the qmatrix */
563  computeIrrevMat(clustering, qmatrix, cmatrix, nbins, ncluster);
564 
565  /* set the variables the problem to the found clustering and test feasibility */
566  SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
567  SCIP_CALL( assignVars( scip, sol, clustering, nbins, ncluster) );
568  SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, TRUE, TRUE, TRUE, TRUE, &feasible) );
569  }
570 
571  if( feasible )
572  *result = SCIP_FOUNDSOL;
573  else
574  *result = SCIP_DIDNOTFIND;
575 
576  /* free allocated memory */
577  for ( i = 0; i < nbins; ++i )
578  {
579  SCIPfreeBufferArray(scip, &clustering[i]);
580 
581  if( i < ncluster )
582  SCIPfreeBufferArray(scip, &qmatrix[i]);
583  }
584 
585  SCIPfreeBufferArray(scip, &isassigned);
586  SCIPfreeBufferArray(scip, &qmatrix);
587  SCIPfreeBufferArray(scip, &binsincluster);
588  SCIPfreeBufferArray(scip, &clustering);
589 
590  return SCIP_OKAY;
591 }
592 
593 /*
594  * * primal heuristic specific interface methods
595  */
596 
597 /** creates the CycGreedy - primal heuristic and includes it in SCIP */
599  SCIP* scip /**< SCIP data structure */
600  )
601 {
602  SCIP_HEURDATA* heurdata;
603  SCIP_HEUR* heur;
604 
605  /* create greedy primal heuristic data */
606  SCIP_CALL( SCIPallocMemory(scip, &heurdata) );
607 
608  /* include primal heuristic */
609 
610  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
612  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecCycGreedy, heurdata) );
613 
614  assert(heur != NULL);
615 
616  /* set non fundamental callbacks via setter functions */
617  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyCycGreedy) );
618  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeCycGreedy) );
619  SCIP_CALL( SCIPsetHeurExitsol(scip, heur, heurExitsolCycGreedy) );
620  SCIP_CALL( SCIPsetHeurInit(scip, heur, heurInitCycGreedy) );
621 
623  "localheur", "If set to true, heuristic assigns bins as soon as any improvement is found",
624  &heurdata->local, FALSE, TRUE, NULL, NULL) );
625 
626  return SCIP_OKAY;
627 }
SCIP_RETCODE SCIPsetHeurExitsol(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXITSOL((*heurexitsol)))
Definition: scip_heur.c:312
#define NULL
Definition: def.h:239
static SCIP_RETCODE assignNextBin(SCIP *scip, SCIP_Bool localheur, SCIP_Real **clusterassignment, SCIP_Real **cmatrix, SCIP_Real **qmatrix, SCIP_Bool *isassigned, int nbins, int ncluster, int *amountassigned, int *binsincluster, SCIP_Real *objective)
static void computeIrrevMat(SCIP_Real **clusterassignment, SCIP_Real **qmatrix, SCIP_Real **cmatrix, int nbins, int ncluster)
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:132
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17343
SCIP_RETCODE assignVars(SCIP *scip, SCIP_SOL *sol, SCIP_Real **clustering, int nbins, int ncluster)
Definition: probdata_cyc.c:79
static void updateIrrevMat(SCIP_Real **clusterassignment, SCIP_Real **qmatrix, SCIP_Real **cmatrix, int newbin, int newcluster, int nbins, int ncluster)
#define FALSE
Definition: def.h:65
SCIP_Real SCIPinfinity(SCIP *scip)
#define TRUE
Definition: def.h:64
#define HEUR_USESSUBSCIP
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:51
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:187
SCIP_Real SCIPcycGetScale(SCIP *scip)
Constraint handler for AND constraints, .
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1175
#define HEUR_DISPCHAR
static SCIP_Real getObjective(SCIP *scip, SCIP_Real **qmatrix, SCIP_Real scale, int ncluster)
#define HEUR_FREQOFS
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17353
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1254
#define HEUR_NAME
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:248
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define HEUR_TIMING
static SCIP_Real getTempObj(SCIP *scip, SCIP_Real **qmatrix, SCIP_Real **cmatrix, SCIP_Real **clusterassignment, int newbin, int newcluster, int nbins, int ncluster)
static SCIP_Real phi(SCIP *scip, SCIP_Real val, SCIP_Real lb, SCIP_Real ub)
Definition: sepa_eccuts.c:744
internal miscellaneous methods
#define HEUR_MAXDEPTH
SCIP_RETCODE SCIPincludeHeurCycGreedy(SCIP *scip)
int SCIPgetEffectiveRootDepth(SCIP *scip)
Definition: scip_tree.c:194
#define SCIP_CALL(x)
Definition: def.h:351
int SCIPcycGetNBins(SCIP *scip)
int phiinv(int k, int ncluster)
Definition: probdata_cyc.c:184
#define SCIP_Bool
Definition: def.h:62
static SCIP_DECL_HEURCOPY(heurCopyCycGreedy)
static SCIP_DECL_HEUREXEC(heurExecCycGreedy)
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:3291
#define HEUR_PRIORITY
problem data for cycle clustering problem
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:86
#define HEUR_DESC
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPcycGetNCluster(SCIP *scip)
static SCIP_DECL_HEURINIT(heurInitCycGreedy)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
Definition: scip_heur.c:264
#define SCIP_Real
Definition: def.h:150
void SCIPheurSetTimingmask(SCIP_HEUR *heur, SCIP_HEURTIMING timingmask)
Definition: heur.c:1294
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:70
Greedy primal heuristic. States are assigned to clusters iteratively. At each iteration all possible ...
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:232
static SCIP_DECL_HEUREXITSOL(heurExitsolCycGreedy)
#define HEUR_FREQ
SCIP_Bool isPartition(SCIP *scip, SCIP_Real **solclustering, int nbins, int ncluster)
Definition: probdata_cyc.c:48
static SCIP_DECL_HEURFREE(heurFreeCycGreedy)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1165
SCIP_VAR *** SCIPcycGetBinvars(SCIP *scip)
SCIP_Real ** SCIPcycGetCmatrix(SCIP *scip)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:129
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:377