search

lanl-ansi / Alpine.jl

A Julia/JuMP-based Global Optimization Solver for Non-convex Programs
https://lanl-ansi.github.io/Alpine.jl/latest/
Other
245 stars 40 forks source link

Piecewise quadratic relaxations #88

Closed harshangrjn closed 5 years ago

harshangrjn commented 6 years ago

Can you confirm, for the piecewise relaxation of the quadratic term in POD, is formulation (5) of https://arxiv.org/pdf/1707.02514.pdf implemented? From function "amp_post_tmc_monomial_mc" it looks like (5) is implemented. If so, the additional cuts we derived on \hat{Y} matrix can be added to strengthen the formulation.

harshangrjn commented 6 years ago

@kaarthiksundar?

kaarthiksundar commented 6 years ago

You are correct - that is what is implemented.

harshangrjn commented 6 years ago

Additional cuts on Y-hat matrix are yet to be tested. Lets keep this open until they are implemented and tested.

kaarthiksundar commented 5 years ago

@harshangrjn Have no plans from my side to implement and test this. Let me know if you are planning on doing this. Otherwise we can close this issue.

harshangrjn commented 5 years ago

Let this stay open until we finalize the best formulation.

krishpat commented 5 years ago

@harshangrjn Is there a paper where you have these cuts on \hat{Y} matrix explained? I can try to implement them and test.

harshangrjn commented 5 years ago

@krishpat Not really! They are simple cuts on the space of lifted variables. I can type them up and share it soon.

kaarthiksundar commented 5 years ago

@harshangrjn If you look more closely in Eq (5) of https://arxiv.org/pdf/1707.02514.pdf, you will see that no \hat{Y} matrix is needed. In fact Eq. (5) is exactly what is implemented without the \hat{Y} matrix since Eq (5) is already linear. No additional binary variables required. It is needed only for the Piecewise McCormick constraints and not in the piecewise quadratic relaxations, in which case we already know it does not work well when compared to the formulation that is implemented.

The sentences in the paper below Eq (5) is not needed - it is a typo in the paper.

Let me know if I am wrong.

harshangrjn commented 5 years ago

Yes! Unlike piecewise McCormick formulation, the piecewise quadratic relaxation doesn't require a lifted variable matrix. Thanks to @krishpat for re-initiating this thread as it can be closed now.

Btw, its not really a typo in the paper as the formulation and linearization are still right. Except that the lifted variable matrix variables are not binary and instead belong to [0,1]. Since anyway one of the variables in the product is always zero, the relaxation is still exact. Though I agree its not compact.