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