6. Advanced API tutorial


This chapter provides information about additional problem classes and functionality provided in the Java API.

6.1. Linear network flow problems

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 [[MathCmd 125]] be a directed network of nodes [[MathCmd 126]] and arcs [[MathCmd 127]]. Associated with every arc [[MathCmd 128]] is a cost [[MathCmd 129]] and a capacity [[MathCmd 130]]. Moreover, associated with each node [[MathCmd 131]] in the network is a lower limit [[MathCmd 132]] and an upper limit [[MathCmd 133]] on the demand (supply) of the node. The minimum cost of a network flow problem can be stated as follows:

\begin{math}\nonumber{}\begin{array}{lcccccl}\nonumber{}\mbox{minimize} &  &  & \sum \limits _{{(i,j)\in{}\mathcal{A}}}c_{{ij}}x_{{ij}} &  &  & \\\nonumber{}\mbox{subject to} & l^{c}_{{i}} & \leq{} & \sum \limits _{{\lbrace{}j:(i,j)\in{}\mathcal{A}\rbrace{}}}x_{{ij}}-\sum \limits _{{\lbrace{}j:(j,i)\in{}\mathcal{A}\rbrace{}}}x_{{ji}} & \leq{} & u^{c}_{{i}} & \forall i\in{}\mathcal{N},\\\nonumber{} & l^{x}_{{ij}} & \leq{} & x_{{ij}} & \leq{} & u^{x}_{{ij}} & \forall (i,j)\in{}\mathcal{A}.\end{array}\end{math} (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 [[MathCmd 135]] or [[MathCmd 136]].

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.

6.1.1. A linear network flow problem example

The following is an example of a linear network optimization problem:

\begin{math}\nonumber{}\begin{array}{lccccccccccccl}\nonumber{}\mbox{maximize} & x_{0} &  &  & + & x_{2} & + &  & - & x_{4} & + & x_{5} &  & \\\nonumber{}\mbox{subject to} & -x_{0} &  &  &  &  & + & x_{3} &  &  &  &  & = & 1,\\\nonumber{} &  &  &  &  & x_{2} & - & x_{3} & + & x_{4} & + & x_{5} & = & -2,\\\nonumber{} & x_{0} & - & x_{1} &  &  &  &  & - & x_{4} & - & x_{5} & = & 0,\\\nonumber{} &  &  & x_{1} & - & x_{2} & + &  &  &  &  &  & = & 0,\end{array}\end{math} (6.1.2)

having the bounds [[MathCmd 138]].

The corresponding graph [[MathCmd 125]] is displayed in fig.6.1.

Figure 6.1: Simple network.

6.1.1.1. Source code

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

/* Copyright: Copyright (c) 1998-2011 MOSEK ApS, Denmark. All rights reserved. File: network1.java Demonstrates a simple use of the network optimizer. Purpose: 1. Specify data for a network. 2. Solve the network problem with the network optimizer. */ package network1; class msgclass extends mosek.Stream { public msgclass () { super (); } public void stream (String msg) { System.out.print (msg); } } public class network1 { static final int NUMCON = 4; static final int NUMVAR = 6; public static void main (String[] args) { double infinity = 0; double cc[] = {0.0, 0.0, 0.0, 0.0}; double cx[] = {1.0, 0.0, 1.0, 0.0, -1.0, 1.0}; mosek.Env.boundkey bkc[] = {mosek.Env.boundkey.fx, mosek.Env.boundkey.fx, mosek.Env.boundkey.fx, mosek.Env.boundkey.fx}; double blc[] = {1.0, 1.0, -2.0, 0.0}; double buc[] = {1.0, 1.0, -2.0, 0.0}; mosek.Env.boundkey bkx[] = {mosek.Env.boundkey.lo, mosek.Env.boundkey.lo, mosek.Env.boundkey.lo, mosek.Env.boundkey.lo, mosek.Env.boundkey.lo, mosek.Env.boundkey.lo}; double blx[] = {0.0, 0.0, 0.0, 0.0, 0.0, 0.0}; double bux[] = {+infinity, +infinity, +infinity, +infinity, +infinity, +infinity}; int from[] = {0, 2, 3, 1, 1, 1}; int to[] = {2, 3, 1, 0, 2, 2}; // Specify solution data double[] xc = new double[NUMCON]; double[] xx = new double[NUMVAR]; double[] y = new double[NUMCON]; double[] slc = new double[NUMCON]; double[] suc = new double[NUMCON]; double[] slx = new double[NUMVAR]; double[] sux = new double[NUMVAR]; mosek.Env.stakey[] skc = new mosek.Env.stakey[NUMCON]; mosek.Env.stakey[] skx = new mosek.Env.stakey[NUMVAR]; for (int i = 0; i < NUMCON; ++i) skc[i] = mosek.Env.stakey.unk; for (int i = 0; i < NUMVAR; ++i) skx[i] = mosek.Env.stakey.unk; mosek.Env env = null; mosek.Task dummytask = null; mosek.Env.solsta[] solsta = new mosek.Env.solsta[1]; mosek.Env.prosta[] prosta = new mosek.Env.prosta[1]; try { // Make mosek environment. env = new mosek.Env (); // Direct the env log stream to the user specified // method env_msg_obj.print msgclass env_msg_obj = new msgclass (); env.set_Stream (mosek.Env.streamtype.log,env_msg_obj); // Initialize the environment. env.init (); // Create a task object linked with the environment env. dummytask = new mosek.Task (env, NUMCON, NUMVAR); // Directs the log task stream to the user specified // method task_msg_obj.print msgclass task_msg_obj = new msgclass (); dummytask.set_Stream (mosek.Env.streamtype.log,task_msg_obj); // Set the problem to be maximized dummytask.putobjsense(mosek.Env.objsense.maximize); // Solve the network problem dummytask.netoptimize(cc, cx, bkc, blc, buc, bkx, blx, bux, from, to, prosta, solsta, false, skc, skx, xc, xx, y, slc, suc, slx, sux); switch (solsta[0]) { case optimal: System.out.println("Embedded network problem is optimal"); break; case prim_infeas_cer: System.out.println("Embedded network problem is primal infeasible"); break; case dual_infeas_cer: System.out.println("Embedded network problem is dual infeasible"); break; default: System.out.println("Embedded network problem solsta : " + solsta[0]); break; } } catch (Exception e) /* Catch both mosek.Error and mosek.Warning */ { System.out.println ("An error or warning was encountered"); System.out.println (e.getMessage ()); } // Dispose of task end environment if (dummytask != null) dummytask.dispose (); if (env != null) env.dispose (); } }

6.1.1.2. Example code comments

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.

  • MOSEK allows that network problems can be inputted and optimized using one function call to the function Task.netoptimize. This is more efficient and uses less memory than a call to the standard optimizer.
  • Since we know that each column of matrix A has two non-zeroes, it can be stored in two arrays, from and to, specifying the origin and destination of the arcs (variables), see graph in fig.fig-network.
  • The solution is written directly to skc, skx, xc, xx, y, slc, suc, slx and sux by Task.netoptimize.

6.2. Embedded network flow problems

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 :

\begin{math}\nonumber{}\begin{array}{lccccl}\nonumber{}\mbox{minimize} &  &  & c^{T}x+c^{f} &  & \\\nonumber{}\mbox{subject to} & l^{c}_{N} & \leq{} & Nx & \leq{} & u^{c}_{N},\\\nonumber{} & l^{c} & \leq{} & Ax & \leq{} & u^{c},\\\nonumber{} & l^{x} & \leq{} & x & \leq{} & u^{x},\end{array}\end{math} (6.2.1)

Where the constraints

\begin{math}\nonumber{}\begin{array}{lcccl}\nonumber{}l^{c}_{N} & \leq{} & Nx & \leq{} & u^{c}_{N}\end{array}\end{math} (6.2.2)

defines a network as explained in section 6.1, and the constraints

\begin{math}\nonumber{}\begin{array}{lcccl}\nonumber{}l^{c} & \leq{} & Ax & \leq{} & u^{c}\end{array}\end{math} (6.2.3)

defines the general non-network linear constraints. As an example consider the small linear optimization problem

\begin{math}\nonumber{}\begin{array}{lccccccccccccl}\nonumber{}\mbox{maximize} & -x_{0} &  &  & + & x_{2} &  &  & - & x_{4} & + & x_{5} &  & \\\nonumber{}\mbox{subject to} & 0.50x_{0} &  &  &  &  & + & 0.50x_{3} &  &  &  &  & = & 0.5,\\\nonumber{} &  &  &  &  & 0.50x_{2} & - & 0.50x_{3} & + & 0.50x_{4} & + & 0.50x_{5} & = & -1,\\\nonumber{} & -0.25x_{0} & + & -2.50x_{1} & + &  &  &  & - & 0.25x_{4} & - & 0.25x_{5} & = & 0,\\\nonumber{} &  &  & 2.50x_{1} & - & 0.25x_{2} &  &  &  &  &  &  & = & 0,\\\nonumber{} &  & - & x_{1} & + & x_{2} & + & x_{3} &  &  & + & x_{5} & \geq{} & 6,\end{array}\end{math} (6.2.4)

with the bounds

\begin{displaymath}\nonumber{}-\infty \leq{}x_{0}\leq{}0,0\leq{}x_{j}\leq{}\infty \mbox{ for }j=1\ldots 5.\end{displaymath}

Recalling the network flow problem structural properties from section 6.1.1, each variable should appear in exactly two constraints with coefficients of either [[MathCmd 135]] or [[MathCmd 136]].

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 :

\begin{math}\nonumber{}\begin{array}{lccccccccccccl}\nonumber{}\mbox{maximize} & x_{0} &  &  & + & x_{2} & + &  & - & x_{4} & + & x_{5} &  & \\\nonumber{}\mbox{subject to} & -x_{0} &  &  &  &  & + & x_{3} &  &  &  &  & = & 1,\\\nonumber{} &  &  &  &  & x_{2} & - & x_{3} & + & x_{4} & + & x_{5} & = & -2,\\\nonumber{} & x_{0} & - & x_{1} &  &  &  &  & - & x_{4} & - & x_{5} & = & 0,\\\nonumber{} &  &  & x_{1} & - & x_{2} & + &  &  &  &  &  & = & 0,\\\nonumber{} &  &  & x_{1} & + & x_{2} & + & x_{3} &  &  & + & x_{5} & \geq{} & 6,\end{array}\end{math} (6.2.5)

with the bounds

\begin{displaymath}\nonumber{}0\leq{}x_{j}\leq{}\infty \mbox{ for }j=0\ldots 5.\end{displaymath}

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.

6.2.1. Example: Exploit embedded network flow structure in the simplex optimizer

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

  • Read an arbitrary linear optimization problem into a task.
  • Use the Task.netextraction function to extract embedded network structure.
  • Optimize the network problem using the Task.netoptimize function.

/* Copyright: Copyright (c) 1998-2011 MOSEK ApS, Denmark. All rights reserved. File: network2.java Demonstrates a simple use of network structure in a model. Purpose: 1. Read an optimization problem from an user specified MPS file. 2. Extract the embedded network. 3. Solve the embedded network with the network optimizer. Note that the general simplex optimizer called though MSK_optimize can also extract embedded network and solve it with the network optimizer. The direct call to the network optimizer, which is demonstrated here, is offered as an option to save memory and overhead when solving either many or large network problems. */ package network2; import mosek.*; class msgclass extends mosek.Stream { public msgclass () { super (); } public void stream (String msg) { System.out.print (msg); } } public class network2 { public static void main (String[] args) { if (args.length != 1) { System.out.println ("Wrong arguments. The syntax is:"); System.out.println ("network2 inputfile"); } else { mosek.Env env = null; mosek.Task task = null, dummytask = null; mosek.Env.solsta[] solsta = new mosek.Env.solsta[1]; mosek.Env.prosta[] prosta = new mosek.Env.prosta[1]; try { // Make mosek environment. env = new mosek.Env (); // Direct the env log stream to the user specified // method env_msg_obj.print msgclass env_msg_obj = new msgclass (); env.set_Stream (mosek.Env.streamtype.log,env_msg_obj); // Initialize the environment. env.init (); // Create a task object linked with the environment env. // We create it initially with 0 variables and 0 columns, // since we don't know the size of the problem. task = new mosek.Task (env, 0,0); task.readdata (args[0]); int numcon,numvar; int[] netnumcon = new int[1]; int[] netnumvar = new int[1]; numcon = task.getnumcon (); numvar = task.getnumvar (); // Specify network data int[] rmap = new int[numcon]; int[] cmap = new int[numvar]; int[] netcon = new int[numcon]; int[] netvar = new int[numvar]; int[] from = new int[numvar]; int[] to = new int[numvar]; // Specify network scaling factors double[] scalcon = new double[numcon]; double[] scalvar = new double[numvar]; // Specify objective and bounds double[] cc = new double[numcon]; double[] cx = new double[numvar]; double[] blc = new double[numcon]; double[] buc = new double[numcon]; double[] blx = new double[numvar]; double[] bux = new double[numvar]; // Specify bound keys mosek.Env.boundkey[] bkc = new mosek.Env.boundkey[numcon]; mosek.Env.boundkey[] bkx = new mosek.Env.boundkey[numvar]; // Specify solution data double[] xc = new double[numcon]; double[] xx = new double[numvar]; double[] y = new double[numcon]; double[] slc = new double[numcon]; double[] suc = new double[numcon]; double[] slx = new double[numvar]; double[] sux = new double[numvar]; mosek.Env.stakey[] skc = new mosek.Env.stakey[numcon]; mosek.Env.stakey[] skx = new mosek.Env.stakey[numvar]; for( int i = 0; i < numcon; ++i ) { skc[i] = mosek.Env.stakey.unk; } for( int j = 0; j < numvar; ++j ) { skx[j] = mosek.Env.stakey.unk; } /* We just use zero cost on slacks */ for( int i = 0; i < numcon; ++i ) cc[i] = 0.0; // Extract embedded network task.netextraction(netnumcon, netnumvar, netcon, netvar, scalcon, scalvar, cx, bkc, blc, buc, bkx, blx, bux, from, to); System.out.println ("network extraction :"); System.out.println ("numcon : " + numcon + " netnumcon : " + netnumcon[0]); System.out.println ("numvar : " + numvar + " netnumvar : " + netnumvar[0]); // Create a task object linked with the environment env. dummytask = new mosek.Task (env, netnumcon[0], netnumvar[0]); // Directs the log task stream to the user specified // method task_msg_obj.print msgclass task_msg_obj = new msgclass (); dummytask.set_Stream (mosek.Env.streamtype.log,task_msg_obj); // Solve the network problem dummytask.netoptimize(cc, cx, bkc, blc, buc, bkx, blx, bux, from, to, prosta, solsta, false, skc, skx, xc, xx, y, slc, suc, slx, sux); if ( solsta[0] == mosek.Env.solsta.optimal ) { System.out.println("Embedded network problem is optimal"); } else if ( solsta[0] == mosek.Env.solsta.prim_infeas_cer ) { System.out.println("Embedded network problem is primal infeasible"); } else if ( solsta[0] == mosek.Env.solsta.dual_infeas_cer ) { System.out.println("Embedded network problem is dual infeasible"); } else { System.out.println("Embedded network problem solsta : "+solsta[0]); } } catch (mosek.ArrayLengthException e) { System.out.println ("Error: An array was too short"); System.out.println (e.toString ()); } catch (java.lang.Exception e) /* Catch both mosek.Error and mosek.Warning */ { System.out.println ("An error or warning was encountered"); System.out.println (e.getMessage ()); } // Dispose of task end environment if (dummytask != null) dummytask.dispose (); if (task != null) task.dispose (); if (env != null) env.dispose (); } } }

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.

Wed Feb 29 16:00:42 2012