library for polynomially constrained
mixed-integer programming

polip :: contents / contributors / instances / archive / bibliography

Open  robustFlows-trans-11-B

Problem typerobustflows
DescriptionBilinear problem testing whether a flow problem is robust against a set of demand vectors - instance robustFlows-trans-11-B
Objective sensemin
Variables21340  (0 binary, 0 general integer, 21340 continuous)
Nonlinear variables21340
Nonlinear constraints1
Linear nonzeros41880
Nonlinear nonzeros10621
Download robustFlows-trans-11-B.pip.gz robustFlows-trans-11-B.zpl.gz
Best known solution
Best known objective
Best known bound
OriginatorLea Rausch, Marc Pfetsch
FormulatorLea Rausch, Marc Pfetsch
DonatorMarc Pfetsch
References Minoux10
Links netgen
Additional information

This is a bilinear model dealing with the following problem. Given a minimum cost flow problem with demand/supply nodes and a demand/supply vector polytope D, can every demand/supply vector in D be transported through the network? Minoux [2010] showed that this problem is NP-hard.

The problem can be formulated as a bilinear problem as follows. Suppose that A is the node-arc incidence matrix, and let l and u be lower and upper bounds on the flow x, respectively. Then the original problem is: Does there exist a flow vector x with
Ax = d, l ≤ x ≤ u for every d ∈ D?
If for some d ∈ D, there does not exist such a flow, by the Farkas lemma, there exist vectors y, s, and t such that
AT y + s - t = 0, dT y + uT s - lTt < 0, s, t ≥ 0.

Hence, one can consider the following bilinear minimization problem:
min { dTr + uT s - lTt : AT y + s - t = 0, s, t ≥ 0, d ∈ D }.
If its value is < 0, the answer to the original problem is "no" (i.e., there exists some d ∈ D that is not transportable), otherwise the answer is "yes".

The flow instances have been generated using netgen. The demand polytopes are given by a box with the original flow as a base point and increasing the flow by 1% and reducing it by 10% for every node. Additionally, we have a balancing equation, i.e., the sum over all components is 0. All instances with "A" at the end correspond to "yes" instances, while "B" refers to "no" instances. The "yes" instances should be hard to solve, since here one has to prove a nonnegative lower bound.

© by maintainers  |     |  imprint