15.2 Analyzing Infeasible Problems

When developing and implementing a new optimization model, the first attempts will often be either infeasible, due to specification of inconsistent constraints, or unbounded, if important constraints have been left out.

In this section we will

  • go over an example demonstrating how to locate infeasible constraints using the MOSEK infeasibility report tool,
  • discuss in more general terms which properties may cause infeasibilities, and
  • present the more formal theory of infeasible and unbounded problems.

Furthermore, Sec. 15.2.7.1 (Primal Feasibility Repair) contains a discussion on a specific method for repairing infeasibility problems where infeasibilities are caused by model parameters rather than errors in the model or the implementation.

15.2.1 Example: Primal Infeasibility

A problem is said to be primal infeasible if no solution exists that satisfies all the constraints of the problem.

As an example of a primal infeasible problem consider the problem of minimizing the cost of transportation between a number of production plants and stores: Each plant produces a fixed number of goods, and each store has a fixed demand that must be met. Supply, demand and cost of transportation per unit are given in Fig. 1.

_images/transportp.png

Fig. 1 Supply, demand and cost of transportation.

The problem represented in Fig. 1 is infeasible, since the total demand

\[2300 = 1100+200+500+500\]

exceeds the total supply

\[2200 = 200+1000+1000\]

If we denote the number of transported goods from plant \(i\) to store \(j\) by \(x_{ij}\) , the problem can be formulated as the LP:

(1)\[\begin{split}\begin{array}{lccccccccccccccl} \mbox{minimize} & x_{11} & + & 2x_{12} & + & 5x_{23} & + & 2x_{24} & + & x_{31} & + & 2x_{33} & + & x_{34} & & \\ \mbox{subject to} & x_{11} & + & x_{12} & & & & & & & & & & & \leq & 200, \\ & & & & & x_{23} & + & x_{24} & & & & & & & \leq & 1000,\\ & & & & & & & & & x_{31} & + & x_{33} & + & x_{34} & \leq & 1000,\\ & x_{11} & & & & & & & + & x_{31} & & & & & = & 1100,\\ & & & x_{12} & & & & & & & & & & & = & 200, \\ & & & & & x_{23} & + & & & & & x_{33} & & & = & 500, \\ & & & & & & & x_{24} & + & & & & & x_{34} & = & 500, \\ & x_{ij} \geq 0. & & & & & & & & & & & & & & \end{array}\end{split}\]

Solving problem (1) using MOSEK will result in a solution, a solution status and a problem status. Among the log output from the execution of MOSEK on the above problem are the lines:

Basic solution
Problem status  : PRIMAL_INFEASIBLE
Solution status : PRIMAL_INFEASIBLE_CER

The first line indicates that the problem status is primal infeasible. The second line says that a certificate of the infeasibility was found. The certificate is returned in place of the solution to the problem.

15.2.2 Locating the cause of Primal Infeasibility

Usually a primal infeasible problem status is caused by a mistake in formulating the problem and therefore the question arises: What is the cause of the infeasible status? When trying to answer this question, it is often advantageous to follow these steps:

  • Remove the objective function. This does not change the infeasibility status but simplifies the problem, eliminating any possibility of issues related to the objective function.
  • Consider whether your problem has some necessary conditions for feasibility and examine if these are satisfied, e.g. total supply should be greater than or equal to total demand.
  • Verify that coefficients and bounds are reasonably sized in your problem.

If the problem is still primal infeasible, some of the constraints must be relaxed or removed completely. The MOSEK infeasibility report (Sec. 15.2.4 (The Infeasibility Report)) may assist you in finding the constraints causing the infeasibility.

Possible ways of relaxing your problem nclude:

  • Increasing (decreasing) upper (lower) bounds on variables and constraints.
  • Removing suspected constraints from the problem.

Returning to the transportation example, we discover that removing the fifth constraint

\[x_{12} = 200\]

makes the problem feasible.

15.2.3 Locating the Cause of Dual Infeasibility

