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 "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

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	POSTPROCESS TRUE

#define	VARTYPEUSEVBDS 2

#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 500

#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 (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)

Macro Definition Documentation

◆ BETTERWEIGHTFORDEMANDNODES

#define BETTERWEIGHTFORDEMANDNODES

Definition at line 56 of file sepa_mcf.c.

◆ SEPA_NAME

#define SEPA_NAME "mcf"

Definition at line 83 of file sepa_mcf.c.

◆ SEPA_DESC

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

Definition at line 84 of file sepa_mcf.c.

◆ SEPA_PRIORITY

#define SEPA_PRIORITY -10000

Definition at line 85 of file sepa_mcf.c.

◆ SEPA_FREQ

#define SEPA_FREQ 0

Definition at line 86 of file sepa_mcf.c.

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST 0.0

Definition at line 87 of file sepa_mcf.c.

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP FALSE

does the separator use a secondary SCIP instance?

Definition at line 88 of file sepa_mcf.c.

◆ SEPA_DELAY

#define SEPA_DELAY FALSE

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

Definition at line 89 of file sepa_mcf.c.

◆ DEFAULT_NCLUSTERS

#define DEFAULT_NCLUSTERS 5

number of clusters to generate in the shrunken network

Definition at line 92 of file sepa_mcf.c.

◆ DEFAULT_MAXWEIGHTRANGE

#define DEFAULT_MAXWEIGHTRANGE 1e+06

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

Definition at line 93 of file sepa_mcf.c.

◆ DEFAULT_MAXTESTDELTA

#define DEFAULT_MAXTESTDELTA 20

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

Definition at line 94 of file sepa_mcf.c.

◆ DEFAULT_TRYNEGSCALING

#define DEFAULT_TRYNEGSCALING FALSE

should negative values also be tested in scaling? for CMIR

Definition at line 95 of file sepa_mcf.c.

◆ DEFAULT_FIXINTEGRALRHS

#define DEFAULT_FIXINTEGRALRHS TRUE

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

Definition at line 96 of file sepa_mcf.c.

◆ DEFAULT_DYNAMICCUTS

#define DEFAULT_DYNAMICCUTS TRUE

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

Definition at line 97 of file sepa_mcf.c.

◆ DEFAULT_MODELTYPE

#define DEFAULT_MODELTYPE 0

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

Definition at line 98 of file sepa_mcf.c.

◆ DEFAULT_MAXSEPACUTS

#define DEFAULT_MAXSEPACUTS 100

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

Definition at line 99 of file sepa_mcf.c.

◆ DEFAULT_MAXSEPACUTSROOT

#define DEFAULT_MAXSEPACUTSROOT 200

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

Definition at line 100 of file sepa_mcf.c.

◆ DEFAULT_MAXINCONSISTENCYRATIO

#define DEFAULT_MAXINCONSISTENCYRATIO 0.02

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

Definition at line 101 of file sepa_mcf.c.

◆ DEFAULT_MAXARCINCONSISTENCYRATIO

#define DEFAULT_MAXARCINCONSISTENCYRATIO 0.5

maximum inconsistency ratio for arcs not to be deleted

Definition at line 102 of file sepa_mcf.c.

◆ DEFAULT_CHECKCUTSHORECONNECTIVITY

#define DEFAULT_CHECKCUTSHORECONNECTIVITY TRUE

should we only separate if the cuts shores are connected

Definition at line 103 of file sepa_mcf.c.

◆ DEFAULT_SEPARATESINGLENODECUTS

#define DEFAULT_SEPARATESINGLENODECUTS TRUE

should we separate inequalities based on single node cuts

Definition at line 104 of file sepa_mcf.c.

◆ DEFAULT_SEPARATEFLOWCUTSET

#define DEFAULT_SEPARATEFLOWCUTSET TRUE

should we separate flowcutset inequalities

Definition at line 105 of file sepa_mcf.c.

◆ DEFAULT_SEPARATEKNAPSACK

#define DEFAULT_SEPARATEKNAPSACK TRUE

should we separate knapsack cover inequalities

