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

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)

@ Martin, Gennady, Alireza Thanks for your answers.

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

@ Ralf Gollmer, Thanks a lot for your answer.

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.

Thanks a lot for the answer