SCIP

Solving Constraint Integer Programs

sepa_mcf.c File Reference

Detailed Description

multi-commodity-flow network cut separator

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

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

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

Definition in file sepa_mcf.c.

#include "blockmemshell/memory.h"
#include "scip/cons_knapsack.h"
#include "scip/cuts.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_sepa.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cut.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_sepa.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/sepa_mcf.h"
#include <string.h>

Go to the source code of this file.

Data Structures

struct  SCIP_McfNetwork

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

◆ BETTERWEIGHTFORDEMANDNODES

 #define BETTERWEIGHTFORDEMANDNODES

Definition at line 47 of file sepa_mcf.c.

◆ SEPA_NAME

 #define SEPA_NAME   "mcf"

Definition at line 75 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 76 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ SEPA_PRIORITY

 #define SEPA_PRIORITY   -10000

Definition at line 77 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ SEPA_FREQ

 #define SEPA_FREQ   0

Definition at line 78 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ SEPA_MAXBOUNDDIST

 #define SEPA_MAXBOUNDDIST   0.0

Definition at line 79 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 80 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 81 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 84 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 85 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 86 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 87 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 88 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 89 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 90 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 91 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 92 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 93 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 94 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 95 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 96 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ DEFAULT_SEPARATEFLOWCUTSET

 #define DEFAULT_SEPARATEFLOWCUTSET   TRUE

should we separate flowcutset inequalities

Definition at line 97 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ DEFAULT_SEPARATEKNAPSACK

 #define DEFAULT_SEPARATEKNAPSACK   TRUE

should we separate knapsack cover inequalities

Definition at line 98 of file sepa_mcf.c.

Referenced by SCIPincludeSepaMcf().

◆ BOUNDSWITCH

 #define BOUNDSWITCH   0.5

Definition at line 101 of file sepa_mcf.c.

Referenced by generateClusterCuts().

◆ POSTPROCESS

 #define POSTPROCESS   TRUE

Definition at line 102 of file sepa_mcf.c.

Referenced by generateClusterCuts().

◆ USEVBDS

 #define USEVBDS   TRUE

Definition at line 103 of file sepa_mcf.c.

Referenced by generateClusterCuts().

◆ MINFRAC

 #define MINFRAC   0.05

Definition at line 104 of file sepa_mcf.c.

Referenced by generateClusterCuts().

◆ MAXFRAC

 #define MAXFRAC   0.999

Definition at line 105 of file sepa_mcf.c.

Referenced by generateClusterCuts().

◆ MAXCOLS

 #define MAXCOLS   2000000

maximum number of columns

Definition at line 107 of file sepa_mcf.c.

Referenced by separateCuts().

◆ MAXAGGRLEN

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

maximal length of base inequality

Definition at line 108 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 109 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 110 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 111 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 112 of file sepa_mcf.c.

Referenced by separateCuts().

◆ MAXNETWORKS

 #define MAXNETWORKS   4

maximum number of networks to consider

Definition at line 113 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 114 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 115 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 116 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 117 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 118 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 119 of file sepa_mcf.c.

Referenced by findUncapacitatedArcs().

◆ HASHSIZE_NODEPAIRS

 #define HASHSIZE_NODEPAIRS   500

minimal size of hash table for nodepairs

Definition at line 120 of file sepa_mcf.c.

Referenced by nodepairqueueCreate().

◆ MCFdebugMessage

 #define MCFdebugMessage   while(FALSE) printf

Definition at line 136 of file sepa_mcf.c.

◆ LHSPOSSIBLE

 #define LHSPOSSIBLE   1u

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

Definition at line 284 of file sepa_mcf.c.

◆ RHSPOSSIBLE

 #define RHSPOSSIBLE   2u

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

Definition at line 285 of file sepa_mcf.c.

◆ LHSASSIGNED

 #define LHSASSIGNED   4u

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

Definition at line 286 of file sepa_mcf.c.

◆ RHSASSIGNED

 #define RHSASSIGNED   8u

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

Definition at line 287 of file sepa_mcf.c.

◆ INVERTED

 #define INVERTED   16u

we need to invert the row

Definition at line 288 of file sepa_mcf.c.

◆ DISCARDED

 #define DISCARDED   32u

we have chosen to not use the constraint

Definition at line 289 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 290 of file sepa_mcf.c.

Referenced by extractCapacityRows().

◆ ONSTACK

 #define ONSTACK   1

node is currently on the processing stack

Definition at line 4096 of file sepa_mcf.c.

Referenced by identifyComponent().

◆ VISITED

 #define VISITED   2

node has been visited and assigned to some component

Definition at line 4097 of file sepa_mcf.c.

Referenced by identifyComponent(), and mcfnetworkExtract().

◆ SCIP_MCFMODELTYPE

 typedef enum SCIP_McfModeltype SCIP_MCFMODELTYPE

Definition at line 150 of file sepa_mcf.c.

◆ MCFEFFORTLEVEL

 typedef enum McfEffortLevel MCFEFFORTLEVEL

Definition at line 159 of file sepa_mcf.c.

◆ SCIP_MCFNETWORK

 typedef struct SCIP_McfNetwork SCIP_MCFNETWORK

Definition at line 181 of file sepa_mcf.c.

◆ MCFDATA

 typedef struct mcfdata MCFDATA

internal MCF extraction data to pass to subroutines

Definition at line 250 of file sepa_mcf.c.

◆ NODEPAIRENTRY

 typedef struct nodepair NODEPAIRENTRY

Definition at line 259 of file sepa_mcf.c.

◆ NODEPAIRQUEUE

 typedef struct nodepairqueue NODEPAIRQUEUE

Definition at line 267 of file sepa_mcf.c.

◆ NODEPARTITION

 typedef struct nodepartition NODEPARTITION

Definition at line 278 of file sepa_mcf.c.

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

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

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

Referenced by mcfnetworkExtract().

◆ SCIP_DECL_SORTINDCOMP()

 static SCIP_DECL_SORTINDCOMP ( compCands )
static

comparator method for flow and capacity row candidates

Definition at line 830 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 844 of file sepa_mcf.c.

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

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 1430 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 1454 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
 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 1507 of file sepa_mcf.c.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 4707 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 4721 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 4739 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 4766 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 4782 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 4794 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 4835 of file sepa_mcf.c.

References SCIP_McfNetwork::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 4869 of file sepa_mcf.c.

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 5182 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 5198 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 5210 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 5227 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 5237 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 5248 of file sepa_mcf.c.

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 5396 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 5413 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 5443 of file sepa_mcf.c.

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

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
 scip SCIP data structure sepa separator sepadata separator data sol the solution that should be separated, or NULL for LP solution allowlocal should local cuts be allowed mcfnetwork MCF network structure nodepartition node partition data structure, or NULL ncuts pointer to count the number of added cuts cutoff pointer to store whether a cutoff was found

Definition at line 5867 of file sepa_mcf.c.

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
 scip SCIP data structure sepa the cut separator itself sol primal solution that should be separated, or NULL for LP solution allowlocal should local cuts be allowed result pointer to store the result of the separation call

Definition at line 6610 of file sepa_mcf.c.

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 6785 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 6799 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 6819 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 6837 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 6861 of file sepa_mcf.c.

◆ SCIP_DECL_SEPAEXECSOL()

 static SCIP_DECL_SEPAEXECSOL ( sepaExecsolMcf )
static

arbitrary primal solution separation method of separator

Definition at line 6888 of file sepa_mcf.c.

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