Scippy

SCIP

Solving Constraint Integer Programs

sepa_partition.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file sepa_partition.c
26 * @brief partition-separator. Searches for two partitions of size 2 and 3 (extension of triangle-inequalities).
27 * @author Leon Eifler
28 */
29
30/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31#include <assert.h>
32#include <string.h>
33
34#include "sepa_partition.h"
35
36#include "probdata_cyc.h"
37#include "scip/cons_linear.h"
38#include "scip/cutsel_hybrid.h"
39
40#define SEPA_NAME "partition"
41#define SEPA_DESC "separator to separate partition-inequalities in cycle-clustering application"
42#define SEPA_PRIORITY 1500
43#define SEPA_FREQ 5
44#define SEPA_MAXBOUNDDIST 0.0
45#define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
46#define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
47#define MAXCUTS 2000 /**< maximal number of cuts that can be added to cut pool */
48#define MAXCUTSCREATED 10000 /**< maximal number of cuts to select from */
49#define MAXROUNDS 20 /**< maximal number of separation rounds per node */
50#define MAXTRIANGLEDISTANCE -0.2 /**< maximal negative violation of triangle-inequality to construct cut from */
51
52
53/** Given two partitions S, T creates the corresponding cut and adds it do SCIP */
54static
55SCIP_RETCODE createPartitionCut(
56 SCIP* scip, /**< SCIP data structure */
57 SCIP_SEPA* sepa, /**< separator */
58 SCIP_ROW*** cuts, /**< array to store generated cut */
59 int* cutsize, /**< size of the cut array */
60 int* ncutscreated, /**< number of created cuts */
61 int* firstpart, /**< the first partition */
62 int* secondpart, /**< the second partition */
63 int nfirst, /**< number of states in first partition */
64 int nsecond, /**< number of states in second partition */
65 SCIP_Real** violations, /**< array to stor the violation of each cut */
66 SCIP_Real violation /**< violation of the cut that should be created */
67 )
68{
69 SCIP_VAR**** edgevars;
70 char cutname[SCIP_MAXSTRLEN];
71 int i;
72 int j;
73 int inda;
74 int indb;
75
76 edgevars = SCIPcycGetEdgevars(scip);
77
78 assert(NULL != edgevars);
79
80 if( *cutsize - 1 <= *ncutscreated )
81 {
82 *cutsize = *cutsize * 2;
83 SCIP_CALL( SCIPreallocBufferArray(scip, cuts, (int) *cutsize) );
84 SCIP_CALL( SCIPreallocBufferArray(scip, violations, (int) *cutsize) );
85 }
86
87 (*violations)[*ncutscreated] = violation;
88
89 /* create cut */
90 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "PartitionCut_%d_%d", nfirst, nsecond);
91 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &((*cuts)[*ncutscreated]), sepa, cutname, -SCIPinfinity(scip),
92 (SCIP_Real) MIN(nfirst, nsecond), FALSE, FALSE, TRUE) );
93
94 SCIP_CALL( SCIPcacheRowExtensions(scip, (*cuts)[*ncutscreated]) );
95
96 for( i = 0; i < nfirst; ++i )
97 {
98 for( j = 0; j < i; ++j )
99 {
100 inda = MAX(firstpart[i], firstpart[j]);
101 indb = MIN(firstpart[i], firstpart[j]);
102 SCIP_CALL( SCIPaddVarToRow(scip, (*cuts)[*ncutscreated], getEdgevar(edgevars, inda, indb, 0), -1.0) );
103 }
104 }
105
106 for( i = 0; i < nsecond; ++i )
107 {
108 for( j = 0; j < i; ++j )
109 {
110 inda = MAX(secondpart[i], secondpart[j]);
111 indb = MIN(secondpart[i], secondpart[j]);
112 SCIP_CALL( SCIPaddVarToRow(scip, (*cuts)[*ncutscreated], getEdgevar(edgevars, inda, indb, 0), -1.0) );
113 }
114 }
115
116 for( i = 0; i < nfirst; ++i )
117 {
118 for( j = 0; j < nsecond; ++j )
119 {
120 SCIP_CALL( SCIPaddVarToRow(scip, (*cuts)[*ncutscreated],
121 getEdgevar(edgevars, firstpart[i], secondpart[j], 1), 1.0) );
122 }
123 }
124
125 SCIP_CALL( SCIPflushRowExtensions(scip, (*cuts)[*ncutscreated]) );
126
127 SCIPdebug( SCIP_CALL( SCIPprintRow(scip, (*cuts)[*ncutscreated], NULL) ) );
128 (*ncutscreated)++;
129
130 return SCIP_OKAY;
131}
132
133/** copy method for separator plugins (called when SCIP copies plugins) */
134static
135SCIP_DECL_SEPACOPY(sepaCopyPartition)
136{ /*lint --e{715}*/
137 assert(scip != NULL);
138 assert(sepa != NULL);
139 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
140
141 /* call inclusion method of constraint handler */
142 SCIP_CALL( SCIPincludeSepaPartition(scip) );
143
144 return SCIP_OKAY;
145}
146
147/** LP solution separation method of separator */
148static
149SCIP_DECL_SEPAEXECLP(sepaExeclpPartition)
150{ /*lint --e{715}*/
151 SCIP_VAR**** edgevars;
152 SCIP_Real* fractionality;
153 SCIP_DIGRAPH* edgegraph;
154 int* idx;
155 int states[5];
156 SCIP_Real violation;
157 SCIP_Real violationchg;
158 SCIP_Real bestvalue;
159 SCIP_Real lpvalforward;
160 SCIP_Real lpvalincluster;
161 SCIP_Real goodscorefac;
162 SCIP_Real badscorefac;
163 SCIP_Real goodmaxparall;
164 SCIP_Real maxparall;
165 SCIP_Real dircutoffdist;
166 SCIP_Real efficacyweight;
167 SCIP_Real objparalweight;
168 SCIP_Real intsuppweight;
169 SCIP_Real* violations;
170 SCIP_ROW** cuts;
171 int cutsize;
172 int ncutscreated;
173 int ncutsapplied;
174 int* firstpart;
175 int* secondpart;
176 int** successors;
177 int* nsuccessors;
178 int nfirst;
179 int nsecond;
180 int nstates;
181 int rounds;
182 int i;
183 int j;
184 int k;
185 int l;
186 SCIP_Bool usecutselection;
187
188
189 /* get necessary probdata */
190 edgevars = SCIPcycGetEdgevars(scip);
191 edgegraph = SCIPcycGetEdgeGraph(scip);
192 nstates = SCIPcycGetNBins(scip);
193 rounds = SCIPsepaGetNCallsAtNode(sepa);
194 cutsize = MAXCUTS;
195 ncutscreated = 0;
196
197 SCIP_CALL( SCIPgetBoolParam(scip, "cycleclustering/usecutselection", &usecutselection) );
198
199 assert(nstates > 0);
200 assert(NULL != edgevars);
201 assert(NULL != edgegraph);
202
203 *result = SCIP_DIDNOTFIND;
204
205 if( SCIPcycGetNCluster(scip) == 3 || rounds >= MAXROUNDS )
206 {
207 *result = SCIP_DIDNOTRUN;
208 return SCIP_OKAY;
209 }
210
211 /* allocate memory */
212 SCIP_CALL( SCIPallocBufferArray(scip, &successors, 5) );
213 SCIP_CALL( SCIPallocBufferArray(scip, &nsuccessors, 5) );
214 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &fractionality, nstates) );
215 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &idx, nstates) );
216 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &firstpart, nstates) );
217 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &secondpart, nstates) );
218 SCIP_CALL( SCIPallocBufferArray(scip, &cuts, cutsize) );
219 SCIP_CALL( SCIPallocBufferArray(scip, &violations, cutsize) );
220
221 /* sort edges by decreasing fractionality of lp-solution */
222 for( i = 0; i < nstates; ++i )
223 {
224 idx[i] = i;
225 fractionality[i] = 0;
226 successors[0] = SCIPdigraphGetSuccessors(edgegraph, i);
227 nsuccessors[0] = SCIPdigraphGetNSuccessors(edgegraph, i);
228
229 for( j = 0; j < nsuccessors[0]; ++j )
230 {
231 states[0] = i;
232 states[1] = successors[0][j];
233
234 lpvalforward = SCIPvarGetLPSol(getEdgevar(edgevars, states[0], states[1], 1));
235 lpvalincluster = SCIPvarGetLPSol(getEdgevar(edgevars, MAX(states[0],states[1]), MIN(states[0],states[1]), 0));
236 fractionality[states[0]] += MIN(lpvalforward, 1 - lpvalforward) + MIN(1 - lpvalincluster, lpvalincluster);
237 }
238 }
239
240 /* sort by fractionality of edgevars */
241 SCIPsortDownRealInt(fractionality, idx, nstates);
242
243 /* we try to construct partition inequalities from triangle-inequalities that are almost satisfied at equality */
244 for( i = 0; i < nstates && ncutscreated < MAXCUTSCREATED; ++i )
245 {
246 states[0] = idx[i];
247 successors[0] = SCIPdigraphGetSuccessors(edgegraph, states[0]);
248 nsuccessors[0] = SCIPdigraphGetNSuccessors(edgegraph, states[0]);
249
250 for( j = 0; j < nsuccessors[0] && ncutscreated < MAXCUTSCREATED; ++j )
251 {
252 states[1] = successors[0][j];
253 successors[1] = SCIPdigraphGetSuccessors(edgegraph, states[1]);
254 nsuccessors[1] = SCIPdigraphGetNSuccessors(edgegraph, states[1]);
255
256 for( k = 0; k < nsuccessors[1] && ncutscreated < MAXCUTSCREATED; ++k )
257 {
258 states[2] = successors[1][k];
259 successors[2] = SCIPdigraphGetSuccessors(edgegraph, states[2]);
260 nsuccessors[2] = SCIPdigraphGetNSuccessors(edgegraph, states[2]);
261
262 /* check if all edges in triangle exist */
263 if( !edgesExist(edgevars, states, 3) )
264 continue;
265
266 if( states[1] > states[2] )
267 {
268 /* first case, construct partition with 2 predecessors and 3 successors */
269 nfirst = 1;
270 firstpart[0] = states[0];
271 firstpart[1] = -1;
272 nsecond = 2;
273 secondpart[0] = states[1];
274 secondpart[1] = states[2];
275 secondpart[2] = -1;
276
277 /* get violation of trianlge inequality for these three states */
278 violation = SCIPvarGetLPSol(getEdgevar(edgevars, states[0], states[1], 1));
279 violation += SCIPvarGetLPSol(getEdgevar(edgevars, states[0], states[2], 1));
280 violation -= SCIPvarGetLPSol(getEdgevar(edgevars, states[1], states[2], 0));
281 violation -= 1;
282
283 if( SCIPisGE(scip, violation, MAXTRIANGLEDISTANCE) )
284 {
285 /* add a state to second partition*/
286 bestvalue = -SCIPinfinity(scip);
287 secondpart[2] = -1;
288 for( l = 0; l < nsuccessors[2]; ++l )
289 {
290 states[3] = successors[2][l];
291 if( !edgesExist(edgevars, states, 4) )
292 continue;
293
294 violationchg = SCIPvarGetLPSol(getEdgevar(edgevars, states[0], states[3], 1));
295 violationchg -= SCIPvarGetLPSol(getEdgevar(edgevars,
296 MAX(states[1],states[3]), MIN(states[1],states[3]), 0));
297 violationchg -= SCIPvarGetLPSol(getEdgevar(edgevars,
298 MAX(states[2],states[3]), MIN(states[2],states[3]), 0));
299
300 if( violationchg > bestvalue )
301 {
302 bestvalue = violationchg;
303 secondpart[2] = states[3];
304 }
305 }
306
307 states[3] = secondpart[2];
308
309 /* if we did not find a state that we can add we can stop */
310 if( states[3] == -1 )
311 continue;
312
313 successors[3] = SCIPdigraphGetSuccessors(edgegraph, states[3]);
314 nsuccessors[3] = SCIPdigraphGetNSuccessors(edgegraph, states[3]);
315
316 nsecond++;
317 violation += bestvalue;
318
319 /* add one more state to first partition */
320 bestvalue = -SCIPinfinity(scip);
321 for( l = 0; l < nsuccessors[3]; ++l )
322 {
323 states[4] = successors[3][l];
324
325 if( !edgesExist(edgevars, states, 5) )
326 continue;
327
328 /* compute what has changed from the violation of the 1-4 inequality */
329 violationchg = -SCIPvarGetLPSol(getEdgevar(edgevars,
330 MAX(states[0], states[4]), MIN(states[0],states[4]), 0)) - 1.0;
331 violationchg += SCIPvarGetLPSol(getEdgevar(edgevars, states[4], secondpart[0], 1));
332 violationchg += SCIPvarGetLPSol(getEdgevar(edgevars, states[4], secondpart[1], 1));
333 violationchg += SCIPvarGetLPSol(getEdgevar(edgevars, states[4], secondpart[2], 1));
334
335 /* create cut if inequality is violated by lp-solution */
336 if( SCIPisPositive(scip, violation + violationchg) )
337 {
338 firstpart[1] = states[4];
339 nfirst = 2;
340 SCIP_CALL( createPartitionCut(scip, sepa, &cuts, &cutsize, &ncutscreated, firstpart, secondpart,
341 nfirst, nsecond, &violations, violation + violationchg) );
342
343 break;
344 }
345 }
346 }
347
348 /* now try to find partition with 3 in first and 2 in second set */
349 nfirst = 2;
350 firstpart[0] = states[1];
351 firstpart[1] = states[2];
352 firstpart[2] = -1;
353 nsecond = 1;
354 secondpart[0] = states[0];
355 secondpart[1] = -1;
356
357 violation = SCIPvarGetLPSol(getEdgevar(edgevars, states[1], states[0], 1));
358 violation += SCIPvarGetLPSol(getEdgevar(edgevars, states[2], states[0], 1));
359 violation -= SCIPvarGetLPSol(getEdgevar(edgevars, states[1], states[2], 0));
360 violation -= 1;
361
362 if( SCIPisGE(scip, violation, MAXTRIANGLEDISTANCE) )
363 {
364 /* add a state to second partition*/
365 bestvalue = -SCIPinfinity(scip);
366 firstpart[2] = -1;
367 for( l = 0; l < nsuccessors[2]; ++l )
368 {
369 states[3] = successors[2][l];
370 if( !edgesExist(edgevars, states, 4) )
371 continue;
372
373 violationchg = SCIPvarGetLPSol(getEdgevar(edgevars, states[3], states[0], 1));
374 violationchg -= SCIPvarGetLPSol(getEdgevar(edgevars,
375 MAX(states[1],states[3]), MIN(states[1],states[3]), 0));
376 violationchg -= SCIPvarGetLPSol(getEdgevar(edgevars,
377 MAX(states[2],states[3]), MIN(states[2],states[3]), 0));
378
379 if( violationchg > bestvalue )
380 {
381 bestvalue = violationchg;
382 firstpart[2] = states[3];
383 }
384 }
385
386 states[3] = firstpart[2];
387
388 if( states[3] == -1 )
389 continue;
390 nfirst++;
391
392 successors[3] = SCIPdigraphGetSuccessors(edgegraph, states[3]);
393 nsuccessors[3] = SCIPdigraphGetNSuccessors(edgegraph, states[3]);
394
395 violation += bestvalue;
396
397 /* add one more state to second partition */
398 bestvalue = -SCIPinfinity(scip);
399 for( l = 0; l < nsuccessors[3]; ++l )
400 {
401 states[4] = successors[3][l];
402
403 if( !edgesExist(edgevars, states, 5) )
404 continue;
405
406 violationchg = -SCIPvarGetLPSol(getEdgevar(edgevars,
407 MAX(states[0], states[4]), MIN(states[0],states[4]), 0)) - 1.0;
408 violationchg += SCIPvarGetLPSol(getEdgevar(edgevars, firstpart[0], states[4], 1));
409 violationchg += SCIPvarGetLPSol(getEdgevar(edgevars, firstpart[1], states[4], 1));
410 violationchg += SCIPvarGetLPSol(getEdgevar(edgevars, firstpart[2], states[4], 1));
411 violationchg += SCIPvarGetLPSol(edgevars[firstpart[2]][states[4]][1]);
412
413 if( SCIPisPositive(scip, violation + violationchg) )
414 {
415 secondpart[1] = states[4];
416 nsecond = 2;
417 SCIP_CALL( createPartitionCut(scip, sepa, &cuts, &cutsize, &ncutscreated, firstpart,
418 secondpart, nfirst, nsecond, &violations, violation + violationchg) );
419
420 break;
421 }
422 }
423 }
424 }
425 }
426 }
427 }
428
429 /* apply the cuts with the highest violation or use cut-selection */
430 if( usecutselection )
431 {
432 SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/goodscorefac", &goodscorefac) );
433 SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/badscorefac", &badscorefac) );
434 SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/goodmaxparall", &goodmaxparall) );
435 SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/maxparall", &maxparall) );
436 SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/dircutoffdist", &dircutoffdist) );
437 SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/efficacyweight", &efficacyweight) );
438 SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/objparalweight", &objparalweight) );
439 SCIP_CALL( SCIPgetRealParam(scip, "cycleclustering/intsuppweight", &intsuppweight) );
440
441 SCIP_CALL( SCIPselectCutsHybrid(scip, cuts, NULL, NULL, goodscorefac, badscorefac,
442 goodmaxparall, maxparall, dircutoffdist, efficacyweight, objparalweight, intsuppweight,
443 ncutscreated, 0, MAXCUTS, &ncutsapplied) );
444 }
445 else
446 {
447 SCIPsortDownRealPtr(violations, ((void **) cuts), ncutscreated);
448 ncutsapplied = MIN(ncutscreated, MAXCUTS);
449 }
450
451 for( j = 0; j < ncutsapplied; ++j )
452 {
453 SCIP_CALL( SCIPaddPoolCut(scip, cuts[j]) );
454 *result = SCIP_SEPARATED;
455 }
456
457 SCIPfreeBlockMemoryArray(scip, &fractionality, nstates);
458 SCIPfreeBlockMemoryArray(scip, &idx, nstates);
459 SCIPfreeBlockMemoryArray(scip, &firstpart, nstates);
460 SCIPfreeBlockMemoryArray(scip, &secondpart, nstates);
461
462 for( i = 0; i < ncutscreated; ++i )
463 {
464 SCIP_CALL( SCIPreleaseRow(scip, &(cuts[i])) );
465 }
466
467 SCIPfreeBufferArray(scip, &cuts);
468 SCIPfreeBufferArray(scip, &violations);
469 SCIPfreeBufferArray(scip, &nsuccessors);
470 SCIPfreeBufferArray(scip, &successors);
471
472 return SCIP_OKAY;
473}
474
475/** creates the Partition separator and includes it in SCIP */
476SCIP_RETCODE SCIPincludeSepaPartition(
477 SCIP* scip /**< SCIP data structure */
478 )
479{
480 SCIP_SEPA* sepa;
481
482 /* include separator */
483 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
484 SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpPartition, NULL, NULL) );
485
486 assert(sepa != NULL);
487
488 /* set non fundamental callbacks via setter functions */
489 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyPartition) );
490
491 return SCIP_OKAY;
492}
cons_linear.h
Constraint handler for linear constraints in their most general form, .
cutsel_hybrid.h
hybrid cut selector
NULL
#define NULL
Definition: def.h:267
SCIP_MAXSTRLEN
#define SCIP_MAXSTRLEN
Definition: def.h:288
SCIP_Bool
#define SCIP_Bool
Definition: def.h:91
MIN
#define MIN(x, y)
Definition: def.h:243
SCIP_Real
#define SCIP_Real
Definition: def.h:173
TRUE
#define TRUE
Definition: def.h:93
FALSE
#define FALSE
Definition: def.h:94
MAX
#define MAX(x, y)
Definition: def.h:239
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:374
SCIPselectCutsHybrid
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)
Definition: cutsel_hybrid.c:438
SCIPdigraphGetNSuccessors
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7804
SCIPdigraphGetSuccessors
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7819
SCIPgetBoolParam
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
SCIPgetRealParam
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:307
SCIPaddPoolCut
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:361
SCIPfreeBlockMemoryArray
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
SCIPreallocBufferArray
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIPallocBlockMemoryArray
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
SCIPcacheRowExtensions
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
SCIPflushRowExtensions
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
SCIPaddVarToRow
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
SCIPprintRow
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2212
SCIPreleaseRow
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1562
SCIPcreateEmptyRowSepa
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:1453
SCIPincludeSepaBasic
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:109
SCIPsepaGetName
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:743
SCIPsepaGetNCallsAtNode
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:880
SCIPsetSepaCopy
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:151
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip_numerics.c:510
SCIPisGE
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:497
SCIPisPositive
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:570
SCIPvarGetLPSol
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
Definition: var.c:18452
SCIPsortDownRealPtr
void SCIPsortDownRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
SCIPsortDownRealInt
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIPsnprintf
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
edgesExist
SCIP_Bool edgesExist(SCIP_VAR ****edgevars, int *states, int nstates)
Definition: probdata_cyc.c:1496
getEdgevar
SCIP_VAR * getEdgevar(SCIP_VAR ****edgevars, int state1, int state2, int direction)
Definition: probdata_cyc.c:1480
SCIPcycGetEdgevars
SCIP_VAR **** SCIPcycGetEdgevars(SCIP *scip)
Definition: probdata_cyc.c:1463
SCIPcycGetNBins
int SCIPcycGetNBins(SCIP *scip)
Definition: probdata_cyc.c:1398
SCIPcycGetNCluster
int SCIPcycGetNCluster(SCIP *scip)
Definition: probdata_cyc.c:1414
SCIPcycGetEdgeGraph
SCIP_DIGRAPH * SCIPcycGetEdgeGraph(SCIP *scip)
Definition: probdata_cyc.c:1528
probdata_cyc.h
problem data for cycle clustering problem
SCIPdebug
#define SCIPdebug(x)
Definition: pub_message.h:93
SEPA_PRIORITY
#define SEPA_PRIORITY
Definition: sepa_partition.c:42
SEPA_DELAY
#define SEPA_DELAY
Definition: sepa_partition.c:46
createPartitionCut
static SCIP_RETCODE createPartitionCut(SCIP *scip, SCIP_SEPA *sepa, SCIP_ROW ***cuts, int *cutsize, int *ncutscreated, int *firstpart, int *secondpart, int nfirst, int nsecond, SCIP_Real **violations, SCIP_Real violation)
Definition: sepa_partition.c:55
SEPA_DESC
#define SEPA_DESC
Definition: sepa_partition.c:41
MAXCUTSCREATED
#define MAXCUTSCREATED
Definition: sepa_partition.c:48
SEPA_USESSUBSCIP
#define SEPA_USESSUBSCIP
Definition: sepa_partition.c:45
SCIP_DECL_SEPAEXECLP
static SCIP_DECL_SEPAEXECLP(sepaExeclpPartition)
Definition: sepa_partition.c:149
MAXTRIANGLEDISTANCE
#define MAXTRIANGLEDISTANCE
Definition: sepa_partition.c:50
MAXROUNDS
#define MAXROUNDS
Definition: sepa_partition.c:49
MAXCUTS
#define MAXCUTS
Definition: sepa_partition.c:47
SEPA_MAXBOUNDDIST
#define SEPA_MAXBOUNDDIST
Definition: sepa_partition.c:44
SEPA_FREQ
#define SEPA_FREQ
Definition: sepa_partition.c:43
SEPA_NAME
#define SEPA_NAME
Definition: sepa_partition.c:40
SCIP_DECL_SEPACOPY
static SCIP_DECL_SEPACOPY(sepaCopyPartition)
Definition: sepa_partition.c:135
SCIPincludeSepaPartition
SCIP_RETCODE SCIPincludeSepaPartition(SCIP *scip)
Definition: sepa_partition.c:476
sepa_partition.h
simple partition-separator
SCIP_Digraph
Definition: struct_misc.h:220
SCIP_Row
Definition: struct_lp.h:202
SCIP_Sepa
Definition: struct_sepa.h:47
SCIP_Var
Definition: struct_var.h:208
SCIP_DIDNOTRUN
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
SCIP_DIDNOTFIND
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
SCIP_SEPARATED
@ SCIP_SEPARATED
Definition: type_result.h:49
SCIP_OKAY
@ SCIP_OKAY
Definition: type_retcode.h:42
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63