Definition at line 106 of file sepa_mcf.c.

◆ BOUNDSWITCH

#define BOUNDSWITCH 0.5

Definition at line 109 of file sepa_mcf.c.

◆ POSTPROCESS

#define POSTPROCESS TRUE

Definition at line 110 of file sepa_mcf.c.

◆ VARTYPEUSEVBDS

#define VARTYPEUSEVBDS 2

We allow variable bound substitution for variables with continuous vartype only. See cuts.c for more information.

Definition at line 112 of file sepa_mcf.c.

◆ MINFRAC

#define MINFRAC 0.05

Definition at line 113 of file sepa_mcf.c.

◆ MAXFRAC

#define MAXFRAC 0.999

Definition at line 114 of file sepa_mcf.c.

◆ MAXCOLS

#define MAXCOLS 2000000

maximum number of columns

Definition at line 116 of file sepa_mcf.c.

◆ MAXAGGRLEN

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

maximal length of base inequality

Definition at line 117 of file sepa_mcf.c.

◆ MINCOLROWRATIO

#define MINCOLROWRATIO 0.01

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

Definition at line 118 of file sepa_mcf.c.

◆ MAXCOLROWRATIO

#define MAXCOLROWRATIO 100.0

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

Definition at line 119 of file sepa_mcf.c.

◆ MAXFLOWVARFLOWROWRATIO

#define MAXFLOWVARFLOWROWRATIO 100.0

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

Definition at line 120 of file sepa_mcf.c.

◆ MAXARCNODERATIO

#define MAXARCNODERATIO 100.0

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

Definition at line 121 of file sepa_mcf.c.

◆ MAXNETWORKS

#define MAXNETWORKS 4

maximum number of networks to consider

Definition at line 122 of file sepa_mcf.c.

◆ MAXFLOWCANDDENSITY

#define MAXFLOWCANDDENSITY 0.1

maximum density of rows to be accepted as flow candidates

Definition at line 123 of file sepa_mcf.c.

◆ MINCOMNODESFRACTION

#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.

◆ MINNODES

#define MINNODES 3

minimal number of nodes in network to keep it for separation

Definition at line 125 of file sepa_mcf.c.

◆ MINARCS

#define MINARCS 3

minimal number of arcs in network to keep it for separation

Definition at line 126 of file sepa_mcf.c.

◆ MAXCAPACITYSLACK

#define MAXCAPACITYSLACK 0.1

maximal slack of weighted capacity constraints to use in aggregation

Definition at line 127 of file sepa_mcf.c.

◆ UNCAPACITATEDARCSTRESHOLD

#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.

◆ HASHSIZE_NODEPAIRS

#define HASHSIZE_NODEPAIRS 500

minimal size of hash table for nodepairs

Definition at line 129 of file sepa_mcf.c.

◆ MCFdebugMessage

#define MCFdebugMessage while(FALSE) printf

Definition at line 145 of file sepa_mcf.c.

◆ LHSPOSSIBLE

#define LHSPOSSIBLE 1u

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

Definition at line 293 of file sepa_mcf.c.

◆ RHSPOSSIBLE

#define RHSPOSSIBLE 2u

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

Definition at line 294 of file sepa_mcf.c.

◆ LHSASSIGNED

#define LHSASSIGNED 4u

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

Definition at line 295 of file sepa_mcf.c.

◆ RHSASSIGNED

#define RHSASSIGNED 8u

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

Definition at line 296 of file sepa_mcf.c.

◆ INVERTED

#define INVERTED 16u

we need to invert the row

Definition at line 297 of file sepa_mcf.c.

◆ DISCARDED

#define DISCARDED 32u

we have chosen to not use the constraint

Definition at line 298 of file sepa_mcf.c.

◆ UNDIRECTED

#define UNDIRECTED 64u

the capacity candidate has two flow variables for a commodity

Definition at line 299 of file sepa_mcf.c.

◆ UNKNOWN

#define UNKNOWN 0

node has not yet been seen

Definition at line 4110 of file sepa_mcf.c.

◆ ONSTACK

