« 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:
|
|
|
Σ |
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
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 »