Solving Network-Flow Problems as LP Problems
PREVIOUS
NEXT
| > Continuous Optimization > Solving Network-Flow Problems > Solving Network-Flow Problems as LP Problems |
Solving Network-Flow Problems as LP Problems |
INDEX
PREVIOUS
NEXT
|
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 10.1 looks like this:
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 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.
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, ILOG 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, ILOG CPLEX passes along as much basis information as possible to the network optimizer.
| Copyright © 1987-2003 ILOG, S.A. All rights reserved. Legal terms. | PREVIOUS NEXT |
