Debugging Models

A number of errors and warnings may be raised when attempting to solve a model. These can generally be classed into two types: models where there is no possible solution (primal infeasible models) and those where nothing stops the objective (or variables in the objective) from going to 0 or infinity (dual infeasible models).

Potential errors and warnings

  • RuntimeWarning: Primal solution violates constraint: 1.0000149786 is greater than 1
    • this warning may be seen in dual infeasible models, see Dual Infeasibility below.
  • RuntimeWarning: Dual cost nan does not match primal cost 1.00122315152
    • this warning may be seen in dual infeasible models, see Dual Infeasibility below.
  • RuntimeWarning: final status of solver 'cvxopt' was 'unknown', not 'optimal’ or RuntimeWarning: final status of solver 'mosek' was ‘UNKNOWN’, not 'optimal’.
    • this is the most difficult warning to debug. It can be thrown when attempting to solve a dual infeasible model or a primal infeasible model. See Dual and Primal Infeasibility below.
  • RuntimeWarning: final status of solver 'mosek' was 'DUAL_INFEAS_CER', not 'optimal’
    • this error is thrown when attempting to solve a dual infeasible model with MOSEK, see Dual Infeasibility below.
  • RuntimeWarning: final status of solver 'mosek' was 'PRIM_INFEAS_CER', not 'optimal’
    • this error is thrown when attempting to solve a primal infeasible model with MOSEK, see Primal Infeasibility below.

Dual Infeasibility

In some cases a model will not solve because the optimal value of one or more variables is 0 or infinity (plus or minus infinity in logspace). Such a problem is known as dual infeasible because the GP’s dual problem, which determines the optimal values of the sensitivites, does not have any feasible solution. If the solver can prove that the dual is infeasible, it will return a dual infeasibility certificate. Otherwise, it may finish with a solution status of unknown.

gpkit.constraints.bounded.Bounded is a simple tool that attempts to detect unbounded variables and get unbounded models to solve by adding extremely large upper bounds and extremely small lower bounds to all variables in a ConstraintSet.

When a model with a Bounded ConstraintSet is solved, it checks whether any variables slid off to the bounds, notes this in the solution dictionary and prints a warning (if verbosity is greater than 0).

For example, Mosek returns DUAL_INFEAS_CER when attempting to solve the following model:

"Demonstrate a trivial unbounded variable"
from gpkit import Variable, Model
from gpkit.constraints.bounded import BoundedConstraintSet

x = Variable("x")

constraints = [x >= 1]

# Model(1/x, constraints).solve()  # does not solve
m = Model(1/x, BoundedConstraintSet(constraints))
# by default, prints bounds warning during solve
sol = m.solve(verbosity=0)
print sol.table()
print "sol['boundedness'] is:", sol["boundedness"]

Upon viewing the printed output,


UNBOUNDED VARIABLES
   value near upper bound: [x]
 sensitive to upper bound: [x]


Cost
----
 1e-30

Free Variables
--------------
x : 1e+30 

sol['boundedness'] is: {'value near upper bound': array([x], dtype=object), 'sensitive to upper bound': array([x], dtype=object)}

it becomes clear that the problem is, unsurprisingly, an x which has no lower bound in the original model.

For details read the Bounded docstring.

Primal Infeasibility

A model is primal infeasible when there is no point which simultaneously satisfies all of the model’s constraints. A simple example is presented below.

"A simple primal infeasible example"
from gpkit import Variable, Model

#Make the necessary Variables
x = Variable("x")
y = Variable("y")

#make the constraints
constraints = [
    x >= 1,
    y >= 2,
    x*y >= 0.5,
    x*y <= 1.5
]

#declare the objective
objective = x*y

#construct the model
m = Model(objective, constraints)

#solve the model
#raises uknown on cvxopt and mosek
#m.solve()

It is not possible for x*y to be less than 1.5 while x is greater than 1 and y is greater than 2.

A common bug in large models that use substitutions is to substitute overly constraining values in for variables that make the model primal infeasible. An example of this is given below.

"Another simple primal infeasible example"
from gpkit import Variable, Model

#Make the necessary Variables
x = Variable("x")
y = Variable("y", 2)

#make the constraints
constraints = [
    x >= 1,
    0.5 <= x*y,
    x*y <= 1.5
    ]

#declare the objective
objective = x*y

#construct the model
m = Model(objective, constraints)

#solve the model
#raises RuntimeWarning uknown on cvxopt and RuntimeWarning
#PRIM_INFES_CER with mosek
#m.solve()

Since y is now set to 2 and x can be no less than 1, it is again impossible for x*y to be less than 1.5 and the model is primal infeasible. If y was instead set to 1, the model would be feasible and the cost would be 1.

Relaxation

If you suspect your model is primal infeasible, you can automatically find the nearest feasible version of it with the Model.feasibility() command, as shown below. The feasible version can either involve relaxing all constraints by the smallest number possible (that is, dividing the less-than side of every constraint by the same number), relaxing each constraint by its own number and minimizing the product of those numbers, or changing each constant by the smallest total percentage possible.