This chapter provides information about additional problem classes and functionality provided in the Java API.
Network flow problems are a special class of linear optimization problems which has many applications. A network consists of a set of points connected by a set of lines. Usually the points and lines are called nodes and arcs. Arcs may have an direction on them. The network is directed if all arcs are directed. The class of network flow problems is defined as follows.
Let be a directed network of nodes
and arcs
. Associated with every arc
is a cost
and a capacity
. Moreover, associated with each node
in the network is a lower limit
and an upper limit
on the demand (supply) of the node. The minimum cost of a network flow problem can be stated as follows:
![]() |
(6.1.1) |
A classical example of a network flow problem is the transportation problem where the objective is to distribute goods from warehouses to customers at lowest possible total cost, see [7] for a detailed application reference.
The above graph formulation of the network flow problem implies the structural properties. Each variable appears in exactly two constraints with a numerical value of either or
.
It is well-known that problems with network flow structure can be solved efficiently with a specialized version of the simplex method. MOSEK includes such a network simplex implementation which can be called either directly using Task.netoptimize or indirectly by letting the standard simplex optimizer extract the embedded network. This section shows how to solve a network problem by a direct call to Task.netoptimize. For further details on how to exploit embedded network in the standard simplex optimizer, see Section 8.3.1.
The following is an example of a linear network optimization problem:
![]() |
(6.1.2) |
having the bounds .
The corresponding graph is displayed in fig.6.1.
In this section we will show how to solve (6.1.2) with the network optimizer.
The Java program included below, which solves this problem, is distributed with MOSEK and can be found in the directory
mosek\6\tools\examples\java
There are a few important differences between the linear network optimization example in section 6.1.1.1 and the general linear optimization problem in section 5.2.
Often problems contains both large parts with network structure and some non-network constraints or variables — such problems are said to have embedded network structure.
A linear optimization with embedded network structure problem can be written as :
![]() |
(6.2.1) |
Where the constraints
![]() |
(6.2.2) |
defines a network as explained in section 6.1, and the constraints
![]() |
(6.2.3) |
defines the general non-network linear constraints. As an example consider the small linear optimization problem
![]() |
(6.2.4) |
with the bounds
![]() |
Recalling the network flow problem structural properties from section 6.1.1, each variable should appear in exactly two constraints with coefficients of either or
.
At first glance it does not seem to contain any network structure, but if we scale constraints 1-4 by respectively 2.0, 2.0, 4.0, 4.0 and columns 1-2 by -1.0, 0.1 we get the following problem :
![]() |
(6.2.5) |
with the bounds
![]() |
This corresponds to the network flow problem in section 6.1.1 plus one extra non-network constraint. We cannot use the network optimizer directly on the above problem since the last constraint destroys the network property. Finding the largest possible network structure in a linear optimization problem is computationally difficult, so MOSEK offers a heuristic Task.netextraction that attempts to find suitable scaling factors maximizing numbers of network constraints and variables. Assuming that the embedded network structure is dominant and the problem has few non-network constraints, we can exploit this structure and potentially speed up the optimization. Since the network constraints can be handled efficiently by the specialized network optimizer, the following idea is used:
An embedded network can be exploited by this scheme in two ways:
The first method is more difficult than the second, but also offers much more flexibility. In 6.2.1 the first method is demonstrated by a code example below. For further details on exploiting embedded network structure in the standard simplex optimizer, see section 8.3.1.
MOSEK is distributed with some network examples which can be found in the directory
mosek\6\tools\examples
The example given in this section demonstrates how to extract and optimize embedded network structure in a arbitrary linear optimization problem. The following idea is used
In the above example we only optimize the embedded network problem. We still need to use the found network solution as a hot-start for the simplex optimizer and solve the original problem. This involves unscaling the network solution back to same unit measure as the original problem. In the example
mosek\6\tools\examples\java\network3.java
we show how to convert the network solution into a valid hot-start for the simplex optimizer.