Detailed Description

multi-commodity-flow network cut separator

Author: Tobias Achterberg; Christian Raack

We try to identify a multi-commodity flow structure in the LP relaxation of the following type:

(1) sum_{a in delta^+(v)} f_a^k - sum_{a in delta^-(v)} f_a^k <= -d_v^k for all v in V and k in K (2) sum_{k in K} f_a^k - c_a x_a <= 0 for all a in A

Constraints (1) are flow conservation constraints, which say that for each commodity k and node v the outflow (delta^+(v)) minus the inflow (delta^-(v)) of a node v must not exceed the negative of the demand of node v in commodity k. To say it the other way around, inflow minus outflow must be at least equal to the demand. Constraints (2) are the arc capacity constraints, which say that the sum of all flow over an arc a must not exceed its capacity c_a x_a, with x being a binary or integer variable. c_a x_a does not need to be a single product of a capacity and an integer variable; we also accept general scalar products.

Definition in file sepa_mcf.c.

#include <assert.h>
#include <string.h>
#include "scip/sepa_mcf.h"
#include "scip/cons_knapsack.h"
#include "scip/pub_misc.h"

Go to the source code of this file.

Macros
#define	BETTERWEIGHTFORDEMANDNODES

#define	SEPA_NAME "mcf"

#define	SEPA_DESC "multi-commodity-flow network cut separator"

#define	SEPA_PRIORITY -10000

#define	SEPA_FREQ 0

#define	SEPA_MAXBOUNDDIST 0.0

#define	SEPA_USESSUBSCIP FALSE

#define	SEPA_DELAY FALSE

#define	DEFAULT_NCLUSTERS 5

#define	DEFAULT_MAXWEIGHTRANGE 1e+06

#define	DEFAULT_MAXTESTDELTA 20

#define	DEFAULT_TRYNEGSCALING FALSE

#define	DEFAULT_FIXINTEGRALRHS TRUE

#define	DEFAULT_DYNAMICCUTS TRUE

#define	DEFAULT_MODELTYPE 0

#define	DEFAULT_MAXSEPACUTS 100

#define	DEFAULT_MAXSEPACUTSROOT 200

#define	DEFAULT_MAXINCONSISTENCYRATIO 0.02

#define	DEFAULT_MAXARCINCONSISTENCYRATIO 0.5

#define	DEFAULT_CHECKCUTSHORECONNECTIVITY TRUE

#define	DEFAULT_SEPARATESINGLENODECUTS TRUE

#define	DEFAULT_SEPARATEFLOWCUTSET TRUE

#define	DEFAULT_SEPARATEKNAPSACK TRUE

#define	BOUNDSWITCH 0.5

#define	USEVBDS TRUE

#define	ALLOWLOCAL TRUE

#define	MINFRAC 0.05

#define	MAXFRAC 0.999

#define	MAXCOLS 2000000

#define	MAXAGGRLEN(nvars) (0.1*(nvars)+1000)

#define	MINCOLROWRATIO 0.01

#define	MAXCOLROWRATIO 100.0

#define	MAXFLOWVARFLOWROWRATIO 100.0

#define	MAXARCNODERATIO 100.0

#define	MAXNETWORKS 4

#define	MAXFLOWCANDDENSITY 0.1

#define	MINCOMNODESFRACTION 0.5

#define	MINNODES 3

#define	MINARCS 3

#define	MAXCAPACITYSLACK 0.1

#define	UNCAPACITATEDARCSTRESHOLD 0.8

#define	HASHSIZE_NODEPAIRS 131101

#define	MCFdebugMessage while(FALSE) printf

#define	LHSPOSSIBLE 1u

#define	RHSPOSSIBLE 2u

#define	LHSASSIGNED 4u

#define	RHSASSIGNED 8u

#define	INVERTED 16u

#define	DISCARDED 32u

#define	UNDIRECTED 64u

#define	UNKNOWN 0

#define	ONSTACK 1

#define	VISITED 2

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, 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_MCFNETWORK mcfnetwork, NODEPARTITION nodepartition, int ncuts, SCIP_Bool cutoff)

