debugging-optimization


This notebook offers tricks for diagnosing problems in the optimization and debugging them.

Finding infeasible pairs

What do you do when the model solver returns with "Infeasible model"?

Consider using the findinfeasiblepair(house, solver) tool. It will give you a range within the matrix for which the results become minimally infeasible. In other words, suppose that the full linear programming matrix is $A$. It returns $i$, $j$, such that $A[1:i, :]$ is infeasible, but $A[1:i-1, :]$ is not, and $A[j:end, :]$ is infeasible but $A[j+1:end, :]$ is not.

You can then investigate individual rows by calling house.A[row,:].

Note that the linear programming problem is always solved as follows: $$ \max_x f' x $$ s.t. $A x < b$ and $x > 0$.

To find out what is constraining these values, look down at the Understanding constraints section.

Breaking apart the matrix

The entries in the $f$ vector correspond to a sequences of parameter values, those of the $b$ vector correspond to variable values, and the rows and columns of $A$ correspond to variables and parameters respectively.

To find out which parameter a particular column of $A$ or value in $f$ corresponds to, use

cumsum(varlengths(house.model, house.paramcomps, house.parameters))

which gives the last index of each paramter.

To find out which variable a particular row of $A$ or value in $b$ corresponds to, use

cumsum(varlengths(house.model, house.constcomps, house.constraints, house.constdictionary))

which gives the last index of each variable.

Understanding constraints

The constraining function will identify which constraints limit the value of each parameter. It's results depend on the value of the parameter lying within $1e-6 p + 1e-6$ of its constraining wall, for parameter value $p$, so the function can miss the constraint for certain solution sets.

In the most recent version of OptiMimi, you can specify an optional subset constraint, a vector of indices of parameters to investigate. This works well with findinfeasiblepair, but keep in mind that findinfeasiblepair returns indices of constraints while constraining looks at parameters. So, you need to do the following steps.

  1. Suppose that findinfeasiblepair returns a set of bounds $I$ to $J$, and you want to understand why $I$ fails. You can always replace $J$ below with length(house.b).
  2. Look at the part of the $A$ and $b$ matrices directly affecting constraint $I$: house.A[I,:]. Record the range of parameter indices to investigate as $A$ to $B$.
  3. Run sol = houseoptimize(house, solver, subset=[I:J-1]) to get a valid solution.
  4. Get the constraints as constraining(house, sol.sol, subset=[A:B]).
  5. If you want to know what constrains it on the other side to be infeasible, do the same thing again from step 3 with the subset range [I+1:J].