9.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. 6.3 (Debugging infeasibility).

9.2.1 Automatic repair

The main idea can be described as follows. Consider the linear optimization problem with \(m\) constraints and \(n\) variables

\[\begin{split}\begin{array}{lccccl} \mbox{minimize} & & & c^T x+c^f & & \\ \mbox{subject to} & l^c & \leq & A x & \leq & u^c, \\ & l^x & \leq & x & \leq & u^x, \end{array}\end{split}\]

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

(9.1)\[\begin{split}\begin{array}{lccccl} \mbox{minimize} & & & p(v_l^c,v_u^c,v_l^x,v_u^x) & & \\ \mbox{subject to} & l^c - v_l^c & \leq & A x & \leq & u^c + v_u^c, \\ & l^x - v_l^x & \leq & x & \leq & u^x + v_u^x, \\ & & & v_l^c,v_u^c,v_l^x,v_u^x \geq 0 & & \end{array}\end{split}\]

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

\[p(v_l^c,v_u^c,v_l^x,v_u^x)\]

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

\[p(v_l^c,v_u^c,v_l^x,v_u^x) = (w_l^c)^T v_l^c + (w_u^c)^T v_u^c + (w_l^x)^T v_l^x + (w_u^x)^T v_u^x.\]

Hence, the penalty function \(p()\) is a weighted sum of the elasticity variables and therefore the problem (9.1) keeps the amount of relaxation at a minimum. Please observe that

  • the problem (9.1) is always feasible.

  • a negative weight implies problem (9.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.

Caveats

Observe if the infeasible problem

\[\begin{split}\begin{array}{lccccl} \mbox{minimize} & x+z & & \\ \mbox{subject to} & x & = & -1,\\ & x & \geq & 0 \end{array}\end{split}\]

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.

9.2.1.1 Using the automatic repair tool

In this subsection we consider an infeasible linear optimization example:

(9.2)\[\begin{split}\begin{array}{lccccc} \mbox{minimize} & -10 x_1 & & -9 x_2, & & \\ \mbox{subject to} & 7/10 x_1 & + & 1 x_2 & \leq & 630, \\ & 1/2 x_1 & + & 5/6 x_2 & \leq & 600, \\ & 1 x_1 & + & 2/3 x_2 & \leq & 708, \\ & 1/10 x_1 & + & 1/4 x_2 & \leq & 135, \\ & x_1, & & x_2 & \geq & 0, \\ & & & x_2 & \geq & 650. \end{array}\end{split}\]

The problem (9.2) is contained in a file:

Listing 9.1 Problem (9.2) in LP format. Click here to download.
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 9.0.0.25(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.