A problem may also be dual infeasible. In this case the primal problem is often unbounded, meaning that feasbile solutions exists such that the objective tends towards infinity. An example of a dual infeasible and primal unbounded problem is:

\[\begin{split}\begin{array}{lcl} \mbox{minimize} & x_1 & \\ \mbox{subject to} & x_1 \leq 5. & \end{array}\end{split}\]

To resolve a dual infeasibility the primal problem must be made more restricted by

  • Adding upper or lower bounds on variables or constraints.
  • Removing variables.
  • Changing the objective.

15.2.3.1 A cautionary note

The problem

\[\begin{split}\begin{array}{lcl} \mbox{minimize} & 0 & \\ \mbox{subject to} & 0 \leq x_1, & \\ & x_j \leq x_{j+1}, & j=1,\ldots ,n-1, \\ & x_n \leq -1 & \end{array}\end{split}\]

is clearly infeasible. Moreover, if any one of the constraints is dropped, then the problem becomes feasible.

This illustrates the worst case scenario where all, or at least a significant portion of the constraints are involved in causing infeasibility. Hence, it may not always be easy or possible to pinpoint a few constraints responsible for infeasibility.

15.2.4 The Infeasibility Report

MOSEK includes functionality for diagnosing the cause of a primal or a dual infeasibility. It can be turned on by setting the MSK_IPAR_INFEAS_REPORT_AUTO to MSK_ON. This causes MOSEK to print a report on variables and constraints involved in the infeasibility.

The MSK_IPAR_INFEAS_REPORT_LEVEL parameter controls the amount of information presented in the infeasibility report. The default value is \(1\).

15.2.4.1 Example: Primal Infeasibility

We will keep working with the problem (1) written in LP format:

Listing 34 The code for problem (1). Click here to download.
\
\ An example of an infeasible linear problem.
\
minimize
 obj: + 1 x11 + 2 x12  
      + 5 x23 + 2 x24
      + 1 x31 + 2 x33 + 1 x34
st
  s0: + x11 + x12       <= 200
  s1: + x23 + x24       <= 1000
  s2: + x31 + x33 + x34 <= 1000
  d1: + x11 + x31        = 1100
  d2: + x12              = 200
  d3: + x23 + x33        = 500
  d4: + x24 + x34        = 500
bounds
end
 

15.2.4.2 Example: Dual Infeasibility

The following problem is dual to (1) and therefore it is dual infeasible.

Listing 35 The dual of problem (1). Click here to download.
maximize + 200 y1 + 1000 y2 + 1000 y3 + 1100 y4 + 200 y5 + 500 y6 + 500 y7
subject to
   x11: y1+y4 < 1
   x12: y1+y5 < 2
   x23: y2+y6 < 5
   x24: y2+y7 < 2
   x31: y3+y4 < 1
   x33: y3+y6 < 2
   x34: y3+y7 < 1
bounds
   -inf <= y1 < 0
   -inf <= y2 < 0
   -inf <= y3 < 0
   y4 free 
   y5 free
   y6 free
   y7 free
end

This can be verified by proving that

\[(y_1,\ldots,y_7)=(-1,0,-1,1,1,0,0)\]

is a certificate of dual infeasibility (see Sec. 12.1.2.2 (Dual Infeasible Problems)) as we can see from this report:

MOSEK DUAL INFEASIBILITY REPORT.

Problem status: The problem is dual infeasible

The following constraints are involved in the infeasibility.

Index    Name             Activity         Objective        Lower bound      Upper bound
5        x33              -1.000000e+00                     NONE             2.000000e+00
6        x34              -1.000000e+00                     NONE             1.000000e+00

The following variables are involved in the infeasibility.

Index    Name             Activity         Objective        Lower bound      Upper bound
0        y1               -1.000000e+00    2.000000e+02     NONE             0.000000e+00
2        y3               -1.000000e+00    1.000000e+03     NONE             0.000000e+00
3        y4               1.000000e+00     1.100000e+03     NONE             NONE
4        y5               1.000000e+00     2.000000e+02     NONE             NONE

