I have written a binary nonlinear programming problem which shown blew.
My decision variables are x_i,j, and y_i,j. The other terms are constants. N=100 and K=4.
I read that 0-1 NLP problem is considered as NP-hard in general.
I also read that the problem can be reduced to another one to demonstrate that it is NP-hard, but I don't know how to do this?
Therefore, I really appreciate if someone can guide me to know:
1- How to prove that this problem is NP-Hard or not?
2- Is it possible to apply Linearization and Relaxation approach to convert it to 0-1 LP and continues LP, respectively? And then solve using interior point method?
Thanks in advance!
Yes,
This problem is probably a tricky one, as you have mixed polynomials all over the place (x multiplied by y), hence many non-convexities.
It is straightforward that when general Binary LPs are NP-hard then Binary NLPs are NP-hard too.
But about your model, I think that you can replace xij * yij multiplication by new binary variable zij and add the constraints zij
I think you need to add an additional constraint besides the one @Majid suggested.
Z_ij
Dear Martin, the constraints which you mentioned are superfluous. In other words, based on what I suggested before, if xij = 0 then zij = xij * yij = 0 (since zij
- Badges
- Science topic
- Similar topics
- Biological Science
- Bioecology
- Systems Ecology
- Landscape Ecology
- Connectivity