Wednesday, October 28, 2009

NLP infeasible

A client of mine sent me a large NLP (36k variables and equations) that was infeasible. When a general local NLP solver returns INFEASIBLE, this may mean two things:

  1. The model is infeasible, i.e. no feasible solution exists
  2. or the model contains some feasible solutions but the solver cannot find any

As is the case for many NLP models this model had many linear equations. So I first solved for the linear equations only using an LP solver. This was still infeasible. Now we know we have case 1. After fixing this problem (some bounds were too tight) I kept the LP in, as with little effort I could construct a feasible solution for the whole problem using the LP solution. The NLP solver I used was CONOPT which is a feasible path algorithm, so it will stay feasible when the initial point is feasible. This trick may speed up the solution procedure but also provides for better results in case the solver stops prematurely: it will give us at least a solution that is feasible.