Dear all,
I have faced a strange behavior of CPLEX 20.1 while solving a nonconvex quadratic problem.
As I couldn’t replicate the issue with small instances, I am attaching the data here:
data information
data (in .mat form): https://surfdrive.surf.nl/files/index.php/s/QPc8RO02tgDTrMF
Julia script: https://surfdrive.surf.nl/files/index.php/s/TL7wxGKTthisIGV
If you save the data file in the original folder (in windows it is C:/Users/“your user folder”), then the script is runnable.
the issue
I have generated a rather large instance, where the objective function is bilinear and the feasible region is polytope (so it is nonempty and bounded). The bound is generated by the last constraint. This implies that the optimal solution exists.
I am trying to solve the problem by Gurobi 9.1.0 and CPLEX 20.1 using JuMP 0.21.5 in Julia 1.5.3.
When Gurobi runs, I get the following log:
Academic license - for non-commercial use only - expires 2021-04-16
Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)
Thread count: 2 physical cores, 4 logical processors, using up to 4 threads
Optimize a model with 602 rows, 200 columns and 33185 nonzeros
Model fingerprint: 0x2c60fa1e
Model has 5440 quadratic objective terms
Coefficient statistics:
Matrix range [1e+00, 4e+01]
Objective range [0e+00, 0e+00]
QObjective range [6e-03, 4e+01]
Bounds range [0e+00, 0e+00]
RHS range [3e-02, 1e+02]
Presolve removed 312 rows and 0 columns
Continuous model is non-convex -- solving as a MIP.
Presolve removed 312 rows and 0 columns
Presolve time: 0.04s
Presolved: 11171 rows, 5641 columns, 43222 nonzeros
Presolved model has 5440 bilinear constraint(s)
Variable types: 5641 continuous, 0 integer (0 binary)
Root relaxation: objective -2.765601e+06, 6176 iterations, 0.69 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 -2765600.6 0 5347 - -2765600.6 - - 0s
H 0 0 -1405.486306 -2765600.6 - - 0s
0 0 -270029.68 0 28 -1405.4863 -270029.68 - - 3s
H 0 0 -20664.19608 -270029.68 1207% - 3s
H 0 0 -89504.20144 -270029.68 202% - 3s
0 0 -261382.87 0 32 -89504.201 -261382.87 192% - 3s
0 0 -199968.11 0 43 -89504.201 -199968.11 123% - 3s
H 0 0 -193021.5816 -199968.11 3.60% - 3s
H 0 0 -196003.8796 -199968.11 2.02% - 3s
0 0 -199962.94 0 38 -196003.88 -199962.94 2.02% - 3s
H 0 0 -196983.3961 -199962.94 1.51% - 5s
0 0 -199961.99 0 45 -196983.40 -199961.99 1.51% - 5s
H 0 0 -197189.5917 -199961.99 1.41% - 6s
H 0 0 -198338.7279 -199961.99 0.82% - 6s
H 0 0 -198682.3295 -199961.99 0.64% - 6s
H 0 0 -198764.2769 -199961.99 0.60% - 6s
0 2 -199961.99 0 45 -198764.28 -199961.99 0.60% - 7s
11 11 -199900.55 4 42 -198764.28 -199900.55 0.57% 761 10s
40 43 -199786.52 11 45 -198764.28 -199786.52 0.51% 664 15s
121 125 -198852.07 21 197 -198764.28 -199681.59 0.46% 398 20s
210 209 -199342.04 29 126 -198764.28 -199681.59 0.46% 318 25s
* 216 119 79 -198990.0425 -199681.59 0.35% 316 25s
249 117 -199194.90 35 47 -198990.04 -199681.59 0.35% 345 31s
274 118 -199264.28 7 65 -198990.04 -199612.39 0.31% 389 36s
283 132 -199287.67 10 28 -198990.04 -199612.39 0.31% 413 41s
395 274 -199253.31 44 15 -198990.04 -199612.39 0.31% 339 45s
* 423 155 56 -199253.3087 -199612.39 0.18% 318 45s
Cutting planes:
RLT: 211
Explored 511 nodes (156782 simplex iterations) in 47.75 seconds
Thread count was 4 (of 4 available processors)
Solution count 10: -199253 -198990 -198764 ... -89504.2
Optimal solution found (tolerance 1.00e-04)
Best objective -1.992533086180e+05, best bound -1.992665129450e+05, gap 0.0066%
and it finds an optimal solution. Now, when I use CPLEX, I get the following log:
User-callback calls 4788, time in user-callback 0.02 sec
Version identifier: 20.1.0.0 | 2020-11-10 | 9bedb6d68
CPXPARAM_OptimalityTarget 3
Warning: global optimality target changes problem type to MIQP.
Found incumbent of value -89.651812 after 0.00 sec. (0.11 ticks)
Tried aggregator 1 time.
MIQP Presolve eliminated 312 rows and 0 columns.
Reduced MIQP has 290 rows, 5640 columns, and 16021 nonzeros.
Reduced MIQP has 0 binaries, 0 generals, 0 SOSs, and 0 indicators.
Reduced MIQP objective Q matrix has 10880 nonzeros.
Presolve time = 0.02 sec. (14.19 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 4 threads.
Root relaxation solution time = 0.03 sec. (20.77 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
0 0 infeasible 7
Root node processing (before b&c):
Real time = 7.94 sec. (11311.06 ticks)
Parallel b&c, 4 threads:
Real time = 0.00 sec. (0.00 ticks)
Sync time (average) = 0.00 sec.
Wait time (average) = 0.00 sec.
------------
Total (root+branch&cut) = 7.94 sec. (11311.06 ticks)
with the termination status
DUAL_INFEASIBLE::TerminationStatusCode = 3
which implies either infeasibility or unboundedness.
I tried to see if the feasible region is small and that is a rounding error, but it seems not to be the case, as minimizing a linear function on the same polytope has a solution.
To investigate if the problem is with JuMP or CPLEX, I extracted the lp file from JuMP:
LP file constructed by JuMP:https://surfdrive.surf.nl/files/index.php/s/pxZDKHnqYDxuWE3
When I pass this file to the solver like Gurobi, I get the same infeasibility/unbounded termination. So, this actually means the model formulated by JuMP is not correct. Does that make sense?
I have tried to check what I can but I am not sure where to look! Any help is appreciated.