Scippy

SCIP

Solving Constraint Integer Programs

heur_redsize.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_redsize.c
17  * @brief primal heuristic that solves the problem with a sparser matrix as a submip
18  * @author Leon Eifler
19  */
20 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
21 
22 #include <assert.h>
23 #include <string.h>
24 
25 #include "heur_redsize.h"
26 #include "cycplugins.h"
27 #include "probdata_cyc.h"
28 
29 #define HEUR_NAME "redsize"
30 #define HEUR_DESC "primal heuristic that solves the problem with a sparser matrix as a submip"
31 #define HEUR_DISPCHAR 'u'
32 #define HEUR_PRIORITY 536870911
33 #define HEUR_FREQ 0
34 #define HEUR_FREQOFS 0
35 #define HEUR_MAXDEPTH -1
36 #define HEUR_TIMING SCIP_HEURTIMING_BEFORENODE
37 #define HEUR_USESSUBSCIP TRUE /**< does the heuristic use a secondary SCIP instance? */
38 
39 #define DEFAULT_REDUCTIONRATE 0.75 /**< default percentile of transition that gets deleted */
40 
41 struct SCIP_HeurData
42 {
43  SCIP_Real reductionrate; /**< percentile of transition that gets deleted */
44 };
45 
46 /*
47  * Local methods
48  */
49 
50 /** Add incomplete solution to main scip */
51 static
53  SCIP* scip, /**< SCIP data structure */
54  SCIP* subscip, /**< SCIP data structure of subscip */
55  SCIP_HEUR* heur, /**< pointer to heuristic */
56  SCIP_SOL* subsol, /**< solution of subscip */
57  SCIP_RESULT* result /**< result pointer */
58  )
59 {
60  SCIP_VAR*** binvars;
61  SCIP_Real** solclustering;
62  SCIP_SOL* newsol;
63  SCIP_Bool feasible;
64  int nbins;
65  int ncluster;
66  int i;
67  int t;
68 
69  nbins = SCIPcycGetNBins(scip);
70  ncluster = SCIPcycGetNCluster(scip);
71  binvars = SCIPcycGetBinvars(subscip);
72 
73  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &solclustering, nbins) );
74 
75  SCIP_CALL( SCIPcreateSol(scip, &newsol, heur) );
76 
77  for( i = 0; i < nbins; ++i )
78  {
79  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &solclustering[i], ncluster) );
80 
81  for( t = 0; t < ncluster; ++t )
82  {
83  solclustering[i][t] = SCIPgetSolVal(subscip, subsol, binvars[i][t]);
84  }
85  }
86 
87  SCIP_CALL( assignVars(scip, newsol, solclustering, nbins, ncluster) );
88 
89  SCIP_CALL( SCIPtrySolFree(scip, &newsol, FALSE, TRUE, TRUE, TRUE, TRUE, &feasible) );
90 
91  if( feasible )
92  *result = SCIP_FOUNDSOL;
93 
94  for( i = 0; i < nbins; ++i )
95  {
96  SCIPfreeBlockMemoryArray(scip, &solclustering[i], ncluster);
97  }
98 
99  SCIPfreeBlockMemoryArray(scip, &solclustering, nbins);
100 
101  return SCIP_OKAY;
102 }
103 
104 /** set all the given percentile of nonzeros to zero */
105 static
107  SCIP* scip, /**< SCIP data structure */
108  SCIP_Real** matrix, /**< the matrix */
109  SCIP_Real percentile, /**< the percentile of entries to be deleted */
110  SCIP_Real scale, /**< scaling between net flow and coherence */
111  int size /**< the size of the matrix */
112  )
113 {
114  SCIP_Real* nonzeros;
115  int* idxnonzeros;
116  int nnonzeros;
117  int currentsize;
118  int i;
119  int j;
120  int k;
121 
122  nnonzeros = 0;
123  currentsize = size;
124 
125  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &nonzeros, size) );
126  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &idxnonzeros, size) );
127 
128  for( i = 0; i < size; ++i )
129  {
130  for( j = 0; j < i; ++j )
131  {
132  if( !SCIPisZero(scip, matrix[i][j]) || !SCIPisZero(scip, matrix[j][i]) )
133  {
134  /* if we have non-zero entry, compute the impact and save it */
135  nonzeros[nnonzeros] = MAX(scale * (matrix[i][j]+matrix[j][i]), matrix[i][j] - matrix[j][i]);
136  idxnonzeros[nnonzeros] = i * size + j;
137 
138  nnonzeros++;
139 
140  /* realloc if necessary */
141  if( currentsize < nnonzeros + 2 )
142  {
143  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &nonzeros, currentsize, currentsize + size) );
144  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &idxnonzeros, currentsize, currentsize + size) );
145  currentsize += size;
146  }
147  }
148  }
149  }
150 
151  /* sort by the least impact */
152  SCIPsortRealInt(nonzeros, idxnonzeros, nnonzeros);
153 
154  /* recompute the indizes and set them to 0 */
155  for( i = 0; i < nnonzeros * percentile; ++i )
156  {
157  j = idxnonzeros[i] % size;
158  k = idxnonzeros[i] / size;
159 
160  matrix[j][k] = 0.0;
161  matrix[k][j] = 0.0;
162  }
163 
164  SCIPfreeBlockMemoryArray(scip, &nonzeros, currentsize);
165  SCIPfreeBlockMemoryArray(scip, &idxnonzeros, currentsize);
166 
167  return SCIP_OKAY;
168 }
169 
170 /** main procedure of the heuristic, creates and solves a sub-SCIP */
171 static
173  SCIP* scip, /**< original SCIP data structure */
174  SCIP_HEUR* heur, /**< heuristic data structure */
175  SCIP_RESULT* result, /**< result data structure */
176  SCIP_Real reductionrate, /**< minimum percentage of integer variables that have to be fixed */
177  SCIP_Longint maxnodes /**< maximum number of nodes for the subproblem */
178  )
179 {
180  SCIP* subscip;
181  SCIP_Real** cmatrix_orig;
182  SCIP_Real** cmatrix_red;
183  SCIP_SOL** subsols;
184 
185  SCIP_Real scale;
186 
187  int nbins;
188  int ncluster;
189  int nsubsols;
190  int i;
191  int j;
192 
193  assert(scip != NULL);
194  assert(heur != NULL);
195  assert(result != NULL);
196 
197  assert(maxnodes >= 0);
198 
199  assert(0.0 <= reductionrate && reductionrate <= 1.0);
200 
201  nbins = SCIPcycGetNBins(scip);
202  ncluster = SCIPcycGetNCluster(scip);
203  cmatrix_orig = SCIPcycGetCmatrix(scip);
204  scale = SCIPcycGetScale(scip);
205 
206  assert(nbins > 0 && ncluster > 0 && nbins >= ncluster);
207  assert(cmatrix_orig != NULL);
208 
209  *result = SCIP_DIDNOTRUN;
210 
211  /* create subscip */
212  SCIP_CALL( SCIPcreate(&subscip) );
213  SCIP_CALL( SCIPincludeCycPlugins(subscip) );
214 
215 #ifdef SCIP_DEBUG
216  /* for debugging, enable full output */
217  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
218  SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", -1) );
219 #else
220  /* disable statistic timing inside sub SCIP and output to console */
221  SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
222  SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
223 #endif
224 
225  /* copy the original cmatrix */
226  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &cmatrix_red, nbins) );
227  for( i = 0; i < nbins; ++i )
228  {
229  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &cmatrix_red[i], nbins) );
230  for( j = 0; j < nbins; ++j )
231  {
232  cmatrix_red[i][j] = cmatrix_orig[i][j];
233  }
234  }
235 
236  /* delete entries from the copied cmatrix */
237  SCIP_CALL( SCIPreduceMatrixSize(subscip, cmatrix_red, reductionrate, scale, nbins) );
238 
239  /* create probdata for the subscip */
240  SCIP_CALL( SCIPcreateProbCyc(subscip, "subscip", nbins, ncluster, cmatrix_red) );
241 
242  /* forbid recursive call of heuristics and separators solving sub-SCIPs */
243  SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) );
244 
245  /* set nodelimit */
246  SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", maxnodes) );
247 
248  /* disable cutting plane separation */
250 
251  /* disable expensive presolving */
253 
254  /* use best estimate node selection */
255  if( SCIPfindNodesel(subscip, "estimate") != NULL && !SCIPisParamFixed(subscip, "nodeselection/estimate/stdpriority") )
256  {
257  SCIP_CALL( SCIPsetIntParam(subscip, "nodeselection/estimate/stdpriority", INT_MAX/4) );
258  }
259 
260  /* use inference branching */
261  if( SCIPfindBranchrule(subscip, "inference") != NULL && !SCIPisParamFixed(subscip, "branching/inference/priority") )
262  {
263  SCIP_CALL( SCIPsetIntParam(subscip, "branching/inference/priority", INT_MAX/4) );
264  }
265 
266  /* enable conflict analysis, disable analysis of boundexceeding LPs, and restrict conflict pool */
267  if( !SCIPisParamFixed(subscip, "conflict/enable") )
268  {
269  SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/enable", TRUE) );
270  }
271  if( !SCIPisParamFixed(subscip, "conflict/useboundlp") )
272  {
273  SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') );
274  }
275  if( !SCIPisParamFixed(subscip, "conflict/maxstoresize") )
276  {
277  SCIP_CALL( SCIPsetIntParam(subscip, "conflict/maxstoresize", 100) );
278  }
279 
280  /* solve the subproblem */
281  SCIP_CALL_ABORT( SCIPsolve(subscip) );
282 
283  /* print solving statistics of subproblem if we are in SCIP's debug mode */
285 
286  /* check, whether a solution was found; due to numerics, it might happen that not all solutions are feasible -> try
287  * all solutions until one was accepted
288  */
289  nsubsols = SCIPgetNSols(subscip);
290  subsols = SCIPgetSols(subscip);
291 
292  for( i = 0; i < nsubsols; ++i )
293  SCIP_CALL( SCIPcycAddIncompleteSol(scip, subscip, heur, subsols[i], result) );
294 
295  SCIP_CALL( SCIPfree(&subscip) );
296 
297  /* free memory */
298  for( i = 0; i < nbins; ++i )
299  {
300  SCIPfreeBlockMemoryArray(scip, &cmatrix_red[i], nbins);
301  }
302  SCIPfreeBlockMemoryArray(scip, &cmatrix_red, nbins);
303 
304  return SCIP_OKAY;
305 }
306 
307 /*
308  * Callback methods of primal heuristic
309  */
310 
311 /** copy method for primal heuristic plugins (called when SCIP copies plugins) */
312 static
313 SCIP_DECL_HEURCOPY(heurCopyRedsize)
314 { /*lint --e{715}*/
315  assert(scip != NULL);
316  assert(heur != NULL);
317  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
318 
319  /* call inclusion method of primal heuristic */
321 
322  return SCIP_OKAY;
323 }
324 
325 /** destructor of primal heuristic to free user data (called when SCIP is exiting) */
326 static
327 SCIP_DECL_HEURFREE(heurFreeRedsize)
328 { /*lint --e{715}*/
329  SCIP_HEURDATA* heurdata;
330 
331  assert(heur != NULL);
332  assert(scip != NULL);
333 
334  /* get heuristic data */
335  heurdata = SCIPheurGetData(heur);
336  assert(heurdata != NULL);
337 
338  /* free heuristic data */
339  SCIPfreeBlockMemory(scip, &heurdata);
340  SCIPheurSetData(heur, NULL);
341 
342  return SCIP_OKAY;
343 }
344 
345 /** execution method of primal heuristic */
346 static
347 SCIP_DECL_HEUREXEC(heurExecRedsize)
348 { /*lint --e{715}*/
349  SCIP_HEURDATA* heurdata;
350 
351  assert(heur != NULL);
352  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
353  assert(scip != NULL);
354  assert(result != NULL);
355 
356  heurdata = SCIPheurGetData(heur);
357 
358  assert(heurdata != NULL);
359 
360  *result = SCIP_DIDNOTRUN;
361 
362  SCIP_CALL( SCIPapplyRedSize(scip, heur, result, heurdata->reductionrate, (SCIP_Longint) 1) );
363 
364  return SCIP_OKAY;
365 }
366 
367 /*
368  * primal heuristic specific interface methods
369  */
370 
371 /** creates the oneopt primal heuristic and includes it in SCIP */
373  SCIP* scip /**< SCIP data structure */
374  )
375 {
376  SCIP_HEURDATA* heurdata;
377  SCIP_HEUR* heur;
378 
379  /* create redsize primal heuristic data */
380  SCIP_CALL( SCIPallocBlockMemory(scip, &heurdata) );
381 
382  /* include primal heuristic */
383  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
385  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecRedsize, heurdata) );
386 
387  assert(heur != NULL);
388 
389  /* set non-NULL pointers to callback methods */
390  SCIP_CALL( SCIPsetHeurCopy(scip, heur, heurCopyRedsize) );
391  SCIP_CALL( SCIPsetHeurFree(scip, heur, heurFreeRedsize) );
392 
393  /* add param */
394  SCIP_CALL( SCIPaddRealParam(scip, "heuristics/" HEUR_NAME "/reduction-rate",
395  "percentile of transition probabilities that gets deleted in the submip",
396  &heurdata->reductionrate, FALSE, DEFAULT_REDUCTIONRATE, 0.0, 1.0, NULL , NULL) );
397 
398  return SCIP_OKAY;
399 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:86
SCIP_RETCODE SCIPcreateProbCyc(SCIP *scip, const char *name, int nbins, int ncluster, SCIP_Real **cmatrix)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:80
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1429
#define HEUR_FREQOFS
Definition: heur_redsize.c:34
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
Definition: heur.c:1340
#define HEUR_USESSUBSCIP
Definition: heur_redsize.c:37
static SCIP_RETCODE SCIPcycAddIncompleteSol(SCIP *scip, SCIP *subscip, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_RESULT *result)
Definition: heur_redsize.c:52
SCIP_RETCODE assignVars(SCIP *scip, SCIP_SOL *sol, SCIP_Real **clustering, int nbins, int ncluster)
Definition: probdata_cyc.c:79
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1353
SCIP_RETCODE SCIPincludeHeurRedsize(SCIP *scip)
Definition: heur_redsize.c:372
#define FALSE
Definition: def.h:73
#define TRUE
Definition: def.h:72
#define SCIPdebug(x)
Definition: pub_message.h:84
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
static SCIP_RETCODE SCIPreduceMatrixSize(SCIP *scip, SCIP_Real **matrix, SCIP_Real percentile, SCIP_Real scale, int size)
Definition: heur_redsize.c:106
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2527
struct SCIP_HeurData SCIP_HEURDATA
Definition: type_heur.h:67
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_Real SCIPcycGetScale(SCIP *scip)
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
Definition: scip_param.c:893
#define DEFAULT_REDUCTIONRATE
Definition: heur_redsize.c:39
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:320
int SCIPgetNSols(SCIP *scip)
Definition: scip_sol.c:2206
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
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:283
#define HEUR_TIMING
Definition: heur_redsize.c:36
#define HEUR_NAME
Definition: heur_redsize.c:29
static SCIP_DECL_HEURCOPY(heurCopyRedsize)
Definition: heur_redsize.c:313
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
Definition: scip_branch.c:288
static SCIP_RETCODE SCIPapplyRedSize(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Real reductionrate, SCIP_Longint maxnodes)
Definition: heur_redsize.c:172
#define HEUR_PRIORITY
Definition: heur_redsize.c:32
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
Definition: heur.c:1350
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_NODESEL * SCIPfindNodesel(SCIP *scip, const char *name)
Definition: scip_nodesel.c:225
#define SCIP_CALL(x)
Definition: def.h:364
SCIP_RETCODE SCIPsetPresolving(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:942
SCIP_RETCODE SCIPsetCharParam(SCIP *scip, const char *name, char value)
Definition: scip_param.c:671
int SCIPcycGetNBins(SCIP *scip)
SCIP_RETCODE SCIPincludeCycPlugins(SCIP *scip)
Definition: cycplugins.c:36
SCIP_EXPORT void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
#define SCIP_Bool
Definition: def.h:70
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
Definition: scip_param.c:210
#define MAX(x, y)
Definition: tclique_def.h:83
static SCIP_DECL_HEUREXEC(heurExecRedsize)
Definition: heur_redsize.c:347
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
problem data for cycle clustering problem
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
#define HEUR_DESC
Definition: heur_redsize.c:30
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
Definition: scip_param.c:555
primal heuristic that solves the problem with a sparser matrix as a submip
#define HEUR_DISPCHAR
Definition: heur_redsize.c:31
SCIP plugins for cycle clustering.
int SCIPcycGetNCluster(SCIP *scip)
SCIP_SOL ** SCIPgetSols(SCIP *scip)
Definition: scip_sol.c:2255
SCIP_RETCODE SCIPsetHeurCopy(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURCOPY((*heurcopy)))
Definition: scip_heur.c:153
#define SCIP_Real
Definition: def.h:163
#define SCIP_Longint
Definition: def.h:148
SCIP_RETCODE SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
Definition: scip_param.c:439
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
Definition: scip_heur.c:169
static SCIP_DECL_HEURFREE(heurFreeRedsize)
Definition: heur_redsize.c:327
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:315
#define SCIP_CALL_ABORT(x)
Definition: def.h:343
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:3231
#define HEUR_MAXDEPTH
Definition: heur_redsize.c:35
#define HEUR_FREQ
Definition: heur_redsize.c:33
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
Definition: scip_param.c:497
SCIP_VAR *** SCIPcycGetBinvars(SCIP *scip)
SCIP_RETCODE SCIPsetSeparating(SCIP *scip, SCIP_PARAMSETTING paramsetting, SCIP_Bool quiet)
Definition: scip_param.c:968
SCIP_Real ** SCIPcycGetCmatrix(SCIP *scip)