Interior-point solution summary
  Problem status  : DUAL_INFEASIBLE
  Solution status : DUAL_INFEASIBLE_CER
  Primal.  obj: 1.0000000000e+02    nrm: 1e+00    Viol.  con: 0e+00    var: 0e+00

Let \(y^*\) denote the reported primal solution. MOSEK states

  • that the problem is dual infeasible,
  • that the reported solution is a certificate of dual infeasibility, and
  • that the infeasibility measure for \(y^*\) is approximately zero.

Since the original objective was maximization, we have that \(c^T y^* >0\). See Sec. 12.1.2 (Infeasibility for Linear Optimization) for how to interpret the parameter values in the infeasibility report for a linear program. We see that the variables y1, y3, y4, y5 and the constraints x33 and x34 contribute to infeasibility with non-zero values in the Activity column.

One possible strategy to fix the infeasibility is to modify the problem so that the certificate of infeasibility becomes invalid. In this case we could do one the following things:

  • Add a lower bound on y3. This will directly invalidate the certificate of dual infeasibility.
  • Increase the object coefficient of y3. Changing the coefficients sufficiently will invalidate the inequality \(c^Ty^*>0\) and thus the certificate.
  • Add lower bounds on x11 or x31. This will directly invalidate the certificate of infeasibility.

Please note that modifying the problem to invalidate the reported certificate does not imply that the problem becomes dual feasible — the reason for infeasibility may simply move, resulting a problem that is still infeasible, but for a different reason.

More often, the reported certificate can be used to give a hint about errors or inconsistencies in the model that produced the problem.

15.2.5 Theory Concerning Infeasible Problems

This section discusses the theory of infeasibility certificates and how MOSEK uses a certificate to produce an infeasibility report. In general, MOSEK solves the problem

(2)\[\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}\]

where the corresponding dual problem is

(3)\[\begin{split}\begin{array}{lccl} \mbox{maximize} & (l^c)^T s_l^c - (u^c)^T s_u^c & & \\ & + (l^x)^T s_l^x - (u^x)^T s_u^x + c^f & & \\ \mbox{subject to} & A^T y + s_l^x - s_u^x & = & c,\\ & -y + s_l^c - s_u^c & = & 0, \\ & s_l^c,s_u^c,s_l^x,s_u^x \leq 0. & & \end{array}\end{split}\]

We use the convension that for any bound that is not finite, the corresponding dual variable is fixed at zero (and thus will have no influence on the dual problem). For example

\[l_j^x = -\infty \quad \Rightarrow \quad (s_l^x)_j=0\]

15.2.6 The Certificate of Primal Infeasibility

A certificate of primal infeasibility is any solution to the homogenized dual problem

\[\begin{split}\begin{array}{lccl} \mbox{maximize} & (l^c)^T s_l^c - (u^c)^T s_u^c & & \\ & + (l^x)^T s_l^x - (u^x)^T s_u^x & & \\ \mbox{subject to} & A^T y + s_l^x - s_u^x & = & 0,\\ & -y + s_l^c - s_u^c & = & 0, \\ & s_l^c,s_u^c,s_l^x,s_u^x \leq 0. & & \end{array}\end{split}\]

with a positive objective value. That is, \((s_l^{c*},s_u^{c*},s_l^{x*},s_u^{x*})\) is a certificate of primal infeasibility if

\[(l^c)^T s_l^{c*} - (u^c)^T s_u^{c*} + (l^x)^T s_l^{x*} - (u^x)^T s_u^{x*} > 0\]

and

\[\begin{split}\begin{array}{lcl} A^T y + s_l^{x*} - s_u^{x*} & = & 0, \\ -y + s_l^{c*} - s_u^{c*} & = & 0, \\ s_l^{c*},s_u^{c*},s_l^{x*},s_u^{x*} \leq 0. & & \end{array}\end{split}\]

The well-known Farkas Lemma tells us that (2) is infeasible if and only if a certificate of primal infeasibility exists.

