Scippy

SCIP

Solving Constraint Integer Programs

sepa_mcf.c File Reference

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 USEVBDS   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   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 (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 NODEPAIRENTRYnodepairqueueRemove (NODEPAIRQUEUE *nodepairqueue)
 
static int nodepartitionGetRepresentative (NODEPARTITION *nodepartition, int v)
 
static void nodepartitionJoin (NODEPARTITION *nodepartition, int rep1, int rep2)
 
static SCIP_RETCODE nodepartitionCreate (SCIP *scip, SCIP_MCFNETWORK *mcfnetwork, NODEPARTITION **nodepartition, int nclusters)
 
static void nodepartitionFree (SCIP *scip, NODEPARTITION **nodepartition)
 
static SCIP_Bool nodeInPartition (NODEPARTITION *nodepartition, unsigned int partition, SCIP_Bool inverted, int v)
 
static int nodepartitionIsConnected (SCIP *scip, SCIP_MCFNETWORK *mcfnetwork, NODEPARTITION *nodepartition, unsigned int partition)
 
static SCIP_RETCODE addCut (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz, SCIP_Bool cutislocal, int cutrank, int *ncuts, SCIP_Bool *cutoff)
 
static SCIP_RETCODE generateClusterCuts (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Bool allowlocal, SCIP_MCFNETWORK *mcfnetwork, NODEPARTITION *nodepartition, int *ncuts, SCIP_Bool *cutoff)
 
static SCIP_RETCODE separateCuts (SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Bool allowlocal, SCIP_RESULT *result)
 
static SCIP_DECL_SEPACOPY (sepaCopyMcf)
 
static SCIP_DECL_SEPAFREE (sepaFreeMcf)
 
static SCIP_DECL_SEPAINITSOL (sepaInitsolMcf)
 
static SCIP_DECL_SEPAEXITSOL (sepaExitsolMcf)
 
static SCIP_DECL_SEPAEXECLP (sepaExeclpMcf)
 
static SCIP_DECL_SEPAEXECSOL (sepaExecsolMcf)
 
SCIP_RETCODE SCIPincludeSepaMcf (SCIP *scip)
 

Macro Definition Documentation

◆ BETTERWEIGHTFORDEMANDNODES

#define BETTERWEIGHTFORDEMANDNODES

Definition at line 46 of file sepa_mcf.c.

◆ SEPA_NAME

#define SEPA_NAME   "mcf"

Definition at line 74 of file sepa_mcf.c.

Referenced by SCIP_DECL_SEPACOPY(), and SCIPincludeSepaMcf().

◆ SEPA_DESC

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

Definition at line 75 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY   -10000

Definition at line 76 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ SEPA_FREQ

#define SEPA_FREQ   0

Definition at line 77 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST   0.0

Definition at line 78 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 79 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ SEPA_DELAY

#define SEPA_DELAY   FALSE

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

Definition at line 80 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ DEFAULT_NCLUSTERS

#define DEFAULT_NCLUSTERS   5

number of clusters to generate in the shrunken network

Definition at line 83 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ DEFAULT_MAXWEIGHTRANGE

#define DEFAULT_MAXWEIGHTRANGE   1e+06

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

Definition at line 84 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ DEFAULT_MAXTESTDELTA

#define DEFAULT_MAXTESTDELTA   20

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

Definition at line 85 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ DEFAULT_TRYNEGSCALING

#define DEFAULT_TRYNEGSCALING   FALSE

should negative values also be tested in scaling? for CMIR

Definition at line 86 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ DEFAULT_FIXINTEGRALRHS

#define DEFAULT_FIXINTEGRALRHS   TRUE

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

Definition at line 87 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ DEFAULT_DYNAMICCUTS

#define DEFAULT_DYNAMICCUTS   TRUE

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

Definition at line 88 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ DEFAULT_MODELTYPE

#define DEFAULT_MODELTYPE   0

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

Definition at line 89 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ DEFAULT_MAXSEPACUTS

#define DEFAULT_MAXSEPACUTS   100

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

Definition at line 90 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ DEFAULT_MAXSEPACUTSROOT

#define DEFAULT_MAXSEPACUTSROOT   200

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

Definition at line 91 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ DEFAULT_MAXINCONSISTENCYRATIO

#define DEFAULT_MAXINCONSISTENCYRATIO   0.02

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

Definition at line 92 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ DEFAULT_MAXARCINCONSISTENCYRATIO

#define DEFAULT_MAXARCINCONSISTENCYRATIO   0.5

maximum inconsistency ratio for arcs not to be deleted

Definition at line 93 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ DEFAULT_CHECKCUTSHORECONNECTIVITY

#define DEFAULT_CHECKCUTSHORECONNECTIVITY   TRUE

should we only separate if the cuts shores are connected

Definition at line 94 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ DEFAULT_SEPARATESINGLENODECUTS

#define DEFAULT_SEPARATESINGLENODECUTS   TRUE

should we separate inequalities based on single node cuts

Definition at line 95 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ DEFAULT_SEPARATEFLOWCUTSET

#define DEFAULT_SEPARATEFLOWCUTSET   TRUE

should we separate flowcutset inequalities

Definition at line 96 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ DEFAULT_SEPARATEKNAPSACK

#define DEFAULT_SEPARATEKNAPSACK   TRUE

should we separate knapsack cover inequalities

Definition at line 97 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ BOUNDSWITCH

#define BOUNDSWITCH   0.5

Definition at line 100 of file sepa_mcf.c.

Referenced by generateClusterCuts().

◆ POSTPROCESS

#define POSTPROCESS   TRUE

Definition at line 101 of file sepa_mcf.c.

Referenced by generateClusterCuts().

◆ USEVBDS

#define USEVBDS   TRUE

Definition at line 102 of file sepa_mcf.c.

Referenced by generateClusterCuts().

◆ MINFRAC

#define MINFRAC   0.05

Definition at line 103 of file sepa_mcf.c.

Referenced by generateClusterCuts().

◆ MAXFRAC

#define MAXFRAC   0.999

Definition at line 104 of file sepa_mcf.c.

Referenced by generateClusterCuts().

◆ MAXCOLS

#define MAXCOLS   2000000

maximum number of columns

Definition at line 106 of file sepa_mcf.c.

Referenced by separateCuts().

◆ MAXAGGRLEN

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

maximal length of base inequality

Definition at line 107 of file sepa_mcf.c.

Referenced by generateClusterCuts().

◆ MINCOLROWRATIO

#define MINCOLROWRATIO   0.01

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

Definition at line 108 of file sepa_mcf.c.

Referenced by separateCuts().

◆ MAXCOLROWRATIO

#define MAXCOLROWRATIO   100.0

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

Definition at line 109 of file sepa_mcf.c.

Referenced by separateCuts().

◆ MAXFLOWVARFLOWROWRATIO

#define MAXFLOWVARFLOWROWRATIO   100.0

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

Definition at line 110 of file sepa_mcf.c.

Referenced by mcfnetworkExtract().

◆ MAXARCNODERATIO

#define MAXARCNODERATIO   100.0

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

Definition at line 111 of file sepa_mcf.c.

Referenced by separateCuts().

◆ MAXNETWORKS

#define MAXNETWORKS   4

maximum number of networks to consider

Definition at line 112 of file sepa_mcf.c.

Referenced by mcfnetworkExtract().

◆ MAXFLOWCANDDENSITY

#define MAXFLOWCANDDENSITY   0.1

maximum density of rows to be accepted as flow candidates

Definition at line 113 of file sepa_mcf.c.

Referenced by extractFlowRows().

◆ MINCOMNODESFRACTION

#define MINCOMNODESFRACTION   0.5

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

Definition at line 114 of file sepa_mcf.c.

Referenced by cleanupNetwork(), and extractFlow().

◆ MINNODES

#define MINNODES   3

minimal number of nodes in network to keep it for separation

Definition at line 115 of file sepa_mcf.c.

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

◆ MINARCS

#define MINARCS   3

minimal number of arcs in network to keep it for separation

Definition at line 116 of file sepa_mcf.c.

Referenced by mcfnetworkExtract().

◆ MAXCAPACITYSLACK

#define MAXCAPACITYSLACK   0.1

maximal slack of weighted capacity constraints to use in aggregation

Definition at line 117 of file sepa_mcf.c.

Referenced by generateClusterCuts().

◆ UNCAPACITATEDARCSTRESHOLD

#define UNCAPACITATEDARCSTRESHOLD   0.8

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

Definition at line 118 of file sepa_mcf.c.

Referenced by findUncapacitatedArcs().

◆ HASHSIZE_NODEPAIRS

#define HASHSIZE_NODEPAIRS   500

minimal size of hash table for nodepairs

Definition at line 119 of file sepa_mcf.c.

Referenced by nodepairqueueCreate().

◆ MCFdebugMessage

◆ LHSPOSSIBLE

#define LHSPOSSIBLE   1u

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

Definition at line 283 of file sepa_mcf.c.

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

◆ RHSPOSSIBLE

#define RHSPOSSIBLE   2u

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

Definition at line 284 of file sepa_mcf.c.

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

◆ LHSASSIGNED

◆ RHSASSIGNED

◆ INVERTED

◆ DISCARDED

#define DISCARDED   32u

we have chosen to not use the constraint

Definition at line 288 of file sepa_mcf.c.

Referenced by extractCapacities(), and getFlowrowFit().

◆ UNDIRECTED

#define UNDIRECTED   64u

the capacity candidate has two flow variables for a commodity

Definition at line 289 of file sepa_mcf.c.

Referenced by extractCapacityRows().

◆ UNKNOWN

#define UNKNOWN   0

node has not yet been seen

Definition at line 4081 of file sepa_mcf.c.

Referenced by adjust0term(), buildsolgraph(), computeDegConsTree(), computePertubedSol(), computeSteinerTreeVnoi(), correct(), correctX(), findDaRoots(), getcloseterms2term(), getlecloseterms(), graph_edge_add(), graph_get2next(), graph_get3next(), graph_get4next(), graph_get4nextTTerms(), graph_init(), graph_load(), graph_pack(), graph_path_exec(), graph_path_execX(), graph_path_invroot(), graph_path_PcMwSd(), graph_path_st(), graph_path_st_pcmw(), graph_path_st_pcmw_extend(), graph_path_st_pcmw_full(), graph_path_st_pcmw_reduce(), graph_path_st_rmw(), graph_path_st_rpc(), graph_pc_deleteTerm(), graph_sdPaths(), graph_sol_getOrg(), graph_sol_reroot(), graph_voronoi(), graph_voronoiMw(), graph_voronoiRepair(), graph_voronoiTerms(), graph_voronoiWithDist(), graph_voronoiWithRadius(), graph_voronoiWithRadiusMw(), identifyComponent(), mcfnetworkExtract(), prune(), reduce_ansAdv2(), reduce_bd34(), reduce_bdr(), reduce_bound(), reduce_boundHopRc(), reduce_chain2(), reduce_cnsAdv(), reduce_da(), reduce_daSlackPrune(), reduce_daSlackPruneMw(), reduce_getSd(), reduce_getSdPcMw(), reduce_ledge(), reduce_npv(), reduce_nts(), reduce_nv(), reduce_nvAdv(), reduce_sd(), reduce_sdPc(), reduce_sdsp(), reduce_sdspSap(), reduce_simple(), reduce_simple_pc(), reduce_sl(), SCIP_DECL_BRANCHEXECLP(), SCIP_DECL_BRANCHEXECPS(), SCIP_DECL_HEUREXEC(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurLocalRun(), SCIPStpHeurPruneRun(), SCIPStpHeurPruneUpdateSols(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), SCIPStpHeurSlackPruneRunPcMw(), SCIPStpHeurTMBuildTree(), SCIPStpHeurTMBuildTreeDc(), SCIPStpHeurTMBuildTreePcMw(), SCIPStpHeurTMPrune(), SCIPStpHeurTMRun(), SCIPStpHeurTMRunLP(), selectBranchingVertexByDegree(), selectBranchingVertexByLp(), selectBranchingVertexByLp2Flow(), selectBranchingVertexBySol(), setNodeSolArray(), trydg1edgepc(), and updateSolNodeArray().

◆ ONSTACK

#define ONSTACK   1

node is currently on the processing stack

Definition at line 4082 of file sepa_mcf.c.

Referenced by identifyComponent().

◆ VISITED

#define VISITED   2

node has been visited and assigned to some component

Definition at line 4083 of file sepa_mcf.c.

Referenced by identifyComponent(), and mcfnetworkExtract().

Typedef Documentation

◆ SCIP_MCFMODELTYPE

Definition at line 149 of file sepa_mcf.c.

◆ MCFEFFORTLEVEL

Definition at line 158 of file sepa_mcf.c.

◆ SCIP_MCFNETWORK

Definition at line 180 of file sepa_mcf.c.

◆ MCFDATA

typedef struct mcfdata MCFDATA

internal MCF extraction data to pass to subroutines

Definition at line 249 of file sepa_mcf.c.

◆ NODEPAIRENTRY

typedef struct nodepair NODEPAIRENTRY

Definition at line 258 of file sepa_mcf.c.

◆ NODEPAIRQUEUE

typedef struct nodepairqueue NODEPAIRQUEUE

Definition at line 266 of file sepa_mcf.c.

◆ NODEPARTITION

typedef struct nodepartition NODEPARTITION

Definition at line 277 of file sepa_mcf.c.

Enumeration Type Documentation

◆ SCIP_McfModeltype

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

◆ McfEffortLevel

effort level for separation

Enumerator
MCFEFFORTLEVEL_OFF 

no separation

MCFEFFORTLEVEL_DEFAULT 

conservative separation

MCFEFFORTLEVEL_AGGRESSIVE 

aggressive separation

Definition at line 152 of file sepa_mcf.c.

Function Documentation

◆ mcfnetworkCreate()

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

creates an empty MCF network data structure

Parameters
scipSCIP data structure
mcfnetworkMCF network structure

Definition at line 294 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
scipSCIP data structure
mcfnetworkMCF network structure

Definition at line 320 of file sepa_mcf.c.

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

Referenced by mcfnetworkExtract(), and SCIP_DECL_SEPAEXITSOL().

◆ mcfnetworkFill()

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

◆ SCIP_DECL_SORTINDCOMP()

static SCIP_DECL_SORTINDCOMP ( compCands  )
static

comparator method for flow and capacity row candidates

Definition at line 829 of file sepa_mcf.c.

References SCIP_Real.

◆ extractFlowRows()

◆ extractCapacityRows()

◆ createNewCommodity()

static SCIP_RETCODE createNewCommodity ( SCIP scip,
MCFDATA mcfdata 
)
static

creates a new commodity

Parameters
scipSCIP data structure
mcfdatainternal MCF extraction data to pass to subroutines

Definition at line 1427 of file sepa_mcf.c.

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

Referenced by extractFlow().

◆ createNewArc()

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

creates a new arc

Parameters
scipSCIP data structure
mcfdatainternal MCF extraction data to pass to subroutines
sourcesource of new arc
targettarget of new arc
newarcidpointer to store id of new arc

Definition at line 1451 of file sepa_mcf.c.

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

Referenced by findUncapacitatedArcs().

◆ addFlowrowToCommodity()

static 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
scipSCIP data structure
mcfdatainternal MCF extraction data to pass to subroutines
rowflow row to add to current commodity
rowsignpossible flow row signs to use
comcolidsarray of column indices of columns in commodity
ncomcolidspointer to number of columns in commodity

Definition at line 1504 of file sepa_mcf.c.

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

Referenced by extractFlow().

◆ invertCommodity()

static void invertCommodity ( SCIP scip,
MCFDATA mcfdata,
int  k,
SCIP_ROW **  comrows,
int  ncomrows,
int *  comcolids,
int  ncomcolids 
)
static
Parameters
scipSCIP data structure
mcfdatainternal MCF extraction data to pass to subroutines
kcommodity that the flow row should enter
comrowsflow rows in commodity k
ncomrowsnumber of flow rows (number of nodes) in commodity k
comcolidscolumn indices of columns in commodity k
ncomcolidsnumber of columns in commodity k

Definition at line 1650 of file sepa_mcf.c.

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

Referenced by extractFlow().

◆ deleteCommodity()

static 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
scipSCIP data structure
mcfdatainternal MCF extraction data to pass to subroutines
kcommodity to delete
comrowsflow rows of the commodity
nrowsnumber of flow rows in the commodity
ndelflowrowspointer to store number of flow rows in deleted commodity
ndelflowvarspointer to store number of flow vars in deleted commodity

Definition at line 1715 of file sepa_mcf.c.

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

Referenced by extractFlow().

◆ getFlowrowFit()

static 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
scipSCIP data structure
mcfdatainternal MCF extraction data to pass to subroutines
rowflow row to check
kcommodity that the flow row should enter
rowsignpointer to store the possible flow row signs
invertcommoditypointer to store whether the commodity has to be inverted to accommodate the row

Definition at line 1799 of file sepa_mcf.c.

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

Referenced by extractFlow(), and getNextFlowrow().

◆ getNextFlowrow()

static 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
scipSCIP data structure
mcfdatainternal MCF extraction data to pass to subroutines
nextrowpointer to store next row
nextrowsignpointer to store possible signs of next row
nextinvertcommoditypointer to store whether current commodity has to be inverted to accommodate the next row

Definition at line 1931 of file sepa_mcf.c.

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

Referenced by extractFlow().

◆ extractFlow()

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

extracts flow conservation rows and puts them into commodities

Parameters
scipSCIP data structure
mcfdatainternal MCF extraction data to pass to subroutines
maxflowvarflowrowratiomaximum ratio of flowvars and flowrows
failedpointer to store whether flowrowflowvarratio exceeded

Definition at line 2048 of file sepa_mcf.c.

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

Referenced by mcfnetworkExtract().

◆ extractCapacities()

static 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
scipSCIP data structure
mcfdatainternal MCF extraction data to pass to subroutines

Definition at line 2242 of file sepa_mcf.c.

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

Referenced by mcfnetworkExtract().

◆ collectIncidentFlowCols()

static 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
scipSCIP data structure
mcfdatainternal MCF extraction data to pass to subroutines
flowrowflow conservation constraint that defines the node
basecommoditycommodity of the base row

Definition at line 2406 of file sepa_mcf.c.

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

Referenced by extractNodes().

◆ getNodeSimilarityScore()

static 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
scipSCIP data structure
mcfdatainternal MCF extraction data to pass to subroutines
baserowlenlength of base node flow row
basearcpatternarc pattern of base node flow row
basenposuncapnumber of uncapacitated vars in base node flow row with positive coeff
basenneguncapnumber of uncapacitated vars in base node flow row with negative coeff
rowrow to compare against base node flow row
scorepointer to store the similarity score
invertcommoditypointer to store whether the arcs in the commodity of the row have to be inverted for the row to be compatible to the base row

Definition at line 2491 of file sepa_mcf.c.

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

Referenced by extractNodes().

◆ extractNodes()

◆ fixCommoditySigns()

static void fixCommoditySigns ( SCIP scip,
MCFDATA mcfdata 
)
static

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

Parameters
scipSCIP data structure
mcfdatainternal MCF extraction data to pass to subroutines

Definition at line 2963 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
scipSCIP data structure
mcfdatainternal MCF extraction data to pass to subroutines
colflow column
sourcenodepointer to store the source node of the flow column
targetnodepointer to store the target node of the flow column

Definition at line 2981 of file sepa_mcf.c.

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

Referenced by findUncapacitatedArcs(), and identifySourcesTargets().

◆ findUncapacitatedArcs()

◆ 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
scipSCIP data structure
mcfdatainternal MCF extraction data to pass to subroutines

Definition at line 3420 of file sepa_mcf.c.

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

Referenced by mcfnetworkExtract().

◆ identifySourcesTargets()

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

◆ 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
scipSCIP data structure
mcfdatainternal MCF extraction data to pass to subroutines
nodevisitedarray to mark visited nodes
startvnode for which the connected component should be generated
compnodesarray to store node ids of the component
ncompnodespointer to store the number of nodes in the component
comparcsarray to store arc ids of the component
ncomparcspointer to store the number of arcs in the component

Definition at line 4087 of file sepa_mcf.c.

References a, SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, SCIP_McfNetwork::narcs, SCIP_McfNetwork::nnodes, NULL, ONSTACK, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, UNKNOWN, and VISITED.

Referenced by mcfnetworkExtract().

◆ mcfnetworkExtract()

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

◆ unionfindInitSets()

static void unionfindInitSets ( int *  representatives,
int  nelems 
)
static

initializes a union find data structure by putting each element into its own set

Parameters
representativesmapping an element v to its representative
nelemsnumber of elements in the ground set

Definition at line 4691 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
representativesmapping an element v to its representative
velement v to get a representative for

Definition at line 4705 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
representativesmapping an element v to its representative
rep1representative of first set
rep2representative of second set

Definition at line 4723 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 4750 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 4766 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 4778 of file sepa_mcf.c.

References SCIP_McfNetwork::nnodes, and NULL.

◆ SCIP_DECL_HASHKEYVAL()

static SCIP_DECL_HASHKEYVAL ( hashKeyValNodepairs  )
static

NodePair HashTable returns the hash value of the key

Definition at line 4819 of file sepa_mcf.c.

References SCIP_McfNetwork::nnodes, and NULL.

◆ nodepairqueueCreate()

◆ nodepairqueueFree()

static void nodepairqueueFree ( SCIP scip,
NODEPAIRQUEUE **  nodepairqueue 
)
static

frees memory of a nodepair queue

Parameters
scipSCIP data structure
nodepairqueuepointer to nodepair priority queue

Definition at line 5166 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
nodepairqueuenodepair priority queue

Definition at line 5182 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
nodepairqueuenodepair priority queue

Definition at line 5194 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
nodepartitionnode partition data structure
vnode id to get representative for

Definition at line 5211 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
nodepartitionnode partition data structure
rep1representative of first cluster
rep2representative of second cluster

Definition at line 5221 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
scipSCIP data structure
mcfnetworkMCF network structure
nodepartitionpointer to node partition data structure
nclustersnumber of clusters to generate

Definition at line 5232 of file sepa_mcf.c.

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

Referenced by separateCuts().

◆ nodepartitionFree()

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

frees node partition data

Parameters
scipSCIP data structure
nodepartitionpointer to node partition data structure

Definition at line 5382 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
nodepartitionnode partition data structure, or NULL
partitionpartition of nodes, or node number in single-node partition
invertedshould partition be inverted?
vnode to check

Definition at line 5399 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

◆ 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
scipSCIP data structure
sepaseparator
sepadataseparator data
solthe solution that should be separated, or NULL for LP solution
cutcoefscoefficients of active variables in cut
cutrhsright hand side of cut
cutindsproblem indices of variables with non-zero coefficient
cutnnznumber of non-zeros in cut
cutislocalis the cut only locally valid?
cutrankrank of the cut
ncutspointer to count the number of added cuts
cutoffpointer to store whether a cutoff was found

Definition at line 5766 of file sepa_mcf.c.

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

Referenced by generateClusterCuts().

◆ generateClusterCuts()

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

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

Parameters
scipSCIP data structure
sepaseparator
sepadataseparator data
solthe solution that should be separated, or NULL for LP solution
allowlocalshould local cuts be allowed
mcfnetworkMCF network structure
nodepartitionnode partition data structure, or NULL
ncutspointer to count the number of added cuts
cutoffpointer to store whether a cutoff was found

Definition at line 5853 of file sepa_mcf.c.

References a, ABS, addCut(), SCIP_McfNetwork::arccapacityrows, SCIP_McfNetwork::arccapacityscales, SCIP_McfNetwork::arcsources, SCIP_McfNetwork::arctargets, BMSclearMemoryArray, BOUNDSWITCH, SCIP_McfNetwork::colcommodity, FALSE, MAXAGGRLEN, MAXCAPACITYSLACK, MAXFRAC, MCFdebugMessage, MCFEFFORTLEVEL_AGGRESSIVE, MCFEFFORTLEVEL_DEFAULT, MINFRAC, SCIP_McfNetwork::modeltype, SCIP_McfNetwork::narcs, SCIP_McfNetwork::ncommodities, SCIP_McfNetwork::nnodes, SCIP_McfNetwork::nodeflowinverted, SCIP_McfNetwork::nodeflowrows, SCIP_McfNetwork::nodeflowscales, nodeInPartition(), nodepartitionIsConnected(), NULL, POSTPROCESS, r, REALABS, SCIP_Bool, SCIP_CALL, SCIP_MCFMODELTYPE_DIRECTED, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPaggrRowCreate(), SCIPaggrRowFree(), SCIPaggrRowSumRows(), SCIPallocBufferArray, SCIPcalcMIR(), SCIPcolGetLPPos(), SCIPcolGetVar(), SCIPcolIsIntegral(), SCIPdebugMsg, SCIPfloor(), SCIPfrac(), SCIPfreeBufferArray, SCIPgetDepth(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPgetNVars(), SCIPgetRowFeasibility(), SCIPgetRowMaxCoef(), SCIPgetRowSolFeasibility(), SCIPgetSolVal(), SCIPisEfficacious(), SCIPisFeasGT(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPisStopped(), SCIPisZero(), SCIPreallocBufferArray, SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetDualsol(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIPvarIsIntegral(), TRUE, and USEVBDS.

Referenced by separateCuts().

◆ separateCuts()

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

searches and adds MCF network cuts that separate the given primal solution

Parameters
scipSCIP data structure
sepathe cut separator itself
solprimal solution that should be separated, or NULL for LP solution
allowlocalshould local cuts be allowed
resultpointer to store the result of the separation call

Definition at line 6596 of file sepa_mcf.c.

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

Referenced by SCIP_DECL_SEPAEXECLP(), and SCIP_DECL_SEPAEXECSOL().

◆ SCIP_DECL_SEPACOPY()

static SCIP_DECL_SEPACOPY ( sepaCopyMcf  )
static

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

Definition at line 6771 of file sepa_mcf.c.

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

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeMcf  )
static

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

Definition at line 6785 of file sepa_mcf.c.

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

◆ SCIP_DECL_SEPAINITSOL()

static SCIP_DECL_SEPAINITSOL ( sepaInitsolMcf  )
static

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

Definition at line 6805 of file sepa_mcf.c.

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

◆ SCIP_DECL_SEPAEXITSOL()

static SCIP_DECL_SEPAEXITSOL ( sepaExitsolMcf  )
static

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

Definition at line 6823 of file sepa_mcf.c.

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

◆ SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpMcf  )
static

LP solution separation method of separator

Definition at line 6847 of file sepa_mcf.c.

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

◆ SCIP_DECL_SEPAEXECSOL()

static SCIP_DECL_SEPAEXECSOL ( sepaExecsolMcf  )
static

arbitrary primal solution separation method of separator

Definition at line 6874 of file sepa_mcf.c.

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