14.3 Sensitivity Analysis¶
Given an optimization problem it is often useful to obtain information about how the optimal objective value changes when the problem parameters are perturbed. E.g, assume that a bound represents the capacity of a machine. Now, it may be possible to expand the capacity for a certain cost and hence it is worthwhile knowing what the value of additional capacity is. This is precisely the type of questions the sensitivity analysis deals with.
Analyzing how the optimal objective value changes when the problem data is changed is called sensitivity analysis.
References
The book [Chvatal83] discusses the classical sensitivity analysis in Chapter 10 whereas the book [RTV97] presents a modern introduction to sensitivity analysis. Finally, it is recommended to read the short paper [Wal00] to avoid some of the pitfalls associated with sensitivity analysis.
Warning
Currently, sensitivity analysis is only available for continuous linear optimization problems. Moreover, MOSEK can only deal with perturbations of bounds and objective function coefficients.
14.3.1 Sensitivity Analysis for Linear Problems¶
14.3.1.1 The Optimal Objective Value Function¶
Assume that we are given the problem
and we want to know how the optimal objective value changes as
where
shows the optimal objective value as a function of
It is possible to prove that the function (14.4) is a piecewise linear and convex function, i.e. its graph may look like in Fig. 14.1 and Fig. 14.2.

Fig. 14.1

Fig. 14.2
Clearly, if the function
which is called the shadow price related to
for which
Since
The function
Given these definitions it should be clear how linearity intervals and shadow prices are defined for the parameters
14.3.1.1.1 Equality Constraints¶
In MOSEK a constraint can be specified as either an equality constraint or a ranged constraint. If some constraint
Thus for an equality constraint the upper and the lower bounds (which are equal) are perturbed simultaneously. Therefore, MOSEK will handle sensitivity analysis differently for a ranged constraint with
14.3.1.2 The Basis Type Sensitivity Analysis¶
The classical sensitivity analysis discussed in most textbooks about linear optimization, e.g. [Chvatal83], is based on an optimal basis. This method may produce misleading results [RTV97] but is computationally cheap. This is the type of sensitivity analysis implemented in MOSEK.
We will now briefly discuss the basis type sensitivity analysis. Given an optimal basic solution which provides a partition of variables into basic and non-basic variables, the basis type sensitivity analysis computes the linearity interval
In summary, the basis type sensitivity analysis is computationally cheap but does not provide complete information. Hence, the results of the basis type sensitivity analysis should be used with care.
14.3.1.3 Example: Sensitivity Analysis¶
As an example we will use the following transportation problem. Consider the problem of minimizing the transportation cost between a number of production plants and stores. Each plant supplies a number of goods and each store has a given demand that must be met. Supply, demand and cost of transportation per unit are shown in Fig. 14.3.