#define ONSTACK 1

node is currently on the processing stack

Definition at line 4111 of file sepa_mcf.c.

◆ VISITED

#define VISITED 2

node has been visited and assigned to some component

Definition at line 4112 of file sepa_mcf.c.

Typedef Documentation

◆ SCIP_MCFMODELTYPE

typedef enum SCIP_McfModeltype SCIP_MCFMODELTYPE

Definition at line 159 of file sepa_mcf.c.

◆ MCFEFFORTLEVEL

typedef enum McfEffortLevel MCFEFFORTLEVEL

Definition at line 168 of file sepa_mcf.c.

◆ SCIP_MCFNETWORK

typedef struct SCIP_McfNetwork SCIP_MCFNETWORK

Definition at line 190 of file sepa_mcf.c.

◆ MCFDATA

typedef struct mcfdata MCFDATA

internal MCF extraction data to pass to subroutines

Definition at line 259 of file sepa_mcf.c.

◆ NODEPAIRENTRY

typedef struct nodepair NODEPAIRENTRY

Definition at line 268 of file sepa_mcf.c.

◆ NODEPAIRQUEUE

typedef struct nodepairqueue NODEPAIRQUEUE

Definition at line 276 of file sepa_mcf.c.

◆ NODEPARTITION

typedef struct nodepartition NODEPARTITION

Definition at line 287 of file sepa_mcf.c.

Enumeration Type Documentation

◆ SCIP_McfModeltype

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

◆ McfEffortLevel

enum McfEffortLevel

effort level for separation

Enumerator
MCFEFFORTLEVEL_OFF	no separation
MCFEFFORTLEVEL_DEFAULT	conservative separation
MCFEFFORTLEVEL_AGGRESSIVE	aggressive separation

Definition at line 162 of file sepa_mcf.c.

Function Documentation

◆ mcfnetworkCreate()

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

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.

Referenced by mcfnetworkExtract().

◆ mcfnetworkFree()

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

References a, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, SCIPfreeMemoryArrayNull, and SCIPreleaseRow().

Referenced by mcfnetworkExtract(), and SCIP_DECL_SEPAEXITSOL().

◆ mcfnetworkFill()

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

References a, ABS, SCIP_McfNetwork::arccapacityrows, SCIP_McfNetwork::arccapacityscales, SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, BMSclearMemoryArray, SCIP_McfNetwork::colcommodity, FALSE, INVERTED, LHSASSIGNED, 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().

◆ SCIP_DECL_SORTINDCOMP()

static SCIP_DECL_SORTINDCOMP ( compCands )

static

comparator method for flow and capacity row candidates

Definition at line 839 of file sepa_mcf.c.

References SCIP_Real.

◆ extractFlowRows()

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

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

Referenced by mcfnetworkExtract().

◆ extractCapacityRows()

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

