14.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. 8.3 (Debugging infeasibility).
14.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 (14.1) keeps the amount of relaxation at a minimum. Please observe that
the problem (14.1) is always feasible.
a negative weight implies problem (14.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.
220.127.116.11 Using the automatic repair tool¶
In this subsection we consider an infeasible linear optimization example:
Task.primalrepair can be used to repair an infeasible problem. This can be used for linear and conic optimization problems, possibly with integer variables.
import sys import mosek # Since the actual value of Infinity is ignores, we define it solely # for symbolic purposes: inf = 0.0 # Define a stream printer to grab output from MOSEK def streamprinter(text): sys.stdout.write(text) sys.stdout.flush() def main(inputfile): # Make a MOSEK environment with mosek.Env() as env: with env.Task(0, 0) as task: # Attach a printer to the task task.set_Stream(mosek.streamtype.log, streamprinter) # Read data task.readdata(inputfile) task.putintparam(mosek.iparam.log_feas_repair, 3) task.primalrepair(None, None, None, None) sum_viol = task.getdouinf(mosek.dinfitem.primal_repair_penalty_obj) print("Minimized sum of violations = %e" % sum_viol) task.optimize() task.solutionsummary(mosek.streamtype.msg) # call the main function try: filename = "../data/feasrepair.lp" if len(sys.argv) > 1: filename = sys.argv main(filename) except Exception as e: print(e) raise
The above code will produce the following log report:
MOSEK Version 18.104.22.168(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
It will also modify the task according to the optimal elasticity variables found. 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.