Given an optimization problem it is often useful to obtain information about how the optimal objective value change when the problem parameters are perturbed. For instance assume that a bound represents a capacity of a machine. Now, it may be possible to expand the capacity for a certain cost and hence it worthwhile to know what the value of additional capacity is. This is precisely the type of questions sensitivity analysis deals with.
Analyzing how the optimal objective value changes when the problem data is changed is called sensitivity analysis.
Currently, sensitivity analysis is only available for continuous linear optimization problems. Moreover, MOSEK can only deal with perturbations in bounds or objective coefficients.
The book [17] discusses the classical sensitivity analysis in Chapter 10 whereas the book [12, Chapter 19] presents a modern introduction to sensitivity analysis. Finally, it is recommended to read the short paper [2] to avoid some of the pitfalls associated with sensitivity analysis.
Assume that we are given the problem
![]() |
(14.4.1) |
and we want to know how the optimal objective value changes as is perturbed. In order to answer this question then define the perturbed problem for
as follows
![]() |
(14.4.2) |
where is the ith column of the identity matrix. The function
![]() |
(14.4.3) |
shows the optimal objective value as a function of . Note that a change in
corresponds to a perturbation in
and hence (14.4.3) shows the optimal objective value as a function of
.
It is possible to prove that the function (14.4.3) is a piecewise linear and convex function i.e. the function may look like the illustration in Figure 14.1.
![]() ![]() ![]() |
Clearly, if the function does not change much when
is changed, then we can conclude that the optimal objective value is insensitive to changes in
. Therefore, we are interested in how
changes for small changes in
. Now define
![]() |
(14.4.4) |
to be the so called shadow price related to . The shadow price specifies how the objective value changes for small changes in
around zero. Moreover, we are interested in the so called linearity interval
![]() |
(14.4.5) |
for which
![]() |
(14.4.6) |
To summarize the sensitivity analysis provides a shadow price and the linearity interval in which the shadow price is constant.
The reader may have noticed that we are sloppy in the definition of the shadow price. The reason is that the shadow price is not defined in the right example in Figure 14.1 because the function is not differentiable for
. However, in that case we can define a left and a right shadow price and a left and a right linearity interval.
In the above discussion we only discussed changes in . We define the other optimal objective value functions as follows
![]() |
(14.4.7) |
Given these definitions it should be clear how linearity intervals and shadow prices are defined for the parameters etc.
In MOSEK a constraint can be specified as either an equality constraints or a ranged constraints. Suppose constraint i is an equality constraint. We then define the optimal value function for constraint i by
![]() |
(14.4.8) |
Thus for a equality constraint the upper and lower bound (which are equal) are perturbed simultaneously. From the point of view of MOSEK sensitivity analysis a ranged constrain with therefore differs from an equality constraint.
The classical sensitivity analysis discussed in most textbooks about linear optimization, e.g. [17, Chapter 10], is based on an optimal basic solution or equivalently on an optimal basis. This method may produce misleading results [12, Chapter 19] but is computationally cheap. Therefore, and for historical reasons this method is available 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 then the basis type sensitivity analysis computes the linearity interval such that the basis remains optimal for the perturbed problem. A shadow price associated with the linearity interval is also computed. However, it is well-known that an optimal basic solution may not be unique and therefore the result depends on the optimal basic solution employed in the sensitivity analysis. This implies that the computed interval is only a subset of the largest interval for which the shadow price is constant. Furthermore, the optimal objective value function might have a breakpoint for
. In this case the basis type sensitivity method will only provide a subset of either the left or the right 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.
Another method for computing the complete linearity interval is called the optimal partition type sensitivity analysis. The main drawback to the optimal partition type sensitivity analysis is it is computationally expensive. This type of sensitivity analysis is currently provided as an experimental feature in MOSEK.
Given optimal primal and dual solutions to (14.4.1) i.e. and
then the optimal objective value is given by
![]() |
(14.4.9) |
The left and right shadow prices and
for
is given by the pair of optimization problems
![]() |
(14.4.10) |
and
![]() |
(14.4.11) |
The above two optimization problems makes it easy to interpret-ate the shadow price. Indeed assume that is an arbitrary optimal solution then it must hold
![]() |
(14.4.12) |
Next the linearity interval for
is computed by solving the two optimization problems
![]() |
(14.4.13) |
and
![]() |
(14.4.14) |
The linearity intervals and shadow prices for
and
can be computed in a similar way to how it is computed for
.
The left and right shadow price for denoted
and
respectively is given by the pair optimization problems
![]() |
(14.4.15) |
and
![]() |
(14.4.16) |
Once again the above two optimization problems makes it easy to interpret-ate the shadow prices. Indeed assume that is an arbitrary primal optimal solution then it must hold
![]() |
(14.4.17) |
The linearity interval for a
is computed as follows
![]() |
(14.4.18) |
and
![]() |
(14.4.19) |
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 Figure 14.2.
If we denote the number of transported goods from location i to location j by , the problem can be formulated as the linear optimization problem
minimize
![]() |
(14.4.20) |
subject to
![]() |
(14.4.21) |
The basis type and the optimal partition type sensitivity results for the transportation problem is shown in Table 14.1 and 14.2 respectively.
Basis type
Con.
1
-300.00
0.00
3.00
3.00
2
-700.00
+∞
0.00
0.00
3
-500.00
0.00
3.00
3.00
4
-0.00
500.00
4.00
4.00
5
-0.00
300.00
5.00
5.00
6
-0.00
700.00
5.00
5.00
7
-500.00
700.00
2.00
2.00
Var.
-∞
300.00
0.00
0.00
-∞
100.00
0.00
0.00
-∞
0.00
0.00
0.00
-∞
500.00
0.00
0.00
-∞
500.00
0.00
0.00
-∞
500.00
0.00
0.00
-0.000000
500.00
2.00
2.00
Optimal partition type
Con.
1
-300.00
500.00
3.00
1.00
2
-700.00
+∞
-0.00
-0.00
3
-500.00
500.00
3.00
1.00
4
-500.00
500.00
2.00
4.00
5
-100.00
300.00
3.00
5.00
6
-500.00
700.00
3.00
5.00
7
-500.00
700.00
2.00
2.00
Var.
-∞
300.00
0.00
0.00
-∞
100.00
0.00
0.00
-∞
500.00
0.00
2.00
-∞
500.00
0.00
0.00
-∞
500.00
0.00
0.00
-∞
500.00
0.00
0.00
-∞
500.00
0.00
2.00
Looking at the results from the optimal partition type sensitivity analysis we see that for the constraint number 1 we have
Basis type
Var.
-∞
3.00
300.00
300.00
-∞
∞
100.00
100.00
-2.00
∞
0.00
0.00
-∞
2.00
500.00
500.00
-3.00
∞
500.00
500.00
-∞
2.00
500.00
500.00
-2.00
∞
0.00
0.00
Optimal partition type
Var.
-∞
3.00
300.00
300.00
-∞
∞
100.00
100.00
-2.00
∞
0.00
0.00
-∞
2.00
500.00
500.00
-3.00
∞
500.00
500.00
-∞
2.00
500.00
500.00
-2.00
∞
0.00
0.00
and
. Therefore, we have a left linearity interval of [-300,0] and a right interval of [0,500]. The corresponding left and right shadow price is 3 and 1 respectively. This implies that if the upper bound on constraint 1 increases by
![]() |
(14.4.22) |
then the optimal objective value will decrease by the value
![]() |
(14.4.23) |
Correspondingly, if the upper bound on constraint 1 is decreased by
![]() |
(14.4.24) |
then the optimal objective value will increased by the value
![]() |
(14.4.25) |
A sensitivity analysis can be performed with the MOSEK command line tool using the command
mosek myproblem.mps -sen sensitivity.ssp
where sensitivity.ssp is a file in the format described in the next section. The ssp file describes which parts of the problem the sensitivity analysis should be performed on.
By default results are written to a file named myproblem.sen. If necessary, this filename can be changed by setting the
MSK_SPAR_SENSITIVITY_RES_FILE_NAME
parameter By default a basis type sensitivity analysis is performed. However, the type of sensitivity analysis (basis or optimal partition) can be changed by setting the parameter
MSK_IPAR_SENSITIVITY_TYPE
appropriately. Following values are accepted for this parameter:
It is also possible to use the command line
mosek myproblem.mps -d MSK_IPAR_SENSITIVITY_ALL MSK_ON
in which case a sensitivity analysis on all the parameters is performed.
MOSEK employs an MPS like file format to specify on which model parameters the sensitivity analysis should be performed. As the optimal partition type sensitivity analysis can be computationally expensive it is important to limit the sensitivity analysis.
* A comment BOUNDS CONSTRAINTS U|L|LU [cname1] U|L|LU [cname2]-[cname3] BOUNDS VARIABLES U|L|LU [vname1] U|L|LU [vname2]-[vname3] OBJECTIVE VARIABLES [vname1] [vname2]-[vname3]Figure 14.3: The sensitivity analysis file format. |
The format of the sensitivity specification file is shown in figure 14.3, where capitalized names are keywords, and names in brackets are names of the constraints and variables to be included in the analysis.
The sensitivity specification file has three sections, i.e.
A line in the body of a section must begin with a whitespace. In the BOUNDS sections one of the keys L, U, and LU must appear next. These keys specify whether the sensitivity analysis is performed on the lower bound, on the upper bound, or on both the lower and the upper bound respectively. Next, a single constraint (variable) or range of constraints (variables) is specified.
Recall from Section 14.4.1.1 that equality constraints are handled in a special way. Sensitivity analysis of an equality constraint can be specified with either L, U, or LU, all indicating the same, namely that upper and lower bounds (which are equal) are perturbed simultaneously.
As an example consider
BOUNDS CONSTRAINTS L "cons1" U "cons2" LU "cons3"-"cons6"
which requests that sensitivity analysis is performed on the lower bound of the constraint named cons1, on the upper bound of the constraint named cons2, and on both lower and upper bound on the constraints named cons3 to cons6.
It is allowed to use indexes instead of names, for instance
BOUNDS CONSTRAINTS L "cons1" U 2 LU 3 - 6
The character “*” indicates that the line contains a comment and is ignored.
As an example consider the sensitivity.ssp file shown in Figure 14.4.
* Comment 1 BOUNDS CONSTRAINTS U "c1" * Analyze upper bound for constraint named c1 U 2 * Analyze upper bound for the second constraint U 3-5 * Analyze upper bound for constraint number 3 to number 5 BOUNDS VARIABLES L 2-4 * This section specifies which bounds on variables should be analyzed L "x11" OBJECTIVE VARIABLES "x11" * This section specifies which objective coefficients should be analyzed 2Figure 14.4: Example of the sensitivity file format. |
The command
mosek transport.lp -sen sensitivity.ssp -d MSK_IPAR_SENSITIVITY_TYPE MSK_SENSITIVITY_TYPE_BASIS
produces the transport.sen file shown below.
BOUNDS CONSTRAINTS INDEX NAME BOUND LEFTRANGE RIGHTRANGE LEFTPRICE RIGHTPRICE 0 c1 UP -6.574875e-18 5.000000e+02 1.000000e+00 1.000000e+00 2 c3 UP -6.574875e-18 5.000000e+02 1.000000e+00 1.000000e+00 3 c4 FIX -5.000000e+02 6.574875e-18 2.000000e+00 2.000000e+00 4 c5 FIX -1.000000e+02 6.574875e-18 3.000000e+00 3.000000e+00 5 c6 FIX -5.000000e+02 6.574875e-18 3.000000e+00 3.000000e+00 BOUNDS VARIABLES INDEX NAME BOUND LEFTRANGE RIGHTRANGE LEFTPRICE RIGHTPRICE 2 x23 LO -6.574875e-18 5.000000e+02 2.000000e+00 2.000000e+00 3 x24 LO -inf 5.000000e+02 0.000000e+00 0.000000e+00 4 x31 LO -inf 5.000000e+02 0.000000e+00 0.000000e+00 0 x11 LO -inf 3.000000e+02 0.000000e+00 0.000000e+00 OBJECTIVE VARIABLES INDEX NAME LEFTRANGE RIGHTRANGE LEFTPRICE RIGHTPRICE 0 x11 -inf 1.000000e+00 3.000000e+02 3.000000e+02 2 x23 -2.000000e+00 +inf 0.000000e+00 0.000000e+00
Setting the parameter
MSK_IPAR_LOG_SENSITIVITY
to 1 or 0 (default) controls whether or not the results from sensitivity calculations are printed to the message stream.
The parameter
MSK_IPAR_LOG_SENSITIVITY_OPT
controls the amount of debug information on internal calculations from the sensitivity analysis.