static SCIP_RETCODE	separateCuts (SCIP scip, SCIP_SEPA sepa, SCIP_SOL sol, 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

#define BETTERWEIGHTFORDEMANDNODES

Definition at line 46 of file sepa_mcf.c.

#define SEPA_NAME "mcf"

Definition at line 56 of file sepa_mcf.c.

Referenced by SCIP_DECL_SEPACOPY(), and SCIPincludeSepaMcf().

#define SEPA_DESC "multi-commodity-flow network cut separator"

Definition at line 57 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define SEPA_PRIORITY -10000

Definition at line 58 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define SEPA_FREQ 0

Definition at line 59 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define SEPA_MAXBOUNDDIST 0.0

Definition at line 60 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define SEPA_USESSUBSCIP FALSE

does the separator use a secondary SCIP instance?

Definition at line 61 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define SEPA_DELAY FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 62 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define DEFAULT_NCLUSTERS 5

number of clusters to generate in the shrunken network

Definition at line 65 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define DEFAULT_MAXWEIGHTRANGE 1e+06

maximal valid range max(|weights|)/min(|weights|) of row weights for CMIR

Definition at line 66 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define DEFAULT_MAXTESTDELTA 20

maximal number of different deltas to try (-1: unlimited) for CMIR

Definition at line 67 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define DEFAULT_TRYNEGSCALING FALSE

should negative values also be tested in scaling? for CMIR

Definition at line 68 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define DEFAULT_FIXINTEGRALRHS TRUE

should an additional variable be complemented if f0 = 0? for CMIR

Definition at line 69 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define DEFAULT_DYNAMICCUTS TRUE

should generated cuts be removed from the LP if they are no longer tight?

Definition at line 70 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define DEFAULT_MODELTYPE 0

model type of network (0: auto, 1:directed, 2:undirected)

Definition at line 71 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define DEFAULT_MAXSEPACUTS 100

maximal number of cuts separated per separation round (-1: unlimited)

Definition at line 72 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define DEFAULT_MAXSEPACUTSROOT 200

maximal number of cuts separated per separation round in root node (-1: unlimited)

Definition at line 73 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define DEFAULT_MAXINCONSISTENCYRATIO 0.02

maximum inconsistency ratio (inconsistencies/(arcs*commodities)) at all

Definition at line 74 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define DEFAULT_MAXARCINCONSISTENCYRATIO 0.5

maximum inconsistency ratio for arcs not to be deleted

Definition at line 75 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define DEFAULT_CHECKCUTSHORECONNECTIVITY TRUE

should we only separate if the cuts shores are connected

Definition at line 76 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define DEFAULT_SEPARATESINGLENODECUTS TRUE

should we separate inequalities based on single node cuts

Definition at line 77 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define DEFAULT_SEPARATEFLOWCUTSET TRUE

should we separate flowcutset inequalities

Definition at line 78 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define DEFAULT_SEPARATEKNAPSACK TRUE

should we separate knapsack cover inequalities

Definition at line 79 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

#define BOUNDSWITCH 0.5

Definition at line 82 of file sepa_mcf.c.

Referenced by generateClusterCuts().

#define USEVBDS TRUE

Definition at line 83 of file sepa_mcf.c.

Referenced by generateClusterCuts().

#define ALLOWLOCAL TRUE

Definition at line 84 of file sepa_mcf.c.

Referenced by generateClusterCuts().

#define MINFRAC 0.05

Definition at line 85 of file sepa_mcf.c.

Referenced by generateClusterCuts().

#define MAXFRAC 0.999

Definition at line 86 of file sepa_mcf.c.

Referenced by generateClusterCuts().

#define MAXCOLS 2000000

maximum number of columns

Definition at line 88 of file sepa_mcf.c.

Referenced by separateCuts().

#define MAXAGGRLEN ( nvars ) (0.1*(nvars)+1000)

maximal length of base inequality

Definition at line 89 of file sepa_mcf.c.

Referenced by generateClusterCuts().

#define MINCOLROWRATIO 0.01

minimum ratio cols/rows for the separator to be switched on

Definition at line 90 of file sepa_mcf.c.

Referenced by separateCuts().

#define MAXCOLROWRATIO 100.0

maximum ratio cols/rows for the separator to be switched on

Definition at line 91 of file sepa_mcf.c.

Referenced by separateCuts().

#define MAXFLOWVARFLOWROWRATIO 100.0

maximum ratio flowvars/flowrows for the separator to be switched on

Definition at line 92 of file sepa_mcf.c.

Referenced by mcfnetworkExtract().

#define MAXARCNODERATIO 100.0

maximum ratio arcs/nodes for the separator to be switched on

Definition at line 93 of file sepa_mcf.c.

Referenced by separateCuts().

#define MAXNETWORKS 4

maximum number of networks to consider

Definition at line 94 of file sepa_mcf.c.

Referenced by mcfnetworkExtract().

#define MAXFLOWCANDDENSITY 0.1

maximum density of rows to be accepted as flow candidates

Definition at line 95 of file sepa_mcf.c.

Referenced by extractFlowRows().

#define MINCOMNODESFRACTION 0.5

minimal size of commodity relative to largest commodity to keep it in the network

Definition at line 96 of file sepa_mcf.c.

Referenced by cleanupNetwork(), and extractFlow().

#define MINNODES 3

minimal number of nodes in network to keep it for separation

Definition at line 97 of file sepa_mcf.c.

Referenced by cleanupNetwork(), extractFlow(), and mcfnetworkExtract().

#define MINARCS 3

minimal number of arcs in network to keep it for separation

Definition at line 98 of file sepa_mcf.c.

Referenced by mcfnetworkExtract().

#define MAXCAPACITYSLACK 0.1

maximal slack of weighted capacity constraints to use in aggregation

Definition at line 99 of file sepa_mcf.c.

Referenced by generateClusterCuts().

#define UNCAPACITATEDARCSTRESHOLD 0.8

threshold for the percentage of commodities an uncapacitated arc should appear in

Definition at line 100 of file sepa_mcf.c.

Referenced by findUncapacitatedArcs().

#define HASHSIZE_NODEPAIRS 131101

minimal size of hash table for nodepairs

Definition at line 101 of file sepa_mcf.c.

Referenced by nodepairqueueCreate().

#define MCFdebugMessage while(FALSE) printf

Definition at line 117 of file sepa_mcf.c.

Referenced by cleanupNetwork(), extractCapacityRows(), extractFlow(), extractFlowRows(), findUncapacitatedArcs(), generateClusterCuts(), identifySourcesTargets(), mcfnetworkExtract(), mcfnetworkFill(), nodepartitionIsConnected(), and separateCuts().

#define LHSPOSSIBLE 1u

we may use the constraint as lhs <= a*x

Definition at line 265 of file sepa_mcf.c.

Referenced by addFlowrowToCommodity(), extractCapacities(), extractCapacityRows(), extractFlowRows(), and getFlowrowFit().

#define RHSPOSSIBLE 2u

we may use the constraint as a*x <= rhs

Definition at line 266 of file sepa_mcf.c.

Referenced by addFlowrowToCommodity(), extractCapacities(), extractCapacityRows(), extractFlowRows(), and getFlowrowFit().

#define LHSASSIGNED 4u

we have chosen to use the constraint as lhs <= a*x

Definition at line 267 of file sepa_mcf.c.

Referenced by addFlowrowToCommodity(), deleteCommodity(), extractCapacities(), extractCapacityRows(), extractNodes(), findUncapacitatedArcs(), getIncidentNodes(), getNodeSimilarityScore(), identifySourcesTargets(), invertCommodity(), and mcfnetworkFill().

#define RHSASSIGNED 8u

we have chosen to use the constraint as a*x <= rhs

Definition at line 268 of file sepa_mcf.c.

Referenced by addFlowrowToCommodity(), deleteCommodity(), extractCapacities(), extractCapacityRows(), extractNodes(), findUncapacitatedArcs(), getIncidentNodes(), getNodeSimilarityScore(), identifySourcesTargets(), invertCommodity(), and mcfnetworkFill().

#define INVERTED 16u

we need to invert the row

Definition at line 269 of file sepa_mcf.c.

Referenced by addFlowrowToCommodity(), deleteCommodity(), extractFlow(), extractNodes(), getFlowrowFit(), getIncidentNodes(), getNextFlowrow(), getNodeSimilarityScore(), invertCommodity(), and mcfnetworkFill().

#define DISCARDED 32u

we have chosen to not use the constraint

Definition at line 270 of file sepa_mcf.c.

Referenced by extractCapacities(), and getFlowrowFit().

#define UNDIRECTED 64u

the capacity candidate has two flow variables for a commodity

Definition at line 271 of file sepa_mcf.c.

Referenced by extractCapacityRows().

#define UNKNOWN 0

node has not yet been seen

Definition at line 4066 of file sepa_mcf.c.

Referenced by identifyComponent(), lpiStrongbranch(), mcfnetworkExtract(), and spxSolve().

#define ONSTACK 1

node is currently on the processing stack

Definition at line 4067 of file sepa_mcf.c.

Referenced by identifyComponent().

#define VISITED 2

node has been visited and assigned to some component

Definition at line 4068 of file sepa_mcf.c.

Referenced by identifyComponent(), and mcfnetworkExtract().

Typedef Documentation

typedef enum SCIP_McfModeltype SCIP_MCFMODELTYPE

Definition at line 131 of file sepa_mcf.c.

typedef enum McfEffortLevel MCFEFFORTLEVEL

Definition at line 140 of file sepa_mcf.c.

typedef struct SCIP_McfNetwork SCIP_MCFNETWORK

Definition at line 162 of file sepa_mcf.c.

typedef struct mcfdata MCFDATA

internal MCF extraction data to pass to subroutines

Definition at line 231 of file sepa_mcf.c.

typedef struct nodepair NODEPAIRENTRY

Definition at line 240 of file sepa_mcf.c.

typedef struct nodepairqueue NODEPAIRQUEUE

Definition at line 248 of file sepa_mcf.c.

typedef struct nodepartition NODEPARTITION

Definition at line 259 of file sepa_mcf.c.

Enumeration Type Documentation

enum SCIP_McfModeltype

model type of the network

Enumerator
SCIP_MCFMODELTYPE_AUTO	model type should be detected automatically
SCIP_MCFMODELTYPE_DIRECTED	directed network where each arc has its own capacity
SCIP_MCFMODELTYPE_UNDIRECTED	directed network where anti-parallel arcs share the capacity

Definition at line 125 of file sepa_mcf.c.

enum McfEffortLevel

effort level for separation

Enumerator
MCFEFFORTLEVEL_OFF	no separation
MCFEFFORTLEVEL_DEFAULT	conservative separation
MCFEFFORTLEVEL_AGGRESSIVE	aggressive separation

Definition at line 134 of file sepa_mcf.c.

Function Documentation

static SCIP_RETCODE mcfnetworkCreate	(	SCIP *	scip,
		SCIP_MCFNETWORK **	mcfnetwork
	)

static

creates an empty MCF network data structure

Parameters

scip	SCIP data structure
mcfnetwork	MCF network structure

Definition at line 276 of file sepa_mcf.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

Referenced by mcfnetworkExtract().

static SCIP_RETCODE mcfnetworkFree	(	SCIP *	scip,
		SCIP_MCFNETWORK **	mcfnetwork
	)

static

frees MCF network data structure

Parameters

scip	SCIP data structure
mcfnetwork	MCF network structure

Definition at line 302 of file sepa_mcf.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeMemory, SCIPfreeMemoryArrayNull, and SCIPreleaseRow().

Referenced by mcfnetworkExtract(), and SCIP_DECL_SEPAEXITSOL().

static SCIP_RETCODE mcfnetworkFill	(	SCIP *	scip,
		SCIP_MCFNETWORK *	mcfnetwork,
		MCFDATA *	mcfdata,
		int *	compnodeid,
		int *	compnodes,
		int	ncompnodes,
		int *	comparcs,
		int	ncomparcs
	)

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 353 of file sepa_mcf.c.

References SCIP_McfNetwork::arccapacityrows, SCIP_McfNetwork::arccapacityscales, SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, BMSclearMemoryArray, SCIP_McfNetwork::colcommodity, FALSE, INVERTED, LHSASSIGNED, MCFdebugMessage, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, SCIP_McfNetwork::nodeflowinverted, SCIP_McfNetwork::nodeflowrows, SCIP_McfNetwork::nodeflowscales, NULL, SCIP_McfNetwork::nuncapacitatedarcs, RHSASSIGNED, SCIP_CALL, SCIP_MCFMODELTYPE_AUTO, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcaptureRow(), SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPfreeBufferArray, SCIPgetLPCols(), SCIPgetLPColsData(), SCIPgetLPRows(), SCIPgetLPRowsData(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetVals(), SCIPvarGetLbGlobal(), SCIPvarGetName(), and SCIPvarGetUbGlobal().

Referenced by mcfnetworkExtract().

static SCIP_DECL_SORTINDCOMP ( compCands )

static

comparator method for flow and capacity row candidates

Definition at line 811 of file sepa_mcf.c.

References SCIP_Real.

static SCIP_RETCODE extractFlowRows	(	SCIP *	scip,
		MCFDATA *	mcfdata
	)

static

extracts flow conservation from the LP

Parameters

scip	SCIP data structure
mcfdata	internal MCF extraction data to pass to subroutines

Definition at line 825 of file sepa_mcf.c.

References FALSE, LHSPOSSIBLE, MAX, MAXFLOWCANDDENSITY, MCFdebugMessage, RHSPOSSIBLE, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPABORT, SCIPallocMemoryArray, SCIPcolGetVar(), SCIPdebugMessage, SCIPerrorMessage, SCIPgetLPRowsData(), SCIPgetNLPCols(), SCIPisEQ(), SCIPisInfinity(), SCIPisPositive(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetDualsol(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsModifiable(), SCIPsortInd(), and SCIPvarGetType().

Referenced by mcfnetworkExtract().

static SCIP_RETCODE extractCapacityRows	(	SCIP *	scip,
		MCFDATA *	mcfdata
	)

static

extracts capacity rows from the LP

Parameters

scip	SCIP data structure
mcfdata	internal MCF extraction data to pass to subroutines

Definition at line 1041 of file sepa_mcf.c.

References BMSclearMemoryArray, SCIP_McfNetwork::colcommodity, LHSASSIGNED, LHSPOSSIBLE, MAX, MCFdebugMessage, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::ncommodities, RHSASSIGNED, RHSPOSSIBLE, SCIP_CALL, SCIP_INVALID, SCIP_INVALIDDATA, SCIP_MCFMODELTYPE_AUTO, SCIP_MCFMODELTYPE_DIRECTED, SCIP_MCFMODELTYPE_UNDIRECTED, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPdebugMessage, 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 SCIP_RETCODE createNewCommodity	(	SCIP *	scip,
		MCFDATA *	mcfdata
	)

static

creates a new commodity

Parameters

scip	SCIP data structure
mcfdata	internal MCF extraction data to pass to subroutines

Definition at line 1409 of file sepa_mcf.c.

References MAX, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and SCIPreallocMemoryArray.

Referenced by extractFlow().

static SCIP_RETCODE createNewArc	(	SCIP *	scip,
		MCFDATA *	mcfdata,
		int	source,
		int	target,
		int *	newarcid
	)

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 1433 of file sepa_mcf.c.

References MAX, SCIP_McfNetwork::nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and SCIPreallocMemoryArray.

Referenced by findUncapacitatedArcs().

static void addFlowrowToCommodity	(	SCIP *	scip,
		MCFDATA *	mcfdata,
		SCIP_ROW *	row,
		unsigned char	rowsign,
		int *	comcolids,
		int *	ncomcolids
	)

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 1486 of file sepa_mcf.c.

References SCIP_McfNetwork::colcommodity, INVERTED, LHSASSIGNED, LHSPOSSIBLE, SCIP_McfNetwork::ncommodities, NULL, RHSASSIGNED, RHSPOSSIBLE, SCIP_Bool, SCIP_INVALID, SCIP_Real, SCIPcolGetLPPos(), SCIPdebugMessage, SCIPgetNLPCols(), SCIPisZero(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetDualsol(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), and TRUE.

Referenced by extractFlow().

static void invertCommodity	(	SCIP *	scip,
		MCFDATA *	mcfdata,
		int	k,
		SCIP_ROW **	comrows,
		int	ncomrows,
		int *	comcolids,
		int	ncomcolids
	)

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 1632 of file sepa_mcf.c.

References INVERTED, LHSASSIGNED, NULL, RHSASSIGNED, SCIP_Bool, SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPisInfinity(), SCIProwGetLhs(), SCIProwGetLPPos(), and SCIProwGetRhs().

Referenced by extractFlow().

static void deleteCommodity	(	SCIP *	scip,
		MCFDATA *	mcfdata,
		int	k,
		SCIP_ROW **	comrows,
		int	nrows,
		int *	ndelflowrows,
		int *	ndelflowvars
	)

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 1697 of file sepa_mcf.c.

References SCIP_McfNetwork::colcommodity, FALSE, INVERTED, LHSASSIGNED, SCIP_McfNetwork::ncommodities, NULL, RHSASSIGNED, SCIP_Bool, SCIPcolGetLPPos(), SCIPdebugMessage, SCIPgetNLPCols(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetName(), and SCIProwGetNLPNonz().

Referenced by extractFlow().

static void getFlowrowFit	(	SCIP *	scip,
		MCFDATA *	mcfdata,
		SCIP_ROW *	row,
		int	k,
		unsigned char *	rowsign,
		SCIP_Bool *	invertcommodity
	)

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 1781 of file sepa_mcf.c.

References SCIP_McfNetwork::colcommodity, DISCARDED, FALSE, INVERTED, LHSPOSSIBLE, NULL, RHSPOSSIBLE, SCIP_Bool, SCIP_Real, SCIPcolGetLPPos(), SCIPdebugMessage, SCIPgetNLPCols(), SCIPgetNLPRows(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetVals(), and TRUE.

Referenced by extractFlow(), and getNextFlowrow().

static void getNextFlowrow	(	SCIP *	scip,
		MCFDATA *	mcfdata,
		SCIP_ROW **	nextrow,
		unsigned char *	nextrowsign,
		SCIP_Bool *	nextinvertcommodity
	)

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 1913 of file sepa_mcf.c.

References FALSE, getFlowrowFit(), INVERTED, SCIP_McfNetwork::ncommodities, NULL, SCIP_Bool, SCIP_Real, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPgetLPCols(), SCIPgetNLPCols(), SCIPgetNLPRows(), and SCIProwGetLPPos().

Referenced by extractFlow().

static SCIP_RETCODE extractFlow	(	SCIP *	scip,
		MCFDATA *	mcfdata,
		SCIP_Real	maxflowvarflowrowratio,
		SCIP_Bool *	failed
	)

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 2030 of file sepa_mcf.c.

References addFlowrowToCommodity(), BMSclearMemoryArray, SCIP_McfNetwork::colcommodity, createNewCommodity(), deleteCommodity(), getFlowrowFit(), getNextFlowrow(), invertCommodity(), INVERTED, MAX, MCFdebugMessage, MINCOMNODESFRACTION, MINNODES, SCIP_McfNetwork::nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetLPRows(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIProwGetName(), and TRUE.

Referenced by mcfnetworkExtract().

static SCIP_RETCODE extractCapacities	(	SCIP *	scip,
		MCFDATA *	mcfdata
	)

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 2224 of file sepa_mcf.c.

References SCIP_McfNetwork::colcommodity, DISCARDED, LHSASSIGNED, LHSPOSSIBLE, MAX, NULL, RHSASSIGNED, RHSPOSSIBLE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPcolGetLPPos(), SCIPdebugMessage, SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPreallocMemoryArray, SCIProwGetCols(), SCIProwGetName(), and SCIProwGetNLPNonz().

Referenced by mcfnetworkExtract().

static void collectIncidentFlowCols	(	SCIP *	scip,
		MCFDATA *	mcfdata,
		SCIP_ROW *	flowrow,
		int	basecommodity
	)

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 2390 of file sepa_mcf.c.

References SCIP_McfNetwork::colcommodity, SCIP_McfNetwork::narcs, NULL, SCIP_Bool, SCIPcolGetLPPos(), SCIPgetNLPCols(), SCIProwGetCols(), SCIProwGetNLPNonz(), and TRUE.

Referenced by extractNodes().

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

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 2476 of file sepa_mcf.c.

References FALSE, INVERTED, LHSASSIGNED, MAX, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, RHSASSIGNED, SCIP_Bool, SCIP_CALL, SCIP_MCFMODELTYPE_DIRECTED, SCIP_MCFMODELTYPE_UNDIRECTED, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetLPPos(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetNLPCols(), SCIPgetNLPRows(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetVals(), and TRUE.

Referenced by extractNodes().

static SCIP_RETCODE extractNodes	(	SCIP *	scip,
		MCFDATA *	mcfdata
	)

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 2678 of file sepa_mcf.c.

References BMSclearMemoryArray, collectIncidentFlowCols(), FALSE, getNodeSimilarityScore(), INVERTED, LHSASSIGNED, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, NULL, RHSASSIGNED, SCIP_Bool, SCIP_CALL, SCIP_MCFMODELTYPE_AUTO, SCIP_MCFMODELTYPE_UNDIRECTED, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPcolGetLPPos(), SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPdebugMessage, SCIPfreeMemoryArray, SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPisNegative(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetVals(), and TRUE.

Referenced by mcfnetworkExtract().

static void fixCommoditySigns	(	SCIP *	scip,
		MCFDATA *	mcfdata
	)

static

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 2949 of file sepa_mcf.c.

Referenced by mcfnetworkExtract().

static void getIncidentNodes	(	SCIP *	scip,
		MCFDATA *	mcfdata,
		SCIP_COL *	col,
		int *	sourcenode,
		int *	targetnode
	)

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 2967 of file sepa_mcf.c.

References INVERTED, LHSASSIGNED, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, NULL, RHSASSIGNED, SCIP_Real, SCIPcolGetLPPos(), SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPgetNLPCols(), SCIPgetNLPRows(), and SCIProwGetLPPos().

Referenced by findUncapacitatedArcs(), and identifySourcesTargets().

static SCIP_RETCODE findUncapacitatedArcs	(	SCIP *	scip,
		MCFDATA *	mcfdata
	)

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 3066 of file sepa_mcf.c.

References SCIP_McfNetwork::colcommodity, createNewArc(), getIncidentNodes(), LHSASSIGNED, MCFdebugMessage, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, NULL, RHSASSIGNED, SCIP_CALL, SCIP_MCFMODELTYPE_DIRECTED, SCIP_MCFMODELTYPE_UNDIRECTED, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPceil(), SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetLPCols(), SCIPgetLPRows(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIProwGetCols(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIPsortIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and UNCAPACITATEDARCSTRESHOLD.

Referenced by mcfnetworkExtract().

static SCIP_RETCODE cleanupNetwork	(	SCIP *	scip,
		MCFDATA *	mcfdata
	)

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 3407 of file sepa_mcf.c.

References BMSclearMemoryArray, SCIP_McfNetwork::colcommodity, MAX, MCFdebugMessage, MINCOMNODESFRACTION, MINNODES, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPcolGetLPPos(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetLPRowsData(), SCIPgetNLPCols(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetNLPNonz(), and TRUE.

Referenced by mcfnetworkExtract().

static SCIP_RETCODE identifySourcesTargets	(	SCIP *	scip,
		MCFDATA *	mcfdata,
		SCIP_SEPADATA *	sepadata,
		MCFEFFORTLEVEL *	effortlevel
	)

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 3723 of file sepa_mcf.c.

References SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, BMSclearMemoryArray, SCIP_McfNetwork::colcommodity, getIncidentNodes(), LHSASSIGNED, MCFdebugMessage, MCFEFFORTLEVEL_DEFAULT, MCFEFFORTLEVEL_OFF, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, NULL, RHSASSIGNED, SCIP_CALL, SCIP_MCFMODELTYPE_DIRECTED, SCIP_MCFMODELTYPE_UNDIRECTED, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcolGetLPPos(), SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPisGE(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetNLPNonz(), and TRUE.

Referenced by mcfnetworkExtract().

static SCIP_RETCODE identifyComponent	(	SCIP *	scip,
		MCFDATA *	mcfdata,
		int *	nodevisited,
		int	startv,
		int *	compnodes,
		int *	ncompnodes,
		int *	comparcs,
		int *	ncomparcs
	)

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 4072 of file sepa_mcf.c.

References 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().

static SCIP_RETCODE mcfnetworkExtract	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		SCIP_MCFNETWORK ***	mcfnetworks,
		int *	nmcfnetworks,
		MCFEFFORTLEVEL *	effortlevel
	)

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 4203 of file sepa_mcf.c.

References SCIP_McfNetwork::arccapacityrows, BMSclearMemoryArray, cleanupNetwork(), SCIP_McfNetwork::colcommodity, extractCapacities(), extractCapacityRows(), extractFlow(), extractFlowRows(), extractNodes(), FALSE, findUncapacitatedArcs(), fixCommoditySigns(), identifyComponent(), identifySourcesTargets(), MAX, MAXFLOWVARFLOWROWRATIO, MAXNETWORKS, MCFdebugMessage, MCFEFFORTLEVEL_OFF, mcfnetworkCreate(), mcfnetworkFill(), mcfnetworkFree(), MINARCS, MINNODES, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, SCIP_McfNetwork::nodeflowrows, 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(), SCIPdebugMessage, SCIPerrorMessage, SCIPfreeBufferArray, SCIPfreeMemoryArrayNull, SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetNLPCols(), SCIPreallocMemoryArray, SCIProwGetCols(), SCIProwGetNLPNonz(), SCIPvarGetType(), TRUE, UNKNOWN, and VISITED.

Referenced by separateCuts().

static void unionfindInitSets	(	int *	representatives,
		int	nelems
	)

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 4678 of file sepa_mcf.c.

Referenced by nodepartitionCreate(), and nodepartitionIsConnected().

static int unionfindGetRepresentative	(	int *	representatives,
		int	v
	)

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 4692 of file sepa_mcf.c.

References NULL.

Referenced by nodepartitionGetRepresentative(), and nodepartitionIsConnected().

static void unionfindJoinSets	(	int *	representatives,
		int	rep1,
		int	rep2
	)

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 4710 of file sepa_mcf.c.

Referenced by nodepartitionIsConnected(), and nodepartitionJoin().

static SCIP_DECL_SORTPTRCOMP ( compNodepairs )

static

comparison method for weighted nodepairs

Definition at line 4737 of file sepa_mcf.c.

static SCIP_DECL_HASHGETKEY ( hashGetKeyNodepairs )

static

NodePair HashTable gets the key of the given element

Definition at line 4753 of file sepa_mcf.c.

static SCIP_DECL_HASHKEYEQ ( hashKeyEqNodepairs )

static

NodePair HashTable returns TRUE iff both keys are equal; two nodepairs are equal if both nodes equal

Definition at line 4765 of file sepa_mcf.c.

References SCIP_McfNetwork::nnodes, and NULL.

static SCIP_DECL_HASHKEYVAL ( hashKeyValNodepairs )

static

NodePair HashTable returns the hash value of the key

Definition at line 4806 of file sepa_mcf.c.

References SCIP_McfNetwork::nnodes, and NULL.

static SCIP_RETCODE nodepairqueueCreate	(	SCIP *	scip,
		SCIP_MCFNETWORK *	mcfnetwork,
		NODEPAIRQUEUE **	nodepairqueue
	)

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 4840 of file sepa_mcf.c.

References SCIP_McfNetwork::arccapacityrows, SCIP_McfNetwork::arccapacityscales, SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, SCIP_McfNetwork::colcommodity, FALSE, HASHSIZE_NODEPAIRS, MAX, MIN, 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, SCIPallocMemory, SCIPallocMemoryArray, SCIPblkmem(), SCIPcalcHashtableSize(), SCIPcolGetLPPos(), SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPdebugMessage, 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 void nodepairqueueFree	(	SCIP *	scip,
		NODEPAIRQUEUE **	nodepairqueue
	)

static

frees memory of a nodepair queue

Parameters

scip	SCIP data structure
nodepairqueue	pointer to nodepair priority queue

Definition at line 5155 of file sepa_mcf.c.

References NULL, SCIPfreeMemory, SCIPfreeMemoryArray, and SCIPpqueueFree().

Referenced by nodepartitionCreate().

static SCIP_Bool nodepairqueueIsEmpty ( NODEPAIRQUEUE * nodepairqueue )

static

returns whether there are any nodepairs left on the queue

Parameters

nodepairqueue nodepair priority queue

Definition at line 5171 of file sepa_mcf.c.

References NULL, and SCIPpqueueFirst().

Referenced by nodepartitionCreate().

static NODEPAIRENTRY* nodepairqueueRemove ( NODEPAIRQUEUE * nodepairqueue )

static

removes the top element from the nodepair priority queue, returns nodepair entry or NULL

Parameters

nodepairqueue nodepair priority queue

Definition at line 5183 of file sepa_mcf.c.

References NULL, and SCIPpqueueRemove().

Referenced by nodepartitionCreate().

static int nodepartitionGetRepresentative	(	NODEPARTITION *	nodepartition,
		int	v
	)

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 5201 of file sepa_mcf.c.

References unionfindGetRepresentative().

Referenced by nodepartitionCreate().

static void nodepartitionJoin	(	NODEPARTITION *	nodepartition,
		int	rep1,
		int	rep2
	)

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 5211 of file sepa_mcf.c.

References unionfindJoinSets().

Referenced by nodepartitionCreate().

static SCIP_RETCODE nodepartitionCreate	(	SCIP *	scip,
		SCIP_MCFNETWORK *	mcfnetwork,
		NODEPARTITION **	nodepartition,
		int	nclusters
	)

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 5222 of file sepa_mcf.c.

References BMSclearMemoryArray, SCIP_McfNetwork::nnodes, nodepairqueueCreate(), nodepairqueueFree(), nodepairqueueIsEmpty(), nodepairqueueRemove(), nodepartitionGetRepresentative(), nodepartitionJoin(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocMemory, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeBufferArray, and unionfindInitSets().

Referenced by separateCuts().

static void nodepartitionFree	(	SCIP *	scip,
		NODEPARTITION **	nodepartition
	)

static

frees node partition data

Parameters

scip	SCIP data structure
nodepartition	pointer to node partition data structure

Definition at line 5372 of file sepa_mcf.c.

References NULL, SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by separateCuts().

static SCIP_Bool nodeInPartition	(	NODEPARTITION *	nodepartition,
		unsigned int	partition,
		SCIP_Bool	inverted,
		int	v
	)

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 5389 of file sepa_mcf.c.

References FALSE, and NULL.

Referenced by generateClusterCuts(), and nodepartitionIsConnected().

static int nodepartitionIsConnected	(	SCIP *	scip,
		SCIP_MCFNETWORK *	mcfnetwork,
		NODEPARTITION *	nodepartition,
		unsigned int	partition
	)

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 5419 of file sepa_mcf.c.

References SCIP_McfNetwork::arccapacityrows, SCIP_McfNetwork::arccapacityscales, SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, FALSE, MCFdebugMessage, SCIP_McfNetwork::narcs, SCIP_McfNetwork::nnodes, SCIP_McfNetwork::nodeflowrows, nodeInPartition(), 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().

static SCIP_RETCODE addCut	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SEPADATA *	sepadata,
		SCIP_SOL *	sol,
		SCIP_Real *	cutcoefs,
		SCIP_Real	cutrhs,
		SCIP_Bool	cutislocal,
		int	cutrank,
		int *	ncuts,
		SCIP_Bool *	cutoff
	)

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
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 5756 of file sepa_mcf.c.

References FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddCut(), SCIPaddPoolCut(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPcreateEmptyRowSepa(), SCIPdebugMessage, SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPgetCutEfficacy(), SCIPgetNLPs(), SCIPgetRowSolActivity(), SCIPgetVarsData(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisZero(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetRank(), SCIPseparateRelaxedKnapsack(), and SCIPsnprintf().

Referenced by generateClusterCuts().

static SCIP_RETCODE generateClusterCuts	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SEPADATA *	sepadata,
		SCIP_SOL *	sol,
		SCIP_MCFNETWORK *	mcfnetwork,
		NODEPARTITION *	nodepartition,
		int *	ncuts,
		SCIP_Bool *	cutoff
	)

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
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 5863 of file sepa_mcf.c.

References addCut(), ALLOWLOCAL, SCIP_McfNetwork::arccapacityrows, SCIP_McfNetwork::arccapacityscales, SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, BMSclearMemoryArray, BOUNDSWITCH, SCIP_McfNetwork::colcommodity, FALSE, MAX, 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, REALABS, SCIP_Bool, SCIP_CALL, SCIP_MCFMODELTYPE_DIRECTED, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcalcMIR(), SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPcolIsIntegral(), SCIPdebugMessage, SCIPfloor(), SCIPfrac(), SCIPfreeBufferArray, SCIPfreeMemoryArray, SCIPgetDepth(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPgetNVars(), SCIPgetRowFeasibility(), SCIPgetRowMaxCoef(), SCIPgetRowSolFeasibility(), SCIPgetSolVal(), SCIPisFeasGT(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPisStopped(), SCIPisZero(), SCIPreallocMemoryArray, SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetDualsol(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIPvarIsIntegral(), TRUE, and USEVBDS.

Referenced by separateCuts().

static SCIP_RETCODE separateCuts	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SOL *	sol,
		SCIP_RESULT *	result
	)

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
result	pointer to store the result of the separation call

Definition at line 6591 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.