A network-flow model is an LP model with special structure. The ILOG 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 ILOG 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 6.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 |
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 ILOG 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.