10.2 Automatic Repair of Infeasible Problems¶
MOSEK provides an automatic repair tool for infeasible linear problems which we cover in this section. Note that most infeasible models are so due to bugs which can (and should) be more reliably fixed manually, using the knowledge of the model structure. We discuss this approach in Sec. 7.3 (Debugging infeasibility).
10.2.1 Automatic repair¶
The main idea can be described as follows. Consider the linear optimization problem with \(m\) constraints and \(n\) variables
which is assumed to be 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. Now an obvious idea is to compute the optimal relaxation by solving an optimization problem. The problem
does exactly that. The additional variables \((v_l^c)_i\), \((v_u^c)_i\), \((v_l^x)_j\) and \((v_u^c)_j\) are elasticity variables because they allow a constraint to be violated and hence add some elasticity to the problem. For instance, the elasticity variable \((v_l^c)_i\) controls how much the lower bound \((l^c)_i\) should be relaxed to make the problem feasible. Finally, the so-called penalty function
is chosen so it penalizes changes to bounds. Given the weights
\(w_l^c \in \real^m\) (associated with \(l^c\) ),
\(w_u^c \in \real^m\) (associated with \(u^c\) ),
\(w_l^x \in \real^n\) (associated with \(l^x\) ),
\(w_u^x \in \real^n\) (associated with \(u^x\) ),
a natural choice is
Hence, the penalty function \(p()\) is a weighted sum of the elasticity variables and therefore the problem (10.1) keeps the amount of relaxation at a minimum. Please observe that
the problem (10.1) is always feasible.
a negative weight implies problem (10.1) is unbounded. For this reason if the value of a weight is negative MOSEK fixes the associated elasticity variable to zero. Clearly, if one or more of the weights are negative, it may imply that it is not possible to repair the problem.
A simple choice of weights is to set them all to \(1\), but of course that does not take into account that constraints may have different importance.
Observe if the infeasible problem
is repaired then it will become unbounded. Hence, a repaired problem may not have an optimal solution.
Another and more important caveat is that only a minimal repair is performed i.e. the repair that barely makes the problem feasible. Hence, the repaired problem is barely feasible and that sometimes makes the repaired problem hard to solve.
10.2.1.1 Using the automatic repair tool¶
In this subsection we consider an infeasible linear optimization example:
The problem (10.2) is contained in a file:
minimize obj: - 10 x1 - 9 x2 st c1: + 7e-01 x1 + x2 <= 630 c2: + 5e-01 x1 + 8.333333333e-01 x2 <= 600 c3: + x1 + 6.6666667e-01 x2 <= 708 c4: + 1e-01 x1 + 2.5e-01 x2 <= 135 bounds x2 >= 650 end
Given the assumption that all weights are 1 the command
mosek -primalrepair -d MSK_IPAR_LOG_FEAS_REPAIR 3 feasrepair.lp
will form the repaired problem and solve it. The parameter
MSK_IPAR_LOG_FEAS_REPAIR controls the amount of log output from the repair. A value of 2 causes the optimal repair to printed out. The output from running the above command is:
MOSEK Version 220.127.116.11(ALPHA) (Build date: 2017-11-7 16:11:50) Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com Platform: Linux/64-X86 Open file 'feasrepair.lp' Reading started. Reading terminated. Time: 0.00 Read summary Type : LO (linear optimization problem) Objective sense : min Scalar variables : 2 Matrix variables : 0 Constraints : 4 Cones : 0 Time : 0.0 Problem Name : Objective sense : min Type : LO (linear optimization problem) Constraints : 4 Cones : 0 Scalar variables : 2 Matrix variables : 0 Integer variables : 0 Primal feasibility repair started. Optimizer started. Presolve started. Linear dependency checker started. Linear dependency checker terminated. Eliminator started. Freed constraints in eliminator : 2 Eliminator terminated. Eliminator - tries : 1 time : 0.00 Lin. dep. - tries : 1 time : 0.00 Lin. dep. - number : 0 Presolve terminated. Time: 0.00 Problem Name : Objective sense : min Type : LO (linear optimization problem) Constraints : 8 Cones : 0 Scalar variables : 14 Matrix variables : 0 Integer variables : 0 Optimizer - threads : 20 Optimizer - solved problem : the primal Optimizer - Constraints : 2 Optimizer - Cones : 0 Optimizer - Scalar variables : 5 conic : 0 Optimizer - Semi-definite variables: 0 scalarized : 0 Factor - setup time : 0.00 dense det. time : 0.00 Factor - ML order time : 0.00 GP order time : 0.00 Factor - nonzeros before factor : 3 after factor : 3 Factor - dense dim. : 0 flops : 5.00e+01 ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME 0 2.7e+01 1.0e+00 4.0e+00 1.00e+00 3.000000000e+00 0.000000000e+00 1.0e+00 0.00 1 2.5e+01 9.1e-01 1.4e+00 0.00e+00 8.711262850e+00 1.115287830e+01 2.4e+00 0.00 2 2.4e+00 8.8e-02 1.4e-01 -7.33e-01 4.062505701e+01 4.422203730e+01 2.3e-01 0.00 3 9.4e-02 3.4e-03 5.5e-03 1.33e+00 4.250700434e+01 4.258548510e+01 9.1e-03 0.00 4 2.0e-05 7.2e-07 1.1e-06 1.02e+00 4.249996599e+01 4.249998669e+01 1.9e-06 0.00 5 2.0e-09 7.2e-11 1.1e-10 1.00e+00 4.250000000e+01 4.250000000e+01 1.9e-10 0.00 Basis identification started. Basis identification terminated. Time: 0.00 Optimizer terminated. Time: 0.01 Basic solution summary Problem status : PRIMAL_AND_DUAL_FEASIBLE Solution status : OPTIMAL Primal. obj: 4.2500000000e+01 nrm: 6e+02 Viol. con: 1e-13 var: 0e+00 Dual. obj: 4.2499999999e+01 nrm: 2e+00 Viol. con: 0e+00 var: 9e-11 Optimal objective value of the penalty problem: 4.250000000000e+01 Repairing bounds. Increasing the upper bound 1.35e+02 on constraint 'c4' (3) with 2.25e+01. Decreasing the lower bound 6.50e+02 on variable 'x2' (4) with 2.00e+01. Primal feasibility repair terminated. Optimizer started. Optimizer terminated. Time: 0.00 Interior-point solution summary Problem status : PRIMAL_AND_DUAL_FEASIBLE Solution status : OPTIMAL Primal. obj: -5.6700000000e+03 nrm: 6e+02 Viol. con: 0e+00 var: 0e+00 Dual. obj: -5.6700000000e+03 nrm: 1e+01 Viol. con: 0e+00 var: 0e+00 Basic solution summary Problem status : PRIMAL_AND_DUAL_FEASIBLE Solution status : OPTIMAL Primal. obj: -5.6700000000e+03 nrm: 6e+02 Viol. con: 0e+00 var: 0e+00 Dual. obj: -5.6700000000e+03 nrm: 1e+01 Viol. con: 0e+00 var: 0e+00 Optimizer summary Optimizer - time: 0.00 Interior-point - iterations : 0 time: 0.00 Basis identification - time: 0.00 Primal - iterations : 0 time: 0.00 Dual - iterations : 0 time: 0.00 Clean primal - iterations : 0 time: 0.00 Clean dual - iterations : 0 time: 0.00 Simplex - time: 0.00 Primal simplex - iterations : 0 time: 0.00 Dual simplex - iterations : 0 time: 0.00 Mixed integer - relaxations: 0 time: 0.00
In this case the optimal repair it is to increase the upper bound on constraint
c4 by 22.5 and decrease the lower bound on variable
x2 by 20.