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