I have written mixed integer nonlinear programming (MINLP) problem which attached blew and now I want to solve this problem. My decision variables are xj, yj and zi. The other terms are constants.
I think this problem is considered as NP-hard but I’m not sure.
I've read somewhere that the first step I should perform is a convexity test on objective and constraint functions. And then select the suitable solver for solving it. But unfortunately, I didn’t have enough experience for solving this problem.
Therefore, I really appreciate if someone can guide me:
Is this problem is convex or non-convex?
How to solve this problem numerical?
Is there any tool that is able to automatically solve this problem?
Is a there a good introductory book where I can start?
Thank you very much in advance!
Hi. Here is my input.
Your problem is neither convex nor linear. It is not convex because your decision variables are not continuous but binary thus do not create a convex set. It is not linear because you have interaction between your decision variables.
Solving this problem is going to take a lot of efforts especially when your K is big. This problem is not only non linear integer but it is a combinatory problem. The first thing to do is to check if you did the best formulation. You should try your best to formulate the problem in the simplest yet complete manner as possible. There are techniques for linearizing non linear functions. You could look into it. This book by H. P. Williams
Model building in mathematical programming is a good reference.
Finally, if you do your best and your problem is still so complex, non linear, non quadratic, you can try to solve it using heuristic methods. The difference between heuristic methods and exact methods is that heuristics give you a solution that you have no guaranty is optimal. But at least the solution will be feasible and near optimal. There are many heuristics out there for the sole purpose.
Good luck
Your problem belongs to the field of Combinatorial Optimization, which I do not think you are acquainted with. First you need to study this subject to have at least a preliminary idea of the possibilities of solving such problems. Then, taking into account your knowledge, you need to reformulate the problem in such a way that your solution methods would be able to solve your models. Your model is from the field of NP-hard problems in the strong sense. This means that, at best, you can solve this model using only heuristic algorithms within a given time limit. I suggest you to create these algorithms yourself, taking into account the peculiarities of your problem. However, the search for heuristic algorithms is not an end in itself. A method is needed to evaluate the quality of the solution A(D) of these algorithms "A", where D is the problem initial data. And here the method of finding Lower Bound LB(D) is very important for estimating the optimal solution OPT(D), where LB (D)
Hi, Do you have an option to use something like SAS? It does support NLP with integer/binary constraints.
Your objective function might need some clarification. it has x_j and y_j mentioned but summation on j is missing. Did I miss something?
Hi,
Branch&Bound for non-convex MINLP's is much more difficult than for MILPs - it would not work if the relaxations do yield only a local optimum and thus no lower bound. So the Bounding part would not work - and Branching alone leads to complete enumeration.
You'll have to resort to convex underestimators then - and software automatically formulating such underestimators in each node. Search for that keyword and you'll find the information needed.
Best regards
Ralf
Have you looked at the procedure known as (generalized) Benders decomposition? It is a procedure for a problem that has some nonlinearities and/or integrality constraints, and where a large "part" of the problem is linear. The basic story is that based on an initial feasible solution you construct an approximation of the problem through the fixation of the nonlinear or integer part, and solve the remaining linear program. The solution to that problem yields a point in space that is used to cut off part of the domain, and the process continues in that fashion. I'm sure you can find a simple description of the method somewhere in more detail.
- Badges
- Science topic
- Similar topics
- Physical Sciences
- Energy