POLIPlibrary for polynomially constrained
| ||
Name | robustFlows-trans-9-A |
Classification | nc|cc|d2 |
Problem type | robustflows |
Description | Bilinear problem testing whether a flow problem is robust against a set of demand vectors - instance robustFlows-trans-9-A |
Objective sense | min |
Variables | 20898 (0 binary, 0 general integer, 20898 continuous) |
Nonlinear variables | 20898 |
Constraints | 10801 |
Nonlinear constraints | 1 |
Linear nonzeros | 41200 |
Nonlinear nonzeros | 10401 |
Download | robustFlows-trans-9-A.pip.gz robustFlows-trans-9-A.zpl.gz |
Best known solution | |
Best known objective | |
Best known bound | |
Originator | Lea Rausch, Marc Pfetsch |
Formulator | Lea Rausch, Marc Pfetsch |
Donator | Marc 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
Hence, one can consider the following bilinear minimization
problem: 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