Let \((s_l^{c*},s_u^{c*},s_l^{x*},s_u^{x*})\) be a certificate of primal infeasibility then

\[(s_l^{c*})_i > 0 ((s_u^{c*})_i > 0)\]

implies that the lower (upper) bound on the \(i\) th constraint is important for the infeasibility. Furthermore,

\[(s_l^{x*})_j > 0 ((s_u^{x*})_i > 0)\]

implies that the lower (upper) bound on the \(j\) th variable is important for the infeasibility.

15.2.7 The certificate of dual infeasibility

A certificate of dual infeasibility is any solution to the problem

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

with negative objective value, where we use the definitions

\[\begin{split}\bar{l}_i^c := \left\lbrace \begin{array}{ll} 0, & l_i^c > -\infty ,\\ -\infty , & \mbox{otherwise}, \end{array} \right\rbrace,~ \bar{u}_i^c := \left\lbrace \begin{array} {ll} 0, & u_i^c < \infty , \\ \infty , & \mbox{otherwise}, \end{array} \right\rbrace\end{split}\]

and

\[\begin{split}\bar{l}_i^x := \left\lbrace \begin{array}{ll} 0, & l_i^x > -\infty , \\ -\infty , & \mbox{otherwise}, \end{array} \right\rbrace\quad \mbox{and} \quad \bar{u}_i^x := \left\lbrace \begin{array}{ll} 0, & u_i^x < \infty , \\ \infty , & \mbox{otherwise}. \end{array} \right\rbrace\end{split}\]

Stated differently, a certificate of dual infeasibility is any \(x^*\) such that

(4)\[\begin{split}\begin{array}{lcccl} & & c^T x^* & < & 0, \\ \bar{l}^c & \leq & A x^* & \leq & \bar{u}^c, \\ \bar{l}^x & \leq & x^* & \leq & \bar{u}^x \end{array}\end{split}\]

The well-known Farkas Lemma tells us that (3) is infeasible if and only if a certificate of dual infeasibility exists.

Note that if \(x^*\) is a certificate of dual infeasibility then for any \(j\) such that

\[x_j^* \leq 0,\]

variable \(j\) is involved in the dual infeasibility.

15.2.7.1 Primal Feasibility Repair

Sec. 15.2.2 (Locating the cause of Primal Infeasibility) 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 cause of the infeasibility.

In this section we discuss how to repair 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.

15.2.7.2 Manual repair

Subsequently we discuss an automatic method for repairing an infeasible optimization problem. However, it should be observed that the best way to repair an infeasible problem usually depends on what the optimization problem models. For instance in many optimization problem it does not make sense to relax the constraints \(x \geq 0\) e.g. it is not possible to produce a negative quantity. Hence, whatever automatic method MOSEK provides it will never be as good as a method that exploits knowledge about what is being modelled. This implies that it is usually better to remove the underlying cause of infeasibility at the modelling stage.

Indeed consider the example

\[\begin{split}\begin{array}{lcccccccccl} \mbox{minimize} & & & & & & & & & &\\ \mbox{subject to} & & x_1 & + & x_2 & & & & & = & 1,\\ & & & & & & x_3 & + & x_4 & = & 1, \\ &- & x_1 & & & - & x_3 & & & = & -1 + \varepsilon \\ & & & - & x_2 & & & - & x_4 & = & -1, \\ & & x_1,& & x_2,& & x_3,& & x_4 & \geq & 0 \end{array}\end{split}\]

then if we add the equalties together we obtain the implied equality

\[0 = \varepsilon\]

which is infeasible for any \(\varepsilon \geq 0\). Here the infeasibility is caused by a linear dependency in the constraint matrix and that the right-hand side does not match if \(\varepsilon \geq 0\).

Observe even if the problem is feasible then just a tiny perturbation to the right-hand side will make the problem infeasible. Therefore, even though the problem can be repaired then a much more robust solution is to avoid problems with linear dependent constraints. Indeed if a problem contains linear dependencies then the problem is either infeasible or contains redundant constraints. In the above case any of the equality constraints can be removed while not changing the set of feasible solutions.

