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