Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

QCQP #92

Closed
blegat opened this issue Aug 25, 2023 · 5 comments
Closed

QCQP #92

blegat opened this issue Aug 25, 2023 · 5 comments

Comments

@blegat
Copy link
Member

blegat commented Aug 25, 2023

We could implement a PolyJuMP.QCQP.Optimizer meta-solver that is parametrized by a QCQP optimizer like Alpine or Gurobi and rewrites polynomial constraints into QCQP.
@matbesancon gave me the reference https://hal.science/hal-03795395/ during the JuMP-dev call that might be relevant

@matbesancon
Copy link
Contributor

sorry note that the one of yesterday is only for polynomial binary optimization

@blegat
Copy link
Member Author

blegat commented Sep 15, 2023

@joaquimg I think you mentioned to me a paper in Boston this summer but I forgot :-P
@Shuvomoy What is the heuristic you use to rewrite monomials into quadratic in https://github.com/Shuvomoy/BnB-PEP-code ?

@Shuvomoy
Copy link

Shuvomoy commented Sep 15, 2023

@blegat @joaquimg It was something like this: suppose we have $$x^3 y z = w,$$ then we introduce dummy variables $$p=x^2, v=yz, u = p x = x^3.$$ Then the original constraint $$x^3 y z = w \Leftrightarrow ( w = u v, p = x^2, u = p x, v = y z).$$

In BnB-PEP, there was only one degree 3 term due to problem structure, so the dummy variable assignment could be done mechanically.

@Shuvomoy
Copy link

We could implement a PolyJuMP.QCQP.Optimizer meta-solver that is parametrized by a QCQP optimizer like Alpine or Gurobi and rewrites polynomial constraints into QCQP. @matbesancon gave me the reference https://hal.science/hal-03795395/ during the JuMP-dev call that might be relevant

I think this will be a great idea. Especially, Gurobi's QCQP solver has gotten very good since it came out in 2019.

@blegat
Copy link
Member Author

blegat commented Dec 4, 2023

Closed by #95

@blegat blegat closed this as completed Dec 4, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Development

No branches or pull requests

3 participants