To summarize linear dependencies in the constraints can give rise to infeasible problems and therefore it is better to avoid them. Note that most network flow models usually is formulated with one linear dependent constraint.

Next consider the problem

\[\begin{split}\begin{array}{lcccccl} \mbox{minimize} & & &\\ \mbox{subject to} & x_1 - 0.01 x_2 & = & 0\\ & x_2 - 0.01 x_3 & = & 0\\ & x_3 - 0.01 x_4 & = & 0\\ & x_1 & \geq & -1.0e-9\\ & x_1 & \geq & 1.0e-9\\ & x_4 & \geq & -1.0e-4 \end{array}\end{split}\]

Now the MOSEK presolve for the sake of efficiency fix variables (and constraints) that has tight bounds where tightness is controlled by the parameter MSK_DPAR_PRESOLVE_TOL_X. Since, the bounds

\[-1.0e-9 \leq x_1 \leq 1.0e-9\]

are tight then the MOSEK presolve will fix variable \(x_1\) at the mid point between the bounds i.e. at 0. It easy to see that this implies \(x_4=0\) too which leads to the incorrect conclusion that the problem is infeasible. Observe tiny change of the size 1.0e-9 make the problem switch from feasible to infeasible. Such a problem is inherently unstable and is hard to solve. We normally call such a problem ill-posed.

In general it is recommended to avoid ill-posed problems, but if that is not possible then one solution to this issue is is to reduce the parameter to say MSK_DPAR_PRESOLVE_TOL_X to say 1.0e-10. This will at least make sure that the presolve does not make the wrong conclusion.

15.2.7.2.1 Automatic Repair

In this section we will describe the idea behind a method that automatically can repair an infeasible probem. 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

(5)\[\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 & \leq & A x + v_l^c - v_u^c & \leq & u^c, \\ & l^x & \leq & x + v_l^x - v_u^x & \leq & 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 penalize 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\) ),

then 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 relaxation and therefore the problem (5) keeps the amount of relaxation at a minimum. Please observe that

  • the problem (5) is always feasible.
  • a negative weight implies problem (5) 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 may imply that it is not possible repair the problem.

A simple choice of weights is to let them all to be \(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 be unbounded. Hence, a repaired problem may not have an optimal solution.

Another and more important caveat is that only a minimial repair is perfomed i.e. the repair that just make the problem feasible. Hence, the repaired problem is barely feasible and that sometimes make the repaired problem hard to solve.

15.2.7.3 Feasibility Repair

MOSEK includes a function that repair an infeasible problem using the idea described in the previous section simply by passing a set of weights to MOSEK. This can be used for linear and conic optimization problems, possibly having integer constrained variables.

An example

Consider the example linear optimization

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

which is infeasible. Now suppose we wish to use MOSEK to suggest a modification to the bounds that makes the problem feasible.

The function MSK_primalrepair can be used to repair an infeasible problem. Details about the function MSK_primalrepair can be seen in the reference.

Listing 36 An example of feasibility repair applied to problem (6). Click here to download.
#include <math.h>
#include <stdio.h>

#include "mosek.h"

static void MSKAPI printstr(void *handle,
                            const char str[])
{
  fputs(str, stdout);
} /* printstr */

int main(int argc, const char *argv[])
{
  const char  *filename = "../data/feasrepair.lp";
  MSKenv_t    env;
  MSKrescodee r;
  MSKtask_t   task;

  if ( argc > 1 )
    filename = argv[1];

  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_readdata(task, filename); /* Read file from current dir */

  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_optimize(task); /* Optimize the repaired task. */

      MSK_solutionsummary(task, MSK_STREAM_MSG);
    }
  }

  printf("Return code: %d\n", r);

  return ( r );
}

will produce the following

Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com

Open file 'feasrepair.lp'

