Scippy

SCIP

Solving Constraint Integer Programs

sepa_edge.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-2022 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 sepa_edge.c
17  * @brief edge-separator. Separates triangle-inequalities in cycle clustering problem
18  * @author Leon Eifler
19  */
20 
21 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
22 #include <assert.h>
23 #include <string.h>
24 
25 #include "sepa_edge.h"
26 
27 #include "probdata_cyc.h"
28 #include "scip/cutsel_hybrid.h"
29 
30 #define SEPA_NAME "edge"
31 #define SEPA_DESC "separator to separate triangle-inequalities in cycle-clustering application"
32 #define SEPA_PRIORITY 5000
33 #define SEPA_FREQ 5
34 #define SEPA_MAXBOUNDDIST 0.0
35 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
36 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
37 #define MAXCUTS 2000 /**< maximal number of cuts that can be added to cut pool */
38 #define MAXCUTSCREATED 10000 /**< maximal number of cuts to select from */
39 #define MAXROUNDS 20
40 
41 /** copy method for separator plugins (called when SCIP copies plugins) */
42 static
43 SCIP_DECL_SEPACOPY(sepaCopyEdge)
44 { /*lint --e{715}*/
45  assert(scip != NULL);
46  assert(sepa != NULL);
47  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
48 
49  /* call inclusion method of constraint handler */
51 
52  return SCIP_OKAY;
53 }
54 
55 /** LP solution separation method of separator */
56 static
57 SCIP_DECL_SEPAEXECLP(sepaExeclpEdge)
58 { /*lint --e{715}*/
59  SCIP_VAR**** edgevars; /* edgevars from probdata */
60  SCIP_DIGRAPH* edgegraph; /* edgegraph from probdata */
61  char cutname[SCIP_MAXSTRLEN]; /* name of the cut */
62  SCIP_Real** sign; /* matrix of sign-permuations */
63  SCIP_Real* violation; /* array of violations */
64  SCIP_ROW** cuts; /* array of generated cuts */
65  SCIP_Real goodscorefac; /* parameters for cut-selection */
66  SCIP_Real badscorefac;
67  SCIP_Real goodmaxparall;
68  SCIP_Real maxparall;
69  SCIP_Real dircutoffdist;
70  SCIP_Real efficacyweight;
71  SCIP_Real objparalweight;
72  SCIP_Real intsuppweight;
73  int* succs1; /* successors of first state */
74  int* succs2; /* successors of second state */
75  int nstates; /* number of states */
76  int ncutscreated; /* number of generated cuts */
77  int ncutsapplied; /* number of cuts that were added to the pool */
78  int size; /* size of the cuts-array */
79  int rounds; /* number of separation rounds */
80  int states[3]; /* states in a triangle */
81  int nsuccs1; /* number of successors */
82  int nsuccs2;
83  int j; /* running indices */
84  int k;
85  int l;
86  SCIP_Bool usecutselection; /* should cut selection be uses */
87 
88  rounds = SCIPsepaGetNCallsAtNode(sepa);
89  if( rounds >= MAXROUNDS )
90  {
91  *result = SCIP_DIDNOTRUN;
92  return SCIP_OKAY;
93  }
94 
95  edgegraph = SCIPcycGetEdgeGraph(scip);
96  edgevars = SCIPcycGetEdgevars(scip);
97  nstates = SCIPcycGetNBins(scip);
98 
99  assert(nstates > 0);
100  assert(NULL != edgevars);
101  assert(NULL != edgegraph);
102 
103  ncutscreated = 0;
104  ncutsapplied = 0;
105  size = MAXCUTS;
106  *result = SCIP_DIDNOTFIND;
107 
108  SCIP_CALL( SCIPgetBoolParam(scip, "cycleclustering/usecutselection", &usecutselection) );
109 
110  SCIP_CALL( SCIPallocClearBufferArray(scip, &violation, size) );
111  SCIP_CALL( SCIPallocBufferArray(scip, &cuts, size) );
113 
114  /* for some inequalities, you can swap the minus sign to any variable of the triangle */
115  for( j = 0; j < 3; ++j )
116  {
117  SCIP_CALL( SCIPallocMemoryArray(scip, &sign[j], 3) ); /*lint !e866*/
118 
119  for( k = 0; k < 3; ++k )
120  {
121  sign[j][k] = 1.0;
122  }
123  sign[j][j] = -1.0;
124  }
125 
126  if( SCIPcycGetNCluster(scip) > 3 )
127  {
128  /* separate edges by the valid inequality z_ij1 + z_ik1 - y_jk0 <= 1 and z_ji + z_ki - y_jk1 <= 1
129  * (minus sign can be anywhere)
130  */
131  for( states[0] = 0; states[0] < nstates && ncutscreated < MAXCUTSCREATED; ++states[0] )
132  {
133  succs1 = SCIPdigraphGetSuccessors(edgegraph, states[0]);
134  nsuccs1 = SCIPdigraphGetNSuccessors(edgegraph, states[0]);
135 
136  for( j = 0; j < nsuccs1 && ncutscreated < MAXCUTSCREATED; ++j )
137  {
138  states[1] = succs1[j];
139  succs2 = SCIPdigraphGetSuccessors(edgegraph, states[1]);
140  nsuccs2 = SCIPdigraphGetNSuccessors(edgegraph, states[1]);
141 
142  for( k = 0; k < nsuccs2 && ncutscreated < MAXCUTSCREATED; ++k )
143  {
144  states[2] = succs2[k];
145 
146  if( !edgesExist(edgevars, states, 3) )
147  continue;
148 
149  if( (states[0] != states[1] && states[0] != states[2] && states[1] > states[2]) )
150  {
151  /* permute the minus sign */
152  for( l = 0; l < 3 ; ++l )
153  {
154  violation[ncutscreated] = sign[l][0]
155  * SCIPvarGetLPSol(getEdgevar(edgevars, states[0], states[1], 1));
156  violation[ncutscreated] += sign[l][1]
157  * SCIPvarGetLPSol(getEdgevar(edgevars, states[0], states[2], 1));
158  violation[ncutscreated] += sign[l][2]
159  * SCIPvarGetLPSol(getEdgevar(edgevars, states[1], states[2], 0)) - 1;
160 
161  if( violation[ncutscreated] > 0 )
162  {
163  (void)SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "trianglefw_%d_%d_%d_%d", states[0], states[1], states[2], l );
164  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &(cuts[ncutscreated]), sepa, cutname,
165  -SCIPinfinity(scip), 1.0, FALSE, FALSE, TRUE) );
166 
167  SCIP_CALL( SCIPcacheRowExtensions(scip, cuts[ncutscreated]) );
168 
169  SCIP_CALL( SCIPaddVarToRow(scip, cuts[ncutscreated],
170  getEdgevar(edgevars, states[1], states[2], 0), sign[l][2]) );
171  SCIP_CALL( SCIPaddVarToRow(scip, cuts[ncutscreated],
172  getEdgevar(edgevars, states[0], states[1], 1), sign[l][0]) );
173  SCIP_CALL( SCIPaddVarToRow(scip, cuts[ncutscreated],
174  getEdgevar(edgevars, states[0], states[2], 1), sign[l][1]) );
175 
176  SCIP_CALL( SCIPflushRowExtensions(scip, cuts[ncutscreated]) );
177 
178  if( ncutscreated >= size - 1 )
179  {
180  SCIP_CALL( SCIPreallocBufferArray(scip, &violation, (int) (size + MAXCUTS)) );
181  SCIP_CALL( SCIPreallocBufferArray(scip, &cuts, (int) (size + MAXCUTS)) );
182  size += MAXCUTS;
183  }
184 
185  ncutscreated++;
186  }
187 
188  violation[ncutscreated] = sign[l][0]
189  * SCIPvarGetLPSol(getEdgevar(edgevars, states[1], states[0], 1));
190  violation[ncutscreated] += sign[l][1]
191  * SCIPvarGetLPSol(getEdgevar(edgevars, states[2], states[0], 1));
192  violation[ncutscreated] += sign[l][2]
193  * SCIPvarGetLPSol(getEdgevar(edgevars, states[1], states[2], 0)) - 1;
194 
195  if( violation[ncutscreated] > 0)
196  {
197  (void)SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "trianglebw_%d_%d_%d_%d", states[0], states[1], states[2], l );
198  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &(cuts[ncutscreated]), sepa, cutname,
199  -SCIPinfinity(scip), 1.0, FALSE, FALSE, TRUE) );
200 
201  SCIP_CALL( SCIPcacheRowExtensions(scip, cuts[ncutscreated]) );
202 
203  SCIP_CALL( SCIPaddVarToRow(scip, cuts[ncutscreated],
204  getEdgevar(edgevars, states[1], states[2], 0), sign[l][2]) );
205  SCIP_CALL( SCIPaddVarToRow(scip, cuts[ncutscreated],
206  getEdgevar(edgevars, states[1], states[0], 1), sign[l][0]) );
207  SCIP_CALL( SCIPaddVarToRow(scip, cuts[ncutscreated],
208  getEdgevar(edgevars, states[2], states[0], 1), sign[l][1]) );
209 
210  SCIP_CALL( SCIPflushRowExtensions(scip, cuts[ncutscreated]) );
211 
212  if( ncutscreated >= size - 1 )
213  {
214  SCIP_CALL( SCIPreallocBufferArray(scip, &violation, (int) (size + MAXCUTS)) );
215  SCIP_CALL( SCIPreallocBufferArray(scip, &cuts, (int) (size + MAXCUTS)) );
216  size += MAXCUTS;
217  }
218 
219  ncutscreated++;
220  }
221  }
222  }
223 
224  if( states[0] > states[1] && states[1] > states[2] )
225  {
226  for( l = 0; l < 3; ++l )
227  {
228  violation[ncutscreated] = sign[l][0]
229  * SCIPvarGetLPSol(getEdgevar(edgevars, states[0], states[1], 0));
230  violation[ncutscreated] += sign[l][1]
231  * SCIPvarGetLPSol(getEdgevar(edgevars, states[0], states[2], 0));
232  violation[ncutscreated] += sign[l][2]
233  * SCIPvarGetLPSol(getEdgevar(edgevars, states[1], states[2], 0)) - 1;
234 
235  if( violation[ncutscreated] > 0 )
236  {
237  (void)SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "edgecut_%d_%d_%d", states[0], states[1], states[2]);
238  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &(cuts[ncutscreated]), sepa, cutname,
239  -SCIPinfinity(scip), 1.0, FALSE, FALSE, TRUE) );
240  SCIP_CALL( SCIPaddVarToRow(scip, cuts[ncutscreated],
241  getEdgevar(edgevars, states[0], states[1], 0), sign[l][0]) );
242  SCIP_CALL( SCIPaddVarToRow(scip, cuts[ncutscreated],
243  getEdgevar(edgevars, states[0], states[2], 0), sign[l][1]) );
244  SCIP_CALL( SCIPaddVarToRow(scip, cuts[ncutscreated],
245  getEdgevar(edgevars, states[1], states[2], 0), sign[l][2]) );
246 
247  if( ncutscreated >= size - 1 )
248  {
249  SCIP_CALL( SCIPreallocBufferArray(scip, &violation, (int) (size + MAXCUTS)) );
250  SCIP_CALL( SCIPreallocBufferArray(scip, &cuts, (int) (size + MAXCUTS)) );
251  size += MAXCUTS;
252  }
253 
254  ncutscreated++;
255  }
256  }
257  }
258  }
259  }
260  }
261  }
262 
263  if( SCIPcycGetNCluster(scip) == 3 )
264  {
265  for( states[0] = 0; states[0] < nstates; ++states[0] )
266  {
267  succs1 = SCIPdigraphGetSuccessors(edgegraph, states[0]);
268  nsuccs1 = SCIPdigraphGetNSuccessors(edgegraph, states[0]);
269 
270  for( j = 0; j < nsuccs1 && ncutscreated < MAXCUTSCREATED; ++j )
271  {
272  states[1] = succs1[j];
273  succs2 = SCIPdigraphGetSuccessors(edgegraph, states[1]);
274  nsuccs2 = SCIPdigraphGetNSuccessors(edgegraph, states[1]);
275 
276  for( k = 0; k < nsuccs2 && ncutscreated < MAXCUTSCREATED; ++k )
277  {
278  states[2] = succs2[k];
279 
280  if( !edgesExist(edgevars, states, 3) )
281  continue;
282 
283  violation[ncutscreated] = SCIPvarGetLPSol(getEdgevar(edgevars, states[0], states[1], 1));
284  violation[ncutscreated] += SCIPvarGetLPSol(getEdgevar(edgevars, states[1], states[2], 1));
285  violation[ncutscreated] -= SCIPvarGetLPSol(getEdgevar(edgevars, states[2], states[0], 1)) - 1;
286 
287  if( violation[ncutscreated] > 0 )
288  {
289  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "edgecut_%d_%d_%d", states[0], states[1], states[2]);
290  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &(cuts[ncutscreated]), sepa, cutname,
291  -SCIPinfinity(scip), 1.0, FALSE, FALSE, TRUE) );
292 
293  SCIP_CALL( SCIPcacheRowExtensions(scip, cuts[ncutscreated]) );
294 
295  SCIP_CALL( SCIPaddVarToRow(scip, cuts[ncutscreated],
296  getEdgevar(edgevars, states[0], states[1], 1), 1.0) );
297  SCIP_CALL( SCIPaddVarToRow(scip, cuts[ncutscreated],
298  getEdgevar(edgevars, states[1], states[2], 1), 1.0) );
299  SCIP_CALL( SCIPaddVarToRow(scip, cuts[ncutscreated],
300  getEdgevar(edgevars, states[2], states[0], 1), -1.0) );
301 
302  SCIP_CALL( SCIPflushRowExtensions(scip, cuts[ncutscreated]) );
303 
304  if( ncutscreated >= size - 1 )
305  {
306  SCIP_CALL( SCIPreallocBufferArray(scip, &violation, (int) (size + MAXCUTS)) );
307  SCIP_CALL( SCIPreallocBufferArray(scip, &cuts, (int) (size + MAXCUTS)) );
308  size += MAXCUTS;
309  }
310 
311  ncutscreated++;
312  }
313  }
314  }
315  }
316  }
317 
318  if( ncutscreated > 0 )
319  {
320  /* apply the cuts with the highest violation or use cut-selection */
321  if( usecutselection )
322  {
323  SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/goodscorefac", &goodscorefac) );
324  SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/badscorefac", &badscorefac) );
325  SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/goodmaxparall", &goodmaxparall) );
326  SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/maxparall", &maxparall) );
327  SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/dircutoffdist", &dircutoffdist) );
328  SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/efficacyweight", &efficacyweight) );
329  SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/objparalweight", &objparalweight) );
330  SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/intsuppweight", &intsuppweight) );
331 
332  SCIP_CALL( SCIPselectCutsHybrid(scip, cuts, NULL, NULL, goodscorefac, badscorefac,
333  goodmaxparall, maxparall, dircutoffdist, efficacyweight, objparalweight, intsuppweight,
334  ncutscreated, 0, MAXCUTS, &ncutsapplied) );
335  }
336  else
337  {
338  SCIPsortDownRealPtr(violation, ((void **) cuts), ncutscreated);
339  ncutsapplied = MIN(ncutscreated, MAXCUTS);
340  }
341 
342  for( j = 0; j < ncutsapplied; ++j )
343  {
344  SCIP_CALL( SCIPaddPoolCut(scip, cuts[j]) );
345  *result = SCIP_SEPARATED;
346  }
347  }
348 
349  /* free memory */
350  for( j = 0; j < ncutscreated; ++j )
351  {
352  SCIP_CALL( SCIPreleaseRow(scip, &(cuts[j])) );
353  }
354  SCIPfreeBufferArray(scip, &cuts);
355  SCIPfreeBufferArray(scip, &violation);
356  for( j = 0; j < 3; ++j )
357  {
358  SCIPfreeMemoryArray(scip, &sign[j]);
359  }
360  SCIPfreeMemoryArray(scip, &sign);
361 
362  return SCIP_OKAY;
363 }
364 
365 /** creates the Edge separator and includes it in SCIP */
367  SCIP* scip /**< SCIP data structure */
368  )
369 {
370  SCIP_SEPA* sepa;
371 
372  /* include separator */
375  sepaExeclpEdge, NULL,
376  NULL) );
377 
378  assert(sepa != NULL);
379 
380  /* set non fundamental callbacks via setter functions */
381  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyEdge) );
382 
383  return SCIP_OKAY;
384 }
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1626
#define SEPA_DESC
Definition: sepa_edge.c:31
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1649
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:117
#define SEPA_USESSUBSCIP
Definition: sepa_edge.c:35
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
SCIP_VAR * getEdgevar(SCIP_VAR ****edgevars, int state1, int state2, int direction)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
#define SCIP_MAXSTRLEN
Definition: def.h:293
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1686
hybrid cut selector
SCIP_RETCODE SCIPincludeSepaEdge(SCIP *scip)
Definition: sepa_edge.c:366
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7721
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
void SCIPsortDownRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
#define SEPA_NAME
Definition: sepa_edge.c:30
SCIP_VAR **** SCIPcycGetEdgevars(SCIP *scip)
#define FALSE
Definition: def.h:87
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10755
#define TRUE
Definition: def.h:86
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:734
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
static SCIP_DECL_SEPAEXECLP(sepaExeclpEdge)
Definition: sepa_edge.c:57
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:142
#define SCIPallocClearMemoryArray(scip, ptr, num)
Definition: scip_mem.h:57
#define SEPA_FREQ
Definition: sepa_edge.c:33
edge-separator. Separates triangle-inequalities in cycle clustering problem
#define MAXCUTSCREATED
Definition: sepa_edge.c:38
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:871
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_Bool edgesExist(SCIP_VAR ****edgevars, int *states, int nstates)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18284
static SCIP_DECL_SEPACOPY(sepaCopyEdge)
Definition: sepa_edge.c:43
#define SCIP_CALL(x)
Definition: def.h:384
int SCIPcycGetNBins(SCIP *scip)
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition: scip_sepa.c:100
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7706
#define SCIP_Bool
Definition: def.h:84
#define MAXROUNDS
Definition: sepa_edge.c:39
SCIP_RETCODE SCIPselectCutsHybrid(SCIP *scip, SCIP_ROW **cuts, SCIP_ROW **forcedcuts, SCIP_RANDNUMGEN *randnumgen, SCIP_Real goodscorefac, SCIP_Real badscorefac, SCIP_Real goodmaxparall, SCIP_Real maxparall, SCIP_Real dircutoffdistweight, SCIP_Real efficacyweight, SCIP_Real objparalweight, SCIP_Real intsupportweight, int ncuts, int nforcedcuts, int maxselectedcuts, int *nselectedcuts)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:352
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1444
problem data for cycle clustering problem
#define MAXCUTS
Definition: sepa_edge.c:37
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1553
int SCIPcycGetNCluster(SCIP *scip)
SCIP_DIGRAPH * SCIPcycGetEdgeGraph(SCIP *scip)
#define SCIP_Real
Definition: def.h:177
#define SEPA_DELAY
Definition: sepa_edge.c:36
#define SEPA_MAXBOUNDDIST
Definition: sepa_edge.c:34
#define SEPA_PRIORITY
Definition: sepa_edge.c:32
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:119