8.1 Understanding optimizer log¶
The optimizer produces a log which splits roughly into four sections:
summary of the input data,
presolve and other pre-optimize problem setup stages,
actual optimizer iterations,
In this tutorial we show how to analyze the most important parts of the log when initially debugging a model: input data (1) and solution summary (4). For the iterations log (3) see Sec. 13.3.4 (The Interior-point Log) or Sec. 13.4.4 (The Mixed-Integer Log).
8.1.1 Input data¶
If MOSEK behaves very far from expectations it may be due to errors in problem setup. The log file will begin with a summary of the structure of the problem, which looks for instance like:
Problem Name : Objective sense : minimize Type : CONIC (conic optimization problem) Constraints : 234 Affine conic cons. : 5348 Disjunctive cons. : 0 Cones : 0 Scalar variables : 20693 Matrix variables : 0 Integer variables : 0
This can be consulted to eliminate simple errors: wrong objective sense, wrong number of variables etc. Note that some modeling tools can introduce additional variables and constraints to the model and perturb the model even further (such as by dualizing). In most MOSEK APIs the problem dimensions should match exactly what the user specified.
If this is not sufficient a bit more information can be obtained by dumping the problem to a file (see Sec. 8 (Debugging Tutorials)) and using the
anapro option of any of the command line tools. It can also be done directly with the function
MSK_analyzeproblem. This will produce a longer summary similar to:
** Variables scalar: 20414 integer: 0 matrix: 0 low: 2082 up: 5014 ranged: 0 free: 12892 fixed: 426 ** Constraints all: 20413 low: 10028 up: 0 ranged: 0 free: 0 fixed: 10385 ** Affine conic constraints (ACC) QUAD: 1 dims: 2865: 1 RQUAD: 2507 dims: 3: 2507 ** Problem data (numerics) |c| nnz: 10028 min=2.09e-05 max=1.00e+00 |A| nnz: 597023 min=1.17e-10 max=1.00e+00 blx fin: 2508 min=-3.60e+09 max=2.75e+05 bux fin: 5440 min=0.00e+00 max=2.94e+08 blc fin: 20413 min=-7.61e+05 max=7.61e+05 buc fin: 10385 min=-5.00e-01 max=0.00e+00 |F| nnz: 612301 min=8.29e-06 max=9.31e+01 |g| nnz: 1203 min=5.00e-03 max=1.00e+00
Again, this can be used to detect simple errors, such as:
Wrong type of conic constraint was used or it has wrong dimension.
The bounds for variables or constraints are incorrect or incomplete. Check if you defined bound keys for all variables. A variable for which no bound was defined is by default fixed at 0.
The model is otherwise incomplete.
Suspicious values of coefficients.
For various data sizes the model does not scale as expected.
Finally saving the problem in a human-friendly text format such as LP or PTF (see Sec. 8 (Debugging Tutorials)) and analyzing it by hand can reveal if the model is correct.
Warnings and errors
At this stage the user can encounter warnings which should not be ignored, unless they are well-understood. They can also serve as hints as to numerical issues with the problem data. A typical warning of this kind is
MOSEK warning 53: A numerically large upper bound value 2.9e+08 is specified for variable 'absh' (2613).
Warnings do not stop the problem setup. If, on the other hand, an error occurs then the model will become invalid. The user should make sure to test for errors/exceptions from all API calls that set up the problem and validate the data. See Sec. 7.3 (Errors and exceptions) for more details.
8.1.2 Solution summary¶
The last item in the log is the solution summary. In the Optimizer API it is only printed by invoking the function
188.8.131.52 Continuous problem¶
A typical solution summary for a continuous (linear, conic, quadratic) problem looks like:
Problem status : PRIMAL_AND_DUAL_FEASIBLE Solution status : OPTIMAL Primal. obj: 8.7560516107e+01 nrm: 1e+02 Viol. con: 3e-12 var: 0e+00 acc: 3e-11 Dual. obj: 8.7560521345e+01 nrm: 1e+00 Viol. con: 5e-09 var: 9e-11 acc: 0e+00
It contains the following elements:
Problem and solution status. For details see Sec. 7.2.3 (Problem and solution status).
A summary of the primal solution: objective value, infinity norm of the solution vector and maximal violations of variables and constraints of different types. The violation of a linear constraint such as \(a^Tx\leq b\) is \(\max(a^Tx-b,0)\). The violation of a conic constraint is the distance to the cone.
The same for the dual solution.
The features of the solution summary which characterize a very good and accurate solution and a well-posed model are:
Status: The solution status is
Duality gap: The primal and dual objective values are (almost) identical, which proves the solution is (almost) optimal.
Norms: Ideally the norms of the solution and the objective values should not be too large. This of course depends on the input data, but a huge solution norm can be an indicator of issues with the scaling, conditioning and/or well-posedness of the model. It may also indicate that the problem is borderline between feasibility and infeasibility and sensitive to small perturbations in this respect.
Violations: The violations are close to zero, which proves the solution is (almost) feasible. Observe that due to rounding errors it can be expected that the violations are proportional to the norm (
nrm:) of the solution. It is rarely the case that violations are exactly zero.
Solution status UNKNOWN
A typical example with solution status
UNKNOWN due to numerical problems will look like:
Problem status : UNKNOWN Solution status : UNKNOWN Primal. obj: 1.3821656824e+01 nrm: 1e+01 Viol. con: 2e-03 var: 0e+00 acc: 0e+00 Dual. obj: 3.0119004098e-01 nrm: 5e+07 Viol. con: 4e-16 var: 1e-01 acc: 0e+00
The primal and dual objective are very different.
The dual solution has very large norm.
There are considerable violations so the solution is likely far from feasible.
Follow the hints in Sec. 8.2 (Addressing numerical issues) to resolve the issue.
Solution status UNKNOWN with a potentially useful solution
UNKNOWN does not necessarily mean that the solution is completely useless. It only means that the solver was unable to make any more progress due to numerical difficulties, and it was not able to reach the accuracy required by the termination criteria (see Sec. 13.3.2 (Interior-point Termination Criterion)). Consider for instance:
Problem status : UNKNOWN Solution status : UNKNOWN Primal. obj: 3.4531019648e+04 nrm: 1e+05 Viol. con: 7e-02 var: 0e+00 acc: 0e+00 Dual. obj: 3.4529720645e+04 nrm: 8e+03 Viol. con: 1e-04 var: 2e-04 acc: 0e+00
Such a solution may still be useful, and it is always up to the user to decide. It may be a good enough approximation of the optimal point. For example, the large constraint violation may be due to the fact that one constraint contained a huge coefficient.
A primal infeasibility certificate is stored in the dual variables:
Problem status : PRIMAL_INFEASIBLE Solution status : PRIMAL_INFEASIBLE_CER Dual. obj: 2.9238975853e+02 nrm: 6e+02 Viol. con: 0e+00 var: 1e-11 acc: 0e+00
It is a Farkas-type certificate as described in Sec. 12.2.2 (Infeasibility for Conic Optimization). In particular, for a good certificate:
The dual objective is positive for a minimization problem, negative for a maximization problem. Ideally it is well bounded away from zero.
The norm is not too big and the violations are small (as for a solution).
If the model was not expected to be infeasible, the likely cause is an error in the problem formulation. Use the hints in Sec. 8.1.1 (Input data) and Sec. 8.3 (Debugging infeasibility) to locate the issue.
Just like a solution, the infeasibility certificate can be of better or worse quality. The infeasibility certificate above is very solid. However, there can be less clear-cut cases, such as for example:
Problem status : PRIMAL_INFEASIBLE Solution status : PRIMAL_INFEASIBLE_CER Dual. obj: 1.6378689238e-06 nrm: 6e+05 Viol. con: 7e-03 var: 2e-04 acc: 0e+00
This infeasibility certificate is more dubious because the dual objective is positive, but barely so in comparison with the large violations. It also has rather large norm. This is more likely an indication that the problem is borderline between feasibility and infeasibility or simply ill-posed and sensitive to tiny variations in input data. See Sec. 8.3 (Debugging infeasibility) and Sec. 8.2 (Addressing numerical issues).
The same remarks apply to dual infeasibility (i.e. unboundedness) certificates. Here the primal objective should be negative a minimization problem and positive for a maximization problem.
8.1.3 Mixed-integer problem¶
Optimal integer solution
For a mixed-integer problem there is no dual solution and a typical optimal solution report will look as follows:
Problem status : PRIMAL_FEASIBLE Solution status : INTEGER_OPTIMAL Primal. obj: 6.0111122960e+06 nrm: 1e+03 Viol. con: 2e-13 var: 2e-14 itg: 5e-15
The interpretation of all elements is as for a continuous problem. The additional field
itg denotes the maximum violation of an integer variable from being an exact integer.
Feasible integer solution
If the solver found an integer solution but did not prove optimality, for instance because of a time limit, the solution status will be
Problem status : PRIMAL_FEASIBLE Solution status : PRIMAL_FEASIBLE Primal. obj: 6.0114607792e+06 nrm: 1e+03 Viol. con: 2e-13 var: 2e-13 itg: 4e-15
In this case it is valuable to go back to the optimizer summary to see how good the best solution is:
31 35 1 0 6.0114607792e+06 6.0078960892e+06 0.06 4.1 Objective of best integer solution : 6.011460779193e+06 Best objective bound : 6.007896089225e+06
In this case the best integer solution found has objective value
6.011460779193e+06, the best proved lower bound is
6.007896089225e+06 and so the solution is guaranteed to be within \(0.06\%\) from optimum. The same data can be obtained as information items through an API. See also Sec. 13.4 (The Optimizer for Mixed-Integer Problems) for more details.
If the problem is declared infeasible the summary is simply
Problem status : PRIMAL_INFEASIBLE Solution status : UNKNOWN Primal. obj: 0.0000000000e+00 nrm: 0e+00 Viol. con: 0e+00 var: 0e+00 itg: 0e+00
If infeasibility was not expected, consult Sec. 8.3 (Debugging infeasibility).