Tuesday, January 10, 2012

Reviewing NLP model

In a fairly complex model, we ended up trying a nonlinear objective:

image

where the rest of the model was linear (after applying some reformulations). As the model contains both integer and binary variables, this now has become an MINLP.

For several reasons this is actually not a very good expression:

  • this expression generates a lot of non-linear variables and non-linear non-zero elements in the matrix
  • as some z(i)’s can be zero it is difficult to protect this against division-by-zero (although the way we ran it had a linear model in front of this model, so our starting point was reasonable and no division-by-zero occurred)

A better formulation would be:

image

Here we only have two non-linear variables: the rest of the variables is now appearing linearly in the constraints. In addition, although we cannot bound each z(i) away from zero, we could introduce a nonzero lower bound on w.

Although we are adding extra constraints and variables to the MINLP model, this actually makes the model easier to solve and more robust.

PS1. The model is now becoming somewhat complex as we try to deal with different types of decisions in the same model. We call this an “integrated model” rather than just messy!

PS2. In some cases fractions can be reformulated using a “fractional programming” technique. In practice for larger models this often turns out to be a difficult reformulation to implement.

Question: it is suggested in a comment below to use (2d?) bisection. Is that really a good idea? Any references for such an approach applied in a similar situation?

5 comments:

  1. Or it can be solved by bisection (on the objective value) using a sequence of MILPs ...

    ReplyDelete
  2. If $\sum_i z_i > 0$, it's a linear-fractional program http://en.wikipedia.org/wiki/Linear-fractional_programming which can be transformed into a linear program using the Charnes-Cooper transformation.

    ReplyDelete
  3. Well, I already mentioned that. The model is not suited for that for different reasons: it would screw up the structure, become difficult to comprehend and there are discrete variables involved leading to more complications.

    ReplyDelete
  4. @Erwin: Oops ...sorry, missed PS2.

    ReplyDelete
  5. A comparison between MINLP solvers and solution with Dinkelbach's algorithm for mixed-integer fractional programming is found here:
    http://egon.cheme.cmu.edu/Papers/MILFP_YouCastroGrossmann.pdf.

    ReplyDelete