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.
14.2.1.1 Using the automatic repair tool¶
In this subsection we consider an infeasible linear optimization example:
The function MSK_primalrepair can be used to repair an infeasible problem. This can be used for linear and conic optimization problems, possibly with integer variables.
#include <math.h>
#include <stdio.h>
#include "mosek.h"
static void MSKAPI printstr(void *handle,
const char str[])
{
fputs(str, stdout);
} /* printstr */
static const char * feasrepair_lp =
"minimize \n"
" obj: - 10 x1 - 9 x2 \n"
"st \n"
" c1: + 7e-01 x1 + x2 <= 630 \n"
" c2: + 5e-01 x1 + 8.333333333e-01 x2 <= 600 \n"
" c3: + x1 + 6.6666667e-01 x2 <= 708 \n"
" c4: + 1e-01 x1 + 2.5e-01 x2 <= 135 \n"
"bounds \n"
"x2 >= 650 \n"
"end \n";
int main(int argc, const char *argv[])
{
MSKenv_t env;
MSKrescodee r, trmcode;
MSKtask_t task;
r = MSK_makeenv(&env, NULL);
if (r == MSK_RES_OK)
r = MSK_makeemptytask(env, &task);
if (r == MSK_RES_OK)
MSK_linkfunctotaskstream(task, MSK_STREAM_LOG, NULL, printstr);
if (r == MSK_RES_OK)
r = MSK_readlpstring(task,feasrepair_lp); /* Read problem from string */
if (r == MSK_RES_OK)
r = MSK_putintparam(task, MSK_IPAR_LOG_FEAS_REPAIR, 3);
if (r == MSK_RES_OK)
{
/* Weights are NULL implying all weights are 1. */
r = MSK_primalrepair(task, NULL, NULL, NULL, NULL);
}
if (r == MSK_RES_OK)
{
double sum_viol;
r = MSK_getdouinf(task, MSK_DINF_PRIMAL_REPAIR_PENALTY_OBJ, &sum_viol);
if (r == MSK_RES_OK)
{
printf("Minimized sum of violations = %e\n", sum_viol);
r = MSK_optimizetrm(task, &trmcode); /* Optimize the repaired task. */
MSK_solutionsummary(task, MSK_STREAM_MSG);
}
}
printf("Return code: %d\n", r);
return (r);
}
The above code will produce the following log report:
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
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.
