Barrier algorithm relatively slow for convex QCQP
AnsweredDear Gurobi team,
I'm working on a heuristic to approximate the dual objective value for convex QCQPs. In order to benchmark my heuristic, I solved a few generated problems with Gurobi and Cplex as a comparison. While doing so noticed that Gurobi's barrier algorithm is three times slower than CPLEX for all generated problems. Here are the logs for one of the problems:
Academic license - for non-commercial use only - expires 2021-04-11
Using license file /Library/gurobi910/mac64/gurobi.lic
Set parameter LogFile to value gurobi.log
Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (mac64)
Copyright (c) 2020, Gurobi Optimization, LLC
Read MPS format model from file MIQCQP_MQC_seed_20_fac_30_relaxed.mps.gz
Reading time = 0.29 seconds
miqpex1: 240 rows, 450 columns, 84402 nonzeros
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 240 rows, 450 columns and 84402 nonzeros
Model fingerprint: 0x680f4b6a
Model has 101475 quadratic objective terms
Model has 4 quadratic constraints
Coefficient statistics:
Matrix range [1e+00, 3e+00]
QMatrix range [1e+02, 3e+03]
QLMatrix range [1e+00, 4e+02]
Objective range [1e+00, 6e+00]
QObjective range [8e+02, 5e+03]
Bounds range [1e+01, 1e+01]
RHS range [1e+00, 6e+00]
Presolve removed 0 rows and 90 columns
Presolve time: 0.09s
Presolved: 2049 rows, 2170 columns, 395618 nonzeros
Presolved model has 5 second-order cone constraints
Ordering time: 0.01s
Barrier statistics:
Dense cols : 365
AA' NZ : 3.956e+05
Factor NZ : 4.645e+05 (roughly 7 MBytes of memory)
Factor Ops : 1.153e+08 (less than 1 second per iteration)
Threads : 8
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 9.80522293e+03 -1.35897497e+05 1.83e+04 7.17e-01 9.81e+01 1s
1 3.45468308e+03 -4.49688404e+04 5.45e+03 1.13e-01 2.35e+01 2s
2 4.77779463e+02 -2.75447736e+03 5.63e+02 1.04e-03 1.35e+00 2s
3 2.86876527e+02 -8.16543753e+01 2.24e+02 1.00e-06 1.65e-01 3s
4 3.28106468e+02 2.10026297e+02 5.55e+01 4.50e-10 6.57e-02 3s
5 4.73018705e+02 2.77257875e+02 1.32e+01 3.00e-11 7.82e-02 4s
6 4.62402525e+02 3.26445115e+02 9.51e+00 2.19e-11 5.70e-02 4s
7 4.90437401e+02 4.33225875e+02 4.46e+00 6.83e-11 3.31e-02 5s
8 4.95643084e+02 4.87198417e+02 2.74e-01 6.44e-13 3.89e-03 5s
9 4.92196909e+02 4.91642323e+02 8.32e-03 6.52e-12 2.24e-04 6s
10 4.91932514e+02 4.91818230e+02 1.42e-03 6.32e-11 4.45e-05 6s
11 4.91906087e+02 4.91903056e+02 1.67e-05 1.47e-10 1.15e-06 7s
12 4.91905201e+02 4.91904924e+02 1.61e-06 2.15e-10 1.05e-07 8s
Barrier solved model in 12 iterations and 7.69 seconds
Optimal objective 4.91905201e+02
Welcome to IBM(R) ILOG(R) CPLEX(R) Interactive Optimizer 20.1.0.0
with Simplex, Mixed Integer & Barrier Optimizers
5725-A06 5725-A29 5724-Y48 5724-Y49 5724-Y54 5724-Y55 5655-Y21
Copyright IBM Corp. 1988, 2020. All Rights Reserved.
Type 'help' for a list of available commands.
Type 'help' followed by a command name for more
information on commands.
CPLEX> Selected objective sense: MINIMIZE
Selected objective name: OBJ
Selected RHS name: RHS1
Selected bound name: BND1
Problem 'MIQCQP_MQC_seed_20_fac_30_relaxed.mps.gz' read.
Read time = 0.29 sec. (94.72 ticks)
CPLEX> Version identifier: 20.1.0.0 | 2020-11-10 | 9bedb6d68
Tried aggregator 1 time.
QCP Presolve eliminated 0 rows and 90 columns.
Aggregator did 1 substitutions.
Reduced QCP has 2410 rows, 2170 columns, and 395979 nonzeros.
Reduced QCP has 5 quadratic constraints.
Presolve time = 0.09 sec. (263.20 ticks)
Parallel mode: using up to 8 threads for barrier.
***NOTE: Found 47 dense columns.
Number of nonzeros in lower triangle of A*A' = 2021918
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 1.17 sec. (3140.10 ticks)
Summary statistics for Cholesky factor:
Threads = 8
Rows in Factor = 2457
Integer space required = 131391
Total non-zeros in factor = 2179458
Total FP ops to factor = 2720837358
Itn Primal Obj Dual Obj Prim Inf Upper Inf Dual Inf Inf Ratio
0 -1.0330172e+04 -1.1481000e+04 2.31e+06 0.00e+00 1.40e+03 1.00e+00
1 -9.1928530e+03 -1.0217573e+04 2.31e+06 0.00e+00 1.40e+03 5.98e-01
2 -7.0939890e+03 -7.8899840e+03 2.06e+06 0.00e+00 1.25e+03 4.16e-01
3 -3.7400269e+03 -4.1783442e+03 1.60e+06 0.00e+00 9.73e+02 4.54e-01
4 -2.9241058e+03 -3.2799514e+03 8.83e+05 0.00e+00 5.37e+02 5.77e-01
5 5.7717591e+00 -4.4431699e+01 7.17e+05 0.00e+00 4.36e+02 2.68e+00
6 4.5189048e+02 4.4777531e+02 1.01e+05 0.00e+00 6.16e+01 3.19e+01
7 4.8970517e+02 4.8947732e+02 8.31e+03 0.00e+00 5.05e+00 5.85e+02
8 4.9179198e+02 4.9178022e+02 4.60e+02 0.00e+00 2.80e-01 1.14e+04
9 4.9189936e+02 4.9189876e+02 2.37e+01 0.00e+00 1.44e-02 2.24e+05
10 4.9190481e+02 4.9190478e+02 1.20e+00 0.00e+00 7.32e-04 4.42e+06
Barrier - Optimal: Objective = 4.9189959346e+02
Solution time = 1.88 sec. Iterations = 10
Deterministic time = 4996.75 ticks (2653.24 ticks/sec)
Both runs are using default settings.
Am I missing something? I already tried different values for the BarOrder parameter, without a change. You can find the problem here: https://file.io/dI7tTs2eiilD
Best,
Jonathan
0
-
This issue has been handled in a Support Ticket.
0
Please sign in to leave a comment.
Comments
1 comment