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 |
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 (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, int depth, 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, int depth, 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 56 of file sepa_mcf.c.
#define SEPA_NAME "mcf" |
Definition at line 84 of file sepa_mcf.c.
#define SEPA_DESC "multi-commodity-flow network cut separator" |
Definition at line 85 of file sepa_mcf.c.
#define SEPA_PRIORITY -10000 |
Definition at line 86 of file sepa_mcf.c.
#define SEPA_FREQ 0 |
Definition at line 87 of file sepa_mcf.c.
#define SEPA_MAXBOUNDDIST 0.0 |
Definition at line 88 of file sepa_mcf.c.
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 89 of file sepa_mcf.c.
#define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 90 of file sepa_mcf.c.
#define DEFAULT_NCLUSTERS 5 |
number of clusters to generate in the shrunken network
Definition at line 93 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 94 of file sepa_mcf.c.
#define DEFAULT_MAXTESTDELTA 20 |
maximal number of different deltas to try (-1: unlimited) for CMIR
Definition at line 95 of file sepa_mcf.c.
#define DEFAULT_TRYNEGSCALING FALSE |
should negative values also be tested in scaling? for CMIR
Definition at line 96 of file sepa_mcf.c.
#define DEFAULT_FIXINTEGRALRHS TRUE |
should an additional variable be complemented if f0 = 0? for CMIR
Definition at line 97 of file sepa_mcf.c.
#define DEFAULT_DYNAMICCUTS TRUE |
should generated cuts be removed from the LP if they are no longer tight?
Definition at line 98 of file sepa_mcf.c.
#define DEFAULT_MODELTYPE 0 |
model type of network (0: auto, 1:directed, 2:undirected)
Definition at line 99 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 100 of file sepa_mcf.c.
#define DEFAULT_MAXSEPACUTSROOT 200 |
maximal number of cuts separated per separation round in root node (-1: unlimited)
Definition at line 101 of file sepa_mcf.c.
#define DEFAULT_MAXINCONSISTENCYRATIO 0.02 |
maximum inconsistency ratio (inconsistencies/(arcs*commodities)) at all
Definition at line 102 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 103 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 104 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
#define DEFAULT_SEPARATESINGLENODECUTS TRUE |
should we separate inequalities based on single node cuts
Definition at line 105 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
#define DEFAULT_SEPARATEFLOWCUTSET TRUE |
should we separate flowcutset inequalities
Definition at line 106 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
#define DEFAULT_SEPARATEKNAPSACK TRUE |
should we separate knapsack cover inequalities
Definition at line 107 of file sepa_mcf.c.
Referenced by SCIPincludeSepaMcf().
#define BOUNDSWITCH 0.5 |
Definition at line 110 of file sepa_mcf.c.
#define POSTPROCESS TRUE |
Definition at line 111 of file sepa_mcf.c.
#define USEVBDS TRUE |
Definition at line 112 of file sepa_mcf.c.
#define MINFRAC 0.05 |
Definition at line 113 of file sepa_mcf.c.
#define MAXFRAC 0.999 |
Definition at line 114 of file sepa_mcf.c.
#define MAXCOLS 2000000 |
#define MAXAGGRLEN | ( | nvars | ) |
maximal length of base inequality
Definition at line 117 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 118 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 119 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 120 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 121 of file sepa_mcf.c.
Referenced by separateCuts().
#define MAXNETWORKS 4 |
maximum number of networks to consider
Definition at line 122 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 123 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 124 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 125 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 126 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 127 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 128 of file sepa_mcf.c.
Referenced by findUncapacitatedArcs().
#define HASHSIZE_NODEPAIRS 500 |
minimal size of hash table for nodepairs
Definition at line 129 of file sepa_mcf.c.
Referenced by nodepairqueueCreate().
Definition at line 145 of file sepa_mcf.c.
Referenced by cleanupNetwork(), extractCapacityRows(), extractFlow(), extractFlowRows(), findUncapacitatedArcs(), generateClusterCuts(), identifySourcesTargets(), and separateCuts().
#define LHSPOSSIBLE 1u |
we may use the constraint as lhs <= a*x
Definition at line 293 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 294 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 295 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 296 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 297 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 298 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 299 of file sepa_mcf.c.
Referenced by extractCapacityRows().
#define UNKNOWN 0 |
node has not yet been seen
Definition at line 4104 of file sepa_mcf.c.
Referenced by identifyComponent(), and mcfnetworkExtract().
#define ONSTACK 1 |
node is currently on the processing stack
Definition at line 4105 of file sepa_mcf.c.
Referenced by identifyComponent().
#define VISITED 2 |
node has been visited and assigned to some component
Definition at line 4106 of file sepa_mcf.c.
typedef enum SCIP_McfModeltype SCIP_MCFMODELTYPE |
Definition at line 159 of file sepa_mcf.c.
typedef enum McfEffortLevel MCFEFFORTLEVEL |
Definition at line 168 of file sepa_mcf.c.
typedef struct SCIP_McfNetwork SCIP_MCFNETWORK |
Definition at line 190 of file sepa_mcf.c.
typedef struct mcfdata MCFDATA |
internal MCF extraction data to pass to subroutines
Definition at line 259 of file sepa_mcf.c.
typedef struct nodepair NODEPAIRENTRY |
Definition at line 268 of file sepa_mcf.c.
typedef struct nodepairqueue NODEPAIRQUEUE |
Definition at line 276 of file sepa_mcf.c.
typedef struct nodepartition NODEPARTITION |
Definition at line 287 of file sepa_mcf.c.
enum SCIP_McfModeltype |
model type of the network
Definition at line 153 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 162 of file sepa_mcf.c.
|
static |
creates an empty MCF network data structure
scip | SCIP data structure |
mcfnetwork | MCF network structure |
Definition at line 304 of file sepa_mcf.c.
References assert(), NULL, 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 330 of file sepa_mcf.c.
References a, assert(), NULL, 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 381 of file sepa_mcf.c.
References a, ABS, SCIP_McfNetwork::arccapacityrows, SCIP_McfNetwork::arccapacityscales, SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, assert(), BMSclearMemoryArray, c, SCIP_McfNetwork::colcommodity, FALSE, i, INVERTED, LHSASSIGNED, SCIP_McfNetwork::modeltype, narcs, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, nnodes, 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(), SCIPfreeBufferArray, SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetNLPCols(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetNLPNonz(), and SCIProwGetVals().
Referenced by mcfnetworkExtract().
|
static |
comparator method for flow and capacity row candidates
Definition at line 839 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 853 of file sepa_mcf.c.
References ABS, assert(), FALSE, i, LHSPOSSIBLE, MAX, MAXFLOWCANDDENSITY, MCFdebugMessage, nbinvars, nintvars, 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().
|
static |
extracts capacity rows from the LP
scip | SCIP data structure |
mcfdata | internal MCF extraction data to pass to subroutines |
Definition at line 1069 of file sepa_mcf.c.
References ABS, assert(), BMSclearMemoryArray, c, i, LHSASSIGNED, LHSPOSSIBLE, MAX, MCFdebugMessage, NULL, 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().
|
static |
creates a new commodity
scip | SCIP data structure |
mcfdata | internal MCF extraction data to pass to subroutines |
Definition at line 1439 of file sepa_mcf.c.
References assert(), 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 1463 of file sepa_mcf.c.
References assert(), MAX, nnodes, NULL, 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 1516 of file sepa_mcf.c.
References assert(), c, i, INVERTED, LHSASSIGNED, LHSPOSSIBLE, 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().
|
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 1662 of file sepa_mcf.c.
References assert(), c, i, INVERTED, LHSASSIGNED, NULL, r, 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 1727 of file sepa_mcf.c.
References assert(), c, FALSE, i, INVERTED, LHSASSIGNED, NULL, r, 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 1811 of file sepa_mcf.c.
References assert(), 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().
|
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 1943 of file sepa_mcf.c.
References assert(), c, FALSE, getFlowrowFit(), i, INVERTED, NULL, r, 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 2060 of file sepa_mcf.c.
References addFlowrowToCommodity(), assert(), BMSclearMemoryArray, c, createNewCommodity(), deleteCommodity(), getFlowrowFit(), getNextFlowrow(), i, invertCommodity(), INVERTED, MAX, MCFdebugMessage, MINCOMNODESFRACTION, MINNODES, nnodes, NULL, r, 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 2254 of file sepa_mcf.c.
References assert(), c, DISCARDED, i, 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().
|
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 2425 of file sepa_mcf.c.
References assert(), c, i, narcs, NULL, 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 2510 of file sepa_mcf.c.
References ABS, assert(), c, FALSE, i, INVERTED, LHSASSIGNED, MAX, narcs, 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().
|
static |
assigns node ids to flow conservation constraints
scip | SCIP data structure |
mcfdata | internal MCF extraction data to pass to subroutines |
Definition at line 2711 of file sepa_mcf.c.
References assert(), BMSclearMemoryArray, c, collectIncidentFlowCols(), FALSE, getNodeSimilarityScore(), i, INVERTED, LHSASSIGNED, narcs, 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().
|
static |
if there are still undecided commodity signs, fix them to +1
mcfdata | internal MCF extraction data to pass to subroutines |
Definition at line 2987 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 3004 of file sepa_mcf.c.
References assert(), c, i, INVERTED, LHSASSIGNED, nnodes, NULL, r, 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 3103 of file sepa_mcf.c.
References assert(), c, createNewArc(), getIncidentNodes(), i, LHSASSIGNED, MCFdebugMessage, narcs, 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().
|
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 3443 of file sepa_mcf.c.
References a, assert(), BMSclearMemoryArray, c, i, MAX, MCFdebugMessage, MINCOMNODESFRACTION, MINNODES, narcs, nnodes, NULL, r, 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 3761 of file sepa_mcf.c.
References a, assert(), BMSclearMemoryArray, c, getIncidentNodes(), i, LHSASSIGNED, MCFdebugMessage, MCFEFFORTLEVEL_DEFAULT, MCFEFFORTLEVEL_OFF, narcs, 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(), sepadata, 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 4110 of file sepa_mcf.c.
References a, assert(), narcs, nnodes, NULL, 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 4241 of file sepa_mcf.c.
References assert(), BMSclearMemoryArray, cleanupNetwork(), extractCapacities(), extractCapacityRows(), extractFlow(), extractFlowRows(), extractNodes(), FALSE, findUncapacitatedArcs(), fixCommoditySigns(), i, identifyComponent(), identifySourcesTargets(), MAX, MAXFLOWVARFLOWROWRATIO, MAXNETWORKS, MCFEFFORTLEVEL_OFF, mcfnetworkCreate(), mcfnetworkFill(), mcfnetworkFree(), MINARCS, MINNODES, narcs, nnodes, SCIP_McfNetwork::nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPfreeMemoryArrayNull, SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPreallocMemoryArray, sepadata, 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 4716 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 4730 of file sepa_mcf.c.
References assert(), and NULL.
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 4748 of file sepa_mcf.c.
References assert().
Referenced by nodepartitionIsConnected(), and nodepartitionJoin().
|
static |
comparison method for weighted nodepairs
Definition at line 4775 of file sepa_mcf.c.
|
static |
NodePair HashTable gets the key of the given element
Definition at line 4791 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 4803 of file sepa_mcf.c.
|
static |
NodePair HashTable returns the hash value of the key
Definition at line 4844 of file sepa_mcf.c.
|
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 4878 of file sepa_mcf.c.
References a, ABS, SCIP_McfNetwork::arccapacityrows, SCIP_McfNetwork::arccapacityscales, SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, assert(), c, SCIP_McfNetwork::colcommodity, FALSE, HASHSIZE_NODEPAIRS, i, MAX, MIN, narcs, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, 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().
|
static |
frees memory of a nodepair queue
scip | SCIP data structure |
nodepairqueue | pointer to nodepair priority queue |
Definition at line 5191 of file sepa_mcf.c.
References assert(), NULL, 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 5207 of file sepa_mcf.c.
References assert(), NULL, SCIP_Bool, and 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 5219 of file sepa_mcf.c.
References assert(), NULL, and 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 5236 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 5246 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 5257 of file sepa_mcf.c.
References assert(), BMSclearMemoryArray, c, nnodes, SCIP_McfNetwork::nnodes, nodepairqueueCreate(), nodepairqueueFree(), nodepairqueueIsEmpty(), nodepairqueueRemove(), nodepartitionGetRepresentative(), nodepartitionJoin(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, SCIPallocBufferArray, 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 5405 of file sepa_mcf.c.
References assert(), NULL, 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 5422 of file sepa_mcf.c.
References assert(), FALSE, NULL, and SCIP_Bool.
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 5452 of file sepa_mcf.c.
References a, SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, assert(), FALSE, narcs, SCIP_McfNetwork::narcs, nnodes, nodeInPartition(), NULL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, 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 5789 of file sepa_mcf.c.
References assert(), cutoff, FALSE, i, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarsToRow(), SCIPallocBufferArray, SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetCutEfficacy(), SCIPgetNLPs(), SCIPgetRowSolActivity(), SCIPgetVarsData(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetRank(), SCIPseparateRelaxedKnapsack(), SCIPsnprintf(), sepadata, sol, and vars.
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 |
depth | current depth |
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 5876 of file sepa_mcf.c.
References a, ABS, addCut(), SCIP_McfNetwork::arccapacityrows, SCIP_McfNetwork::arccapacityscales, SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, assert(), BMSclearMemoryArray, BOUNDSWITCH, c, SCIP_McfNetwork::colcommodity, cutoff, depth, FALSE, MAXAGGRLEN, MAXCAPACITYSLACK, MAXFRAC, MCFdebugMessage, MCFEFFORTLEVEL_AGGRESSIVE, MCFEFFORTLEVEL_DEFAULT, MINFRAC, SCIP_McfNetwork::modeltype, narcs, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, nnodes, SCIP_McfNetwork::nnodes, SCIP_McfNetwork::nodeflowinverted, SCIP_McfNetwork::nodeflowrows, SCIP_McfNetwork::nodeflowscales, nodeInPartition(), nodepartitionIsConnected(), NULL, nvars, 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, 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(), sepadata, sol, TRUE, USEVBDS, and var.
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 |
depth | current depth |
result | pointer to store the result of the separation call |
Definition at line 6620 of file sepa_mcf.c.
References assert(), cutoff, depth, FALSE, generateClusterCuts(), i, MAXARCNODERATIO, MAXCOLROWRATIO, MAXCOLS, MCFdebugMessage, MCFEFFORTLEVEL_DEFAULT, MCFEFFORTLEVEL_OFF, mcfnetworkExtract(), MINCOLROWRATIO, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, nodepartitionCreate(), nodepartitionFree(), NULL, nvars, result, 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(), sepadata, sol, 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 6796 of file sepa_mcf.c.
References assert(), NULL, 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 6810 of file sepa_mcf.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeMemory, SCIPsepaGetData(), SCIPsepaSetData(), and sepadata.
|
static |
solving process initialization method of separator (called when branch and bound process is about to begin)
Definition at line 6830 of file sepa_mcf.c.
References assert(), MCFEFFORTLEVEL_OFF, NULL, SCIP_OKAY, SCIPsepaGetData(), sepadata, and TRUE.
|
static |
solving process deinitialization method of separator (called before branch and bound process data is freed)
Definition at line 6848 of file sepa_mcf.c.
References assert(), i, mcfnetworkFree(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeMemoryArrayNull, SCIPsepaGetData(), and sepadata.
|
static |
LP solution separation method of separator
Definition at line 6872 of file sepa_mcf.c.
References depth, NULL, result, 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 6899 of file sepa_mcf.c.
References depth, result, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, separateCuts(), and sol.