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