SCIP
Solving Constraint Integer Programs
sepa_mcf.h 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.h.
Go to the source code of this file.
Functions | |
| SCIP_RETCODE | SCIPincludeSepaMcf (SCIP *scip) |