Scippy

SCIP

Solving Constraint Integer Programs

heur_fuzzyround.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_fuzzyround.c
17  * @brief primal heuristic that constructs a feasible solution from the lp-relaxation. Round only on the state-variables (binvars)
18  * and then reconstruct the rest of the variables accordingly.
19  * @author Leon Eifler
20  */
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 
23 #include <assert.h>
24 #include <string.h>
25 
26 #include "heur_fuzzyround.h"
27 
28 #include "probdata_cyc.h"
29 #include "scip/cons_and.h"
30 
31 #define HEUR_NAME "fuzzyround"
32 #define HEUR_DESC "primal heuristic that constructs a feasible solution from the lp-relaxation"
33 #define HEUR_DISPCHAR '&'
34 #define HEUR_PRIORITY 1000
35 #define HEUR_FREQ 1
36 #define HEUR_FREQOFS 0
37 #define HEUR_MAXDEPTH -1
38 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE
39 #define HEUR_USESSUBSCIP FALSE /**< does the heuristic use a secondary SCIP instance? */
40 
41 /*
42  * Local methods
43  */
44 
45 /** execution method of primal heuristic */
46 static
47 SCIP_DECL_HEUREXEC(heurExecFuzzyround)
48 { /*lint --e{715}*/
49  SCIP_VAR*** binvars;
50  SCIP_SOL* sol;
51  SCIP_Real** clustering;
52  SCIP_Real maxlpval;
53  SCIP_Bool feasible = FALSE;
54  int* binsincluster;
55  int nbins;
56  int ncluster;
57  int i;
58  int k;
59  int maxcluster;
60 
61  assert(heur != NULL);
62  assert(strcmp(SCIPheurGetName(heur), HEUR_NAME) == 0);
63  assert(scip != NULL);
64  assert(result != NULL);
65 
66  *result = SCIP_DIDNOTRUN;
67 
68  /* only call heuristic, if an optimal LP solution is at hand */
70  return SCIP_OKAY;
71 
72  /* only call separator, if there are fractional variables */
73  if( SCIPgetNLPBranchCands(scip) == 0 )
74  return SCIP_OKAY;
75 
76  nbins = SCIPcycGetNBins(scip);
77  ncluster = SCIPcycGetNCluster(scip);
78  assert(nbins > 0);
79  assert(ncluster > 0 && ncluster <= nbins);
80 
81  binvars = SCIPcycGetBinvars(scip);
82  assert(binvars != NULL);
83 
84  /* allocate memory */
85  SCIP_CALL( SCIPallocClearBufferArray(scip, &clustering , nbins) );
86  SCIP_CALL( SCIPallocClearBufferArray(scip, &binsincluster, ncluster) );
87 
88  for( i = 0; i < nbins; ++i )
89  {
90  SCIP_CALL( SCIPallocClearBufferArray(scip, &clustering[i], ncluster) ); /*lint !e866*/
91  }
92 
93  /* for each bin, set the assignment with the highest lp-value to 1, the rest to 0 */
94  for( i = 0; i < nbins; ++i )
95  {
96  assert(NULL != binvars[i]);
97 
98  maxlpval = 0;
99  maxcluster = -1;
100 
101  for (k = 0; k < ncluster; ++k)
102  {
103  assert(NULL != binvars[i][k]);
104  if( SCIPisGT(scip, SCIPvarGetLPSol(binvars[i][k]), maxlpval) )
105  {
106  maxlpval = SCIPvarGetLPSol(binvars[i][k]);
107  maxcluster = k;
108  binsincluster[k]++;
109  }
110  else if( SCIPisEQ(scip, SCIPvarGetLPSol(binvars[i][k]), maxlpval) && maxcluster != -1
111  && binsincluster[maxcluster] > binsincluster[k] )
112  {
113  binsincluster[maxcluster]--;
114  binsincluster[k]++;
115  maxcluster = k;
116  }
117  }
118 
119  assert(maxcluster >= 0);
120 
121  clustering[i][maxcluster] = 1.0;
122  }
123 
124  assert(isPartition(scip, clustering, nbins, ncluster));
125 
126  SCIP_CALL( SCIPcreateSol(scip, &sol, heur) );
127  SCIP_CALL( assignVars(scip, sol, clustering, nbins, ncluster) );
128  SCIP_CALL( SCIPtrySolFree(scip, &sol, FALSE, TRUE, TRUE, TRUE, TRUE, &feasible) );
129 
130  if( feasible )
131  *result = SCIP_FOUNDSOL;
132  else
133  *result = SCIP_DIDNOTFIND;
134 
135  /* free allocated memory */
136  for( i = 0; i < nbins; ++i )
137  {
138  SCIPfreeBufferArray(scip, &clustering[i]);
139  }
140  SCIPfreeBufferArray(scip, &clustering);
141  SCIPfreeBufferArray(scip, &binsincluster);
142 
143  return SCIP_OKAY;
144 }
145 
146 /*
147  * primal heuristic specific interface methods
148  */
149 
150 /** creates the oneopt primal heuristic and includes it in SCIP */
152  SCIP* scip /**< SCIP data structure */
153  )
154 {
155  SCIP_HEUR* heur;
156 
157  /* include primal heuristic */
158  SCIP_CALL( SCIPincludeHeurBasic(scip, &heur,
160  HEUR_MAXDEPTH, HEUR_TIMING, HEUR_USESSUBSCIP, heurExecFuzzyround, NULL) );
161 
162  assert(heur != NULL);
163 
164  return SCIP_OKAY;
165 }
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
const char * SCIPheurGetName(SCIP_HEUR *heur)
Definition: heur.c:1429
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:113
SCIP_RETCODE assignVars(SCIP *scip, SCIP_SOL *sol, SCIP_Real **clustering, int nbins, int ncluster)
Definition: probdata_cyc.c:79
#define HEUR_TIMING
SCIP_EXPORT SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18036
#define HEUR_USESSUBSCIP
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:419
#define FALSE
Definition: def.h:73
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define HEUR_FREQ
Constraint handler for AND constraints, .
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition: scip_lp.c:159
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
static SCIP_DECL_HEUREXEC(heurExecFuzzyround)
#define NULL
Definition: lpi_spx1.cpp:155
#define SCIP_CALL(x)
Definition: def.h:364
int SCIPcycGetNBins(SCIP *scip)
#define SCIP_Bool
Definition: def.h:70
#define HEUR_FREQOFS
problem data for cycle clustering problem
#define HEUR_DESC
int SCIPcycGetNCluster(SCIP *scip)
#define HEUR_MAXDEPTH
#define SCIP_Real
Definition: def.h:163
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define HEUR_DISPCHAR
SCIP_RETCODE SCIPincludeHeurFuzzyround(SCIP *scip)
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:3231
#define HEUR_NAME
#define HEUR_PRIORITY
SCIP_VAR *** SCIPcycGetBinvars(SCIP *scip)
primal heuristic that constructs a feasible solution from the lp-relaxation. Round only on the state-...