Fig. 14.3 Supply, demand and cost of transportation.¶
If we denote the number of transported goods from location
subject to
The sensitivity parameters are shown in Table 14.1 and Table 14.2.
Con. |
||||
---|---|---|---|---|
Var. |
||||
Var. |
||||
---|---|---|---|---|
Examining the results from the sensitivity analysis we see
that for constraint number
If the upper bound on constraint
then the optimal objective value will increase by the value
14.3.2 Sensitivity Analysis with MOSEK¶
MOSEK provides the functions Task.primalsensitivity
and Task.dualsensitivity
for performing sensitivity analysis. The code in Listing 14.2 gives an example of its use.
here
to download.¶package com.mosek.example;
import mosek.*;
public class sensitivity {
public static void main (String[] args) {
// Since the value infinity is never used, we define
// 'infinity' symbolic purposes only
double
infinity = 0;
try (Task task = new Task()) {
mosek.boundkey[] bkc = {
mosek.boundkey.up, mosek.boundkey.up,
mosek.boundkey.up, mosek.boundkey.fx,
mosek.boundkey.fx, mosek.boundkey.fx,
mosek.boundkey.fx
};
mosek.boundkey[] bkx = {
mosek.boundkey.lo, mosek.boundkey.lo,
mosek.boundkey.lo, mosek.boundkey.lo,
mosek.boundkey.lo, mosek.boundkey.lo,
mosek.boundkey.lo
};
int[] ptrb = {0, 2, 4, 6, 8, 10, 12};
int[] ptre = {2, 4, 6, 8, 10, 12, 14};
int[] sub = {0, 3, 0, 4, 1, 5, 1, 6, 2, 3, 2, 5, 2, 6};
double[] blc = { -infinity, -infinity,
-infinity, 800, 100, 500, 500
};
double[] buc = {400, 1200, 1000, 800, 100, 500, 500};
double[] c = {1.0, 2.0, 5.0, 2.0, 1.0, 2.0, 1.0};
double[] blx = {0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0};
double[] bux = {infinity, infinity,
infinity, infinity,
infinity, infinity,
infinity
};
double[] val = {1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0,
1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0
};
int numcon = 7; /* Number of constraints. */
int numvar = 7; /* Number of variables. */
int NUMANZ = 14; /* Number of non-zeros in A. */
// Directs the log task stream to the user specified
// method task_msg_obj.print
task.set_Stream(
mosek.streamtype.log,
new mosek.Stream()
{ public void stream(String msg) { System.out.print(msg); }});
task.inputdata(numcon, numvar,
c,
0.0,
ptrb,
ptre,
sub,
val,
bkc,
blc,
buc,
bkx,
blx,
bux);
/* A maximization problem */
task.putobjsense(mosek.objsense.minimize);
task.optimize();
/* Analyze upper bound on c1 and the equality constraint on c4 */
int subi[] = {0, 3};
mosek.mark marki[] = {mosek.mark.up, mosek.mark.up};
/* Analyze lower bound on the variables x12 and x31 */
int subj[] = {1, 4};
mosek.mark markj[] = {mosek.mark.lo, mosek.mark.lo};
double[] leftpricei = new double[2];
double[] rightpricei = new double[2];
double[] leftrangei = new double[2];
double[] rightrangei = new double[2];
double[] leftpricej = new double[2];
double[] rightpricej = new double[2];
double[] leftrangej = new double[2];
double[] rightrangej = new double[2];
task.primalsensitivity( subi,
marki,
subj,
markj,
leftpricei,
rightpricei,
leftrangei,
rightrangei,
leftpricej,
rightpricej,
leftrangej,
rightrangej);
System.out.println("Results from sensitivity analysis on bounds:\n");
System.out.println("For constraints:\n");
for (int i = 0; i < 2; ++i)
System.out.print("leftprice = " + leftpricei[i] +
" rightprice = " + rightpricei[i] +
" leftrange = " + leftrangei[i] +
" rightrange = " + rightrangei[i] + "\n");
System.out.print("For variables:\n");
for (int i = 0; i < 2; ++i)
System.out.print("leftprice = " + leftpricej[i] +
" rightprice = " + rightpricej[i] +
" leftrange = " + leftrangej[i] +
" rightrange = " + rightrangej[i] + "\n");
double[] leftprice = new double[2];
double[] rightprice = new double[2];
double[] leftrange = new double[2];
double[] rightrange = new double[2];
int subc[] = {2, 5};
task.dualsensitivity( subc,
leftprice,
rightprice,
leftrange,
rightrange
);
System.out.println(
"Results from sensitivity analysis on objective coefficients:"
);
for (int i = 0; i < 2; ++i)
System.out.print("leftprice = " + leftprice[i] +
" rightprice = " + rightprice[i] +
" leftrange = " + leftrange[i] +
" rightrange = " + rightrange[i] + "\n");
} catch (mosek.Exception e)
/* Catch both mosek.Error and mosek.Warning */
{
System.out.println ("An error or warning was encountered");
System.out.println (e.getMessage ());
throw e;
}
}
}