I have a problem with constraints of the form yi = fi(x), where x and yi are variables, and f_i are nonlinear functions. Our approach consists of linearizing the function fi and using SOS2 constraints to model the resulting piecewise linear functions. Q1: a few of the functions fi are actually convex. Is there a different way of handling the constraint than the one described above that would exploit the convexity property? Or is there maybe some strategies that can used at optimization time? Q2: say that all the fi are convex (Scenario 1) or nonconvex (Scenario 2)? Should I expect a difference in terms of resolution time? In other words, when modelling with SOS2 constraints, does the property of the fi matter? Thanks Alexis
asked
aguigue |

Q1: If \(f_i()\) is convex, the pw-linear (SOS2) approximation \(\ell_i()\) will overestimate it, i.e., \(y_i=f_i(x)\le \ell_i(x)\). If it happens that the \(f_i\) are not just convex but also differentiable with closed-form gradients, you can trap \(y_i\) between the pw-linear approximation and the tangent: \(f_{i}(\hat{x})+\nabla f_{i}(\hat{x})\left(x-\hat{x}\right)\le y_{i}\le\ell_{i}(x)\) where \(\hat{x}\) is the value of \(x\) in a proposed incumbent. The lower limit on \(y_i\) can be added on the fly using a callback if your MIP solver supports such callbacks. Q2: I don't have a definitive answer, but given how few valid generalizations there are about MIP models, I'd be surprised if one popped up here regarding execution time.
answered
Paul Rubin ♦♦ |