Scippy

SCIP

Solving Constraint Integer Programs

Functions
sepa_mcf.h File Reference
Separators

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

#include "scip/scip.h"

Go to the source code of this file.

Functions

SCIP_RETCODE SCIPincludeSepaMcf (SCIP *scip)
 

Function Documentation

SCIP_RETCODE SCIPincludeSepaMcf ( SCIP *  scip)

creates the mcf separator and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 6886 of file sepa_mcf.c.

References DEFAULT_CHECKCUTSHORECONNECTIVITY, DEFAULT_DYNAMICCUTS, DEFAULT_FIXINTEGRALRHS, DEFAULT_MAXARCINCONSISTENCYRATIO, DEFAULT_MAXINCONSISTENCYRATIO, DEFAULT_MAXSEPACUTS, DEFAULT_MAXSEPACUTSROOT, DEFAULT_MAXTESTDELTA, DEFAULT_MAXWEIGHTRANGE, DEFAULT_MODELTYPE, DEFAULT_NCLUSTERS, DEFAULT_SEPARATEFLOWCUTSET, DEFAULT_SEPARATEKNAPSACK, DEFAULT_SEPARATESINGLENODECUTS, DEFAULT_TRYNEGSCALING, FALSE, MCFEFFORTLEVEL_OFF, NULL, SCIP_CALL, SCIP_OKAY, SCIP_REAL_MAX, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocMemory, SCIPincludeSepaBasic(), SCIPsetSepaCopy(), SCIPsetSepaExitsol(), SCIPsetSepaFree(), SCIPsetSepaInitsol(), SEPA_DELAY, SEPA_DESC, SEPA_FREQ, SEPA_MAXBOUNDDIST, SEPA_NAME, SEPA_PRIORITY, SEPA_USESSUBSCIP, and TRUE.

Referenced by SCIP_DECL_SEPACOPY(), and SCIPincludeDefaultPlugins().