SCIP
Solving Constraint Integer Programs
sepa_mcf.c File Reference
Detailed Description
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 "blockmemshell/memory.h"#include "scip/cons_knapsack.h"#include "scip/cuts.h"#include "scip/pub_lp.h"#include "scip/pub_message.h"#include "scip/pub_misc.h"#include "scip/pub_misc_sort.h"#include "scip/pub_sepa.h"#include "scip/pub_var.h"#include "scip/scip_branch.h"#include "scip/scip_cut.h"#include "scip/scip_general.h"#include "scip/scip_lp.h"#include "scip/scip_mem.h"#include "scip/scip_message.h"#include "scip/scip_numerics.h"#include "scip/scip_param.h"#include "scip/scip_prob.h"#include "scip/scip_sepa.h"#include "scip/scip_sol.h"#include "scip/scip_solvingstats.h"#include "scip/scip_tree.h"#include "scip/sepa_mcf.h"#include <string.h>Go to the source code of this file.
Data Structures | |
| struct | SCIP_McfNetwork |
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) |
Macro Definition Documentation
◆ BETTERWEIGHTFORDEMANDNODES
| #define BETTERWEIGHTFORDEMANDNODES |
Definition at line 46 of file sepa_mcf.c.
◆ SEPA_NAME
| #define SEPA_NAME "mcf" |
Definition at line 74 of file sepa_mcf.c.
Referenced by SCIP_DECL_SEPACOPY(), and SCIPincludeSepaMcf().
◆ SEPA_DESC
| #define SEPA_DESC "multi-commodity-flow network cut separator" |
Definition at line 75 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ SEPA_PRIORITY
| #define SEPA_PRIORITY -10000 |
Definition at line 76 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ SEPA_FREQ
| #define SEPA_FREQ 0 |
Definition at line 77 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ SEPA_MAXBOUNDDIST
| #define SEPA_MAXBOUNDDIST 0.0 |
Definition at line 78 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ SEPA_USESSUBSCIP
| #define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 79 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ SEPA_DELAY
| #define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 80 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ DEFAULT_NCLUSTERS
| #define DEFAULT_NCLUSTERS 5 |
number of clusters to generate in the shrunken network
Definition at line 83 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ DEFAULT_MAXWEIGHTRANGE
| #define DEFAULT_MAXWEIGHTRANGE 1e+06 |
maximal valid range max(|weights|)/min(|weights|) of row weights for CMIR
Definition at line 84 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ DEFAULT_MAXTESTDELTA
| #define DEFAULT_MAXTESTDELTA 20 |
maximal number of different deltas to try (-1: unlimited) for CMIR
Definition at line 85 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ DEFAULT_TRYNEGSCALING
| #define DEFAULT_TRYNEGSCALING FALSE |
should negative values also be tested in scaling? for CMIR
Definition at line 86 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ DEFAULT_FIXINTEGRALRHS
| #define DEFAULT_FIXINTEGRALRHS TRUE |
should an additional variable be complemented if f0 = 0? for CMIR
Definition at line 87 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ DEFAULT_DYNAMICCUTS
| #define DEFAULT_DYNAMICCUTS TRUE |
should generated cuts be removed from the LP if they are no longer tight?
Definition at line 88 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ DEFAULT_MODELTYPE
| #define DEFAULT_MODELTYPE 0 |
model type of network (0: auto, 1:directed, 2:undirected)
Definition at line 89 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ DEFAULT_MAXSEPACUTS
| #define DEFAULT_MAXSEPACUTS 100 |
maximal number of cuts separated per separation round (-1: unlimited)
Definition at line 90 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ DEFAULT_MAXSEPACUTSROOT
| #define DEFAULT_MAXSEPACUTSROOT 200 |
maximal number of cuts separated per separation round in root node (-1: unlimited)
Definition at line 91 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ DEFAULT_MAXINCONSISTENCYRATIO
| #define DEFAULT_MAXINCONSISTENCYRATIO 0.02 |
maximum inconsistency ratio (inconsistencies/(arcs*commodities)) at all
Definition at line 92 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ DEFAULT_MAXARCINCONSISTENCYRATIO
| #define DEFAULT_MAXARCINCONSISTENCYRATIO 0.5 |
maximum inconsistency ratio for arcs not to be deleted
Definition at line 93 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ DEFAULT_CHECKCUTSHORECONNECTIVITY
| #define DEFAULT_CHECKCUTSHORECONNECTIVITY TRUE |
should we only separate if the cuts shores are connected
Definition at line 94 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ DEFAULT_SEPARATESINGLENODECUTS
| #define DEFAULT_SEPARATESINGLENODECUTS TRUE |
should we separate inequalities based on single node cuts
Definition at line 95 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ DEFAULT_SEPARATEFLOWCUTSET
| #define DEFAULT_SEPARATEFLOWCUTSET TRUE |
should we separate flowcutset inequalities
Definition at line 96 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ DEFAULT_SEPARATEKNAPSACK
| #define DEFAULT_SEPARATEKNAPSACK TRUE |
should we separate knapsack cover inequalities
Definition at line 97 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
◆ BOUNDSWITCH
| #define BOUNDSWITCH 0.5 |
Definition at line 100 of file sepa_mcf.c.
Referenced by generateClusterCuts().
◆ POSTPROCESS
| #define POSTPROCESS TRUE |
Definition at line 101 of file sepa_mcf.c.
Referenced by generateClusterCuts().
◆ USEVBDS
| #define USEVBDS TRUE |
Definition at line 102 of file sepa_mcf.c.
Referenced by generateClusterCuts().
◆ MINFRAC
| #define MINFRAC 0.05 |
Definition at line 103 of file sepa_mcf.c.
Referenced by generateClusterCuts().
◆ MAXFRAC
| #define MAXFRAC 0.999 |
Definition at line 104 of file sepa_mcf.c.
Referenced by generateClusterCuts().
◆ MAXCOLS
| #define MAXCOLS 2000000 |
◆ MAXAGGRLEN
| #define MAXAGGRLEN | ( | nvars | ) | (0.1*(nvars)+1000) |
maximal length of base inequality
Definition at line 107 of file sepa_mcf.c.
Referenced by generateClusterCuts().
◆ MINCOLROWRATIO
| #define MINCOLROWRATIO 0.01 |
minimum ratio cols/rows for the separator to be switched on
Definition at line 108 of file sepa_mcf.c.
Referenced by separateCuts().
◆ MAXCOLROWRATIO
| #define MAXCOLROWRATIO 100.0 |
maximum ratio cols/rows for the separator to be switched on
Definition at line 109 of file sepa_mcf.c.
Referenced by separateCuts().
◆ MAXFLOWVARFLOWROWRATIO
| #define MAXFLOWVARFLOWROWRATIO 100.0 |
maximum ratio flowvars/flowrows for the separator to be switched on
Definition at line 110 of file sepa_mcf.c.
Referenced by mcfnetworkExtract().
◆ MAXARCNODERATIO
| #define MAXARCNODERATIO 100.0 |
maximum ratio arcs/nodes for the separator to be switched on
Definition at line 111 of file sepa_mcf.c.
Referenced by separateCuts().
◆ MAXNETWORKS
| #define MAXNETWORKS 4 |
maximum number of networks to consider
Definition at line 112 of file sepa_mcf.c.
Referenced by mcfnetworkExtract().
◆ MAXFLOWCANDDENSITY
| #define MAXFLOWCANDDENSITY 0.1 |
maximum density of rows to be accepted as flow candidates
Definition at line 113 of file sepa_mcf.c.
Referenced by extractFlowRows().
◆ MINCOMNODESFRACTION
| #define MINCOMNODESFRACTION 0.5 |
minimal size of commodity relative to largest commodity to keep it in the network
Definition at line 114 of file sepa_mcf.c.
Referenced by cleanupNetwork(), and extractFlow().
◆ MINNODES
| #define MINNODES 3 |
minimal number of nodes in network to keep it for separation
Definition at line 115 of file sepa_mcf.c.
Referenced by cleanupNetwork(), extractFlow(), and mcfnetworkExtract().
◆ MINARCS
| #define MINARCS 3 |
minimal number of arcs in network to keep it for separation
Definition at line 116 of file sepa_mcf.c.
Referenced by mcfnetworkExtract().
◆ MAXCAPACITYSLACK
| #define MAXCAPACITYSLACK 0.1 |
maximal slack of weighted capacity constraints to use in aggregation
Definition at line 117 of file sepa_mcf.c.
Referenced by generateClusterCuts().
◆ UNCAPACITATEDARCSTRESHOLD
| #define UNCAPACITATEDARCSTRESHOLD 0.8 |
threshold for the percentage of commodities an uncapacitated arc should appear in
Definition at line 118 of file sepa_mcf.c.
Referenced by findUncapacitatedArcs().
◆ HASHSIZE_NODEPAIRS
| #define HASHSIZE_NODEPAIRS 500 |
minimal size of hash table for nodepairs
Definition at line 119 of file sepa_mcf.c.
Referenced by nodepairqueueCreate().
◆ MCFdebugMessage
| #define MCFdebugMessage while(FALSE) printf |
Definition at line 135 of file sepa_mcf.c.
Referenced by cleanupNetwork(), extractCapacityRows(), extractFlow(), extractFlowRows(), findUncapacitatedArcs(), generateClusterCuts(), identifySourcesTargets(), mcfnetworkExtract(), mcfnetworkFill(), nodepartitionIsConnected(), and separateCuts().
◆ LHSPOSSIBLE
| #define LHSPOSSIBLE 1u |
we may use the constraint as lhs <= a*x
Definition at line 283 of file sepa_mcf.c.
Referenced by addFlowrowToCommodity(), extractCapacities(), extractCapacityRows(), extractFlowRows(), and getFlowrowFit().
◆ RHSPOSSIBLE
| #define RHSPOSSIBLE 2u |
we may use the constraint as a*x <= rhs
Definition at line 284 of file sepa_mcf.c.
Referenced by addFlowrowToCommodity(), extractCapacities(), extractCapacityRows(), extractFlowRows(), and getFlowrowFit().
◆ LHSASSIGNED
| #define LHSASSIGNED 4u |
we have chosen to use the constraint as lhs <= a*x
Definition at line 285 of file sepa_mcf.c.
Referenced by addFlowrowToCommodity(), deleteCommodity(), extractCapacities(), extractCapacityRows(), extractNodes(), findUncapacitatedArcs(), getIncidentNodes(), getNodeSimilarityScore(), identifySourcesTargets(), invertCommodity(), and mcfnetworkFill().
◆ RHSASSIGNED
| #define RHSASSIGNED 8u |
we have chosen to use the constraint as a*x <= rhs
Definition at line 286 of file sepa_mcf.c.
Referenced by addFlowrowToCommodity(), deleteCommodity(), extractCapacities(), extractCapacityRows(), extractNodes(), findUncapacitatedArcs(), getIncidentNodes(), getNodeSimilarityScore(), identifySourcesTargets(), invertCommodity(), and mcfnetworkFill().
◆ INVERTED
| #define INVERTED 16u |
we need to invert the row
Definition at line 287 of file sepa_mcf.c.
Referenced by addFlowrowToCommodity(), deleteCommodity(), extractFlow(), extractNodes(), getFlowrowFit(), getIncidentNodes(), getNextFlowrow(), getNodeSimilarityScore(), invertCommodity(), and mcfnetworkFill().
◆ DISCARDED
| #define DISCARDED 32u |
we have chosen to not use the constraint
Definition at line 288 of file sepa_mcf.c.
Referenced by extractCapacities(), and getFlowrowFit().
◆ UNDIRECTED
| #define UNDIRECTED 64u |
the capacity candidate has two flow variables for a commodity
Definition at line 289 of file sepa_mcf.c.
Referenced by extractCapacityRows().
◆ UNKNOWN
| #define UNKNOWN 0 |
node has not yet been seen
Definition at line 4081 of file sepa_mcf.c.
Referenced by adjust0term(), buildsolgraph(), computeDegConsTree(), computePertubedSol(), computeSteinerTreeVnoi(), correct(), correctX(), findDaRoots(), getcloseterms2term(), getlecloseterms(), graph_edge_add(), graph_get2next(), graph_get3next(), graph_get4next(), graph_get4nextTTerms(), graph_init(), graph_load(), graph_pack(), graph_path_exec(), graph_path_execX(), graph_path_invroot(), graph_path_PcMwSd(), graph_path_st(), graph_path_st_pcmw(), graph_path_st_pcmw_extend(), graph_path_st_pcmw_full(), graph_path_st_pcmw_reduce(), graph_path_st_rmw(), graph_path_st_rpc(), graph_pc_deleteTerm(), graph_sdPaths(), graph_sol_getOrg(), graph_sol_reroot(), graph_voronoi(), graph_voronoiMw(), graph_voronoiRepair(), graph_voronoiTerms(), graph_voronoiWithDist(), graph_voronoiWithRadius(), graph_voronoiWithRadiusMw(), identifyComponent(), mcfnetworkExtract(), prune(), reduce_ansAdv2(), reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundHopRc(), reduce_chain2(), reduce_cnsAdv(), reduce_da(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), reduce_getSd(), reduce_getSdPcMw(), reduce_ledge(), reduce_npv(), reduce_nts(), reduce_nv(), reduce_nvAdv(), reduce_sd(), reduce_sdPc(), reduce_sdsp(), reduce_sdspSap(), reduce_simple(), reduce_simple_pc(), reduce_sl(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_BRANCHEXECPS(), SCIP_DECL_HEUREXEC(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), SCIPStpHeurSlackPruneRunPcMw(), SCIPStpHeurTMBuildTree(), SCIPStpHeurTMBuildTreeDc(), SCIPStpHeurTMBuildTreePcMw(), SCIPStpHeurTMPrune(), SCIPStpHeurTMRun(), SCIPStpHeurTMRunLP(), selectBranchingVertexByDegree(), selectBranchingVertexByLp(), selectBranchingVertexByLp2Flow(), selectBranchingVertexBySol(), setNodeSolArray(), trydg1edgepc(), and updateSolNodeArray().
◆ ONSTACK
| #define ONSTACK 1 |
node is currently on the processing stack
Definition at line 4082 of file sepa_mcf.c.
Referenced by identifyComponent().
◆ VISITED
| #define VISITED 2 |
node has been visited and assigned to some component
Definition at line 4083 of file sepa_mcf.c.
Referenced by identifyComponent(), and mcfnetworkExtract().
Typedef Documentation
◆ SCIP_MCFMODELTYPE
| typedef enum SCIP_McfModeltype SCIP_MCFMODELTYPE |
Definition at line 149 of file sepa_mcf.c.
◆ MCFEFFORTLEVEL
| typedef enum McfEffortLevel MCFEFFORTLEVEL |
Definition at line 158 of file sepa_mcf.c.
◆ SCIP_MCFNETWORK
| typedef struct SCIP_McfNetwork SCIP_MCFNETWORK |
Definition at line 180 of file sepa_mcf.c.
◆ MCFDATA
| typedef struct mcfdata MCFDATA |
internal MCF extraction data to pass to subroutines
Definition at line 249 of file sepa_mcf.c.
◆ NODEPAIRENTRY
| typedef struct nodepair NODEPAIRENTRY |
Definition at line 258 of file sepa_mcf.c.
◆ NODEPAIRQUEUE
| typedef struct nodepairqueue NODEPAIRQUEUE |
Definition at line 266 of file sepa_mcf.c.
◆ NODEPARTITION
| typedef struct nodepartition NODEPARTITION |
Definition at line 277 of file sepa_mcf.c.
Enumeration Type Documentation
◆ SCIP_McfModeltype
| enum SCIP_McfModeltype |
model type of the network
Definition at line 143 of file sepa_mcf.c.
◆ McfEffortLevel
| enum McfEffortLevel |
effort level for separation
| Enumerator | |
|---|---|
| MCFEFFORTLEVEL_OFF | no separation |
| MCFEFFORTLEVEL_DEFAULT | conservative separation |
| MCFEFFORTLEVEL_AGGRESSIVE | aggressive separation |
Definition at line 152 of file sepa_mcf.c.
Function Documentation
◆ mcfnetworkCreate()
|
static |
creates an empty MCF network data structure
- Parameters
-
scip SCIP data structure mcfnetwork MCF network structure
Definition at line 294 of file sepa_mcf.c.
References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.
Referenced by mcfnetworkExtract().
◆ mcfnetworkFree()
|
static |
frees MCF network data structure
- Parameters
-
scip SCIP data structure mcfnetwork MCF network structure
Definition at line 320 of file sepa_mcf.c.
References a, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, SCIPfreeMemoryArrayNull, and SCIPreleaseRow().
Referenced by mcfnetworkExtract(), and SCIP_DECL_SEPAEXITSOL().
◆ mcfnetworkFill()
|
static |
fills the MCF network structure with the MCF data
- Parameters
-
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 371 of file sepa_mcf.c.
References a, ABS, 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, NULL, SCIP_McfNetwork::nuncapacitatedarcs, r, 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().
◆ SCIP_DECL_SORTINDCOMP()
|
static |
comparator method for flow and capacity row candidates
Definition at line 829 of file sepa_mcf.c.
References SCIP_Real.
◆ extractFlowRows()
|
static |
extracts flow conservation from the LP
- Parameters
-
scip SCIP data structure mcfdata internal MCF extraction data to pass to subroutines
Definition at line 843 of file sepa_mcf.c.
References ABS, FALSE, LHSPOSSIBLE, MAX, MAXFLOWCANDDENSITY, MCFdebugMessage, r, 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().
◆ extractCapacityRows()
|
static |
extracts capacity rows from the LP
- Parameters
-
scip SCIP data structure mcfdata internal MCF extraction data to pass to subroutines
Definition at line 1059 of file sepa_mcf.c.
References ABS, BMSclearMemoryArray, SCIP_McfNetwork::colcommodity, LHSASSIGNED, LHSPOSSIBLE, MAX, MCFdebugMessage, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::ncommodities, r, 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().
◆ createNewCommodity()
|
static |
creates a new commodity
- Parameters
-
scip SCIP data structure mcfdata internal MCF extraction data to pass to subroutines
Definition at line 1427 of file sepa_mcf.c.
References MAX, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, and SCIPreallocMemoryArray.
Referenced by extractFlow().
◆ createNewArc()
|
static |
creates a new arc
- Parameters
-
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 1451 of file sepa_mcf.c.
References MAX, SCIP_McfNetwork::nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, and SCIPreallocMemoryArray.
Referenced by findUncapacitatedArcs().
◆ addFlowrowToCommodity()
|
static |
adds the given flow row and all involved columns to the current commodity
- Parameters
-
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 1504 of file sepa_mcf.c.
References SCIP_McfNetwork::colcommodity, INVERTED, LHSASSIGNED, LHSPOSSIBLE, SCIP_McfNetwork::ncommodities, NULL, r, 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().
◆ invertCommodity()
|
static |
- Parameters
-
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 1650 of file sepa_mcf.c.
References INVERTED, LHSASSIGNED, NULL, r, RHSASSIGNED, SCIP_Bool, SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPisInfinity(), SCIProwGetLhs(), SCIProwGetLPPos(), and SCIProwGetRhs().
Referenced by extractFlow().
◆ deleteCommodity()
|
static |
deletes a commodity and removes the flow rows again from the system
- Parameters
-
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 1715 of file sepa_mcf.c.
References SCIP_McfNetwork::colcommodity, FALSE, INVERTED, LHSASSIGNED, SCIP_McfNetwork::ncommodities, NULL, r, RHSASSIGNED, SCIP_Bool, SCIPcolGetLPPos(), SCIPdebugMsg, SCIPgetNLPCols(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetName(), and SCIProwGetNLPNonz().
Referenced by extractFlow().
◆ getFlowrowFit()
|
static |
checks whether the given row fits into the given commodity and returns the possible flow row signs
- Parameters
-
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 1799 of file sepa_mcf.c.
References SCIP_McfNetwork::colcommodity, DISCARDED, FALSE, INVERTED, LHSPOSSIBLE, NULL, r, RHSPOSSIBLE, SCIP_Bool, SCIP_Real, SCIPcolGetLPPos(), SCIPdebugMsg, SCIPgetNLPCols(), SCIPgetNLPRows(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetVals(), and TRUE.
Referenced by extractFlow(), and getNextFlowrow().
◆ getNextFlowrow()
|
static |
returns a flow conservation row that fits into the current commodity, or NULL
- Parameters
-
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 1931 of file sepa_mcf.c.
References FALSE, getFlowrowFit(), INVERTED, SCIP_McfNetwork::ncommodities, NULL, r, SCIP_Bool, SCIP_Real, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPgetLPCols(), SCIPgetNLPCols(), SCIPgetNLPRows(), and SCIProwGetLPPos().
Referenced by extractFlow().
◆ extractFlow()
|
static |
extracts flow conservation rows and puts them into commodities
- Parameters
-
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 2048 of file sepa_mcf.c.
References addFlowrowToCommodity(), BMSclearMemoryArray, SCIP_McfNetwork::colcommodity, createNewCommodity(), deleteCommodity(), getFlowrowFit(), getNextFlowrow(), invertCommodity(), INVERTED, MAX, MCFdebugMessage, MINCOMNODESFRACTION, MINNODES, SCIP_McfNetwork::nnodes, NULL, r, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetLPRows(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIProwGetName(), and TRUE.
Referenced by mcfnetworkExtract().
◆ extractCapacities()
|
static |
Arc-Detection – identifies capacity constraints for the arcs and assigns arc ids to columns and capacity constraints
- Parameters
-
scip SCIP data structure mcfdata internal MCF extraction data to pass to subroutines
Definition at line 2242 of file sepa_mcf.c.
References SCIP_McfNetwork::colcommodity, DISCARDED, LHSASSIGNED, LHSPOSSIBLE, MAX, NULL, r, RHSASSIGNED, RHSPOSSIBLE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPcolGetLPPos(), SCIPdebugMsg, SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPreallocMemoryArray, SCIProwGetCols(), SCIProwGetName(), and SCIProwGetNLPNonz().
Referenced by mcfnetworkExtract().
◆ collectIncidentFlowCols()
|
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
- Parameters
-
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 2406 of file sepa_mcf.c.
References SCIP_McfNetwork::colcommodity, SCIP_McfNetwork::narcs, NULL, SCIP_Bool, SCIPcolGetLPPos(), SCIPgetNLPCols(), SCIProwGetCols(), SCIProwGetNLPNonz(), and TRUE.
Referenced by extractNodes().
◆ getNodeSimilarityScore()
|
static |
compares given row against a base node flow row and calculates a similarity score; score is 0.0 if the rows are incompatible
- Parameters
-
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 2491 of file sepa_mcf.c.
References ABS, FALSE, INVERTED, LHSASSIGNED, MAX, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, r, 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().
◆ extractNodes()
|
static |
assigns node ids to flow conservation constraints
- Parameters
-
scip SCIP data structure mcfdata internal MCF extraction data to pass to subroutines
Definition at line 2692 of file sepa_mcf.c.
References BMSclearMemoryArray, collectIncidentFlowCols(), FALSE, getNodeSimilarityScore(), INVERTED, LHSASSIGNED, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, NULL, r, 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().
◆ fixCommoditySigns()
if there are still undecided commodity signs, fix them to +1
- Parameters
-
scip SCIP data structure mcfdata internal MCF extraction data to pass to subroutines
Definition at line 2963 of file sepa_mcf.c.
Referenced by mcfnetworkExtract().
◆ getIncidentNodes()
|
static |
identifies the (at most) two nodes which contain the given flow variable
- Parameters
-
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 2981 of file sepa_mcf.c.
References INVERTED, LHSASSIGNED, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, NULL, r, RHSASSIGNED, SCIP_Real, SCIPcolGetLPPos(), SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPgetNLPCols(), SCIPgetNLPRows(), and SCIProwGetLPPos().
Referenced by findUncapacitatedArcs(), and identifySourcesTargets().
◆ findUncapacitatedArcs()
|
static |
find uncapacitated arcs for flow columns that have no associated arc yet
- Parameters
-
scip SCIP data structure mcfdata internal MCF extraction data to pass to subroutines
Definition at line 3080 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, NULL, r, 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().
◆ cleanupNetwork()
|
static |
cleans up the network: gets rid of commodities without arcs or with at most one node
- Parameters
-
scip SCIP data structure mcfdata internal MCF extraction data to pass to subroutines
Definition at line 3420 of file sepa_mcf.c.
References a, BMSclearMemoryArray, SCIP_McfNetwork::colcommodity, MAX, MCFdebugMessage, MINCOMNODESFRACTION, MINNODES, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, NULL, r, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcolGetLPPos(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetLPRowsData(), SCIPgetNLPCols(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetNLPNonz(), and TRUE.
Referenced by mcfnetworkExtract().
◆ identifySourcesTargets()
|
static |
for each arc identifies a source and target node
- Parameters
-
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 3738 of file sepa_mcf.c.
References a, 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, NULL, r, 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().
◆ identifyComponent()
|
static |
returns lists of nodes and arcs in the connected component of the given startv
- Parameters
-
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 4087 of file sepa_mcf.c.
References a, SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, SCIP_McfNetwork::narcs, SCIP_McfNetwork::nnodes, NULL, ONSTACK, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, UNKNOWN, and VISITED.
Referenced by mcfnetworkExtract().
◆ mcfnetworkExtract()
|
static |
extracts MCF network structures from the current LP
- Parameters
-
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 4218 of file sepa_mcf.c.
References a, 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, NULL, 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().
◆ unionfindInitSets()
|
static |
initializes a union find data structure by putting each element into its own set
- Parameters
-
representatives mapping an element v to its representative nelems number of elements in the ground set
Definition at line 4691 of file sepa_mcf.c.
Referenced by nodepartitionCreate(), and nodepartitionIsConnected().
◆ unionfindGetRepresentative()
|
static |
applies a union find algorithm to get the representative of v
- Parameters
-
representatives mapping an element v to its representative v element v to get a representative for
Definition at line 4705 of file sepa_mcf.c.
References NULL.
Referenced by nodepartitionGetRepresentative(), and nodepartitionIsConnected().
◆ unionfindJoinSets()
|
static |
joins two sets in the union find framework
- Parameters
-
representatives mapping an element v to its representative rep1 representative of first set rep2 representative of second set
Definition at line 4723 of file sepa_mcf.c.
Referenced by nodepartitionIsConnected(), and nodepartitionJoin().
◆ SCIP_DECL_SORTPTRCOMP()
|
static |
comparison method for weighted nodepairs
Definition at line 4750 of file sepa_mcf.c.
◆ SCIP_DECL_HASHGETKEY()
|
static |
NodePair HashTable gets the key of the given element
Definition at line 4766 of file sepa_mcf.c.
◆ SCIP_DECL_HASHKEYEQ()
|
static |
NodePair HashTable returns TRUE iff both keys are equal; two nodepairs are equal if both nodes equal
Definition at line 4778 of file sepa_mcf.c.
References SCIP_McfNetwork::nnodes, and NULL.
◆ SCIP_DECL_HASHKEYVAL()
|
static |
NodePair HashTable returns the hash value of the key
Definition at line 4819 of file sepa_mcf.c.
References SCIP_McfNetwork::nnodes, and NULL.
◆ nodepairqueueCreate()
|
static |
creates a priority queue and fills it with the given nodepair entries
- Parameters
-
scip SCIP data structure mcfnetwork MCF network structure nodepairqueue pointer to nodepair priority queue
Definition at line 4853 of file sepa_mcf.c.
References a, ABS, SCIP_McfNetwork::colcommodity, FALSE, HASHSIZE_NODEPAIRS, MAX, MIN, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nodeflowrows, SCIP_McfNetwork::nodeflowscales, NULL, 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().
◆ nodepairqueueFree()
|
static |
frees memory of a nodepair queue
- Parameters
-
scip SCIP data structure nodepairqueue pointer to nodepair priority queue
Definition at line 5166 of file sepa_mcf.c.
References NULL, SCIPfreeBuffer, SCIPfreeBufferArray, and SCIPpqueueFree().
Referenced by nodepartitionCreate().
◆ nodepairqueueIsEmpty()
|
static |
returns whether there are any nodepairs left on the queue
- Parameters
-
nodepairqueue nodepair priority queue
Definition at line 5182 of file sepa_mcf.c.
References NULL, and SCIPpqueueFirst().
Referenced by nodepartitionCreate().
◆ nodepairqueueRemove()
|
static |
removes the top element from the nodepair priority queue, returns nodepair entry or NULL
- Parameters
-
nodepairqueue nodepair priority queue
Definition at line 5194 of file sepa_mcf.c.
References NULL, and SCIPpqueueRemove().
Referenced by nodepartitionCreate().
◆ nodepartitionGetRepresentative()
|
static |
returns the representative node in the cluster of the given node
- Parameters
-
nodepartition node partition data structure v node id to get representative for
Definition at line 5211 of file sepa_mcf.c.
References unionfindGetRepresentative().
Referenced by nodepartitionCreate().
◆ nodepartitionJoin()
|
static |
joins two clusters given by their representative nodes
- Parameters
-
nodepartition node partition data structure rep1 representative of first cluster rep2 representative of second cluster
Definition at line 5221 of file sepa_mcf.c.
References unionfindJoinSets().
Referenced by nodepartitionCreate().
◆ nodepartitionCreate()
|
static |
partitions nodes into a small number of clusters
- Parameters
-
scip SCIP data structure mcfnetwork MCF network structure nodepartition pointer to node partition data structure nclusters number of clusters to generate
Definition at line 5232 of file sepa_mcf.c.
References BMSclearMemoryArray, SCIP_McfNetwork::nnodes, nodepairqueueCreate(), nodepairqueueFree(), nodepairqueueIsEmpty(), nodepairqueueRemove(), nodepartitionGetRepresentative(), nodepartitionJoin(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBuffer, SCIPallocBufferArray, SCIPdebug, SCIPdebugMsg, SCIPfreeBufferArray, and unionfindInitSets().
Referenced by separateCuts().
◆ nodepartitionFree()
|
static |
frees node partition data
- Parameters
-
scip SCIP data structure nodepartition pointer to node partition data structure
Definition at line 5382 of file sepa_mcf.c.
References NULL, SCIPfreeBuffer, and SCIPfreeBufferArray.
Referenced by separateCuts().
◆ nodeInPartition()
|
static |
returns whether given node v is in a cluster that belongs to the partition S
- Parameters
-
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 5399 of file sepa_mcf.c.
Referenced by generateClusterCuts(), and nodepartitionIsConnected().
◆ nodepartitionIsConnected()
|
static |
returns whether each of the sets S and T defined by the nodepartition is connected
- Parameters
-
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 5429 of file sepa_mcf.c.
References a, ABS, SCIP_McfNetwork::arccapacityrows, SCIP_McfNetwork::arccapacityscales, SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, FALSE, MCFdebugMessage, SCIP_McfNetwork::narcs, SCIP_McfNetwork::nnodes, SCIP_McfNetwork::nodeflowrows, nodeInPartition(), NULL, 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().
◆ addCut()
|
static |
adds given cut to LP if violated
- Parameters
-
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 5766 of file sepa_mcf.c.
References FALSE, NULL, 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().
◆ generateClusterCuts()
|
static |
enumerates cuts between subsets of the clusters generates single-node cuts if nodepartition == NULL, otherwise generates cluster cuts
- Parameters
-
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 5853 of file sepa_mcf.c.
References a, ABS, 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(), NULL, POSTPROCESS, r, 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().
◆ separateCuts()
|
static |
searches and adds MCF network cuts that separate the given primal solution
- Parameters
-
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 6596 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(), NULL, 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().
◆ SCIP_DECL_SEPACOPY()
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 6771 of file sepa_mcf.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaMcf(), SCIPsepaGetName(), and SEPA_NAME.
◆ SCIP_DECL_SEPAFREE()
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 6785 of file sepa_mcf.c.
References NULL, SCIP_OKAY, SCIPfreeMemory, SCIPsepaGetData(), and SCIPsepaSetData().
◆ SCIP_DECL_SEPAINITSOL()
|
static |
solving process initialization method of separator (called when branch and bound process is about to begin)
Definition at line 6805 of file sepa_mcf.c.
References MCFEFFORTLEVEL_OFF, NULL, SCIP_OKAY, SCIPsepaGetData(), and TRUE.
◆ SCIP_DECL_SEPAEXITSOL()
|
static |
solving process deinitialization method of separator (called before branch and bound process data is freed)
Definition at line 6823 of file sepa_mcf.c.
References mcfnetworkFree(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeMemoryArrayNull, and SCIPsepaGetData().
◆ SCIP_DECL_SEPAEXECLP()
|
static |
LP solution separation method of separator
Definition at line 6847 of file sepa_mcf.c.
References NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPgetLPSolstat(), SCIPgetNLPBranchCands(), SCIPisStopped(), and separateCuts().
◆ SCIP_DECL_SEPAEXECSOL()
|
static |
arbitrary primal solution separation method of separator
Definition at line 6874 of file sepa_mcf.c.
References SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, and separateCuts().