# TOMLAB  
# REGISTER (TOMLAB)
# LOGIN  
# myTOMLAB
TOMLAB LOGO

« Previous « Start » Next »

E  TOMLAB /CPLEX Network Solver

The TOMLAB /CPLEX network solver is a special interface for network problems described by a set of nodes and arcs. The TOMLAB format is not applicable for these types of problem. See cplexnet for information on calling the solver.

A network-flow problem finds the minimal-cost flow through a network, where a network consists of a set N of nodes and a set A of arcs connecting the nodes. An arc a in the set A is an ordered pair (i, j) where i and j are nodes in the set N; node i is called the tail or the from-node and node j is called the head or the to-node of the arc a. Not all the pairs of nodes in a set N are necessarily connected by arcs in the set A. More than one arc may connect a pair of nodes; in other words, a1 = (i, j) and a2 = (i, j) may be two different arcs in A, both connecting the nodes i and j in N.

Each arc a may be associated with four values:
  • xa is the flow value, that is, the amount passing through the arc a from its tail (or from-node) to its head (or to-node). The flow values are the modeling variables of a network-flow problem. Negative values are allowed; a negative flow value indicates that there is flow from the head to the tail.

  • la, the lower bound, determines the minimum flow allowed through the arc a. By default, the lower bound on an arc is 0 (zero).

  • ua, the upper bound, determines the maximum flow allowed through the arc a. By default, the upper bound on an arc is positive infinity.

  • ca, the objective value, determines the contribution to the objective function of one unit of flow through the arc.
Each node n is associated with one value:
  • sn is the supply value at node n.
By convention, a node with strictly positive supply value (that is, sn > 0) is called a supply node or a source, and a node with strictly negative supply value (that is, sn < 0) is called a demand node or a sink. A node where sn = 0 is called a transshipment node. The sum of all supplies must match the sum of all demands; if not, then the network flow problem is infeasible.

Tn is the set of arcs whose tails are node n; Hn is the set of arcs whose heads are node n. The usual form of a network problem looks like this:

 
min
x
 
Σ
a ∈ A
caxa
   
s/t
 
Σ
a ∈ Ta
xa
 
Σ
a ∈ Ha
xa = sn ∀ n ∈ N
  la xa ua
    (1)


A test routines that illustrates a simple problem is included in the TOMLAB distribution. Figure 1 shows the network problem solved:



Figure 1: Network problem in cpxNetTest1.m


pngs/tomlab_cplex002.png

The following code will call the network solver and deliver the optimal solution.
x = cpxNetTest1;
It is possible to call the TOMLAB /CPLEX solver using a special non-MATLAB input format. Example cpxNetTest2 illustrates how to load and solve the problem described in nexample.net.

E.1  cplexnet

Purpose
The Network Interface. It solves network programming (NP) problems. Equation 1 describes the problem structure.
Calling Syntax
[x, slack, v, rc, f_k, Inform, Iter] = cplexnet(obj, ub, lb, tail, head, supply, callback, PriLev, BIG, cpxControl, logfile, savefile, savemode, netfile);
Description of Inputs

Problem inputs. The following fields are used:
 
obj Objective function cost coefficients for the arcs.
 
ub Upper bounds for the arcs.
lb Lower bounds for the arcs.
 
tail Indices for the tails (start).
head Indices for the heads (end).
 
supply The supply and demand vector for the nodes.
 
The following parameters are optional:
 
callback Logical scalar defining if callback is used in CPLEX callback = 1 activates the callback. See TOMLAB /CPLEX User's Guide. The callback calls the m-file specified below. The user may edit this file, or make a new copy, which is put before in the Matlab path.
 
PriLev Printing level in cplex.m file and the CPLEX C-interface.
  = 0 Silent
  = 1 Warnings and Errors
  = 2 Summary information
  = 3 More detailed information
BIG Defines default lower and upper bounds, default 1E20.
  = 0 Silent
  = 1 Warnings and Errors
  = 2 Summary information
  = 3 More detailed information
  > 10 Pause statements, and maximal printing (debug mode)
