By convention, an MINLP is called "convex" if its *continuous relaxation* is convex.  That is, if we relax the MINLP by ignoring the integrality condition, then we obtain a convex NLP.

try to model your problem in GAMS. If it is MILP it's usually easy to solve. Otherwise the solver may not find even a feasible solution. 

Thanks Alireza Soroudi for your kind opinion.

I am waiting for a quality discussion about the question.

By convention, an MINLP is called "convex" if its *continuous relaxation* is convex.  That is, if we relax the MINLP by ignoring the integrality condition, then we obtain a convex NLP.

Prof. Adam

Thank you very much for your kind information about convexity of continuous relaxed MINLP problems. 

Sir, let me know some references about it? Once again, I will be very thankful to you for suggesting me any reference for convexity test of an MINLP problem.

If you think about that, the feasible region of a convex problem is a convex set. A set S is convex if, given two points x,y in S, every convex combination t*x + (1-t)*y belongs to S (where t is in [0,1]). Clearly, if x and y are integer, you can always find a value of t in [0,1] such that  t*x + (1-t)*y is not integer, hence there exist a convex combination of x and y which does not belong to S. This means that the feasible region of a problem with integer variables is not convex, so every instance of MILP/MINLP is not a convex problem. As Prof. Letchford wrote, it makes sense to consider convexity only if you relax the integrality condition. The continuous relaxation of an MILP is an LP that is convex. The continuous relaxation of an MINLP is a NLP, which can be convex or not, and this depends on the type of objective function/constraints.

Thanks a lot Dr. Alberto Costa.

While I agree that the integrality restrictions mean the feasible region is not convex, I disagree with the statement that it is not important to know the convexity of the continuous relaxation.  The MINLP is easier to solve if the continuous relaxations are convex, as you only have to branch on the nonconvexity associated with the integrality restrictions.   If the continuous  relaxations are nonconvex, the algorithms used often involve an additional relaxation/approximation to address that nonconvexity.   So now you not only have to branch to address the integrality restrictions, but the nonconvexity of the relaxation objective or feasible region.   That potentially makes such MINLPs more difficult to solve.   One reference I find useful on this subject is Pierre Bonami's slides from the 2014 ROADEF conference, available at http://ibm.co/1gtDdlj.   Not only are the slides useful, but they have an extensive bibliography of useful journal articles. 

Dear Mahamad, this issue is covered in the four surveys that I mentioned in my answer to your other question.

Thank you Prof. A. N. Letchford.

I would like to especially thank Mr. Ed Klotz of IBM for sharing his point of view over here.

There are already excellent answers on the theoretical foundations for your core question. As an applied OR person specializing in the power systems applications where your interests are, let me build on what Alireza has mentioned. Firstly, it IS very important to know if the MILP or MINLP or even the underlying relaxed LP/NLP are convex or not. You can have for instance the simplest economic load dispatch with losses represented as piecewise linear approximation. It is convex BUT the moment you try negative bids for generators (as we experience in some electricity markets these days) - the convexity breaks down as the model tries to maximize rather than minimize losses filling up the highest lost segments first. This problem has been encountered in some markets and called 'non-physical loss'. Secondly, if you solve the problem with one of the commercial solvers through one of the many math programming languages, the choice of solvers would be influenced by the answer you have. Solvers that rely on Outer Approximation method (that DICOPT implemented a while ago) has a better chance to track the global optimal than some of the branch and bound based methods, purely because the way the algorithm is structured. There is no guarantee as always but I have tested this a lot on Optimal Power Flow models with integer decisions (and AC power flow constraints) for voltage stability analysis and found the outer approximation to perform significantly better. Finally, at the expense of stating the obvious, I think it is just a good idea to know the structure of the problem to be able to tune your solution algorithm and interpret the results. The number of blank looks I get these days when I bring up the convexity issue, it definitely unnerves the 'old school' boys like me :-)

Hi everyone. I want just to make some comments regarding this issue, hoping it is still relevant for those involved in the conversation and for those who will look for a reference in it. As noted above, the fact that at least one of the variables is constrained to have discrete values makes any Mixed-integer problem by definition non-convex. Usually the way to deal with these kind of non-convex problems is through enumeration, which requires us to explore all the different possible values of those discrete variables. Since the number of combinations of the possible discrete solutions grows exponentially (e.g. with n binary variables you have 2^n possible combinations) one needs to rely on tools to avoid exploring all these combinations. Among these tools, we can solve the continuous relaxation of the original problem (defining the discrete variables as continuous variables bounded by the original discrete bounds) which can inform us on bounds for the original problem. Each time we find a solution that satisfies the original integrality constraints, i.e. that all the variables originally discrete have a discrete value and satisfy all the constraints, we find a feasible solution to the original problem which also provides a primal bound (upper bound in case you are minimizing). Every other solution of the continuous relaxation, that is solving a problem in a larger feasible region compared to the original, provides a dual bound (lower bound if minimizing) to the original problem. Using these bounds we can reduce the search space for our enumeration algorithms resulting in the famous Branch and Bound methods.

Soon after developing these methods for Mixed Integer linear programs (which by definition have a convex continuous relaxation), it was identified that the actual boundary between Polynomial solvable and Non-polynomial solvable was not in the linear/nonlinear boundary but in the convex/non convex boundary; meaning that there are polynomial algorithms to solve nonlinear convex programs. This allowed that one could solve the convex MINLP problems using the same Branch and Bound techniques with each node being Polynomial solvable. Finally, other methods relying on the decomposition of the MINLP in MILP and NLP problems were developed. The decomposition of the original problem was done though the gradient based approximation of the nonlinear functions (outer approximation), which produces a supporting hyperplane, i.e. an inequality that won't cut off any part of the feasible region, if the constraints defined a convex feasible region.

So, to the original question, whether if it is necessary to test convexity of the MILP/MINLP problems we have:

• By definition the problem is nonconvex.
• If we used the convention of naming these problems convex based on continuous relaxation for MILP it is not necessary, they are convex in this definition, for MINLP it depends on which solver/algorithm are you using.
• In case you know it is convex, you can apply an algorithm which is guaranteed to return you the global optimal solution (e.g. Outer approximation). These algorithms are not even guaranteed to return a feasible solution in case you have a nonconvex MINLP, but are considerably efficient.
• There are algorithms available to return the global optimal solution of nonconvex MINLP problems. These rely on convexification of the nonconvex terms in your problem, and you end up paying a cost in terms of computational time for these kind of guarantees.

Together with some colleagues we have recently published a paper comparing solvers for convex MINLP. It is open access and you can find it here Article A review and comparison of solvers for convex MINLP

Cheers!