References ABS, BMSclearMemoryArray, 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, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPdebugMsg, SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetLPRowsData(), SCIPgetNLPCols(), SCIPisEQ(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetDualsol(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsModifiable(), SCIPsortInd(), SCIPvarIsIntegral(), and UNDIRECTED.

Referenced by mcfnetworkExtract().

◆ createNewCommodity()

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

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

Referenced by extractFlow().

◆ createNewArc()

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

References MAX, nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, and SCIPreallocMemoryArray.

Referenced by findUncapacitatedArcs().

◆ addFlowrowToCommodity()

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

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

◆ invertCommodity()

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

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

Referenced by extractFlow().

◆ deleteCommodity()

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

References FALSE, INVERTED, LHSASSIGNED, NULL, r, RHSASSIGNED, SCIP_Bool, SCIPcolGetLPPos(), SCIPdebugMsg, SCIPgetNLPCols(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetName(), and SCIProwGetNLPNonz().

Referenced by extractFlow().

◆ getFlowrowFit()

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

References DISCARDED, FALSE, INVERTED, LHSPOSSIBLE, NULL, r, RHSPOSSIBLE, SCIP_Bool, SCIP_Real, SCIPcolGetLPPos(), SCIPdebugMsg, SCIPgetNLPCols(), SCIPgetNLPRows(), SCIProwGetCols(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetVals(), and TRUE.

Referenced by extractFlow(), and getNextFlowrow().

◆ getNextFlowrow()

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

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

Referenced by extractFlow().

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

References addFlowrowToCommodity(), BMSclearMemoryArray, createNewCommodity(), deleteCommodity(), getFlowrowFit(), getNextFlowrow(), 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().

◆ extractCapacities()

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

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

Referenced by mcfnetworkExtract().

◆ collectIncidentFlowCols()

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

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

Referenced by extractNodes().

◆ getNodeSimilarityScore()

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

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

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

References BMSclearMemoryArray, collectIncidentFlowCols(), FALSE, getNodeSimilarityScore(), 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().

◆ fixCommoditySigns()

static void fixCommoditySigns ( MCFDATA * mcfdata )

static

if there are still undecided commodity signs, fix them to +1

Parameters

mcfdata internal MCF extraction data to pass to subroutines

Definition at line 2993 of file sepa_mcf.c.

Referenced by mcfnetworkExtract().

◆ getIncidentNodes()

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

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

Referenced by findUncapacitatedArcs(), and identifySourcesTargets().

◆ findUncapacitatedArcs()

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

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

◆ cleanupNetwork()

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

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

◆ identifySourcesTargets()

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

References a, BMSclearMemoryArray, getIncidentNodes(), 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(), and TRUE.

Referenced by mcfnetworkExtract().

◆ identifyComponent()

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

References a, narcs, nnodes, NULL, ONSTACK, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, UNKNOWN, and VISITED.

Referenced by mcfnetworkExtract().

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

References BMSclearMemoryArray, cleanupNetwork(), extractCapacities(), extractCapacityRows(), extractFlow(), extractFlowRows(), extractNodes(), FALSE, findUncapacitatedArcs(), fixCommoditySigns(), 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, TRUE, UNKNOWN, and VISITED.

Referenced by separateCuts().

◆ unionfindInitSets()

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

Referenced by nodepartitionCreate(), and nodepartitionIsConnected().

◆ unionfindGetRepresentative()

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

References NULL.

Referenced by nodepartitionGetRepresentative(), and nodepartitionIsConnected().

◆ unionfindJoinSets()

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

Referenced by nodepartitionIsConnected(), and nodepartitionJoin().

◆ SCIP_DECL_SORTPTRCOMP()

static SCIP_DECL_SORTPTRCOMP ( compNodepairs )

static

comparison method for weighted nodepairs

Definition at line 4785 of file sepa_mcf.c.

◆ SCIP_DECL_HASHGETKEY()

static SCIP_DECL_HASHGETKEY ( hashGetKeyNodepairs )

static

NodePair HashTable gets the key of the given element

Definition at line 4801 of file sepa_mcf.c.

◆ SCIP_DECL_HASHKEYEQ()

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

References nnodes, and NULL.

◆ SCIP_DECL_HASHKEYVAL()

static SCIP_DECL_HASHKEYVAL ( hashKeyValNodepairs )

static

NodePair HashTable returns the hash value of the key

Definition at line 4854 of file sepa_mcf.c.

References nnodes, and NULL.

◆ nodepairqueueCreate()

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

References a, ABS, SCIP_McfNetwork::arccapacityrows, SCIP_McfNetwork::arccapacityscales, SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, SCIP_McfNetwork::colcommodity, FALSE, HASHSIZE_NODEPAIRS, 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().

◆ nodepairqueueFree()

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

References NULL, SCIPfreeBuffer, SCIPfreeBufferArray, and SCIPpqueueFree().

Referenced by nodepartitionCreate().

◆ nodepairqueueIsEmpty()

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

References NULL, and SCIPpqueueFirst().

Referenced by nodepartitionCreate().

◆ nodepairqueueRemove()

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

References NULL, and SCIPpqueueRemove().

Referenced by nodepartitionCreate().

◆ nodepartitionGetRepresentative()

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

References unionfindGetRepresentative().

Referenced by nodepartitionCreate().

◆ nodepartitionJoin()

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

References unionfindJoinSets().

Referenced by nodepartitionCreate().

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

References BMSclearMemoryArray, nnodes, SCIP_McfNetwork::nnodes, nodepairqueueCreate(), nodepairqueueFree(), nodepairqueueIsEmpty(), nodepairqueueRemove(), nodepartitionGetRepresentative(), nodepartitionJoin(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBuffer, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, and unionfindInitSets().

Referenced by separateCuts().

◆ nodepartitionFree()

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

References NULL, SCIPfreeBuffer, and SCIPfreeBufferArray.

Referenced by separateCuts().

◆ nodeInPartition()

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

References FALSE, and NULL.

Referenced by generateClusterCuts(), and nodepartitionIsConnected().

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

References a, SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, FALSE, narcs, SCIP_McfNetwork::narcs, nnodes, nodeInPartition(), NULL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, unionfindGetRepresentative(), unionfindInitSets(), and unionfindJoinSets().

Referenced by generateClusterCuts().

◆ addCut()

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

adds given cut to LP if violated

Parameters

scip	SCIP data structure
sepa	separator
sepadata	separator data
sol	the solution that should be separated, or NULL for LP solution
cutcoefs	coefficients of active variables in cut
cutrhs	right hand side of cut
cutinds	problem indices of variables with non-zero coefficient
cutnnz	number of non-zeros in cut
cutislocal	is the cut only locally valid?
cutrank	rank of the cut
ncuts	pointer to count the number of added cuts
cutoff	pointer to store whether a cutoff was found

Definition at line 5799 of file sepa_mcf.c.

References FALSE, NULL, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarsToRow(), SCIPallocBufferArray, SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetCutEfficacy(), SCIPgetNLPs(), SCIPgetRowSolActivity(), SCIPgetVarsData(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetRank(), SCIPseparateRelaxedKnapsack(), and SCIPsnprintf().

Referenced by generateClusterCuts().

◆ generateClusterCuts()

static 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

enumerates cuts between subsets of the clusters generates single-node cuts if nodepartition == NULL, otherwise generates cluster cuts

Parameters

scip	SCIP data structure
sepa	separator
sepadata	separator data
sol	the solution that should be separated, or NULL for LP solution
allowlocal	should local cuts be allowed
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 5886 of file sepa_mcf.c.

Referenced by separateCuts().

◆ separateCuts()

static SCIP_RETCODE separateCuts	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SOL *	sol,
		SCIP_Bool	allowlocal,
		int	depth,
		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
allowlocal	should local cuts be allowed
depth	current depth
result	pointer to store the result of the separation call

Definition at line 6630 of file sepa_mcf.c.

References FALSE, generateClusterCuts(), MAXARCNODERATIO, MAXCOLROWRATIO, MAXCOLS, MCFdebugMessage, MCFEFFORTLEVEL_DEFAULT, MCFEFFORTLEVEL_OFF, mcfnetworkExtract(), MINCOLROWRATIO, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, nodepartitionCreate(), nodepartitionFree(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_MCFMODELTYPE_DIRECTED, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPdebug, SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPgetNVars(), SCIPsepaGetData(), SCIPsepaWasLPDelayed(), and TRUE.

Referenced by SCIP_DECL_SEPAEXECLP(), and SCIP_DECL_SEPAEXECSOL().

◆ SCIP_DECL_SEPACOPY()

static SCIP_DECL_SEPACOPY ( sepaCopyMcf )

static

copy method for separator plugins (called when SCIP copies plugins)

Definition at line 6805 of file sepa_mcf.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaMcf(), SCIPsepaGetName(), and SEPA_NAME.

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeMcf )

static

destructor of separator to free user data (called when SCIP is exiting)

Definition at line 6819 of file sepa_mcf.c.

References NULL, SCIP_OKAY, SCIPfreeMemory, SCIPsepaGetData(), and SCIPsepaSetData().

◆ SCIP_DECL_SEPAINITSOL()

static SCIP_DECL_SEPAINITSOL ( sepaInitsolMcf )

static

solving process initialization method of separator (called when branch and bound process is about to begin)

Definition at line 6839 of file sepa_mcf.c.

References MCFEFFORTLEVEL_OFF, NULL, SCIP_OKAY, SCIPsepaGetData(), and TRUE.

◆ SCIP_DECL_SEPAEXITSOL()

static SCIP_DECL_SEPAEXITSOL ( sepaExitsolMcf )

static

solving process deinitialization method of separator (called before branch and bound process data is freed)

Definition at line 6857 of file sepa_mcf.c.

References mcfnetworkFree(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeMemoryArrayNull, and SCIPsepaGetData().

◆ SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpMcf )

static

LP solution separation method of separator

Definition at line 6881 of file sepa_mcf.c.

References NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPgetLPSolstat(), SCIPgetNLPBranchCands(), SCIPisStopped(), and separateCuts().

◆ SCIP_DECL_SEPAEXECSOL()

static SCIP_DECL_SEPAEXECSOL ( sepaExecsolMcf )

static

arbitrary primal solution separation method of separator

Definition at line 6908 of file sepa_mcf.c.

References SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, and separateCuts().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ BETTERWEIGHTFORDEMANDNODES

◆ SEPA_NAME

◆ SEPA_DESC

◆ SEPA_PRIORITY

◆ SEPA_FREQ

◆ SEPA_MAXBOUNDDIST

◆ SEPA_USESSUBSCIP

◆ SEPA_DELAY

◆ DEFAULT_NCLUSTERS

◆ DEFAULT_MAXWEIGHTRANGE

◆ DEFAULT_MAXTESTDELTA

◆ DEFAULT_TRYNEGSCALING

◆ DEFAULT_FIXINTEGRALRHS

◆ DEFAULT_DYNAMICCUTS

◆ DEFAULT_MODELTYPE

◆ DEFAULT_MAXSEPACUTS

◆ DEFAULT_MAXSEPACUTSROOT

◆ DEFAULT_MAXINCONSISTENCYRATIO

◆ DEFAULT_MAXARCINCONSISTENCYRATIO

◆ DEFAULT_CHECKCUTSHORECONNECTIVITY

◆ DEFAULT_SEPARATESINGLENODECUTS

◆ DEFAULT_SEPARATEFLOWCUTSET

◆ DEFAULT_SEPARATEKNAPSACK

◆ BOUNDSWITCH

◆ POSTPROCESS

◆ VARTYPEUSEVBDS

◆ MINFRAC

◆ MAXFRAC

◆ MAXCOLS

◆ MAXAGGRLEN

◆ MINCOLROWRATIO

◆ MAXCOLROWRATIO

◆ MAXFLOWVARFLOWROWRATIO

◆ MAXARCNODERATIO

◆ MAXNETWORKS

◆ MAXFLOWCANDDENSITY

◆ MINCOMNODESFRACTION

◆ MINNODES

◆ MINARCS

◆ MAXCAPACITYSLACK

◆ UNCAPACITATEDARCSTRESHOLD

◆ HASHSIZE_NODEPAIRS

◆ MCFdebugMessage

◆ LHSPOSSIBLE

◆ RHSPOSSIBLE

◆ LHSASSIGNED

◆ RHSASSIGNED

◆ INVERTED

◆ DISCARDED

◆ UNDIRECTED

◆ UNKNOWN

◆ ONSTACK

◆ VISITED

Typedef Documentation

◆ SCIP_MCFMODELTYPE

◆ MCFEFFORTLEVEL

◆ SCIP_MCFNETWORK

◆ MCFDATA

◆ NODEPAIRENTRY

◆ NODEPAIRQUEUE

◆ NODEPARTITION

Enumeration Type Documentation

◆ SCIP_McfModeltype

◆ McfEffortLevel

Function Documentation

◆ mcfnetworkCreate()

◆ mcfnetworkFree()

◆ mcfnetworkFill()

◆ SCIP_DECL_SORTINDCOMP()

◆ extractFlowRows()

◆ extractCapacityRows()

◆ createNewCommodity()