CPLEX Appendix E

This page is part of the CPLEX Manual. See CPLEX.

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:

• x_a 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.

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

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

c_a, 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:

• s_n 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.

T_n 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:

Failed to parse (unknown function "\multicolumn"): {\displaystyle \begin{array}{rccccl} \min\limits_{x} & \multicolumn{5}{l}{{\sum\limits_{a \in A}c_{a}x_{a}}} \\ & \\ s/t & \multicolumn{5}{l}{\sum\limits_{a \in T_a}x_{a} - \sum\limits_{a \in H_a}x_{a} = s_{n} \forall n \in N}\\ & l_{a} & \leq & x_{a} & \leq & u_{a} \\ \end{array} }

A test routines that illustrates a simple problem is included in the TOMLAB distribution. <xr id="fig:netProblem" /> shows the network problem solved:

The following code will call the network solver and deliver the optimal solution.

<figure id="fig:netProblem">

Network problem in cpxNetTest1.m.

</figure>

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.

cpxcb_BARRIER

• cpxcb_BARRIER