Read summary
Type             : LO (linear optimization problem)
Objective sense  : min
Constraints      : 4           
Scalar variables : 2           
Matrix variables : 0           
Time             : 0.0     

Computer
Platform               : Windows/64-X86  
Cores                  : 4               

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.
Interior-point optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Total number of eliminations : 2
Eliminator terminated.
Eliminator - tries                  : 1                 time                   : 0.00            
Eliminator - elim's                 : 2               
Lin. dep.  - tries                  : 1                 time                   : 0.00            
Lin. dep.  - number                 : 0               
Presolve terminated. Time: 0.00    
Optimizer  - threads                : 1               
Optimizer  - solved problem         : the primal      
Optimizer  - Constraints            : 2
Optimizer  - Cones                  : 0
Optimizer  - Scalar variables       : 6                 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.40e+001       
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   2.7e+001 1.0e+000 4.8e+000 1.00e+000  4.195228609e+000  0.000000000e+000  1.0e+000 0.00  
1   2.4e+001 8.6e-001 1.5e+000 0.00e+000  1.227497414e+001  1.504971820e+001  2.6e+000 0.00  
2   2.6e+000 9.7e-002 1.7e-001 -6.19e-001 4.363064729e+001  4.648523094e+001  3.0e-001 0.00  
3   4.7e-001 1.7e-002 3.1e-002 1.24e+000  4.256803136e+001  4.298540657e+001  5.2e-002 0.00  
4   8.7e-004 3.2e-005 5.7e-005 1.08e+000  4.249989892e+001  4.250078747e+001  9.7e-005 0.00  
5   8.7e-008 3.2e-009 5.7e-009 1.00e+000  4.249999999e+001  4.250000008e+001  9.7e-009 0.00  
6   8.7e-012 3.2e-013 5.7e-013 1.00e+000  4.250000000e+001  4.250000000e+001  9.7e-013 0.00  
Basis identification started.
Primal basis identification phase started.
ITER      TIME
0         0.00    
Primal basis identification phase terminated. Time: 0.00
Dual basis identification phase started.
ITER      TIME
0         0.00    
Dual basis identification phase terminated. Time: 0.00
Basis identification terminated. Time: 0.00
Interior-point optimizer terminated. Time: 0.00. 

Optimizer terminated. Time: 0.03    
Basic solution summary
Problem status  : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal.  obj: 4.2500000000e+001   Viol.  con: 1e-013   var: 0e+000 
Dual.    obj: 4.2500000000e+001   Viol.  con: 0e+000   var: 5e-013 
Optimal objective value of the penalty problem: 4.250000000000e+001

Repairing bounds.
Increasing the upper bound -2.25e+001 on constraint 'c4' (3) with 1.35e+002.
Decreasing the lower bound 6.50e+002 on variable 'x2' (4) with 2.00e+001.
Primal feasibility repair terminated.
Optimizer started.
Interior-point optimizer started.
Presolve started.
Presolve terminated. Time: 0.00    
Interior-point optimizer terminated. Time: 0.00. 

Optimizer terminated. Time: 0.00    

Interior-point solution summary
Problem status  : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal.  obj: -5.6700000000e+003  Viol.  con: 0e+000   var: 0e+000 
Dual.    obj: -5.6700000000e+003  Viol.  con: 0e+000   var: 0e+000 

Basic solution summary
Problem status  : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal.  obj: -5.6700000000e+003  Viol.  con: 0e+000   var: 0e+000 
Dual.    obj: -5.6700000000e+003  Viol.  con: 0e+000   var: 0e+000 

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    
Clean primal-dual   - iterations : 0         time: 0.00    
Simplex                 -                        time: 0.00    
Primal simplex        - iterations : 0         time: 0.00    
Dual simplex          - iterations : 0         time: 0.00    
Primal-dual simplex   - iterations : 0         time: 0.00    
Mixed integer           - relaxations: 0         time: 0.00    

reports the optimal repair. In this case it is to increase the upper bound on constraint c4 by 1.35e2 and decrease the lower bound on variable x2 by 20.