Skip to main content

A conic quadratic constraints are considered convex if the variables are continuous, but is getting considered non convex if variables are binary?

Awaiting user input
Saurabh Belgaonkar
First Comment
First Question

A conic quadratic constraints are considered convex if the variables are continuous, but is getting considered non-convex if the variables are binary. 

So, I have the constraints in the quadratic form like this:
x^TQx <= y^2
and if x is considered as continuous, the Gurobi recognizes the constraint as convex and solves it appropriately. 

However, y is considered binary, gurobi recognizes it as non-convex and takes a lot of time to solve. Is there any reason for it, and any way to mitigate this problem?

0

Comments

4 comments

Date Votes
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Could you please share the log outputs of the two different runs? So one run where y is continuous and one run where y is binary?

    0
  • Saurabh Belgaonkar
    • Edited
    First Comment
    First Question

    Thanks for the reply.

    I am forcing Gurobi to use a convex optimizer as a non-convex optimizer is taking a long time.
    This is the output when the variable is continuous:

    Set parameter Username
    Academic license - for non-commercial use only - expires 2025-02-10
    Set parameter NonConvex to value 0
    Set parameter MIPGap to value 0.005
    Set parameter TimeLimit to value 5
    Warning: linear constraint 210 and linear constraint 211 have the same name "Source_SOC_constraint"
    Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (win64 - Windows 11+.0 (22631.2))

    CPU model: 12th Gen Intel(R) Core(TM) i7-12700H, instruction set [SSE2|AVX|AVX2]
    Thread count: 14 physical cores, 20 logical processors, using up to 20 threads

    Optimize a model with 287 rows, 1393 columns and 1599 nonzeros
    Model fingerprint: 0xef7edfe0
    Model has 169 quadratic constraints
    Coefficient statistics:
      Matrix range     [2e-02, 1e+00]
      QMatrix range    [1e+00, 2e+07]
      Objective range  [1e+00, 1e+00]
      Bounds range     [1e+00, 1e+02]
      RHS range        [1e+00, 2e+03]
    Presolve removed 43 rows and 347 columns
    Presolve time: 0.01s
    Presolved: 582 rows, 1385 columns, 2681 nonzeros
    Presolved model has 169 second-order cone constraints
    Ordering time: 0.00s

    Barrier statistics:
     AA' NZ     : 2.018e+03
     Factor NZ  : 5.502e+03 (roughly 1 MB of memory)
     Factor Ops : 6.199e+04 (less than 1 second per iteration)
     Threads    : 1

                      Objective                Residual
    Iter       Primal          Dual         Primal    Dual     Compl     Time
       0   5.24347161e+06 -4.59707006e+06  3.00e+03 2.42e+02  1.04e+05     0s
       1   4.00897914e+05 -4.27301277e+06  1.96e+02 1.14e+01  8.24e+03     0s
       2   8.35538275e+04 -2.63423607e+06  1.48e+01 2.78e+00  1.61e+03     0s
       3   3.25564823e+04 -4.82120657e+05  8.52e-03 3.17e-01  2.35e+02     0s
       4   1.85941531e+04 -1.01330140e+05  3.94e-04 6.61e-02  5.39e+01     0s
       5   9.05223183e+03 -1.76286416e+04  1.07e-04 1.19e-02  1.19e+01     0s
       6   4.42740375e+03 -2.12454924e+03  2.85e-05 2.32e-03  2.91e+00     0s
       7   3.29361404e+03  6.90176853e+02  1.30e-05 8.02e-04  1.15e+00     0s
       8   2.91506519e+03  1.85479784e+03  7.40e-06 2.23e-04  4.69e-01     0s
       9   2.68628581e+03  2.19264576e+03  4.09e-06 7.85e-05  2.18e-01     0s
      10   2.56454591e+03  2.33448113e+03  2.33e-06 2.16e-05  1.02e-01     0s
      11   2.48859672e+03  2.37358433e+03  1.20e-06 8.78e-06  5.09e-02     0s
      12   2.45589630e+03  2.39315023e+03  7.22e-07 3.20e-06  2.77e-02     0s
      13   2.44103796e+03  2.39802053e+03  5.03e-07 1.90e-06  1.90e-02     0s
      14   2.40975384e+03  2.40487054e+03  3.18e-08 1.97e-07  2.16e-03     0s
      15   2.40713231e+03  2.40665403e+03  2.95e-09 2.99e-08  2.11e-04     0s
      16   2.40703819e+03  2.40682423e+03  1.06e-08 1.64e-08  9.46e-05     0s
      17   2.40702943e+03  2.40691284e+03  4.25e-09 8.79e-09  5.15e-05     0s
      18   2.40702427e+03  2.40696489e+03  3.74e-10 4.56e-09  2.63e-05     0s
      19   2.40702371e+03  2.40699731e+03  2.85e-10 2.09e-09  1.17e-05     0s
      20   2.40702357e+03  2.40702091e+03  4.55e-09 7.71e-10  1.18e-06     0s
      21   2.40702335e+03  

    Barrier solved model in 21 iterations and 0.06 seconds (0.01 work units) Optimal objective 2.40702335e+03


    This is the output when the variable is binary:

     
     
    It's saying matrix Q is not PSD, and diagonal adjustment is required.
    0
  • Saurabh Belgaonkar
    First Comment
    First Question

    So, I have tried increasing the PSD tolerance using the PSDtol parameter, but in this case, it doesn't work, as the diagonal adjustment required is quite high ( 1.0 e+00). It works in some cases though.

    If possible could you provide any suggestions on how to tackle this problem?

    Thanks a lot for your help.

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    If possible could you provide any suggestions on how to tackle this problem? 

    Could you please try setting PreQLinearize=0? If this does not help, could you please share the two models, one with and one without binaries? You can generate the model files by using the write method. Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.

    Best regards, 
    Jaromił

    0

Please sign in to leave a comment.

Didn't find what you were looking for?

New post