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-2025 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, INCLUSTER), -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, INCLUSTER), -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], CONSECUTIVE_CLUSTER), 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], CONSECUTIVE_CLUSTER));
    235 lpvalincluster = SCIPvarGetLPSol(getEdgevar(edgevars, MAX(states[0],states[1]), MIN(states[0],states[1]), INCLUSTER));
    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], CONSECUTIVE_CLUSTER));
    279 violation += SCIPvarGetLPSol(getEdgevar(edgevars, states[0], states[2], CONSECUTIVE_CLUSTER));
    280 violation -= SCIPvarGetLPSol(getEdgevar(edgevars, states[1], states[2], INCLUSTER));
    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], CONSECUTIVE_CLUSTER));
    295 violationchg -= SCIPvarGetLPSol(getEdgevar(edgevars,
    296 MAX(states[1],states[3]), MIN(states[1],states[3]), INCLUSTER));
    297 violationchg -= SCIPvarGetLPSol(getEdgevar(edgevars,
    298 MAX(states[2],states[3]), MIN(states[2],states[3]), INCLUSTER));
    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]), INCLUSTER)) - 1.0;
    331 violationchg += SCIPvarGetLPSol(getEdgevar(edgevars, states[4], secondpart[0], CONSECUTIVE_CLUSTER));
    332 violationchg += SCIPvarGetLPSol(getEdgevar(edgevars, states[4], secondpart[1], CONSECUTIVE_CLUSTER));
    333 violationchg += SCIPvarGetLPSol(getEdgevar(edgevars, states[4], secondpart[2], CONSECUTIVE_CLUSTER));
    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], CONSECUTIVE_CLUSTER));
    358 violation += SCIPvarGetLPSol(getEdgevar(edgevars, states[2], states[0], CONSECUTIVE_CLUSTER));
    359 violation -= SCIPvarGetLPSol(getEdgevar(edgevars, states[1], states[2], INCLUSTER));
    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], CONSECUTIVE_CLUSTER));
    374 violationchg -= SCIPvarGetLPSol(getEdgevar(edgevars,
    375 MAX(states[1],states[3]), MIN(states[1],states[3]), INCLUSTER));
    376 violationchg -= SCIPvarGetLPSol(getEdgevar(edgevars,
    377 MAX(states[2],states[3]), MIN(states[2],states[3]), INCLUSTER));
    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]), INCLUSTER)) - 1.0;
    408 violationchg += SCIPvarGetLPSol(getEdgevar(edgevars, firstpart[0], states[4], CONSECUTIVE_CLUSTER));
    409 violationchg += SCIPvarGetLPSol(getEdgevar(edgevars, firstpart[1], states[4], CONSECUTIVE_CLUSTER));
    410 violationchg += SCIPvarGetLPSol(getEdgevar(edgevars, firstpart[2], states[4], CONSECUTIVE_CLUSTER));
    411 violationchg += SCIPvarGetLPSol(edgevars[firstpart[2]][states[4]][CONSECUTIVE_CLUSTER]);
    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:248
    SCIP_MAXSTRLEN
    #define SCIP_MAXSTRLEN
    Definition: def.h:269
    SCIP_Bool
    #define SCIP_Bool
    Definition: def.h:91
    MIN
    #define MIN(x, y)
    Definition: def.h:224
    SCIP_Real
    #define SCIP_Real
    Definition: def.h:156
    TRUE
    #define TRUE
    Definition: def.h:93
    FALSE
    #define FALSE
    Definition: def.h:94
    MAX
    #define MAX(x, y)
    Definition: def.h:220
    SCIP_CALL
    #define SCIP_CALL(x)
    Definition: def.h:355
    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: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:24664
    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: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: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_RETCODE
    enum SCIP_Retcode SCIP_RETCODE
    Definition: type_retcode.h:63