SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
multi-commodity-flow network cut separator
We try to identify a multi-commodity flow structure in the LP relaxation of the following type:
(1) sum_{a in delta^+(v)} f_a^k - sum_{a in delta^-(v)} f_a^k <= -d_v^k for all v in V and k in K (2) sum_{k in K} f_a^k - c_a x_a <= 0 for all a in A
Constraints (1) are flow conservation constraints, which say that for each commodity k and node v the outflow (delta^+(v)) minus the inflow (delta^-(v)) of a node v must not exceed the negative of the demand of node v in commodity k. To say it the other way around, inflow minus outflow must be at least equal to the demand. Constraints (2) are the arc capacity constraints, which say that the sum of all flow over an arc a must not exceed its capacity c_a x_a, with x being a binary or integer variable. c_a x_a does not need to be a single product of a capacity and an integer variable; we also accept general scalar products.
Definition in file sepa_mcf.c.
#include <assert.h>#include <string.h>#include "scip/sepa_mcf.h"#include "scip/cons_knapsack.h"#include "scip/pub_misc.h"Go to the source code of this file.
Typedefs | |
| typedef enum SCIP_McfModeltype | SCIP_MCFMODELTYPE |
| typedef enum McfEffortLevel | MCFEFFORTLEVEL |
| typedef struct SCIP_McfNetwork | SCIP_MCFNETWORK |
| typedef struct mcfdata | MCFDATA |
| typedef struct nodepair | NODEPAIRENTRY |
| typedef struct nodepairqueue | NODEPAIRQUEUE |
| typedef struct nodepartition | NODEPARTITION |
Enumerations | |
| enum | SCIP_McfModeltype { SCIP_MCFMODELTYPE_AUTO = 0, SCIP_MCFMODELTYPE_DIRECTED = 1, SCIP_MCFMODELTYPE_UNDIRECTED = 2 } |
| enum | McfEffortLevel { MCFEFFORTLEVEL_OFF = 0, MCFEFFORTLEVEL_DEFAULT = 1, MCFEFFORTLEVEL_AGGRESSIVE = 2 } |
Functions | |
| static SCIP_RETCODE | mcfnetworkCreate (SCIP *scip, SCIP_MCFNETWORK **mcfnetwork) |
| static SCIP_RETCODE | mcfnetworkFree (SCIP *scip, SCIP_MCFNETWORK **mcfnetwork) |
| static SCIP_RETCODE | mcfnetworkFill (SCIP *scip, SCIP_MCFNETWORK *mcfnetwork, MCFDATA *mcfdata, int *compnodeid, int *compnodes, int ncompnodes, int *comparcs, int ncomparcs) |
| static | SCIP_DECL_SORTINDCOMP (compCands) |
| static SCIP_RETCODE | extractFlowRows (SCIP *scip, MCFDATA *mcfdata) |
| static SCIP_RETCODE | extractCapacityRows (SCIP *scip, MCFDATA *mcfdata) |
| static SCIP_RETCODE | createNewCommodity (SCIP *scip, MCFDATA *mcfdata) |
| static SCIP_RETCODE | createNewArc (SCIP *scip, MCFDATA *mcfdata, int source, int target, int *newarcid) |
| static void | addFlowrowToCommodity (SCIP *scip, MCFDATA *mcfdata, SCIP_ROW *row, unsigned char rowsign, int *comcolids, int *ncomcolids) |
| static void | invertCommodity (SCIP *scip, MCFDATA *mcfdata, int k, SCIP_ROW **comrows, int ncomrows, int *comcolids, int ncomcolids) |
| static void | deleteCommodity (SCIP *scip, MCFDATA *mcfdata, int k, SCIP_ROW **comrows, int nrows, int *ndelflowrows, int *ndelflowvars) |
| static void | getFlowrowFit (SCIP *scip, MCFDATA *mcfdata, SCIP_ROW *row, int k, unsigned char *rowsign, SCIP_Bool *invertcommodity) |
| static void | getNextFlowrow (SCIP *scip, MCFDATA *mcfdata, SCIP_ROW **nextrow, unsigned char *nextrowsign, SCIP_Bool *nextinvertcommodity) |
| static SCIP_RETCODE | extractFlow (SCIP *scip, MCFDATA *mcfdata, SCIP_Real maxflowvarflowrowratio, SCIP_Bool *failed) |
| static SCIP_RETCODE | extractCapacities (SCIP *scip, MCFDATA *mcfdata) |
| static void | collectIncidentFlowCols (SCIP *scip, MCFDATA *mcfdata, SCIP_ROW *flowrow, int basecommodity) |
| static SCIP_RETCODE | getNodeSimilarityScore (SCIP *scip, MCFDATA *mcfdata, int baserowlen, int *basearcpattern, int basenposuncap, int basenneguncap, SCIP_ROW *row, SCIP_Real *score, SCIP_Bool *invertcommodity) |
| static SCIP_RETCODE | extractNodes (SCIP *scip, MCFDATA *mcfdata) |
| static void | fixCommoditySigns (SCIP *scip, MCFDATA *mcfdata) |
| static void | getIncidentNodes (SCIP *scip, MCFDATA *mcfdata, SCIP_COL *col, int *sourcenode, int *targetnode) |
| static SCIP_RETCODE | findUncapacitatedArcs (SCIP *scip, MCFDATA *mcfdata) |
| static SCIP_RETCODE | cleanupNetwork (SCIP *scip, MCFDATA *mcfdata) |
| static SCIP_RETCODE | identifySourcesTargets (SCIP *scip, MCFDATA *mcfdata, SCIP_SEPADATA *sepadata, MCFEFFORTLEVEL *effortlevel) |
| static SCIP_RETCODE | identifyComponent (SCIP *scip, MCFDATA *mcfdata, int *nodevisited, int startv, int *compnodes, int *ncompnodes, int *comparcs, int *ncomparcs) |
| static SCIP_RETCODE | mcfnetworkExtract (SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_MCFNETWORK ***mcfnetworks, int *nmcfnetworks, MCFEFFORTLEVEL *effortlevel) |
| static void | unionfindInitSets (int *representatives, int nelems) |
| static int | unionfindGetRepresentative (int *representatives, int v) |
| static void | unionfindJoinSets (int *representatives, int rep1, int rep2) |
| static | SCIP_DECL_SORTPTRCOMP (compNodepairs) |
| static | SCIP_DECL_HASHGETKEY (hashGetKeyNodepairs) |
| static | SCIP_DECL_HASHKEYEQ (hashKeyEqNodepairs) |
| static | SCIP_DECL_HASHKEYVAL (hashKeyValNodepairs) |
| static SCIP_RETCODE | nodepairqueueCreate (SCIP *scip, SCIP_MCFNETWORK *mcfnetwork, NODEPAIRQUEUE **nodepairqueue) |
| static void | nodepairqueueFree (SCIP *scip, NODEPAIRQUEUE **nodepairqueue) |
| static SCIP_Bool | nodepairqueueIsEmpty (NODEPAIRQUEUE *nodepairqueue) |
| static NODEPAIRENTRY * | nodepairqueueRemove (NODEPAIRQUEUE *nodepairqueue) |
| static int | nodepartitionGetRepresentative (NODEPARTITION *nodepartition, int v) |
| static void | nodepartitionJoin (NODEPARTITION *nodepartition, int rep1, int rep2) |
| static SCIP_RETCODE | nodepartitionCreate (SCIP *scip, SCIP_MCFNETWORK *mcfnetwork, NODEPARTITION **nodepartition, int nclusters) |
| static void | nodepartitionFree (SCIP *scip, NODEPARTITION **nodepartition) |
| static SCIP_Bool | nodeInPartition (NODEPARTITION *nodepartition, unsigned int partition, SCIP_Bool inverted, int v) |
| static int | nodepartitionIsConnected (SCIP *scip, SCIP_MCFNETWORK *mcfnetwork, NODEPARTITION *nodepartition, unsigned int partition) |
| static SCIP_RETCODE | addCut (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz, SCIP_Bool cutislocal, int cutrank, int *ncuts, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | generateClusterCuts (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Bool allowlocal, SCIP_MCFNETWORK *mcfnetwork, NODEPARTITION *nodepartition, int *ncuts, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | separateCuts (SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Bool allowlocal, SCIP_RESULT *result) |
| static | SCIP_DECL_SEPACOPY (sepaCopyMcf) |
| static | SCIP_DECL_SEPAFREE (sepaFreeMcf) |
| static | SCIP_DECL_SEPAINITSOL (sepaInitsolMcf) |
| static | SCIP_DECL_SEPAEXITSOL (sepaExitsolMcf) |
| static | SCIP_DECL_SEPAEXECLP (sepaExeclpMcf) |
| static | SCIP_DECL_SEPAEXECSOL (sepaExecsolMcf) |
| SCIP_RETCODE | SCIPincludeSepaMcf (SCIP *scip) |
| #define BETTERWEIGHTFORDEMANDNODES |
Definition at line 46 of file sepa_mcf.c.
| #define SEPA_NAME "mcf" |
Definition at line 56 of file sepa_mcf.c.
Referenced by SCIP_DECL_SEPACOPY(), and SCIPincludeSepaMcf().
| #define SEPA_DESC "multi-commodity-flow network cut separator" |
Definition at line 57 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define SEPA_PRIORITY -10000 |
Definition at line 58 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define SEPA_FREQ 0 |
Definition at line 59 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define SEPA_MAXBOUNDDIST 0.0 |
Definition at line 60 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 61 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 62 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define DEFAULT_NCLUSTERS 5 |
number of clusters to generate in the shrunken network
Definition at line 65 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define DEFAULT_MAXWEIGHTRANGE 1e+06 |
maximal valid range max(|weights|)/min(|weights|) of row weights for CMIR
Definition at line 66 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define DEFAULT_MAXTESTDELTA 20 |
maximal number of different deltas to try (-1: unlimited) for CMIR
Definition at line 67 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define DEFAULT_TRYNEGSCALING FALSE |
should negative values also be tested in scaling? for CMIR
Definition at line 68 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define DEFAULT_FIXINTEGRALRHS TRUE |
should an additional variable be complemented if f0 = 0? for CMIR
Definition at line 69 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define DEFAULT_DYNAMICCUTS TRUE |
should generated cuts be removed from the LP if they are no longer tight?
Definition at line 70 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define DEFAULT_MODELTYPE 0 |
model type of network (0: auto, 1:directed, 2:undirected)
Definition at line 71 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define DEFAULT_MAXSEPACUTS 100 |
maximal number of cuts separated per separation round (-1: unlimited)
Definition at line 72 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define DEFAULT_MAXSEPACUTSROOT 200 |
maximal number of cuts separated per separation round in root node (-1: unlimited)
Definition at line 73 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define DEFAULT_MAXINCONSISTENCYRATIO 0.02 |
maximum inconsistency ratio (inconsistencies/(arcs*commodities)) at all
Definition at line 74 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define DEFAULT_MAXARCINCONSISTENCYRATIO 0.5 |
maximum inconsistency ratio for arcs not to be deleted
Definition at line 75 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define DEFAULT_CHECKCUTSHORECONNECTIVITY TRUE |
should we only separate if the cuts shores are connected
Definition at line 76 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define DEFAULT_SEPARATESINGLENODECUTS TRUE |
should we separate inequalities based on single node cuts
Definition at line 77 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define DEFAULT_SEPARATEFLOWCUTSET TRUE |
should we separate flowcutset inequalities
Definition at line 78 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define DEFAULT_SEPARATEKNAPSACK TRUE |
should we separate knapsack cover inequalities
Definition at line 79 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
| #define BOUNDSWITCH 0.5 |
Definition at line 82 of file sepa_mcf.c.
Referenced by generateClusterCuts().
| #define POSTPROCESS TRUE |
Definition at line 83 of file sepa_mcf.c.
Referenced by generateClusterCuts().
| #define USEVBDS TRUE |
Definition at line 84 of file sepa_mcf.c.
Referenced by generateClusterCuts().
| #define MINFRAC 0.05 |
Definition at line 85 of file sepa_mcf.c.
Referenced by generateClusterCuts().
| #define MAXFRAC 0.999 |
Definition at line 86 of file sepa_mcf.c.
Referenced by generateClusterCuts().
| #define MAXCOLS 2000000 |
| #define MAXAGGRLEN | ( | nvars | ) | (0.1*(nvars)+1000) |
maximal length of base inequality
Definition at line 89 of file sepa_mcf.c.
Referenced by generateClusterCuts().
| #define MINCOLROWRATIO 0.01 |
minimum ratio cols/rows for the separator to be switched on
Definition at line 90 of file sepa_mcf.c.
Referenced by separateCuts().
| #define MAXCOLROWRATIO 100.0 |
maximum ratio cols/rows for the separator to be switched on
Definition at line 91 of file sepa_mcf.c.
Referenced by separateCuts().
| #define MAXFLOWVARFLOWROWRATIO 100.0 |
maximum ratio flowvars/flowrows for the separator to be switched on
Definition at line 92 of file sepa_mcf.c.
Referenced by mcfnetworkExtract().
| #define MAXARCNODERATIO 100.0 |
maximum ratio arcs/nodes for the separator to be switched on
Definition at line 93 of file sepa_mcf.c.
Referenced by separateCuts().
| #define MAXNETWORKS 4 |
maximum number of networks to consider
Definition at line 94 of file sepa_mcf.c.
Referenced by mcfnetworkExtract().
| #define MAXFLOWCANDDENSITY 0.1 |
maximum density of rows to be accepted as flow candidates
Definition at line 95 of file sepa_mcf.c.
Referenced by extractFlowRows().
| #define MINCOMNODESFRACTION 0.5 |
minimal size of commodity relative to largest commodity to keep it in the network
Definition at line 96 of file sepa_mcf.c.
Referenced by cleanupNetwork(), and extractFlow().
| #define MINNODES 3 |
minimal number of nodes in network to keep it for separation
Definition at line 97 of file sepa_mcf.c.
Referenced by cleanupNetwork(), extractFlow(), and mcfnetworkExtract().
| #define MINARCS 3 |
minimal number of arcs in network to keep it for separation
Definition at line 98 of file sepa_mcf.c.
Referenced by mcfnetworkExtract().
| #define MAXCAPACITYSLACK 0.1 |
maximal slack of weighted capacity constraints to use in aggregation
Definition at line 99 of file sepa_mcf.c.
Referenced by generateClusterCuts().
| #define UNCAPACITATEDARCSTRESHOLD 0.8 |
threshold for the percentage of commodities an uncapacitated arc should appear in
Definition at line 100 of file sepa_mcf.c.
Referenced by findUncapacitatedArcs().
| #define HASHSIZE_NODEPAIRS 500 |
minimal size of hash table for nodepairs
Definition at line 101 of file sepa_mcf.c.
Referenced by nodepairqueueCreate().
| #define MCFdebugMessage while(FALSE) printf |
Definition at line 117 of file sepa_mcf.c.
Referenced by cleanupNetwork(), extractCapacityRows(), extractFlow(), extractFlowRows(), findUncapacitatedArcs(), generateClusterCuts(), identifySourcesTargets(), mcfnetworkExtract(), mcfnetworkFill(), nodepartitionIsConnected(), and separateCuts().
| #define LHSPOSSIBLE 1u |
we may use the constraint as lhs <= a*x
Definition at line 265 of file sepa_mcf.c.
Referenced by addFlowrowToCommodity(), extractCapacities(), extractCapacityRows(), extractFlowRows(), and getFlowrowFit().
| #define RHSPOSSIBLE 2u |
we may use the constraint as a*x <= rhs
Definition at line 266 of file sepa_mcf.c.
Referenced by addFlowrowToCommodity(), extractCapacities(), extractCapacityRows(), extractFlowRows(), and getFlowrowFit().
| #define LHSASSIGNED 4u |
we have chosen to use the constraint as lhs <= a*x
Definition at line 267 of file sepa_mcf.c.
Referenced by addFlowrowToCommodity(), deleteCommodity(), extractCapacities(), extractCapacityRows(), extractNodes(), findUncapacitatedArcs(), getIncidentNodes(), getNodeSimilarityScore(), identifySourcesTargets(), invertCommodity(), and mcfnetworkFill().
| #define RHSASSIGNED 8u |
we have chosen to use the constraint as a*x <= rhs
Definition at line 268 of file sepa_mcf.c.
Referenced by addFlowrowToCommodity(), deleteCommodity(), extractCapacities(), extractCapacityRows(), extractNodes(), findUncapacitatedArcs(), getIncidentNodes(), getNodeSimilarityScore(), identifySourcesTargets(), invertCommodity(), and mcfnetworkFill().
| #define INVERTED 16u |
we need to invert the row
Definition at line 269 of file sepa_mcf.c.
Referenced by addFlowrowToCommodity(), deleteCommodity(), extractFlow(), extractNodes(), getFlowrowFit(), getIncidentNodes(), getNextFlowrow(), getNodeSimilarityScore(), invertCommodity(), and mcfnetworkFill().
| #define DISCARDED 32u |
we have chosen to not use the constraint
Definition at line 270 of file sepa_mcf.c.
Referenced by extractCapacities(), and getFlowrowFit().
| #define UNDIRECTED 64u |
the capacity candidate has two flow variables for a commodity
Definition at line 271 of file sepa_mcf.c.
Referenced by extractCapacityRows().
| #define UNKNOWN 0 |
node has not yet been seen
Definition at line 4067 of file sepa_mcf.c.
Referenced by identifyComponent(), and mcfnetworkExtract().
| #define ONSTACK 1 |
node is currently on the processing stack
Definition at line 4068 of file sepa_mcf.c.
Referenced by identifyComponent().
| #define VISITED 2 |
node has been visited and assigned to some component
Definition at line 4069 of file sepa_mcf.c.
Referenced by identifyComponent(), and mcfnetworkExtract().
| typedef enum SCIP_McfModeltype SCIP_MCFMODELTYPE |
Definition at line 131 of file sepa_mcf.c.
| typedef enum McfEffortLevel MCFEFFORTLEVEL |
Definition at line 140 of file sepa_mcf.c.
| typedef struct SCIP_McfNetwork SCIP_MCFNETWORK |
Definition at line 162 of file sepa_mcf.c.
| typedef struct mcfdata MCFDATA |
internal MCF extraction data to pass to subroutines
Definition at line 231 of file sepa_mcf.c.
| typedef struct nodepair NODEPAIRENTRY |
Definition at line 240 of file sepa_mcf.c.
| typedef struct nodepairqueue NODEPAIRQUEUE |
Definition at line 248 of file sepa_mcf.c.
| typedef struct nodepartition NODEPARTITION |
Definition at line 259 of file sepa_mcf.c.
| enum SCIP_McfModeltype |
model type of the network
Definition at line 125 of file sepa_mcf.c.
| enum McfEffortLevel |
effort level for separation
| Enumerator | |
|---|---|
| MCFEFFORTLEVEL_OFF | no separation |
| MCFEFFORTLEVEL_DEFAULT | conservative separation |
| MCFEFFORTLEVEL_AGGRESSIVE | aggressive separation |
Definition at line 134 of file sepa_mcf.c.
|
static |
creates an empty MCF network data structure
| scip | SCIP data structure |
| mcfnetwork | MCF network structure |
Definition at line 276 of file sepa_mcf.c.
References SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.
Referenced by mcfnetworkExtract().
|
static |
frees MCF network data structure
| scip | SCIP data structure |
| mcfnetwork | MCF network structure |
Definition at line 302 of file sepa_mcf.c.
References SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, SCIPfreeMemoryArrayNull, and SCIPreleaseRow().
Referenced by mcfnetworkExtract(), and SCIP_DECL_SEPAEXITSOL().
|
static |
fills the MCF network structure with the MCF data
| scip | SCIP data structure |
| mcfnetwork | MCF network structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
| compnodeid | temporary storage for v -> compv mapping; must be set to -1 for all v |
| compnodes | array of node ids of the component |
| ncompnodes | number of nodes in the component |
| comparcs | array of arc ids of the component |
| ncomparcs | number of arcs in the component |
Definition at line 353 of file sepa_mcf.c.
References SCIP_McfNetwork::arccapacityrows, SCIP_McfNetwork::arccapacityscales, SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, BMSclearMemoryArray, SCIP_McfNetwork::colcommodity, FALSE, INVERTED, LHSASSIGNED, MCFdebugMessage, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, SCIP_McfNetwork::nodeflowinverted, SCIP_McfNetwork::nodeflowrows, SCIP_McfNetwork::nodeflowscales, SCIP_McfNetwork::nuncapacitatedarcs, RHSASSIGNED, SCIP_CALL, SCIP_MCFMODELTYPE_AUTO, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcaptureRow(), SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPfreeBufferArray, SCIPgetLPCols(), SCIPgetLPColsData(), SCIPgetLPRows(), SCIPgetLPRowsData(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetVals(), SCIPvarGetLbGlobal(), SCIPvarGetName(), and SCIPvarGetUbGlobal().
Referenced by mcfnetworkExtract().
|
static |
comparator method for flow and capacity row candidates
Definition at line 811 of file sepa_mcf.c.
References SCIP_Real.
|
static |
extracts flow conservation from the LP
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
Definition at line 825 of file sepa_mcf.c.
References FALSE, LHSPOSSIBLE, MAX, MAXFLOWCANDDENSITY, MCFdebugMessage, RHSPOSSIBLE, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPABORT, SCIPallocMemoryArray, SCIPcolGetVar(), SCIPdebugMsg, SCIPerrorMessage, SCIPgetLPRowsData(), SCIPgetNLPCols(), SCIPisEQ(), SCIPisInfinity(), SCIPisPositive(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetDualsol(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsModifiable(), SCIPsortInd(), and SCIPvarGetType().
Referenced by mcfnetworkExtract().
|
static |
extracts capacity rows from the LP
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
Definition at line 1041 of file sepa_mcf.c.
References BMSclearMemoryArray, SCIP_McfNetwork::colcommodity, LHSASSIGNED, LHSPOSSIBLE, MAX, MCFdebugMessage, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::ncommodities, RHSASSIGNED, RHSPOSSIBLE, SCIP_CALL, SCIP_INVALID, SCIP_INVALIDDATA, SCIP_MCFMODELTYPE_AUTO, SCIP_MCFMODELTYPE_DIRECTED, SCIP_MCFMODELTYPE_UNDIRECTED, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPdebugMsg, SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetLPRowsData(), SCIPgetNLPCols(), SCIPisEQ(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetDualsol(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsModifiable(), SCIPsortInd(), SCIPvarGetType(), and UNDIRECTED.
Referenced by mcfnetworkExtract().
|
static |
creates a new commodity
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
Definition at line 1409 of file sepa_mcf.c.
References MAX, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, and SCIPreallocMemoryArray.
Referenced by extractFlow().
|
static |
creates a new arc
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
| source | source of new arc |
| target | target of new arc |
| newarcid | pointer to store id of new arc |
Definition at line 1433 of file sepa_mcf.c.
References MAX, SCIP_McfNetwork::nnodes, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, and SCIPreallocMemoryArray.
Referenced by findUncapacitatedArcs().
|
static |
adds the given flow row and all involved columns to the current commodity
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
| row | flow row to add to current commodity |
| rowsign | possible flow row signs to use |
| comcolids | array of column indices of columns in commodity |
| ncomcolids | pointer to number of columns in commodity |
Definition at line 1486 of file sepa_mcf.c.
References SCIP_McfNetwork::colcommodity, INVERTED, LHSASSIGNED, LHSPOSSIBLE, SCIP_McfNetwork::ncommodities, RHSASSIGNED, RHSPOSSIBLE, SCIP_Bool, SCIP_INVALID, SCIP_Real, SCIPcolGetLPPos(), SCIPdebugMsg, SCIPgetNLPCols(), SCIPisZero(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetDualsol(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), and TRUE.
Referenced by extractFlow().
|
static |
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
| k | commodity that the flow row should enter |
| comrows | flow rows in commodity k |
| ncomrows | number of flow rows (number of nodes) in commodity k |
| comcolids | column indices of columns in commodity k |
| ncomcolids | number of columns in commodity k |
Definition at line 1632 of file sepa_mcf.c.
References INVERTED, LHSASSIGNED, RHSASSIGNED, SCIP_Bool, SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPisInfinity(), SCIProwGetLhs(), SCIProwGetLPPos(), and SCIProwGetRhs().
Referenced by extractFlow().
|
static |
deletes a commodity and removes the flow rows again from the system
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
| k | commodity to delete |
| comrows | flow rows of the commodity |
| nrows | number of flow rows in the commodity |
| ndelflowrows | pointer to store number of flow rows in deleted commodity |
| ndelflowvars | pointer to store number of flow vars in deleted commodity |
Definition at line 1697 of file sepa_mcf.c.
References SCIP_McfNetwork::colcommodity, FALSE, INVERTED, LHSASSIGNED, SCIP_McfNetwork::ncommodities, RHSASSIGNED, SCIP_Bool, SCIPcolGetLPPos(), SCIPdebugMsg, SCIPgetNLPCols(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetName(), and SCIProwGetNLPNonz().
Referenced by extractFlow().
|
static |
checks whether the given row fits into the given commodity and returns the possible flow row signs
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
| row | flow row to check |
| k | commodity that the flow row should enter |
| rowsign | pointer to store the possible flow row signs |
| invertcommodity | pointer to store whether the commodity has to be inverted to accommodate the row |
Definition at line 1781 of file sepa_mcf.c.
References SCIP_McfNetwork::colcommodity, DISCARDED, FALSE, INVERTED, LHSPOSSIBLE, RHSPOSSIBLE, SCIP_Bool, SCIP_Real, SCIPcolGetLPPos(), SCIPdebugMsg, SCIPgetNLPCols(), SCIPgetNLPRows(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetVals(), and TRUE.
Referenced by extractFlow(), and getNextFlowrow().
|
static |
returns a flow conservation row that fits into the current commodity, or NULL
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
| nextrow | pointer to store next row |
| nextrowsign | pointer to store possible signs of next row |
| nextinvertcommodity | pointer to store whether current commodity has to be inverted to accommodate the next row |
Definition at line 1913 of file sepa_mcf.c.
References FALSE, getFlowrowFit(), INVERTED, SCIP_McfNetwork::ncommodities, SCIP_Bool, SCIP_Real, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPgetLPCols(), SCIPgetNLPCols(), SCIPgetNLPRows(), and SCIProwGetLPPos().
Referenced by extractFlow().
|
static |
extracts flow conservation rows and puts them into commodities
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
| maxflowvarflowrowratio | maximum ratio of flowvars and flowrows |
| failed | pointer to store whether flowrowflowvarratio exceeded |
Definition at line 2030 of file sepa_mcf.c.
References addFlowrowToCommodity(), BMSclearMemoryArray, SCIP_McfNetwork::colcommodity, createNewCommodity(), deleteCommodity(), getFlowrowFit(), getNextFlowrow(), invertCommodity(), INVERTED, MAX, MCFdebugMessage, MINCOMNODESFRACTION, MINNODES, SCIP_McfNetwork::nnodes, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetLPRows(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIProwGetName(), and TRUE.
Referenced by mcfnetworkExtract().
|
static |
Arc-Detection – identifies capacity constraints for the arcs and assigns arc ids to columns and capacity constraints
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
Definition at line 2224 of file sepa_mcf.c.
References SCIP_McfNetwork::colcommodity, DISCARDED, LHSASSIGNED, LHSPOSSIBLE, MAX, RHSASSIGNED, RHSPOSSIBLE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPcolGetLPPos(), SCIPdebugMsg, SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPreallocMemoryArray, SCIProwGetCols(), SCIProwGetName(), and SCIProwGetNLPNonz().
Referenced by mcfnetworkExtract().
|
static |
collects all flow columns of all commodities (except the one of the base row) that are incident to the node described by the given flow row
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
| flowrow | flow conservation constraint that defines the node |
| basecommodity | commodity of the base row |
Definition at line 2390 of file sepa_mcf.c.
References SCIP_McfNetwork::colcommodity, SCIP_McfNetwork::narcs, SCIP_Bool, SCIPcolGetLPPos(), SCIPgetNLPCols(), SCIProwGetCols(), SCIProwGetNLPNonz(), and TRUE.
Referenced by extractNodes().
|
static |
compares given row against a base node flow row and calculates a similarity score; score is 0.0 if the rows are incompatible
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
| baserowlen | length of base node flow row |
| basearcpattern | arc pattern of base node flow row |
| basenposuncap | number of uncapacitated vars in base node flow row with positive coeff |
| basenneguncap | number of uncapacitated vars in base node flow row with negative coeff |
| row | row to compare against base node flow row |
| score | pointer to store the similarity score |
| invertcommodity | pointer to store whether the arcs in the commodity of the row have to be inverted for the row to be compatible to the base row |
Definition at line 2476 of file sepa_mcf.c.
References FALSE, INVERTED, LHSASSIGNED, MAX, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, RHSASSIGNED, SCIP_Bool, SCIP_CALL, SCIP_MCFMODELTYPE_DIRECTED, SCIP_MCFMODELTYPE_UNDIRECTED, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetLPPos(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNLPCols(), SCIPgetNLPRows(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetVals(), and TRUE.
Referenced by extractNodes().
|
static |
assigns node ids to flow conservation constraints
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
Definition at line 2678 of file sepa_mcf.c.
References BMSclearMemoryArray, collectIncidentFlowCols(), FALSE, getNodeSimilarityScore(), INVERTED, LHSASSIGNED, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, RHSASSIGNED, SCIP_Bool, SCIP_CALL, SCIP_MCFMODELTYPE_AUTO, SCIP_MCFMODELTYPE_UNDIRECTED, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcolGetLPPos(), SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPisNegative(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetVals(), and TRUE.
Referenced by mcfnetworkExtract().
if there are still undecided commodity signs, fix them to +1
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
Definition at line 2949 of file sepa_mcf.c.
Referenced by mcfnetworkExtract().
|
static |
identifies the (at most) two nodes which contain the given flow variable
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
| col | flow column |
| sourcenode | pointer to store the source node of the flow column |
| targetnode | pointer to store the target node of the flow column |
Definition at line 2967 of file sepa_mcf.c.
References INVERTED, LHSASSIGNED, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, RHSASSIGNED, SCIP_Real, SCIPcolGetLPPos(), SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPgetNLPCols(), SCIPgetNLPRows(), and SCIProwGetLPPos().
Referenced by findUncapacitatedArcs(), and identifySourcesTargets().
|
static |
find uncapacitated arcs for flow columns that have no associated arc yet
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
Definition at line 3066 of file sepa_mcf.c.
References SCIP_McfNetwork::colcommodity, createNewArc(), getIncidentNodes(), LHSASSIGNED, MCFdebugMessage, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, RHSASSIGNED, SCIP_CALL, SCIP_MCFMODELTYPE_DIRECTED, SCIP_MCFMODELTYPE_UNDIRECTED, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPceil(), SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetLPCols(), SCIPgetLPRows(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIProwGetCols(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIPsortIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and UNCAPACITATEDARCSTRESHOLD.
Referenced by mcfnetworkExtract().
|
static |
cleans up the network: gets rid of commodities without arcs or with at most one node
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
Definition at line 3406 of file sepa_mcf.c.
References BMSclearMemoryArray, SCIP_McfNetwork::colcommodity, MAX, MCFdebugMessage, MINCOMNODESFRACTION, MINNODES, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcolGetLPPos(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetLPRowsData(), SCIPgetNLPCols(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetNLPNonz(), and TRUE.
Referenced by mcfnetworkExtract().
|
static |
for each arc identifies a source and target node
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
| sepadata | separator data |
| effortlevel | pointer to store effort level of separation |
Definition at line 3724 of file sepa_mcf.c.
References SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, BMSclearMemoryArray, SCIP_McfNetwork::colcommodity, getIncidentNodes(), LHSASSIGNED, MCFdebugMessage, MCFEFFORTLEVEL_DEFAULT, MCFEFFORTLEVEL_OFF, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, RHSASSIGNED, SCIP_CALL, SCIP_MCFMODELTYPE_DIRECTED, SCIP_MCFMODELTYPE_UNDIRECTED, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcolGetLPPos(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPisGE(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetNLPNonz(), and TRUE.
Referenced by mcfnetworkExtract().
|
static |
returns lists of nodes and arcs in the connected component of the given startv
| scip | SCIP data structure |
| mcfdata | internal MCF extraction data to pass to subroutines |
| nodevisited | array to mark visited nodes |
| startv | node for which the connected component should be generated |
| compnodes | array to store node ids of the component |
| ncompnodes | pointer to store the number of nodes in the component |
| comparcs | array to store arc ids of the component |
| ncomparcs | pointer to store the number of arcs in the component |
Definition at line 4073 of file sepa_mcf.c.
References SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, SCIP_McfNetwork::narcs, SCIP_McfNetwork::nnodes, ONSTACK, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, UNKNOWN, and VISITED.
Referenced by mcfnetworkExtract().
|
static |
extracts MCF network structures from the current LP
| scip | SCIP data structure |
| sepadata | separator data |
| mcfnetworks | pointer to store array of MCF network structures |
| nmcfnetworks | pointer to store number of MCF networks |
| effortlevel | effort level of separation |
Definition at line 4204 of file sepa_mcf.c.
References SCIP_McfNetwork::arccapacityrows, BMSclearMemoryArray, cleanupNetwork(), SCIP_McfNetwork::colcommodity, extractCapacities(), extractCapacityRows(), extractFlow(), extractFlowRows(), extractNodes(), FALSE, findUncapacitatedArcs(), fixCommoditySigns(), identifyComponent(), identifySourcesTargets(), MAX, MAXFLOWVARFLOWROWRATIO, MAXNETWORKS, MCFdebugMessage, MCFEFFORTLEVEL_OFF, mcfnetworkCreate(), mcfnetworkFill(), mcfnetworkFree(), MINARCS, MINNODES, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, SCIP_McfNetwork::nodeflowrows, SCIP_Bool, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPABORT, SCIPallocBufferArray, SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPdebugMsg, SCIPerrorMessage, SCIPfreeBufferArray, SCIPfreeMemoryArrayNull, SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetNLPCols(), SCIPreallocMemoryArray, SCIProwGetCols(), SCIProwGetNLPNonz(), SCIPvarGetType(), TRUE, UNKNOWN, and VISITED.
Referenced by separateCuts().
|
static |
initializes a union find data structure by putting each element into its own set
| representatives | mapping an element v to its representative |
| nelems | number of elements in the ground set |
Definition at line 4679 of file sepa_mcf.c.
Referenced by nodepartitionCreate(), and nodepartitionIsConnected().
|
static |
applies a union find algorithm to get the representative of v
| representatives | mapping an element v to its representative |
| v | element v to get a representative for |
Definition at line 4693 of file sepa_mcf.c.
Referenced by nodepartitionGetRepresentative(), and nodepartitionIsConnected().
|
static |
joins two sets in the union find framework
| representatives | mapping an element v to its representative |
| rep1 | representative of first set |
| rep2 | representative of second set |
Definition at line 4711 of file sepa_mcf.c.
Referenced by nodepartitionIsConnected(), and nodepartitionJoin().
|
static |
comparison method for weighted nodepairs
Definition at line 4738 of file sepa_mcf.c.
|
static |
NodePair HashTable gets the key of the given element
Definition at line 4754 of file sepa_mcf.c.
|
static |
NodePair HashTable returns TRUE iff both keys are equal; two nodepairs are equal if both nodes equal
Definition at line 4766 of file sepa_mcf.c.
References SCIP_McfNetwork::nnodes.
|
static |
NodePair HashTable returns the hash value of the key
Definition at line 4807 of file sepa_mcf.c.
References SCIP_McfNetwork::nnodes.
|
static |
creates a priority queue and fills it with the given nodepair entries
| scip | SCIP data structure |
| mcfnetwork | MCF network structure |
| nodepairqueue | pointer to nodepair priority queue |
Definition at line 4841 of file sepa_mcf.c.
References SCIP_McfNetwork::colcommodity, FALSE, HASHSIZE_NODEPAIRS, MAX, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nodeflowrows, SCIP_McfNetwork::nodeflowscales, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBuffer, SCIPallocBufferArray, SCIPblkmem(), SCIPcolGetLPPos(), SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPdebugMsg, SCIPgetNLPCols(), SCIPgetRowFeasibility(), SCIPgetRowMaxCoef(), SCIPhashtableCreate(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIPinfinity(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPpqueueCreate(), SCIPpqueueInsert(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetDualsol(), SCIProwGetLhs(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIPvarGetName(), and TRUE.
Referenced by nodepartitionCreate().
|
static |
frees memory of a nodepair queue
| scip | SCIP data structure |
| nodepairqueue | pointer to nodepair priority queue |
Definition at line 5156 of file sepa_mcf.c.
References SCIPfreeBuffer, SCIPfreeBufferArray, and SCIPpqueueFree().
Referenced by nodepartitionCreate().
|
static |
returns whether there are any nodepairs left on the queue
| nodepairqueue | nodepair priority queue |
Definition at line 5172 of file sepa_mcf.c.
References SCIPpqueueFirst().
Referenced by nodepartitionCreate().
|
static |
removes the top element from the nodepair priority queue, returns nodepair entry or NULL
| nodepairqueue | nodepair priority queue |
Definition at line 5184 of file sepa_mcf.c.
References SCIPpqueueRemove().
Referenced by nodepartitionCreate().
|
static |
returns the representative node in the cluster of the given node
| nodepartition | node partition data structure |
| v | node id to get representative for |
Definition at line 5202 of file sepa_mcf.c.
References unionfindGetRepresentative().
Referenced by nodepartitionCreate().
|
static |
joins two clusters given by their representative nodes
| nodepartition | node partition data structure |
| rep1 | representative of first cluster |
| rep2 | representative of second cluster |
Definition at line 5212 of file sepa_mcf.c.
References unionfindJoinSets().
Referenced by nodepartitionCreate().
|
static |
partitions nodes into a small number of clusters
| scip | SCIP data structure |
| mcfnetwork | MCF network structure |
| nodepartition | pointer to node partition data structure |
| nclusters | number of clusters to generate |
Definition at line 5223 of file sepa_mcf.c.
References BMSclearMemoryArray, SCIP_McfNetwork::nnodes, nodepairqueueCreate(), nodepairqueueFree(), nodepairqueueIsEmpty(), nodepairqueueRemove(), nodepartitionGetRepresentative(), nodepartitionJoin(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBuffer, SCIPallocBufferArray, SCIPdebug, SCIPdebugMsg, SCIPfreeBufferArray, and unionfindInitSets().
Referenced by separateCuts().
|
static |
frees node partition data
| scip | SCIP data structure |
| nodepartition | pointer to node partition data structure |
Definition at line 5373 of file sepa_mcf.c.
References SCIPfreeBuffer, and SCIPfreeBufferArray.
Referenced by separateCuts().
|
static |
returns whether given node v is in a cluster that belongs to the partition S
| nodepartition | node partition data structure, or NULL |
| partition | partition of nodes, or node number in single-node partition |
| inverted | should partition be inverted? |
| v | node to check |
Definition at line 5390 of file sepa_mcf.c.
References FALSE.
Referenced by generateClusterCuts(), and nodepartitionIsConnected().
|
static |
returns whether each of the sets S and T defined by the nodepartition is connected
| scip | SCIP data structure |
| mcfnetwork | MCF network structure |
| nodepartition | node partition data structure |
| partition | partition of nodes, or node number in single-node partition |
Definition at line 5420 of file sepa_mcf.c.
References SCIP_McfNetwork::arccapacityrows, SCIP_McfNetwork::arccapacityscales, SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, FALSE, MCFdebugMessage, SCIP_McfNetwork::narcs, SCIP_McfNetwork::nnodes, SCIP_McfNetwork::nodeflowrows, nodeInPartition(), SCIP_Bool, SCIP_FILECREATEERROR, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetVar(), SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetRowLPFeasibility(), SCIPinfinity(), SCIPinfoMessage(), SCIPisFeasIntegral(), SCIPisFeasPositive(), SCIProwGetCols(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIPsnprintf(), SCIPvarGetLPSol(), SCIPvarIsIntegral(), TRUE, unionfindGetRepresentative(), unionfindInitSets(), and unionfindJoinSets().
Referenced by generateClusterCuts().
|
static |
adds given cut to LP if violated
| scip | SCIP data structure |
| sepa | separator |
| sepadata | separator data |
| sol | the solution that should be separated, or NULL for LP solution |
| cutcoefs | coefficients of active variables in cut |
| cutrhs | right hand side of cut |
| cutinds | problem indices of variables with non-zero coefficient |
| cutnnz | number of non-zeros in cut |
| cutislocal | is the cut only locally valid? |
| cutrank | rank of the cut |
| ncuts | pointer to count the number of added cuts |
| cutoff | pointer to store whether a cutoff was found |
Definition at line 5757 of file sepa_mcf.c.
References FALSE, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarsToRow(), SCIPallocBufferArray, SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetCutEfficacy(), SCIPgetNLPs(), SCIPgetRowSolActivity(), SCIPgetVarsData(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetRank(), SCIPseparateRelaxedKnapsack(), and SCIPsnprintf().
Referenced by generateClusterCuts().
|
static |
enumerates cuts between subsets of the clusters generates single-node cuts if nodepartition == NULL, otherwise generates cluster cuts
| scip | SCIP data structure |
| sepa | separator |
| sepadata | separator data |
| sol | the solution that should be separated, or NULL for LP solution |
| allowlocal | should local cuts be allowed |
| mcfnetwork | MCF network structure |
| nodepartition | node partition data structure, or NULL |
| ncuts | pointer to count the number of added cuts |
| cutoff | pointer to store whether a cutoff was found |
Definition at line 5844 of file sepa_mcf.c.
References addCut(), SCIP_McfNetwork::arccapacityrows, SCIP_McfNetwork::arccapacityscales, SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, BMSclearMemoryArray, BOUNDSWITCH, SCIP_McfNetwork::colcommodity, FALSE, MAXAGGRLEN, MAXCAPACITYSLACK, MAXFRAC, MCFdebugMessage, MCFEFFORTLEVEL_AGGRESSIVE, MCFEFFORTLEVEL_DEFAULT, MINFRAC, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, SCIP_McfNetwork::nodeflowinverted, SCIP_McfNetwork::nodeflowrows, SCIP_McfNetwork::nodeflowscales, nodeInPartition(), nodepartitionIsConnected(), POSTPROCESS, REALABS, SCIP_Bool, SCIP_CALL, SCIP_MCFMODELTYPE_DIRECTED, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPaggrRowCreate(), SCIPaggrRowFree(), SCIPaggrRowSumRows(), SCIPallocBufferArray, SCIPcalcMIR(), SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPcolIsIntegral(), SCIPdebugMsg, SCIPfloor(), SCIPfrac(), SCIPfreeBufferArray, SCIPgetDepth(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPgetNVars(), SCIPgetRowFeasibility(), SCIPgetRowMaxCoef(), SCIPgetRowSolFeasibility(), SCIPgetSolVal(), SCIPisEfficacious(), SCIPisFeasGT(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPisStopped(), SCIPisZero(), SCIPreallocBufferArray, SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetDualsol(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIPvarIsIntegral(), TRUE, and USEVBDS.
Referenced by separateCuts().
|
static |
searches and adds MCF network cuts that separate the given primal solution
| scip | SCIP data structure |
| sepa | the cut separator itself |
| sol | primal solution that should be separated, or NULL for LP solution |
| allowlocal | should local cuts be allowed |
| result | pointer to store the result of the separation call |
Definition at line 6589 of file sepa_mcf.c.
References FALSE, generateClusterCuts(), MAXARCNODERATIO, MAXCOLROWRATIO, MAXCOLS, MCFdebugMessage, MCFEFFORTLEVEL_DEFAULT, MCFEFFORTLEVEL_OFF, mcfnetworkExtract(), MINCOLROWRATIO, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, nodepartitionCreate(), nodepartitionFree(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_MCFMODELTYPE_DIRECTED, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPdebug, SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPgetNVars(), SCIPsepaGetData(), SCIPsepaWasLPDelayed(), and TRUE.
Referenced by SCIP_DECL_SEPAEXECLP(), and SCIP_DECL_SEPAEXECSOL().
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 6764 of file sepa_mcf.c.
References SCIP_CALL, SCIP_OKAY, SCIPincludeSepaMcf(), SCIPsepaGetName(), and SEPA_NAME.
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 6778 of file sepa_mcf.c.
References SCIP_OKAY, SCIPfreeMemory, SCIPsepaGetData(), and SCIPsepaSetData().
|
static |
solving process initialization method of separator (called when branch and bound process is about to begin)
Definition at line 6798 of file sepa_mcf.c.
References MCFEFFORTLEVEL_OFF, SCIP_OKAY, SCIPsepaGetData(), and TRUE.
|
static |
solving process deinitialization method of separator (called before branch and bound process data is freed)
Definition at line 6816 of file sepa_mcf.c.
References mcfnetworkFree(), SCIP_CALL, SCIP_OKAY, SCIPfreeMemoryArrayNull, and SCIPsepaGetData().
|
static |
LP solution separation method of separator
Definition at line 6840 of file sepa_mcf.c.
References SCIP_CALL, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPgetLPSolstat(), SCIPgetNLPBranchCands(), SCIPisStopped(), and separateCuts().
|
static |
arbitrary primal solution separation method of separator
Definition at line 6867 of file sepa_mcf.c.
References SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, and separateCuts().