Scippy

SCIP

Solving Constraint Integer Programs

probdata_cyc.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 probdata_cyc.c
17  * @brief problem data for cycle clustering problem
18  * @author Leon Eifler
19  *
20  * This file implements the problem data for the cycle clustering problem.
21  *
22  * The problem data contains original transition matrix, the scaling parameter that appears in the objective function,
23  * and all variables that appear in the problem.
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 #include "probdata_cyc.h"
28 
29 #include "scip/cons_nonlinear.h"
30 #include "scip/cons_linear.h"
31 #include "scip/cons_logicor.h"
32 #include "scip/var.h"
33 #include <assert.h>
34 
35 struct SCIP_ProbData
36 {
37  SCIP_VAR**** edgevars; /**< variables for the edges (pairs of states) inside and between consecutive clusters */
38  SCIP_DIGRAPH* edgegraph; /**< digraph which tells us which variables are actually created */
39  SCIP_VAR*** binvars; /**< variable-matrix belonging to the state(bin)-cluster assignment */
40  SCIP_Real** cmatrix; /**< matrix to save the transition matrix */
41  SCIP_Real scale; /**< the weight-factor for the coherence in the objective function */
42  char model_variant; /**< the model that is used. w for weighted objective, e for normal edge-representation */
43  int nbins; /**< the number of states */
44  int ncluster; /**< the number of clusters */
45 };
46 
47 /** Check if the clustering has exactly one state in every cluster. */
49  SCIP* scip, /**< SCIP data structure */
50  SCIP_Real** solclustering, /**< matrix with the clustering */
51  int nbins, /**< the number of bins */
52  int ncluster /**< the number of clusters */
53  )
54 {
55  int i;
56  int j;
57 
58  /* check if the assignment violates paritioning, e.g. because we are in a subscip */
59  for( i = 0; i < nbins; ++i )
60  {
61  SCIP_Real sum = 0.0;
62 
63  for( j = 0; j < ncluster; ++j )
64  {
65  if( !SCIPisIntegral(scip, solclustering[i][j]) )
66  return FALSE;
67  if( !SCIPisZero(scip, solclustering[i][j]) )
68  sum += solclustering[i][j];
69  }
70  if( !SCIPisEQ(scip, sum, 1.0) )
71  return FALSE;
72 
73  }
74 
75  return TRUE;
76 }
77 
78 /** Assign the variables in scip according to the found clustering. */
80  SCIP* scip, /**< SCIP data structure */
81  SCIP_SOL* sol, /**< the SCIP solution */
82  SCIP_Real** clustering, /**< the matrix with the clusterassignment */
83  int nbins, /**< the number of bins */
84  int ncluster /**< the number of cluster */
85  )
86 {
87  SCIP_VAR* var;
88  SCIP_VAR*** binvars;
89  SCIP_VAR**** edgevars;
90  int i;
91  int j;
92  int c;
93 
94  binvars = SCIPcycGetBinvars(scip);
95  edgevars = SCIPcycGetEdgevars(scip);
96 
97  assert(nbins > 0 && ncluster > 0);
98  assert(binvars != NULL);
99  assert(edgevars != NULL);
100 
101  for ( c = 0; c < ncluster; ++c )
102  {
103  /* set values of state-variables */
104  for ( i = 0; i < nbins; ++i )
105  {
106  if( NULL != binvars[i][c] )
107  {
108  if( SCIPvarIsTransformed(binvars[i][c]) )
109  var = binvars[i][c];
110  else
111  var = SCIPvarGetTransVar(binvars[i][c] );
112 
113  /* check if the clusterassignment is feasible for the variable bounds. If not do not assign the variable */
114  if( var != NULL && SCIPisLE(scip, SCIPvarGetLbGlobal(var), clustering[i][c]) &&
115  SCIPisGE(scip, SCIPvarGetUbGlobal(var), clustering[i][c]) &&
117  {
118  SCIP_CALL( SCIPsetSolVal( scip, sol, var, clustering[i][c]) );
119  }
120 
121  assert(SCIPisIntegral(scip, clustering[i][c]));
122  }
123  }
124 
125  /* set the value for the edgevariables for each pair of states */
126  for( i = 0; i < nbins; ++i )
127  {
128  for( j = 0; j < i; ++j )
129  {
130  if( NULL == edgevars[i][j] || NULL == edgevars[j][i])
131  continue;
132 
133  /* check if bins are in same cluster */
134  if( SCIPisEQ(scip, 1.0, clustering[i][c] * clustering[j][c]) )
135  {
136  var = edgevars[i][j][0];
137  if( var != NULL && SCIPisGE(scip, SCIPvarGetUbGlobal(var), clustering[j][c] * clustering[i][c])
139  {
140  SCIP_CALL( SCIPsetSolVal( scip, sol, var, 1.0 ) );
141  }
142  }
143 
144  /* check if bins are in consecutive clusters */
145  else if( SCIPisEQ(scip, 1.0, clustering[i][c] * clustering[j][phi(c, ncluster)]) )
146  {
147  var = edgevars[i][j][1];
148  if( var != NULL && SCIPvarGetStatus(var) != SCIP_VARSTATUS_MULTAGGR &&
149  SCIPisGE(scip, SCIPvarGetUbGlobal(var), clustering[j][phi(c, ncluster)] * clustering[i][c]) )
150  {
151  SCIP_CALL( SCIPsetSolVal( scip, sol, var, 1.0 ) );
152  }
153  }
154 
155  else if( SCIPisEQ(scip, 1.0, clustering[j][c] * clustering[i][phi(c, ncluster)]) )
156  {
157  var = edgevars[j][i][1];
158  if( var != NULL && SCIPvarGetStatus(var) != SCIP_VARSTATUS_MULTAGGR &&
159  SCIPisGE(scip, SCIPvarGetUbGlobal(var), clustering[j][c] * clustering[i][phi(c, ncluster)]) )
160  {
161  SCIP_CALL( SCIPsetSolVal( scip, sol, var, 1.0 ) );
162  }
163  }
164  }
165  }
166  }
167 
168  return SCIP_OKAY;
169 }
170 
171 /** function that returns the successive cluster along the cycle */
172 int phi(
173  int k, /**< the cluster */
174  int ncluster /**< the number of clusters*/
175  )
176 {
177  assert(k < ncluster && k >= 0);
178  assert(ncluster > 0);
179 
180  return (k+1) % ncluster;
181 }
182 
183 /** function that returns the predecessor-cluster along the cycle */
184 int phiinv(
185  int k, /**< the cluster */
186  int ncluster /**< the number of clusters */
187  )
188 {
189  assert(k < ncluster && k >= 0);
190  assert(ncluster > 0);
191 
192  if( k - 1 < 0 )
193  return ncluster - 1;
194  else
195  return k - 1;
196 }
197 
198 /** creates all the variables for the problem. The constraints are added later, depending on the model that is used */
199 static
201  SCIP* scip, /**< SCIP data Structure */
202  SCIP_PROBDATA* probdata /**< the problem data */
203  )
204 {
205  int i;
206  int j;
207  int c;
208  int edgetype;
209  int nbins = probdata->nbins;
210  int ncluster = probdata->ncluster;
211  char varname[SCIP_MAXSTRLEN];
212 
213  /* create variables for bins */
215  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->binvars), nbins) );
216 
217  for( i = 0; i < nbins; ++i )
218  {
219  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->binvars[i]), ncluster) ); /*lint !e866*/
220  }
221 
222  for( i = 0; i < nbins; ++i )
223  {
224  for( c = 0; c < ncluster; ++c )
225  {
226  (void)SCIPsnprintf(varname, SCIP_MAXSTRLEN, "x_%d_%d", i, c);
227  SCIP_CALL( SCIPcreateVarBasic(scip, &probdata->binvars[i][c], varname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY) );
228  SCIP_CALL( SCIPaddVar(scip, probdata->binvars[i][c]) );
229  }
230  }
231 
232  /* create variables for the edges in each cluster combination. Index 0 are edges within cluster, 1 edges between
233  * consequtive clusters and 2 edges between non-consequtive clusters
234  */
235  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->edgevars), nbins) );
236 
237  for( i = 0; i < nbins; ++i )
238  {
239  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(probdata->edgevars[i]), nbins) ); /*lint !e866*/
240 
241  for( j = 0; j < nbins; ++j )
242  {
243  if( i == j || (SCIPisZero(scip, (probdata->cmatrix[i][j] - probdata->cmatrix[j][i]))
244  && SCIPisZero(scip, (probdata->cmatrix[i][j] + probdata->cmatrix[j][i]) )) )
245  continue;
246 
247  SCIP_CALL( SCIPdigraphAddArc(probdata->edgegraph, i, j, NULL) );
248 
249  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(probdata->edgevars[i][j]), 3) ); /*lint !e866*/
250 
251  for( edgetype = 0; edgetype < 3; ++edgetype )
252  {
253  if( edgetype == 0 && i < j )
254  continue;
255 
256  (void)SCIPsnprintf(varname, SCIP_MAXSTRLEN, "y_%d_%d_%d", i, j, edgetype);
257  SCIP_CALL( SCIPcreateVarBasic(scip, &probdata->edgevars[i][j][edgetype], varname,
258  0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY) );
259  SCIP_CALL( SCIPaddVar(scip, probdata->edgevars[i][j][edgetype]) );
260  }
261  }
262  }
263 
264  return SCIP_OKAY;
265 }
266 
267 /** create the problem without variable amount of clusters, use simpler non-facet-defining inequalities */
268 static
270  SCIP* scip, /**< SCIP Data Structure */
271  SCIP_PROBDATA* probdata /**< the problem data */
272  )
273 {
274  int i;
275  int j;
276  int c1;
277  int c2;
278  char consname[SCIP_MAXSTRLEN];
279  SCIP_CONS* temp;
280  int nbins = probdata->nbins;
281  int ncluster = probdata->ncluster;
282  SCIP_Real scale;
283 
284  SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/scale_coherence", &scale) );
285  probdata->scale = scale;
286 
287  /* create constraints */
288 
289  /* create the set-partitioning constraints of the bins */
290  for( i = 0; i < nbins; ++i )
291  {
292  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "setpart_%d", i+1 );
293  SCIP_CALL( SCIPcreateConsSetpart(scip, &temp, consname, 0, NULL, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE,
294  FALSE, FALSE, FALSE) );
295 
296  for ( c1 = 0; c1 < ncluster; ++c1 )
297  {
298  SCIP_CALL( SCIPaddCoefSetppc(scip, temp, probdata->binvars[i][c1]) );
299  }
300  SCIP_CALL( SCIPaddCons(scip, temp) );
301  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
302  }
303 
304  /* create constraints for the edge-cut variables */
305  SCIPinfoMessage(scip, NULL, "Using edge-representation with simplified structure. Fixed amount of cluster. \n");
306  for( i = 0; i < nbins; ++i )
307  {
308  for( j = 0; j < i; ++j )
309  {
310  if( probdata->edgevars[i][j] == NULL )
311  continue;
312 
313  /* these edges are not within a cluster */
314  SCIP_CALL( SCIPchgVarObj(scip, probdata->edgevars[i][j][0],
315  (probdata->cmatrix[i][j] + probdata->cmatrix[j][i]) * scale) );
316 
317  /* these are the edges that are between consequtive clusters */
318  SCIP_CALL( SCIPchgVarObj(scip, probdata->edgevars[i][j][1], (probdata->cmatrix[i][j] - probdata->cmatrix[j][i])) );
319  SCIP_CALL( SCIPchgVarObj(scip, probdata->edgevars[j][i][1], (probdata->cmatrix[j][i] - probdata->cmatrix[i][j])) );
320 
321  /* create constraints that determine when the edge-variables have to be non-zero */
322  for( c1 = 0; c1 < ncluster; ++c1 )
323  {
324  /* constraints for edges within clusters */
325  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "bins_%d_%d_incluster_%d", i+1, j+1, c1+1 );
326  SCIP_CALL( SCIPcreateConsLinear(scip, &temp, consname, 0, NULL, NULL, -SCIPinfinity(scip), 1.0,
327  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
328 
329  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[i][j][0], -1.0) );
330  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[i][c1], 1.0) );
331  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[j][c1], 1.0) );
332 
333  SCIP_CALL( SCIPaddCons(scip, temp) );
334  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
335 
336  /* constraints for edges between clusters */
337  for( c2 = 0; c2 < ncluster; ++c2 )
338  {
339  SCIP_VAR* var;
340 
341  if( c2 == c1 )
342  continue;
343 
344  if( c2 == c1 + 1 || ( c2 == 0 && c1 == ncluster -1) )
345  var = probdata->edgevars[i][j][1];
346  else if( c2 == c1 - 1 || ( c1 == 0 && c2 == ncluster -1) )
347  var = probdata->edgevars[j][i][1];
348  else
349  var = probdata->edgevars[i][j][2];
350 
351  /* if two bins are in a different cluster -> the corresponding edge must be cut */
352  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "bins_%d_%d_inclusters_%d_%d", i+1, j+1, c1+1, c2+1 );
353  SCIP_CALL( SCIPcreateConsLinear(scip, &temp, consname, 0, NULL, NULL, -SCIPinfinity(scip), 1.0,
354  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
355 
356  SCIP_CALL( SCIPaddCoefLinear(scip, temp, var, -1.0) );
357  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[i][c1], 1.0) );
358  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[j][c2], 1.0) );
359 
360  SCIP_CALL( SCIPaddCons(scip, temp) );
361  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
362  }
363  }
364  }
365  }
366 
367  /* only one cluster-pair at the same time can be active for an edge*/
368  for( i = 0; i < nbins; ++i )
369  {
370  for( j = 0; j < i; ++j )
371  {
372  if( NULL == probdata->edgevars[i][j] )
373  continue;
374 
375  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "sumedge_%d_%d", i+1, j+1 );
376  SCIP_CALL( SCIPcreateConsBasicLinear(scip, &temp, consname, 0, NULL, NULL, 1.0, 1.0 ) );
377 
378  for( c1 = 0; c1 < 3; ++c1 )
379  {
380  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[i][j][c1], 1.0) );
381  }
382  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[j][i][1], 1.0) );
383 
384  SCIP_CALL( SCIPaddCons(scip, temp) );
385  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
386  }
387  }
388 
389  /* add constraint that ensures that each cluster is used */
390  for( c1 = 0; c1 < ncluster; ++c1 )
391  {
392  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "cluster_%d_used", c1+1 );
393  SCIP_CALL( SCIPcreateConsBasicLogicor(scip, &temp, consname, 0, NULL) );
394 
395  for( i = 0; i < nbins; ++i )
396  {
397  SCIP_CALL( SCIPaddCoefLogicor(scip, temp, probdata->binvars[i][c1]) );
398  }
399 
400  SCIP_CALL( SCIPaddCons(scip, temp) );
401  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
402  }
403 
404  return SCIP_OKAY;
405 }
406 
407 /** create the problem without variable amount of clusters, using three edge-variables for each pair of states.
408  * This is the tested default version.
409  */
410 static
412  SCIP* scip, /**< SCIP Data Structure */
413  SCIP_PROBDATA* probdata /**< The problem data */
414  )
415 {
416  int i;
417  int j;
418  int c1;
419  int nbins = probdata->nbins;
420  int ncluster = probdata->ncluster;
421  char consname[SCIP_MAXSTRLEN];
422  SCIP_CONS* temp;
423  SCIP_Real scale;
424 
425  SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/scale_coherence", &scale) );
426  probdata->scale = scale;
427 
428  /* create constraints */
429 
430  /* create the set-partitioning constraints of the bins */
431  for( i = 0; i < nbins; ++i )
432  {
433  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "setpart_%d", i+1);
434  SCIP_CALL( SCIPcreateConsSetpart(scip, &temp, consname, 0, NULL, TRUE, TRUE, TRUE, TRUE, TRUE,
435  FALSE, FALSE, FALSE, FALSE, FALSE) );
436 
437  for ( c1 = 0; c1 < ncluster; ++c1 )
438  {
439  SCIP_CALL( SCIPaddCoefSetppc(scip, temp, probdata->binvars[i][c1]) );
440  }
441 
442  SCIP_CALL( SCIPaddCons(scip, temp) );
443  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
444  }
445 
446  /* create constraints for the edge-variables */
448  "Using edge-representation with simplified structure. No variable amount of cluster. \n");
449 
450  for( i = 0; i < nbins; ++i )
451  {
452  for( j = 0; j < i; ++j )
453  {
454  if( NULL == probdata->edgevars[i][j] )
455  continue;
456 
457  /* the general formulation is needed if there are more than 3 clusters. In the case of three clusters the
458  * formulation is simplified
459  */
460  if( ncluster > 3 )
461  {
462  /* these edges are within a cluster */
463  SCIP_CALL( SCIPchgVarObj(scip, probdata->edgevars[i][j][0],
464  (probdata->cmatrix[i][j] + probdata->cmatrix[j][i]) * scale) );
465 
466  /* these are the edges that are between consequtive clusters */
467  SCIP_CALL( SCIPchgVarObj(scip, probdata->edgevars[i][j][1],
468  (probdata->cmatrix[i][j] - probdata->cmatrix[j][i])) );
469  SCIP_CALL( SCIPchgVarObj(scip, probdata->edgevars[j][i][1],
470  (probdata->cmatrix[j][i] - probdata->cmatrix[i][j])) );
471 
472  /* create constraints that determine when the edge-variables have to be non-zero*/
473  for( c1 = 0; c1 < ncluster; ++c1 )
474  {
475  /* constraints for edges within clusters and between clusters*/
476  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "bins_%d_%d_incluster_%d", i, j, c1);
477  SCIP_CALL( SCIPcreateConsLinear(scip, &temp, consname, 0, NULL, NULL, -SCIPinfinity(scip), 1.0,
479 
480  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[i][j][0], -1.0) );
481  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[i][c1], 1.0) );
482  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[j][c1], 1.0) );
483  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[i][j][1], 1.0) );
484  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[i][phiinv(c1, ncluster)], -1.0) );
485  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[j][phi(c1, ncluster)], -1.0) );
486 
487  SCIP_CALL( SCIPaddCons(scip, temp) );
488  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
489 
490  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "bins_%d_%d_incluster_part2_%d", i, j, c1);
491  SCIP_CALL( SCIPcreateConsLinear(scip, &temp, consname, 0, NULL, NULL, -SCIPinfinity(scip), 1.0,
493 
494  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[i][j][0], -1.0) );
495  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[i][c1], 1.0) );
496  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[j][c1], 1.0) );
497  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[j][i][1], 1.0) );
498  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[i][phi(c1, ncluster)], -1.0) );
499  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[j][phiinv(c1, ncluster)], -1.0) );
500 
501  SCIP_CALL( SCIPaddCons(scip, temp) );
502  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
503 
504  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "bins_%d_%d_incluster_%d_%d", i, j, c1, phi(c1, ncluster));
505  SCIP_CALL( SCIPcreateConsLinear(scip, &temp, consname, 0, NULL, NULL, -SCIPinfinity(scip), 1.0,
507 
508  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[i][j][1], -1.0) );
509  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[i][c1], 1.0) );
510  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[j][phi(c1, ncluster)], 1.0) );
511  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[i][j][0], 1.0) );
512  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[i][phi(c1, ncluster)], -1.0) );
513  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[j][c1], -1.0) );
514 
515  SCIP_CALL( SCIPaddCons(scip, temp) );
516  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
517 
518  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "bins_%d_%d_incluster_%d_%d", i, j, c1, phiinv(c1, ncluster));
519  SCIP_CALL( SCIPcreateConsLinear(scip, &temp, consname, 0, NULL, NULL, -SCIPinfinity(scip), 1.0,
521 
522  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[j][i][1], -1.0) );
523  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[i][c1], 1.0) );
524  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[j][phiinv(c1,ncluster)], 1.0) );
525  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[i][j][0], 1.0) );
526  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[i][phiinv(c1, ncluster)], -1.0) );
527  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[j][c1], -1.0) );
528 
529  SCIP_CALL( SCIPaddCons(scip, temp) );
530  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
531  }
532  }
533  /* some variables become obsolete with three clusters */
534  else
535  {
536  /* these are the edges that are between consequtive clusters */
537  SCIP_CALL( SCIPchgVarObj(scip, probdata->edgevars[i][j][1],
538  (probdata->cmatrix[i][j] - probdata->cmatrix[j][i])
539  - (probdata->cmatrix[i][j] + probdata->cmatrix[j][i]) * scale) );
540  SCIP_CALL( SCIPchgVarObj(scip, probdata->edgevars[j][i][1],
541  (probdata->cmatrix[j][i] - probdata->cmatrix[i][j])
542  - (probdata->cmatrix[i][j] + probdata->cmatrix[j][i]) * scale) );
543 
544  SCIP_CALL( SCIPaddOrigObjoffset(scip, (probdata->cmatrix[i][j] + probdata->cmatrix[j][i]) * scale) );
545 
546  /* create constraints that determine when the edge-variables have to be non-zero*/
547  for( c1 = 0; c1 < ncluster; ++c1 )
548  {
549  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "bins_%d_%d_incluster_%d", i, j, c1);
550  SCIP_CALL( SCIPcreateConsLinear(scip, &temp, consname, 0, NULL, NULL, -SCIPinfinity(scip), 1.0,
552  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[i][j][1], -1.0) );
553 
554  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[j][i][1], 1.0) );
555  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[i][c1], 1.0) );
556  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[j][phi(c1, ncluster)], 1.0) );
557  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[i][phiinv(c1, ncluster)], -1.0) );
558  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[j][phiinv(c1, ncluster)], -1.0) );
559 
560  SCIP_CALL( SCIPaddCons(scip, temp) );
561  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
562 
563  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "bins_%d_%d_incluster_%d", j, i, c1);
564  SCIP_CALL( SCIPcreateConsLinear(scip, &temp, consname, 0, NULL, NULL, -SCIPinfinity(scip), 1.0,
566 
567  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[j][i][1], -1.0) );
568  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[i][j][1], 1.0) );
569  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[j][c1], 1.0) );
570  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[i][phi(c1, ncluster)], 1.0) );
571  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[i][phiinv(c1, ncluster)], -1.0) );
572  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->binvars[j][phiinv(c1, ncluster)], -1.0) );
573 
574  SCIP_CALL( SCIPaddCons(scip, temp) );
575  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
576  }
577  }
578  }
579  }
580 
581  /* only one cluster-pair at the same time can be active for an edge*/
582  for( i = 0; i < nbins; ++i )
583  {
584  for( j = 0; j < i; ++j )
585  {
586  if( NULL == probdata->edgevars[i][j] || (SCIPisZero(scip, (probdata->cmatrix[i][j] - probdata->cmatrix[j][i]))
587  && SCIPisZero(scip, (probdata->cmatrix[i][j] + probdata->cmatrix[j][i]) * scale) ) )
588  continue;
589 
590  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "sumedge_%d_%d", i, j);
591  SCIP_CALL( SCIPcreateConsBasicLinear(scip, &temp, consname, 0, NULL, NULL, -SCIPinfinity(scip), 1.0) );
592 
593  for( c1 = 0; c1 < 2; ++c1 )
594  {
595  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[i][j][c1], 1.0) );
596  }
597 
598  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[j][i][1], 1.0) );
599 
600  SCIP_CALL( SCIPaddCons(scip, temp) );
601  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
602  }
603  }
604 
605  /* add constraint that ensures that each cluster is used */
606  for( c1 = 0; c1 < ncluster; ++c1 )
607  {
608  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "cluster_%d_used", c1);
609  SCIP_CALL( SCIPcreateConsBasicLogicor(scip, &temp, consname, 0, NULL) );
610 
611  for( i = 0; i < nbins; ++i )
612  {
613  SCIP_CALL( SCIPaddCoefLogicor(scip, temp, probdata->binvars[i][c1]) );
614  }
615 
616  SCIP_CALL( SCIPaddCons(scip, temp) );
617  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
618  }
619 
620  return SCIP_OKAY;
621 }
622 
623 /** create the problem without variable amount of clusters, using quadratic formulations. This is inferior to the
624  * simplified variant. Only useful for comparing relaxations.
625  */
626 static
628  SCIP* scip, /**< SCIP Data Structure */
629  SCIP_PROBDATA* probdata /**< The problem data */
630  )
631 {
632  SCIP_VAR** quadvars1;
633  SCIP_VAR** quadvars2;
634  SCIP_VAR** edgevars;
635  SCIP_Real* quadcoefs;
636  SCIP_CONS* temp;
637  SCIP_Real scale;
638  char varname[SCIP_MAXSTRLEN];
639  char consname[SCIP_MAXSTRLEN];
640  int i;
641  int j;
642  int c1;
643  int c;
644  int nbins = probdata->nbins;
645  int ncluster = probdata->ncluster;
646 
647  SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/scale_coherence", &scale) );
648  probdata->scale = scale;
649  /* create variables for bins */
651 
652  /* allocate memory to create nonlinear constraints */
653  SCIP_CALL( SCIPallocBufferArray(scip, &quadvars1, nbins * nbins) );
654  SCIP_CALL( SCIPallocBufferArray(scip, &quadvars2, nbins * nbins) );
655  SCIP_CALL( SCIPallocBufferArray(scip, &quadcoefs, nbins * nbins) );
656 
657  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->binvars), nbins) );
658 
659  for( i = 0; i < nbins; ++i )
660  {
661  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->binvars[i]), ncluster) ); /*lint !e866*/
662  }
663 
664  for( i = 0; i < nbins; ++i )
665  {
666  for( c = 0; c < ncluster; ++c )
667  {
668  (void)SCIPsnprintf(varname, SCIP_MAXSTRLEN, "x_%d_%d", i, c);
669  SCIP_CALL( SCIPcreateVarBasic(scip, &probdata->binvars[i][c], varname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY) );
670  SCIP_CALL( SCIPaddVar(scip, probdata->binvars[i][c]) );
671  }
672  }
673 
674  /* create variables for the edges in each cluster combination. Index 0 are edges within cluster, 1 edges between
675  * consequtive clusters and 2 edges between non-consequtive clusters
676  */
677  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(edgevars), (SCIP_Longint) ncluster * 2) );
678 
679  for( i = 0; i < 2 * ncluster; ++i )
680  {
681  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "f_%d", i);
682 
683  SCIP_CALL( SCIPcreateVarBasic(scip, &edgevars[i], varname, -SCIPinfinity(scip), SCIPinfinity(scip),
684  1.0, SCIP_VARTYPE_CONTINUOUS) );
685  SCIP_CALL( SCIPaddVar(scip, edgevars[i]) );
686  }
687 
688  /* create variables for the edges in each cluster combination. Index 0 are edges within cluster, 1 edges between
689  * consequtive clusters and 2 edges between non-consequtive clusters
690  */
691  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(probdata->edgevars), nbins) );
692 
693  for( i = 0; i < nbins; ++i )
694  {
695  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(probdata->edgevars[i]), nbins) ); /*lint !e866*/
696 
697  for( j = 0; j < nbins; ++j )
698  probdata->edgevars[i][j] = NULL;
699  }
700 
701  /*
702  * create constraints
703  */
704 
705  /* create the set-partitioning constraints of the bins */
706  for( i = 0; i < nbins; ++i )
707  {
708  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "setpart_%d", i+1);
709  SCIP_CALL( SCIPcreateConsSetpart(scip, &temp, consname, 0, NULL, TRUE, TRUE, TRUE, TRUE, TRUE,
710  FALSE, FALSE, FALSE, FALSE, FALSE) );
711 
712  for ( c1 = 0; c1 < ncluster; ++c1 )
713  {
714  SCIP_CALL( SCIPaddCoefSetppc(scip, temp, probdata->binvars[i][c1]) );
715  }
716 
717  SCIP_CALL( SCIPaddCons(scip, temp) );
718  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
719  }
720 
721  /* add constraint that ensures that each cluster is used */
722  for( c1 = 0; c1 < ncluster; ++c1 )
723  {
724  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "cluster_%d_used", c1);
725  SCIP_CALL( SCIPcreateConsBasicLogicor(scip, &temp, consname, 0, NULL) );
726 
727  for( i = 0; i < nbins; ++i )
728  {
729  SCIP_CALL( SCIPaddCoefLogicor(scip, temp, probdata->binvars[i][c1]) );
730  }
731 
732  SCIP_CALL( SCIPaddCons(scip, temp) );
733  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
734  }
735 
736  for( c = 0; c < ncluster; ++c)
737  {
738  SCIP_Real one = 1.0;
739  int nquadterms = 0;
740 
741  /* collect quadratic terms */
742  for( i = 0; i < nbins; ++i )
743  {
744  for( j = 0; j < nbins; ++j )
745  {
746  if( i != j )
747  {
748  quadvars1[nquadterms] = probdata->binvars[i][c];
749  quadvars2[nquadterms] = probdata->binvars[j][phi(c,ncluster)];
750  quadcoefs[nquadterms] = probdata->cmatrix[j][i] - probdata->cmatrix[i][j];
751  ++nquadterms;
752  }
753  }
754  }
755 
756  /* create, add, and release constraint */
757  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "irrev_%d", c);
758  SCIP_CALL( SCIPcreateConsQuadraticNonlinear(scip, &temp, consname, 1, &edgevars[c], &one, nquadterms, quadvars1,
759  quadvars2, quadcoefs, -SCIPinfinity(scip), 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) );
760  SCIP_CALL( SCIPaddCons(scip, temp) );
761  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
762  }
763 
764  for( c = 0; c < ncluster; ++c )
765  {
766  SCIP_Real one = 1.0;
767  int nquadterms = 0;
768 
769  for( i = 0; i < nbins; ++i)
770  {
771  for( j = 0; j < nbins; ++j )
772  {
773  if( i > j )
774  {
775  quadvars1[nquadterms] = probdata->binvars[i][c];
776  quadvars2[nquadterms] = probdata->binvars[j][c];
777  quadcoefs[nquadterms] = -scale * (probdata->cmatrix[i][j] + probdata->cmatrix[j][i]);
778  ++nquadterms;
779  }
780  }
781  }
782 
783  /* create, add, and release constraint */
784  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "coh_%d", c);
785  SCIP_CALL( SCIPcreateConsQuadraticNonlinear(scip, &temp, consname, 1, &edgevars[c+ncluster], &one, nquadterms, quadvars1,
786  quadvars2, quadcoefs, -SCIPinfinity(scip), 0.0, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE) );
787  SCIP_CALL( SCIPaddCons(scip, temp) );
788  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
789  }
790 
791  for (i = 0; i < 2*ncluster; i++ )
792  {
793  SCIP_CALL( SCIPreleaseVar(scip, &edgevars[i]) );
794  }
795 
796  SCIPfreeBlockMemoryArray(scip, &edgevars, (SCIP_Longint) 2 * ncluster);
797 
798  /* free memory */
799  SCIPfreeBufferArray(scip, &quadcoefs);
800  SCIPfreeBufferArray(scip, &quadvars2);
801  SCIPfreeBufferArray(scip, &quadvars1);
802 
803  return SCIP_OKAY;
804 }
805 
806 
807 /** create the problem with variable amount of clusters. Very large number of constraints not viable for large scale
808  * problems.
809  */
810 static
812  SCIP* scip, /**< SCIP Data Structure */
813  SCIP_PROBDATA* probdata /**< The problem data */
814  )
815 {
816  SCIP_CONS* temp;
817  SCIP_Real scale;
818  SCIP_Real sign[3][3];
819  char consname[SCIP_MAXSTRLEN];
820  int nbins = probdata->nbins;
821  int i;
822  int j;
823  int k;
824  int l;
825 
826  SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/scale_coherence", &scale) );
827  probdata->scale = scale;
828 
829  for( i = 0; i < 3; ++i )
830  {
831  for( j = 0; j < 3; ++j )
832  {
833  sign[i][j] = 1.0;
834  }
835  sign[i][i] = -1.0;
836  }
837  /*
838  * create constraints
839  */
840 
841  /* create constraints for the edge-cut variables */
843  "Using edge-representation with simplified structure. No variable amount of cluster. \n");
844 
845  for( i = 0; i < nbins; ++i )
846  {
847  for( j = 0; j < nbins; ++j )
848  {
849  /* set the objective weight for the edge-variables */
850 
851  /* these edges are not within a cluster */
852  if( j < i )
853  {
854  SCIP_CALL( SCIPchgVarObj(scip, probdata->edgevars[i][j][0], (probdata->cmatrix[i][j] + probdata->cmatrix[j][i]) * scale) );
855  /* these are the edges that are between consequtive clusters */
856  SCIP_CALL( SCIPchgVarObj(scip, probdata->edgevars[i][j][1], (probdata->cmatrix[i][j] - probdata->cmatrix[j][i])) );
857  SCIP_CALL( SCIPchgVarObj(scip, probdata->edgevars[j][i][1], (probdata->cmatrix[j][i] - probdata->cmatrix[i][j])) );
858 
859  (void)SCIPsnprintf(consname, SCIP_MAXSTRLEN, "bins_%d_%d", i+1, j+1);
860  SCIP_CALL( SCIPcreateConsLinear(scip, &temp, consname, 0, NULL, NULL, -SCIPinfinity(scip), 1.0,
862 
863  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[i][j][0], 1.0) );
864  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[i][j][1], 1.0) );
865  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[j][i][1], 1.0) );
866 
867  SCIP_CALL( SCIPaddCons(scip, temp) );
868  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
869  }
870 
871  for( k = 0; k < nbins; ++k )
872  {
873  if( i == k || i == j || k == j )
874  continue;
875 
876  if( k < j && j < i )
877  {
878  for( l = 0; l < 3; l++ )
879  {
880  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "tri_%d_%d_%d", i, j, k);
881  SCIP_CALL( SCIPcreateConsLinear(scip, &temp, consname, 0, NULL, NULL, -SCIPinfinity(scip), 1.0,
883 
884  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[i][j][0], sign[l][0]) );
885  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[j][k][0], sign[l][1]) );
886  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[i][k][0], sign[l][2]) );
887 
888  SCIP_CALL( SCIPaddCons(scip, temp) );
889  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
890  }
891  }
892 
893  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "tri_%d_%d_%d", i, j, k);
894  SCIP_CALL( SCIPcreateConsLinear(scip, &temp, consname, 0, NULL, NULL, -SCIPinfinity(scip), 1.0,
896 
897  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[MAX(i,j)][MIN(i,j)][0], 1.0) );
898  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[j][k][1], 1.0) );
899  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[i][k][1], -1.0) );
900 
901  SCIP_CALL( SCIPaddCons(scip, temp) );
902  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
903 
904  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "tri_%d_%d_%d", i, j, k);
905  SCIP_CALL( SCIPcreateConsLinear(scip, &temp, consname, 0, NULL, NULL, -SCIPinfinity(scip), 1.0,
907 
908  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[MAX(i,j)][MIN(i,j)][0], 1.0) );
909  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[k][j][1], 1.0) );
910  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[k][i][1], -1.0) );
911 
912  SCIP_CALL( SCIPaddCons(scip, temp) );
913  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
914 
915  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "tri_%d_%d_%d", i, j, k);
916  SCIP_CALL( SCIPcreateConsLinear(scip, &temp, consname, 0, NULL, NULL, -SCIPinfinity(scip), 1.0,
918 
919  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[MAX(i,j)][MIN(i,j)][0], -1.0) );
920  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[j][k][1], 1.0) );
921  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[i][k][1], 1.0) );
922 
923  SCIP_CALL( SCIPaddCons(scip, temp) );
924  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
925 
926  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "tri_%d_%d_%d", i, j, k);
927  SCIP_CALL( SCIPcreateConsLinear(scip, &temp, consname, 0, NULL, NULL, -SCIPinfinity(scip), 1.0,
929 
930  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[MAX(i,j)][MIN(i,j)][0], -1.0) );
931  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[k][j][1], 1.0) );
932  SCIP_CALL( SCIPaddCoefLinear(scip, temp, probdata->edgevars[k][i][1], 1.0) );
933 
934  SCIP_CALL( SCIPaddCons(scip, temp) );
935  SCIP_CALL( SCIPreleaseCons(scip, &temp) );
936  }
937  }
938  }
939 
940  return SCIP_OKAY;
941 }
942 
943 /** Scip callback to transform the problem */
944 static
945 SCIP_DECL_PROBTRANS(probtransCyc)
946 {
947  int i;
948  int j;
949  int c;
950  int edgetype;
951  int nbins = sourcedata->nbins;
952  int ncluster = sourcedata->ncluster;
953 
954  assert(scip != NULL);
955  assert(sourcedata != NULL);
956  assert(targetdata != NULL);
957 
958  /* allocate memory */
959  SCIP_CALL( SCIPallocBlockMemory(scip, targetdata) );
960 
961  (*targetdata)->nbins = sourcedata->nbins;
962  (*targetdata)->ncluster = sourcedata->ncluster;
963  (*targetdata)->model_variant = sourcedata->model_variant;
964  (*targetdata)->scale = sourcedata->scale;
965 
966  /* allocate memory */
967  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->cmatrix), nbins) );
968  for( i = 0; i < nbins; ++i )
969  {
970  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->cmatrix[i]), nbins) ); /*lint !e866*/
971  }
972  /* copy the matrizes */
973  for ( i = 0; i < nbins; ++i )
974  {
975  for ( j = 0; j < nbins; ++j )
976  {
977  (*targetdata)->cmatrix[i][j] = sourcedata->cmatrix[i][j];
978  }
979  }
980 
981  /* copy the variables */
982  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->binvars), nbins) );
983  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &((*targetdata)->edgevars), nbins) );
984 
985  for( i = 0; i < nbins; ++i )
986  {
987  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &((*targetdata)->edgevars[i]), nbins) ); /*lint !e866*/
988  for( j = 0; j < nbins; ++j )
989  {
990  if( sourcedata->edgevars[i][j] == NULL || i == j)
991  continue;
992  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &((*targetdata)->edgevars[i][j]), 3) ); /*lint !e866*/
993  for( edgetype = 0; edgetype < 3; ++edgetype )
994  {
995  if( edgetype == 0 && i < j )
996  continue;
997  if( sourcedata->edgevars[i][j][edgetype] != NULL )
998  {
999  SCIP_CALL( SCIPtransformVar(scip, sourcedata->edgevars[i][j][edgetype],
1000  &((*targetdata)->edgevars[i][j][edgetype])) );
1001  }
1002  else
1003  ((*targetdata)->edgevars[i][j][edgetype]) = NULL;
1004  }
1005  }
1006  }
1007 
1008  for( i = 0; i < nbins; ++i )
1009  {
1010  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->binvars[i]), ncluster) ); /*lint !e866*/
1011 
1012  for( c = 0; c < ncluster; ++c )
1013  {
1014  if( sourcedata->binvars[i][c] != NULL )
1015  {
1016  SCIP_CALL( SCIPtransformVar(scip, sourcedata->binvars[i][c], &((*targetdata)->binvars[i][c])) );
1017  }
1018  else
1019  (*targetdata)->binvars[i][c] = NULL;
1020  }
1021  }
1022 
1023  SCIP_CALL( SCIPcopyDigraph(scip, &((*targetdata)->edgegraph), sourcedata->edgegraph) );
1024 
1025  return SCIP_OKAY;
1026 }
1027 
1028 /** delete-callback method of scip */
1029 static
1030 SCIP_DECL_PROBDELORIG(probdelorigCyc)
1031 {
1032  int c;
1033  int edgetype;
1034  int i;
1035  int j;
1036 
1037  assert(probdata != NULL);
1038  assert(*probdata != NULL);
1039 
1040  /* release all the variables */
1041 
1042  /* binvars */
1043  for ( c = 0; c < (*probdata)->nbins; ++c )
1044  {
1045  for ( i = 0; i < (*probdata)->ncluster; ++i )
1046  {
1047  if( (*probdata)->binvars[c][i] != NULL )
1048  {
1049  SCIP_CALL( SCIPreleaseVar(scip, &((*probdata)->binvars[c][i])) );
1050  }
1051  }
1052  SCIPfreeBlockMemoryArray( scip, &((*probdata)->binvars[c]), (*probdata)->ncluster);
1053  }
1054 
1055  /* cut-edge vars */
1056  for ( i = 0; i < (*probdata)->nbins; ++i )
1057  {
1058  for( j = 0; j < (*probdata)->nbins; ++j )
1059  {
1060  if( (*probdata)->edgevars[i][j] != NULL && j != i )
1061  {
1062  for ( edgetype = 0; edgetype < 3; ++edgetype )
1063  {
1064  if( edgetype == 0 && i < j )
1065  continue;
1066 
1067  if( (*probdata)->edgevars[i][j][edgetype] != NULL )
1068  {
1069  SCIP_CALL( SCIPreleaseVar( scip, &((*probdata)->edgevars[i][j][edgetype])) );
1070  }
1071  }
1072 
1073  SCIPfreeBlockMemoryArray(scip, &((*probdata)->edgevars[i][j]), 3);
1074  }
1075  }
1076 
1077  SCIPfreeBlockMemoryArray(scip, &((*probdata)->edgevars[i]), (*probdata)->nbins);
1078  }
1079 
1080  SCIPfreeBlockMemoryArray(scip, &((*probdata)->edgevars), (*probdata)->nbins);
1081  SCIPfreeBlockMemoryArray(scip, &((*probdata)->binvars), (*probdata)->nbins);
1082 
1083  SCIPdigraphFreeComponents((*probdata)->edgegraph);
1084  SCIPdigraphFree(&((*probdata)->edgegraph));
1085 
1086  for ( i = 0; i < (*probdata)->nbins; ++i )
1087  {
1088  SCIPfreeBlockMemoryArray(scip, &((*probdata)->cmatrix[i]), (*probdata)->nbins);
1089  }
1090  SCIPfreeBlockMemoryArray(scip, &(*probdata)->cmatrix, (*probdata)->nbins);
1091 
1092  SCIPfreeBlockMemory(scip, probdata);
1093 
1094  return SCIP_OKAY;
1095 }
1096 
1097 /** scip-callback to delete the transformed problem */
1098 static
1099 SCIP_DECL_PROBDELTRANS(probdeltransCyc)
1100 {
1101  int c;
1102  int edgetype;
1103  int i;
1104  int j;
1105 
1106  assert(probdata != NULL);
1107  assert(*probdata != NULL);
1108 
1109  /* release all the variables */
1110 
1111  /* binvars */
1112  for ( i = 0; i < (*probdata)->nbins; ++i )
1113  {
1114  for ( c = 0; c < (*probdata)->ncluster; ++c )
1115  {
1116  if( (*probdata)->binvars[i][c] != NULL )
1117  {
1118  SCIP_CALL( SCIPreleaseVar(scip, &((*probdata)->binvars[i][c])) );
1119  }
1120  }
1121  SCIPfreeBlockMemoryArray(scip, &((*probdata)->binvars[i]), (*probdata)->ncluster);
1122  }
1123 
1124  /* cut-edge vars */
1125  for ( i = 0; i < (*probdata)->nbins; ++i )
1126  {
1127  for( j = 0; j < (*probdata)->nbins; ++j )
1128  {
1129  if( (*probdata)->edgevars[i][j] != NULL && j != i )
1130  {
1131  for ( edgetype = 0; edgetype < 3; ++edgetype )
1132  {
1133  if( 0 == edgetype && j > i )
1134  continue;
1135 
1136  if( (*probdata)->edgevars[i][j][edgetype] != NULL )
1137  {
1138  SCIP_CALL( SCIPreleaseVar( scip, &((*probdata)->edgevars[i][j][edgetype])) );
1139  }
1140  }
1141 
1142  SCIPfreeBlockMemoryArray(scip, &((*probdata)->edgevars[i][j]), 3);
1143  }
1144  }
1145 
1146  SCIPfreeBlockMemoryArray(scip, &((*probdata)->edgevars[i]), (*probdata)->nbins);
1147  }
1148 
1149  SCIPfreeBlockMemoryArray(scip, &((*probdata)->edgevars), (*probdata)->nbins);
1150  SCIPfreeBlockMemoryArray(scip, &((*probdata)->binvars), (*probdata)->nbins);
1151 
1152  SCIPdigraphFreeComponents((*probdata)->edgegraph);
1153  SCIPdigraphFree(&((*probdata)->edgegraph));
1154 
1155  for ( i = 0; i < (*probdata)->nbins; ++i )
1156  {
1157  SCIPfreeBlockMemoryArray(scip, &((*probdata)->cmatrix[i]), (*probdata)->nbins);
1158  }
1159  SCIPfreeBlockMemoryArray(scip, &(*probdata)->cmatrix, (*probdata)->nbins);
1160 
1161  SCIPfreeBlockMemory(scip, probdata);
1162 
1163  return SCIP_OKAY;
1164 }
1165 
1166 /** callback method of scip for copying the probdata */
1167 static
1169 {
1170  SCIP_Bool success;
1171  SCIP_VAR* var;
1172  int nbins;
1173  int ncluster;
1174  int edgetype;
1175  int i;
1176  int j;
1177  int c;
1178 
1179  assert(scip != NULL);
1180  assert(sourcescip != NULL);
1181  assert(sourcedata != NULL);
1182  assert(targetdata != NULL);
1183 
1184  /* set up data */
1185  SCIP_CALL( SCIPallocBlockMemory(scip, targetdata) );
1186 
1187  nbins = sourcedata->nbins;
1188  ncluster = sourcedata->ncluster;
1189  success = FALSE;
1190 
1191  (*targetdata)->nbins = nbins;
1192  (*targetdata)->ncluster = ncluster;
1193  (*targetdata)->model_variant = sourcedata->model_variant;
1194  (*targetdata)->scale = sourcedata->scale;
1195 
1196  /* allocate memory */
1197  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->cmatrix), nbins) );
1198  for( i = 0; i < nbins; ++i )
1199  {
1200  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->cmatrix[i]), nbins) ); /*lint !e866*/
1201  }
1202  /* copy the matrizes */
1203  for ( i = 0; i < nbins; ++i )
1204  {
1205  for ( j = 0; j < nbins; ++j )
1206  {
1207  (*targetdata)->cmatrix[i][j] = sourcedata->cmatrix[i][j];
1208  }
1209  }
1210 
1211  /* copy the variables */
1212  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->binvars), nbins) );
1213  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &((*targetdata)->edgevars), nbins) );
1214 
1215  for( i = 0; i < nbins; ++i )
1216  {
1217  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &((*targetdata)->edgevars[i]), nbins) ); /*lint !e866*/
1218 
1219  for( j = 0; j < nbins; ++j )
1220  {
1221  if( (sourcedata)->edgevars[i][j] == NULL || j == i )
1222  continue;
1223 
1224  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->edgevars[i][j]), 3) ); /*lint !e866*/
1225 
1226  for( edgetype = 0; edgetype < 3; ++edgetype )
1227  {
1228  if( edgetype == 0 && j > i )
1229  continue;
1230 
1231  if( sourcedata->edgevars[i][j][edgetype] != NULL )
1232  {
1233  SCIP_CALL( SCIPgetTransformedVar(sourcescip, sourcedata->edgevars[i][j][edgetype], &var) );
1234 
1235  if( SCIPvarIsActive(var) )
1236  {
1237  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, var, &((*targetdata)->edgevars[i][j][edgetype]),
1238  varmap, consmap, global, &success) );
1239 
1240  assert(success);
1241  assert((*targetdata)->edgevars[i][j][edgetype] != NULL);
1242 
1243  SCIP_CALL( SCIPcaptureVar(scip, (*targetdata)->edgevars[i][j][edgetype]) );
1244  }
1245  else
1246  (*targetdata)->edgevars[i][j][edgetype] = NULL;
1247  }
1248  else
1249  (*targetdata)->edgevars[i][j][edgetype] = NULL;
1250  }
1251  }
1252  }
1253 
1254  for( i = 0; i < nbins; ++i )
1255  {
1256  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &((*targetdata)->binvars[i]), ncluster) ); /*lint !e866*/
1257 
1258  for( c = 0; c < ncluster; ++c )
1259  {
1260  if( sourcedata->binvars[i][c] != NULL )
1261  {
1262  SCIP_CALL( SCIPgetTransformedVar(sourcescip, sourcedata->binvars[i][c], &var) );
1263 
1264  if( SCIPvarIsActive(var) )
1265  {
1266  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, var, &((*targetdata)->binvars[i][c]),
1267  varmap, consmap, global, &success) );
1268 
1269  assert(success);
1270  assert((*targetdata)->binvars[i][c] != NULL);
1271 
1272  SCIP_CALL( SCIPcaptureVar(scip, (*targetdata)->binvars[i][c]) );
1273  }
1274  else
1275  (*targetdata)->binvars[i][c] = NULL;
1276  }
1277  else
1278  (*targetdata)->binvars[i][c] = NULL;
1279  }
1280  }
1281 
1282  SCIP_CALL( SCIPcopyDigraph(scip, &((*targetdata)->edgegraph), sourcedata->edgegraph) );
1283 
1284  assert(success);
1285 
1286  *result = SCIP_SUCCESS;
1287 
1288  return SCIP_OKAY;
1289 }
1290 
1291 /**
1292  * Create the probdata for an cyc-clustering problem
1293  */
1295  SCIP* scip, /**< SCIP data structure */
1296  const char* name, /**< problem name */
1297  int nbins, /**< number of bins */
1298  int ncluster, /**< number of cluster */
1299  SCIP_Real** cmatrix /**< The transition matrix */
1300  )
1301 {
1302  SCIP_PROBDATA* probdata = NULL;
1303  int i;
1304  int j;
1305  char model;
1306 
1307  assert(nbins > 0); /* at least one node */
1308  assert(ncluster <= nbins);
1309 
1310  SCIP_CALL( SCIPcreateProbBasic(scip, name) );
1311 
1312  /* Set up the problem */
1313  SCIP_CALL( SCIPallocBlockMemory(scip, &probdata) );
1314 
1315  SCIP_CALL( SCIPcreateDigraph(scip, &(probdata->edgegraph), nbins) );
1316 
1317  /* allocate memory for the matrizes and create them from the edge-arrays */
1318  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->cmatrix), nbins) );
1319  for ( i = 0; i < nbins; ++i )
1320  {
1321  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(probdata->cmatrix[i]), nbins) ); /*lint !e866*/
1322  for( j = 0; j < nbins; ++j )
1323  {
1324  probdata->cmatrix[i][j] = cmatrix[i][j];
1325  }
1326  }
1327 
1328  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Creating problem: %s \n", name);
1329 
1330  /* create variables */
1331  probdata->nbins=nbins;
1332  probdata->ncluster=ncluster;
1333 
1334  SCIP_CALL( SCIPgetCharParam(scip, "cycleclustering/model", &model) );
1335 
1336  /* create constraints depending on model selection */
1337  switch( model )
1338  {
1339  case 's':
1340  SCIP_CALL( createVariables(scip, probdata) );
1341  SCIP_CALL( createProbSimplified(scip, probdata) );
1342  break;
1343  case 't':
1344  SCIP_CALL( createVariables(scip, probdata) );
1345  SCIP_CALL( createProbSimplifiedTest(scip, probdata) );
1346  break;
1347  case 'e':
1348  SCIP_CALL( createVariables(scip, probdata) );
1349  SCIP_CALL( createProbOnlyEdge(scip, probdata) );
1350  break;
1351  case 'q':
1352  SCIP_CALL( createProbQP(scip, probdata) );
1353  break;
1354  default:
1355  SCIPABORT();
1356  break;
1357  }
1358 
1359  /** add callback methods to scip */
1360  SCIP_CALL( SCIPsetProbDelorig(scip, probdelorigCyc) );
1361  SCIP_CALL( SCIPsetProbCopy(scip, probcopyCyc) );
1362  SCIP_CALL( SCIPsetProbData(scip, probdata) );
1363  SCIP_CALL( SCIPsetProbTrans(scip, probtransCyc) );
1364  SCIP_CALL( SCIPsetProbDeltrans(scip, probdeltransCyc) );
1365 
1366  return SCIP_OKAY;
1367 }
1368 
1369 /** Getter methods for the various parts of the probdata */
1370 
1371 
1372 /** Returns the transition matrix*/
1374  SCIP* scip /**< SCIP data structure */
1375  )
1376 {
1377  SCIP_PROBDATA* probdata;
1378 
1379  assert(scip != NULL);
1380 
1381  probdata = SCIPgetProbData(scip);
1382 
1383  assert(probdata != NULL);
1384 
1385  return probdata->cmatrix;
1386 }
1387 
1388 /** Returns the number of states */
1390  SCIP* scip /**< SCIP data structure */
1391  )
1392 {
1393  SCIP_PROBDATA* probdata;
1394 
1395  assert(scip != NULL);
1396 
1397  probdata = SCIPgetProbData(scip);
1398 
1399  assert(probdata != NULL);
1400 
1401  return probdata->nbins;
1402 }
1403 
1404 /** Returns the number of clusters*/
1406  SCIP* scip /**< SCIP data structure */
1407  )
1408 {
1409  SCIP_PROBDATA* probdata;
1410 
1411  assert(scip!= NULL);
1412 
1413  probdata = SCIPgetProbData(scip);
1414 
1415  assert(probdata != NULL);
1416 
1417  return probdata->ncluster;
1418 }
1419 
1420 /** Returns the state-variable-matrix*/
1422  SCIP* scip /**< SCIP data structure */
1423  )
1424 {
1425  SCIP_PROBDATA* probdata;
1426 
1427  assert(scip!= NULL);
1428 
1429  probdata = SCIPgetProbData(scip);
1430 
1431  assert(probdata != NULL);
1432  assert(probdata->binvars != NULL);
1433 
1434  return probdata->binvars;
1435 }
1436 
1437 /** Returns the scaling parameter*/
1439  SCIP* scip /**< SCIP data structure */
1440  )
1441 {
1442  SCIP_PROBDATA* probdata;
1443 
1444  assert(scip!= NULL);
1445 
1446  probdata = SCIPgetProbData(scip);
1447 
1448  assert(probdata != NULL);
1449 
1450  return probdata->scale;
1451 }
1452 
1453 /** Returns the edge variables */
1455  SCIP* scip /**< SCIP data structure */
1456  )
1457 {
1458  SCIP_PROBDATA* probdata;
1459 
1460  assert(scip!= NULL);
1461 
1462  probdata = SCIPgetProbData(scip);
1463 
1464  assert(probdata != NULL);
1465  assert(probdata->edgevars != NULL);
1466 
1467  return probdata->edgevars;
1468 }
1469 
1470 /** return one specific edge variable */
1472  SCIP_VAR**** edgevars, /**< edgevar data structure*/
1473  int state1, /**< first state */
1474  int state2, /**< second state */
1475  int direction /**< direction, 0 = incluster, 1 = forward */
1476  )
1477 {
1478  assert(edgevars != NULL);
1479  assert(edgevars[state1] != NULL);
1480  assert(edgevars[state1][state2] != NULL);
1481  assert(edgevars[state1][state2][direction] != NULL);
1482 
1483  return edgevars[state1][state2][direction];
1484 }
1485 
1486 /** check for an array of states, if all possible edge-combinations exist */
1488  SCIP_VAR**** edgevars, /**< edgevar data structure */
1489  int* states, /**< state array */
1490  int nstates /**< size of state array */
1491  )
1492 {
1493  int i;
1494  int j;
1495 
1496  assert(edgevars != NULL);
1497  assert(states != NULL);
1498 
1499  for( i = 0; i < nstates; ++i )
1500  {
1501  assert(edgevars[states[i]] != NULL);
1502 
1503  for( j = 0; j < nstates; ++j )
1504  {
1505  if( j != i )
1506  {
1507  assert(edgevars[states[j]] != NULL);
1508 
1509  if( edgevars[states[i]][states[j]] == NULL )
1510  return FALSE;
1511  }
1512  }
1513  }
1514 
1515  return TRUE;
1516 }
1517 
1518 /** Returns the edge-graph */
1520  SCIP* scip /**< SCIP data structure */
1521  )
1522 {
1523  SCIP_PROBDATA* probdata;
1524 
1525  assert(scip!= NULL);
1526 
1527  probdata = SCIPgetProbData(scip);
1528 
1529  assert(probdata != NULL);
1530  assert(probdata->edgegraph != NULL);
1531 
1532  return probdata->edgegraph;
1533 }
1534 
1535 
1536 /** print the model-values like coherence in the clusters and transition-probabilities between clusters that are not
1537  * evident from the scip-solution
1538  */
1540  SCIP* scip, /**< SCIP data structure */
1541  SCIP_SOL* sol /**< The solution containg the values */
1542  )
1543 {
1544  SCIP_PROBDATA* probdata;
1545  SCIP_Real value;
1546  SCIP_Real objvalue = 0;
1547  SCIP_Real flow = 0;
1548  SCIP_Real coherence = 0;
1549  int c1;
1550  int c2;
1551  int c3;
1552  int i;
1553  int j;
1554 
1555  assert(scip!= NULL);
1556 
1557  probdata = SCIPgetProbData(scip);
1558 
1559  assert(probdata != NULL);
1560 
1561  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "\nDisplaying aggregated solution data: \n");
1562 
1563  for( c1 = 0; c1 < probdata->ncluster; ++c1 )
1564  {
1565  value = 0;
1566 
1567  for( i = 0; i < probdata->nbins; ++i )
1568  {
1569  for( j = 0; j < probdata->nbins; ++j )
1570  {
1571  if( j == i )
1572  continue;
1573 
1574  value+= probdata->cmatrix[i][j] * SCIPgetSolVal(scip, sol, probdata->binvars[i][c1])
1575  * SCIPgetSolVal(scip, sol, probdata->binvars[j][c1]);
1576  }
1577  }
1578 
1579  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " Coherence in cluster %d : %f \n", c1 + 1, value);
1580  coherence += value;
1581  objvalue += probdata->scale * value;
1582  }
1583 
1584  for( c1 = 0; c1 < probdata->ncluster; ++c1 )
1585  {
1586  for( c2 = 0; c2 < probdata->ncluster; ++c2 )
1587  {
1588  value = 0;
1589 
1590  for( i = 0; i < probdata->nbins; ++i )
1591  {
1592  for( j = 0; j < probdata->nbins; ++j )
1593  {
1594  value+= probdata->cmatrix[i][j] * SCIPgetSolVal(scip, sol, probdata->binvars[i][c1]) *
1595  SCIPgetSolVal(scip, sol, probdata->binvars[j][c2]);
1596  }
1597  }
1598  }
1599 
1600  c3 = (c1 + 1) % probdata->ncluster;
1601  value = 0;
1602 
1603  for( i = 0; i < probdata->nbins; ++i )
1604  {
1605  for( j = 0; j < probdata->nbins; ++j )
1606  {
1607  value+= (probdata->cmatrix[i][j] - probdata->cmatrix[j][i])
1608  * SCIPgetSolVal(scip, sol, probdata->binvars[i][c1]) * SCIPgetSolVal(scip, sol, probdata->binvars[j][c3]);
1609  }
1610  }
1611 
1613  " Net flow from %d to %d : %f \n", c1, phi(c1, probdata->ncluster), value);
1614 
1615  flow += value;
1616  objvalue += value;
1617  }
1618 
1619  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " Total coherence : %f \n", coherence);
1620  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " Total net flow : %f \n", flow);
1621  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, " Total objective value : %f \n", objvalue);
1622 
1623  return SCIP_OKAY;
1624 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:101
SCIP_RETCODE SCIPaddCoefLogicor(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
SCIP_RETCODE SCIPgetCharParam(SCIP *scip, const char *name, char *value)
Definition: scip_param.c:317
SCIP_RETCODE SCIPcreateProbCyc(SCIP *scip, const char *name, int nbins, int ncluster, SCIP_Real **cmatrix)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:84
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_setppc.c:9371
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_RETCODE SCIPaddOrigObjoffset(SCIP *scip, SCIP_Real addval)
Definition: scip_prob.c:1288
void SCIPdigraphFreeComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8419
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17910
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 SCIPsetProbCopy(SCIP *scip, SCIP_DECL_PROBCOPY((*probcopy)))
Definition: scip_prob.c:296
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:88
SCIP_RETCODE assignVars(SCIP *scip, SCIP_SOL *sol, SCIP_Real **clustering, int nbins, int ncluster)
Definition: probdata_cyc.c:79
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1436
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1245
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
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_RETCODE SCIPsetProbData(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: scip_prob.c:1012
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
Definition: scip_var.c:185
static SCIP_DECL_PROBTRANS(probtransCyc)
Definition: probdata_cyc.c:945
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:99
SCIP_Real SCIPcycGetScale(SCIP *scip)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
Definition: scip_prob.c:170
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
static SCIP_DECL_PROBCOPY(probcopyCyc)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17920
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip_prob.c:1240
static SCIP_RETCODE createProbOnlyEdge(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_cyc.c:811
int phi(int k, int ncluster)
Definition: probdata_cyc.c:172
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2768
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
static SCIP_RETCODE createProbSimplifiedTest(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_cyc.c:269
SCIP_RETCODE SCIPcreateConsQuadraticNonlinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadterms, SCIP_VAR **quadvars1, SCIP_VAR **quadvars2, SCIP_Real *quadcoefs, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable)
SCIP_RETCODE SCIPcreateConsSetpart(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_setppc.c:9200
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_Bool edgesExist(SCIP_VAR ****edgevars, int *states, int nstates)
SCIP_RETCODE SCIPcreateConsBasicLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars)
#define SCIP_CALL(x)
Definition: def.h:384
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7564
int SCIPcycGetNBins(SCIP *scip)
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
Definition: scip_var.c:4510
internal methods for problem variables
int phiinv(int k, int ncluster)
Definition: probdata_cyc.c:184
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1212
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE SCIPsetProbTrans(SCIP *scip, SCIP_DECL_PROBTRANS((*probtrans)))
Definition: scip_prob.c:211
static SCIP_RETCODE createProbSimplified(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_cyc.c:411
constraint handler for nonlinear constraints specified by algebraic expressions
#define MAX(x, y)
Definition: tclique_def.h:83
problem data for cycle clustering problem
Constraint handler for linear constraints in their most general form, .
static SCIP_DECL_PROBDELTRANS(probdeltransCyc)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
static SCIP_RETCODE createVariables(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_cyc.c:200
struct SCIP_ProbData SCIP_PROBDATA
Definition: type_prob.h:44
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:702
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1666
int SCIPcycGetNCluster(SCIP *scip)
SCIP_PROBDATA * SCIPgetProbData(SCIP *scip)
Definition: scip_prob.c:962
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17370
SCIP_DIGRAPH * SCIPcycGetEdgeGraph(SCIP *scip)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1211
#define SCIP_Real
Definition: def.h:177
static SCIP_RETCODE createProbQP(SCIP *scip, SCIP_PROBDATA *probdata)
Definition: probdata_cyc.c:627
SCIP_RETCODE SCIPtransformVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1346
#define SCIP_Longint
Definition: def.h:162
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPcycPrintSolutionValues(SCIP *scip, SCIP_SOL *sol)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPsetProbDeltrans(SCIP *scip, SCIP_DECL_PROBDELTRANS((*probdeltrans)))
Definition: scip_prob.c:232
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
Definition: var.c:17393
SCIP_RETCODE SCIPsetProbDelorig(SCIP *scip, SCIP_DECL_PROBDELORIG((*probdelorig)))
Definition: scip_prob.c:190
SCIP_Bool isPartition(SCIP *scip, SCIP_Real **solclustering, int nbins, int ncluster)
Definition: probdata_cyc.c:48
SCIPallocBlockMemory(scip, subsol))
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
Definition: misc.c:7470
SCIP_VAR * SCIPvarGetTransVar(SCIP_VAR *var)
Definition: var.c:17610
#define SCIPABORT()
Definition: def.h:356
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
SCIP_RETCODE SCIPcopyDigraph(SCIP *scip, SCIP_DIGRAPH **targetdigraph, SCIP_DIGRAPH *sourcedigraph)
SCIP_VAR *** SCIPcycGetBinvars(SCIP *scip)
SCIP_Real ** SCIPcycGetCmatrix(SCIP *scip)
static SCIP_DECL_PROBDELORIG(probdelorigCyc)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17580