Section 12.2.2 discusses how MOSEK treats infeasible problems. In particular, it is discussed which information MOSEK returns when a problem is infeasible and how this information can be used to pinpoint the elements causing the infeasibility.
In this section we will discuss a method for repairing a primal infeasible problem by relaxing the constraints in a controlled way. For the sake of simplicity we discuss the method in the context of linear optimization. MOSEK can also repair infeasibilities in quadratic and conic optimization problems possibly having integer constrained variables. Please note that infeasibilities in nonlinear optimization problems can't be repaired using the method described below.
Consider the linear optimization problem with m constraints and n variables
![]() |
(13.1.1) |
which we assume is infeasible. Moreover, we assume that
![]() |
(13.1.2) |
and
![]() |
(13.1.3) |
because otherwise the problem (13.1.1) is trivially infeasible.
One way of making the problem feasible is to reduce the lower bounds and increase the upper bounds. If the change is sufficiently large the problem becomes feasible.
One obvious question is: What is the smallest change to the bounds that will make the problem feasible?
We associate a weight with each bound:
Now, the problem
![]() |
(13.1.4) |
minimizes the weighted sum of changes to the bounds that makes the problem feasible. The variables ,
,
and
are elasticity variables because they allow a constraint to be violated and hence add some elasticity to the problem. For instance, the elasticity variable
shows how much the lower bound
should be relaxed to make the problem feasible. Since p is minimized and
![]() |
(13.1.5) |
a large tends to imply that the elasticity variable
will be small in an optimal solution.
The reader may want to verify that the problem (13.1.4) is always feasible given the assumptions (13.1.2) and (13.1.3).
Please note that if a weight is negative then the resulting problem (13.1.4) is unbounded.
The weights ,
,
, and
can be regarded as a costs (penalties) for violating the associated constraints. Thus a higher weight implies that higher priority is given to the satisfaction of the associated constraint.
The main idea can now be presented as follows. If you have an infeasible problem, then form the problem (13.1.4) and optimize it. Next inspect the optimal solution , and
to problem (13.1.4). This solution provides a suggested relaxation of the bounds that will make the problem feasible.
Assume that is an optimal objective value to (13.1.4). An extension of the idea presented above is to solve the problem
![]() |
(13.1.6) |
which minimizes the true objective while making sure that total weighted violations of the bounds is minimal, i.e. equals to .
MOSEK includes functionality that help you construct the problem (13.1.4) simply by passing a set of weights to MOSEK. This can be used for linear, quadratic, and conic optimization problems, possibly having integer constrained variables.
As the problem (13.1.4) is presented it does not make sense to use negative weights since that makes the problem unbounded. Therefore, if the value of a weight is negative MOSEK fixes the associated elasticity variable to zero, e.g. if
![]() |
then MOSEK imposes the bound
![]() |
This implies that the lower bound on the ith constraint will not be violated. (Clearly, this could also imply that the problem is infeasible so negative weight should be used with care). Associating a negative weights with a constraint tells MOSEK that the constraint should not be relaxed.
MOSEK can automatically create a new problem of the form (13.1.4) starting from an existing problem by adding the elasticity variables and the extra constraints. Specificly, the variables ,
,
,
, and p are appended to existing variable vector x in their natural order. Moreover, the constraint (13.1.5) is appended to the constraints.
The new variables and constraints are automatically given names as follows:
The additional constraints
![]() |
are given names as follows. There is exactly one constraint per variable in the original problem, and thus the ith of these constraints is named after the ith variable in the original problem. For instance, if the first original variable is named “x0”, then the first of the above constraints is named “MSK-x1”. If necessary, the prefix “MSK-” can be replaced by a different string by changing the
MSK_SPAR_FEASREPAIR_NAME_PREFIX
parameter.
The variable p is by default given the name WSUMVIOLVAR, and the constraint (13.1.5) is given the name WSUMVIOLCON.
The substring “WSUMVIOL” can be replaced by a different string by changing the
MSK_SPAR_FEASREPAIR_NAME_WSUMVIOL
parameter.
Consider the example linear optimization
![]() |
(13.2.1) |
This is an infeasible problem. Now suppose we wish to use MOSEK to suggest a modification to the bounds that makes the problem feasible.
The command
mosek -d MSK_IPAR_FEASREPAIR_OPTIMIZE MSK_FEASREPAIR_OPTIMIZE_PENALTY -d MSK_IPAR_OPF_WRITE_SOLUTIONS MSK_ON feasrepair.lp -infrepo minv.opf
writes the problem (13.1.4) and it's solution to an OPF formatted file. In this case the file minv.opf.
The parameter
MSK_IPAR_FEASREPAIR_OPTIMIZE
controls whether the function returns the problem (13.1.4) or the problem (13.1.6). In the case
MSK_IPAR_FEASREPAIR_OPTIMIZE
is equal to
MSK_FEASREPAIR_OPTIMIZE_NONE
then (13.1.4) is returned, but the problem is not solved. For MSK_FEASREPAIR_OPTIMIZE_PENALTY the problem (13.1.4) is returned and solved. Finally for MSK_FEASREPAIR_OPTIMIZE_COMBINED (13.1.6) is returned and solved.