cpxControl Structure, where the fields are set to the CPLEX parameters that the user wants to specify values for. The following parameters are the only ones of general interest. Default values are recommended:
NETITLIM Limits the number of iterations that the network optimizer performs. Default BIGINT.
NETEPOPT Optimality tolerance for the network optimizer. The optimality tolerance specifies the amount a reduced cost may violate the criterion for an optimal solution. Default 1e-6. Valid values from 1e-11 to 1e-1.
NETEPRHS Feasibility tolerance for the network optimizer. The feasibility tolerance specifies the degree to which a problem's flow value may violate its bounds. This tolerance influences the selection of an optimal basis and can be reset to a higher value when a problem is having difficulty maintaining feasibility during optimization. You may also wish to lower this tolerance after finding an optimal solution if there is any doubt that the solution is truly optimal. If the feasibility tolerance is set too low, CPLEX may falsely conclude that a problem is infeasible. If you encounter reports of infeasibility in the optimization, a small adjustment in the feasibility tolerance may improve performance. Default 1e-6. Valid values from 1e-11 to 1e-1.
NETPPRIIND Pricing algorithm for the network optimizer. On the rare occasions when the network optimizer seems to take too long to find a solution, you may want to change the pricing algorithm to try to speed up computation. All the choices use variations of partial reduced-cost pricing.
  NETPPRIIND = 0: automatic, default (same as 3)
  NETPPRIIND = 1: Partial pricing.
  NETPPRIIND = 2: Multiple partial pricing.
  NETPPRIIND = 3: Multiple partial pricing with sorting.
 
NETFIND The CPLEX network extractor searches an LP constraint matrix for a submatrix with the following characteristics:
  - the coefficients of the submatrix are all 0 (zero), 1 (one), or -1 (minus one);
  - each variable appears in at most two rows with at most one coefficient of +1 and at most one coefficient of -1.
  CPLEX can perform different levels of extraction. The level it performs depends on the NETFIND parameter.
  NETFIND = 1: CPLEX extracts only the obvious network; it uses no scaling; it scans rows in their natural order; it stops extraction as soon as no more rows can be added to the network found so far.
  NETFIND = 2: Default. CPLEX also uses reflection scaling (that is, it multiplies rows by -1) in an attempt to extract a larger network.
  NETFIND = 3: CPLEX uses general scaling, rescaling both rows and columns, in an attempt to extract a larger network.
  In terms of total solution time expended, it may or may not be advantageous to extract the largest possible network. Characteristics of your problem will determine the tradeoff between network size and the number of simplex iterations required to finish solving the model after solving the embedded network.
  Even if your problem does not conform precisely to network conventions, the network optimizer may still be advantageous to use. When it is possible to transform the original statement of a linear program into network conventions by these algebraic operations:
  - changing the signs of coefficients.
  - multiplying constraints by constants.
  - rescaling columns.
  - adding or eliminating redundant relations.
  then CPLEX will carry out such transformations automatically if you set the NETFIND parameter appropriately.
PREPASS If your LP problem includes network structures, there is a possibility that CPLEX preprocessing may eliminate those structures from your model. For that reason, you should consider turning off preprocessing before you invoke the network optimizer on a problem.
  PREPASS = -1: Default. Determined automatically.
  PREPASS = 0: Do not use Presolve.
 
logfile Name of file to write the CPLEX log information to. If empty, no log is written.
 
savefile Name of a file to save the CPLEX problem object. This is useful for sending problems to ILOG for analysis. The format of the file is controlled by the savemode. If empty, no file is written.
 
savemode The format of the file given in savefile is possible to choose by setting savemode to one of the following values:
 
 
1 SAV Binary SAV format
2 MPS MPS format (ASCII)
3 LP CPLEX LP format (ASCII)
4 RMP MPS file with generic names
5 REW MPS file with generic names
6 RLP LP file with generic names
 
  Modes 4-6 are of limited interest, since the TOMLAB interface does not provide a way to change the default row names.
 
netfile File for input.
 

Description of Outputs
Result structure. The following fields are used:
 
 
x Solution vector x with decision variable values (n × 1 vector).
slack Slack variables (m × 1 vector).
v Lagrangian multipliers (dual solution vector) (m × 1 vector).
rc Reduced costs. Lagrangian multipliers for simple bounds on x.
f_k Objective function value f(x)=cT*x at optimum.
 
Inform Result of CPLEX run. See the m-file help.
Iter Number of iterations.

« Previous « Start » Next »