Skip to main content

bilinear transformation and GRB.Param.NonConvex

Answered

Comments

3 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    HI Thomas,

    Am I right, that the bilinear transformation is only applied if the GRB.Param.NonConvex is set to 2? I am not totally sure, but got this impression with some of my datasets.

    Am I right, that GRB.Param.PreQLinearize is therefore also only relevant if GRB.Param.NonConvex is set to 2?

    The PreQLinearize affects the model even without setting the NonConvex parameter. It may behave differently if a model has products of continuous variables and products of binary variables, because then more freedom for linearization is present.

    For example, if you have a model with only binary products, then you should see a difference when experimenting with the PreQLinearize parameter without having to set the NonConvex parameter.

    Did I make a typo or is the parameter not available (anymore)?

    The parameter is no longer available. Gurobi now automatically "applies this parameter".

    Best regards, 
    Jaromił

    0
  • Thomas Leveringhaus
    Collaborator
    Investigator
    Gurobi-versary

    Dear Jaromił,

    thank you very much for your replies.

    The background of my question regarding PreQLinearize is the following:
    I have to solve a MI-QCQP. So I have my variable vector x consisting of binary and continous variables: x = [x_b,x_c]. In my problem, I only have quadratic inequality constraints and (fortunately, with regard to convexity and complexity) no quadratic equality constraints.
    The quadratic part of an exemplary quadratic inequality constraint (or the objective) is x.T @ H @ x. If H is "totally" nonconvex, the problem can't be solved with NonConvex unequal to 2. But I would like to solve it with NonConvex unequal to 2, because it is much faster ...
    If I split the quadratic part, I receive: [x_b,x_c].T @ [[H_bb,H_bc],[H_cb,H_cc]] @ [x_b,x_c]. Since H is symmetric, H_bc and H_cb equal each other. Is it correct that Gurobi should be able to convexificate the quadratic sub-parts x_b.T @ H_bb @ x_b as well as x_b.T @ H_bc @ x_c as well as x_c.T @ H_cb @ x_b by bilinear transformation, if H_bb, H_bc & H_cb are nonvconvex? If Yes, than only the sub-part x_c.T @ H_cc @ x_c with H_cc beeing nonconvex remains as a problem with NonConvex unequal to 2. During modelling (before giving all data to Gurobi) I can use approximations that make H_cc convex, but the total H remains nonconvex. So far, based on tests with my data sets, I have not had the impression that this works, but there might be other reasons or mistakes ... But if I understand you correctly, it should work, right?

    Thank you very much

    Thomas

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Thomas,

    Gurobi does not always linearize the product x_b * x_c (binary times continuous variables). It depends on how many of such products are present. If there are too many then Gurobi will not linearize all of them to not construct too many linearization constraints. Additionally, finite bounds for the continuous variables are used to make the linearization work.

    But if I understand you correctly, it should work, right?

    If your model does not have an extreme amount of x_b*x_b and x_b*x_c products, you provided finite bounds for all continuous variables, and all remaining constraints with x_c*x_c are convex then your approach should work. This is also noted in the documentation of the NonConvex parameter

    With setting 0, an error is reported if the original user model contains non-convex quadratic constructs, except for Q matrix linearization controlled by the PreQLinearize parameter.

    It might make sense to try testing your approach on a small model. This way, it is easier to find what works and what does not work and if you have a minimal reproducible example where you think your approach should work then, you could post it.

    Best regards, 
    Jaromił

    0

Please sign in to leave a comment.