Solving network-flow problems as LP problems
Explains the conversion between a network flow model and a conventional LP model.
A network-flow model is an LP model with special structure. The
CPLEX network optimizer is a highly efficient implementation of the
primal simplex technique adapted to take advantage of this special
structure. In particular, no basis factoring occurs. However, it is
possible to solve network models using any of the CPLEX LP optimizers
if first, you convert the network data structures to those of an LP
model. To convert the network data structures to LP data structures,
in the Interactive Optimizer, use the command change problem lp ;
from the Callable Library, use the routine CPXcopynettolp.
The LP formulation of our example from Figure 1 looks like this:
| Minimize | ||||||||||||||||||||||||||||
| 3a1 | + | 3a2 | + | 4a3 | + | 3a4 | + | 5a5 | + | 6a6 | + | 7a7 | + | 4a8 | + | 2a9 | + | 6a10 | + | 5a11 | + | 4a12 | + | 3a13 | + | 6a14 | ||
| subject to | ||||||||||||||||||||||||||||
| a1 | = | 20 | ||||||||||||||||||||||||||
| -a1 | + | a2 | - | a8 | - | a9 | + | a14 | = | 0 | ||||||||||||||||||
| - | a2 | + | a3 | + | a9 | = | 0 | |||||||||||||||||||||
| - | a3 | + | a4 | + | a10 | + | a11 | - | a12 | = | -15 | |||||||||||||||||
| a7 | + | a8 | - | a10 | - | a13 | = | 5 | ||||||||||||||||||||
| - | a5 | + | a6 | - | a11 | + | a12 | + | a13 | - | a14 | = | 0 | |||||||||||||||
| - | a4 | + | a5 | = | 0 | |||||||||||||||||||||||
| - | a6 | - | a7 | = | -10 | |||||||||||||||||||||||
| with these bounds | ||||||||||||||||||||||||||||
| 18 | ≤ |
a1 | ≤ |
24 | 0 | ≤ |
a2 | ≤ |
25 | a3 | = | 12 | ||||||||||||||||
| 0 | ≤ |
a4 | ≤ |
10 | 0 | ≤ |
a5 | ≤ |
9 | a6 | free | |||||||||||||||||
| 0 | ≤ |
a7 | ≤ |
20 | 0 | ≤ |
a8 | ≤ |
10 | 0 | ≤ |
a9 | ≤ |
5 | ||||||||||||||
| 0 | ≤ |
a10 | ≤ |
15 | 0 | ≤ |
a11 | ≤ |
10 | 0 | ≤ |
a12 | ≤ |
11 | ||||||||||||||
| 0 | ≤ |
a13 | ≤ |
6 | 0 | ≤ |
a14 | |||||||||||||||||||||
In that formulation, in each column there is exactly one coefficient equal to 1 (one), exactly one coefficient equal to -1, and all other coefficients are 0 (zero).
Since a network-flow problem corresponds in this way to an LP problem,
you can indeed solve a network-flow problem by means of a CPLEX LP
optimizer as well. If you read a network-flow problem into the Interactive
Optimizer, you can transform it into its LP formulation with the command change problem lp.
After this change, you can apply any of the LP optimizers to this
problem.
When you change a network-flow problem into an LP problem, the
basis information that is available in the network-flow problem is
passed along to the LP formulation. In fact, if you have already solved
the network-flow problem to optimality, then if you call the primal
or dual simplex optimizers (for example, with the Interactive Optimizer
command primopt or tranopt), that
simplex optimizer will perform no iterations.
Generally, you can also use the same basis from a basis file for both the LP and the network optimizers. However, there is one exception: in order to use an LP basis with the network optimizer, at least one slack variable or one artificial variable needs to be basic. Starting from an advanced basis explains more about this topic in the context of LP optimizers.
If you have already read the LP formulation of a problem into the
Interactive Optimizer, you can transform it into a network with the
command change problem network. Given any LP problem
and this command, CPLEX will try to find the largest network embedded
in the LP problem and transform it into a network-flow problem. However,
as it does so, it discards all rows and columns that are not part
of the embedded network. At the same time, CPLEX passes along as much
basis information as possible to the network optimizer.