Gurobi ignores constraints

#1

Dear all,

I am trying to solve the following optimization problem using Gurobi:

cvx_begin
cvx_solver gurobi
variable dp(length(p0))
minimize norm(A*dp - b)
subject to
    p0 + dp <= 1
    p0 + dp >= 0
cvx_end

The problem is solved really really fast but the constraints described after “subject to” are not satisfied. some entries of p0 are clearly above 1 with values like 1.7.
This problem only arises when using Gurobi. MOSEK completely satisfies these constraints.

Is there something I overlooked?

I would really appreciate any help here.
Thank you in advance.

Here is the output cvx produces:

Calling Gurobi 8.11: 64289 variables, 51365 equality constraints
------------------------------------------------------------
Academic license - for non-commercial use only
Warning: Unknown parameter: 'isvname'
 
> In cvx_gurobi
  In cvx_run_solver (line 50)
  In cvx_gurobi
  In cvxprob/solve (line 429)
  In cvx_end (line 88)
Warning: Unknown parameter: 'appname'
 
> In cvx_gurobi
  In cvx_run_solver (line 50)
  In cvx_gurobi
  In cvxprob/solve (line 429)
  In cvx_end (line 88)
Warning: Unknown parameter: 'isv_key'
 
> In cvx_gurobi
  In cvx_run_solver (line 50)
  In cvx_gurobi
  In cvxprob/solve (line 429)
  In cvx_end (line 88)
Warning for adding variables: zero or small (< 1e-13) coefficients, ignored
Optimize a model with 51365 rows, 64289 columns and 107501 nonzeros
Variable types: 57828 continuous, 6461 integer (6461 binary)
Coefficient statistics:
  Matrix range     [1e-13, 2e+01]
  Objective range  [0e+00, 0e+00]
  Bounds range     [1e+00, 1e+00]
  RHS range        [0e+00, 0e+00]
Found heuristic solution: objective 0.0000000

Explored 0 nodes (0 simplex iterations) in 0.04 seconds
Thread count was 1 (of 4 available processors)

Solution count 1: 0 

Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0
(Mark L. Stone) #2

The Gurobi output seems to suggest your model has binary or integer constraint, and the first version (prior to editing) of your post shows a binary declaration, yet the model you show has no binary or integer declaration. Please clarify.

Presuming you are “complaining” about value of dp:. The model you show has no constraint on dp “by itself”; only on the sum p0 + dp. Therefore, the optimal objective value of zero can be achieved if 0 <= p0 + A\b <= 1, even if dp has elements exceeding one, which would be allowed.

It makes no sense to complain about the value of p0, because it is input data to your program.

Other possibilities:
Bug in CVX (are you using CVX 3.0beta, if so, use CVX 2.1 instead)).
Bad numerics messing things up due to wide span of coefficient values in A as reported by Gurobi.

#3

First of all thank you for your reply Mark.

I edited to a simplified model because the error occurs regardless if I use binary variables or not.

To clarify - this is the model I am talking about now:

cvx_begin
cvx_solver_settings -clear
cvx_solver gurobi
variable dp(length(p0))
minimize norm(A*dp - b)
subject to
   p0 + dp <= 1
   p0 + dp >= 0
cvx_end

This is the log output:

Calling Gurobi 8.11: 51366 variables, 44904 equality constraints
------------------------------------------------------------
Academic license - for non-commercial use only
Warning: Unknown parameter: 'isvname'
 
> In cvx_gurobi
  In cvx_run_solver (line 50)
  In cvx_gurobi
  In cvxprob/solve (line 429)
  In cvx_end (line 88)
Warning: Unknown parameter: 'appname'
 
> In cvx_gurobi
  In cvx_run_solver (line 50)
  In cvx_gurobi
  In cvxprob/solve (line 429)
  In cvx_end (line 88)
Warning: Unknown parameter: 'isv_key'
 
> In cvx_gurobi
  In cvx_run_solver (line 50)
  In cvx_gurobi
  In cvxprob/solve (line 429)
  In cvx_end (line 88)
Warning for adding variables: zero or small (< 1e-13) coefficients, ignored
Optimize a model with 44904 rows, 51366 columns and 87140 nonzeros
Coefficient statistics:
  Matrix range     [1e-13, 2e+01]
  Objective range  [0e+00, 0e+00]
  Bounds range     [0e+00, 0e+00]
  RHS range        [0e+00, 0e+00]

Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...

Presolve removed 44904 rows and 51366 columns
Presolve time: 0.04s
Presolve: All rows and columns removed
Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0    0.0000000e+00   0.000000e+00   0.000000e+00      0s

Solved with dual simplex
Solved in 0 iterations and 0.08 seconds
Optimal objective  0.000000000e+00
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0

I am using Version 2.1, Build 1127 (95903bf) as reported by cvx_version.

So if I get you right you’re saying that the constraint is formulated wrongly. But how can I formulate the restriction that each element of the vector p0+dp shall be between 0 and 1?
Concerning the numerics: I already tried setting
cvx_solver_settings(‘NumericFocus’, 3)
but unfortunately it did not make any difference.

I also do not quite understand why MOSEK for instance solves this as expected while Gurobi does not.

(Mark L. Stone) #4

You haven’t shown clearly what the violation is. do not know whether you have formulated the constraints correctly because I don;t know what you intend. Your constraints, as entered, are on p0 + dp Please address the 2nd and 3rd paragraphs of my previous reply, so that we can understand what violation you are claiming.

#5

I have a vector p0 with the following elements as an example:

0.5
0.3
0.2
0.7
0.9

now I want to solve the minimization problem A*dp - b with the restriction, that each element of the sum of the vectors dp and p0 will be between 0 and 1.
For dp in this case the following range of values would then be acceptable:

-0.5 to 0.5
-0.3 to 0.7
-0.2 to 0.8
-0.7 to 0.3
-0.9 to 0.1

I hope that was what you we’re asking for.
This works just as expected using MOSEK but not using Gurobi.

directly in Matlab I have implemented this as

subject to
   p0 + dp <= p_range(:,2)
   p0 + dp >= p_range(:,1)
cvx_end

with p_range holding 1’s in the second column and 0’s in the first column if this makes a difference.

(Mark L. Stone) #6

Can you provide a small reproducible version of this which exhibits the “error”? I.e., complete with all input data.

Given that the output you showed says that Gurobi solved the problem in presolve, you can try turning off presolve in Gurobi via cvx_solver_settings http://cvxr.com/cvx/doc/solver.html#advanced-solver-settings in the event that perhaps there is a bug or susceptibility to bad numerics in presolve.

The most parsimonious way of entering your constraints into CVX is
0 <= p0 + dp <= 1

#7

The following link provides a zipped .mat with the relevant input data and a matlab test script exhibiting the issue. I have tested it using Matlab R2018b.

Thank you for having a look.

(Mark L. Stone) #8

As a matter of forum security,please restrict code and data to what can be posted directly on this site, not external sites.

#9

Okay I have tried to find a problem of small size so I can post it here that also shows this behavior:

A is a sparse complex double 189x35 with values:

 (135,1)     -0.1367 + 0.1749i
 (136,2)      0.3306 - 1.4107i
 (137,3)      0.3082 - 0.9338i
 (138,4)      0.6593 - 0.0817i
 (139,5)      0.8954 + 0.4595i
 (142,6)     -0.0576 + 0.8289i
 (143,7)      0.0082 - 0.9681i
 (144,8)     -0.1282 - 0.7835i
 (145,9)      0.4682 - 0.1218i
 (146,10)     1.1559 + 0.4019i
 (149,11)    -0.5109 + 1.3432i
 (150,12)    -0.8386 - 0.3687i
 (151,13)    -1.1434 - 0.3746i
 (152,14)    -0.4320 + 0.0146i
 (153,15)     0.5149 + 0.3410i
 (156,16)    -1.0249 + 1.5887i
 (157,17)    -1.5286 + 0.0538i
 (158,18)    -1.9509 - 0.0512i
 (159,19)    -1.2376 + 0.1025i
 (160,20)    -0.2473 + 0.2031i
 (163,21)    -0.9040 + 1.6541i
 (164,22)    -1.4053 + 0.1511i
 (165,23)    -1.8340 - 0.0006i
 (166,24)    -1.1514 + 0.0509i
 (167,25)    -0.2053 + 0.0614i
 (170,26)    -0.3075 + 1.4840i
 (171,27)    -0.6141 - 0.0928i
 (172,28)    -0.9139 - 0.2075i
 (173,29)    -0.2691 - 0.0842i
 (174,30)     0.5634 + 0.0011i
 (177,31)    -0.0308 + 0.9085i
 (178,32)     0.0584 - 0.5424i
 (179,33)    -0.0019 - 0.4877i
 (180,34)     0.5524 - 0.1569i
 (181,35)     1.1244 + 0.0683i

b is a complex double 189x1 with the following values

0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.00000000000000 + 0.00000000000000i
0.451767892286248 - 0.0984887685992476i
-0.186746287565961 - 0.234210313521049i
-0.238986677779402 - 0.162931702335663i
-0.108019031983878 - 0.0255370344699410i
0.0624773386874219 + 0.0619360566624633i
-0.0507106034192851 + 0.109103863179097i
-0.127467959301767 + 0.0251467219763494i
0.0666658055458473 - 0.0548227929207385i
-0.0813844508335685 - 0.0218026386120410i
-0.0820679949343032 + 0.0198765786071449i
-0.0112529687722592 + 0.0526438968550827i
0.0836580727468601 + 0.0477425284687704i
0.00355951427924545 + 0.0518731443499330i
-0.0539214938161495 + 0.0187313822942415i
0.163303763602547 - 0.0635323596692992i
-0.113183247016945 - 0.0497037574804551i
-0.115550082696522 + 0.0121551619440631i
-0.0154684578885712 + 0.0683736091289466i
0.100964183042530 + 0.0709684813352773i
-0.0198239474131061 + 0.0746670647141227i
-0.116776030566267 + 0.0190795745477130i
0.167982806160731 - 0.0603182094059083i
-0.124935861747283 - 0.0702828640627505i
-0.130155507106062 - 0.00314970532293843i
-0.0200062601527203 + 0.0662538381398065i
0.0979050572101737 + 0.0764718086854680i
-0.0462833790394791 + 0.0784580936450336i
-0.161777593142035 + 0.00957275068951476i
0.133020624365489 - 0.0449856977253197i
-0.118931365583437 - 0.0804272625178288i
-0.123490805374515 - 0.0179016145774857i
-0.0115195108958254 + 0.0540691772551751i
0.102567193347161 + 0.0678176281886014i
-0.0529340473245425 + 0.0708568638741452i
-0.174726774711446 + 0.000457544296932331i
0.136165454559517 - 0.0195220890769397i
-0.103617154683121 - 0.0803790496728034i
-0.103705808105524 - 0.0238078399416313i
0.00674003168769088 + 0.0436321007599248i
0.117550498822787 + 0.0565574412292208i
-0.0378169689315449 + 0.0624002479131001i
-0.157862691058826 - 0.00272905109715679i
0.152432779665275 - 0.0155656616792726i
-0.0897966417891108 - 0.0680899093187325i
-0.0855489889892977 - 0.0160992478814708i
0.0173778857016314 + 0.0421782192403136i
0.123734857929576 + 0.0508709549566237i
-0.0183957437700206 + 0.0594886200512273i
-0.127720193444215 + 0.00343276839472515i
0.110241821985153 - 0.0460574170483952i
-0.0802186976402323 - 0.0433040937918527i
-0.0762026347110561 + 0.00172357157714947i
0.00617471299674294 + 0.0463020693059800i
0.0969321759717160 + 0.0497130287699387i
-0.0125180752600083 + 0.0588762545132580i
-0.0958746705828264 + 0.0154352779374145i
0.0255874180120349 - 0.0638047518937523i
-0.0648768749025830 - 0.0135118078110220i
-0.0649839174849397 + 0.0174920624416018i
-0.0200996711151028 + 0.0432625707771713i
0.0170560861991252 + 0.0484749127356651i
-0.0196610215316924 + 0.0491359066250268i
-0.0548279397979754 + 0.0184327916292436i

here is the code:

data = load('inputData.mat');
A = data.A;
b = data.b;
p0 = ones(35,1)*0.5;
g = data.g
p_range = g.p_range
cvx_begin
    %cvx_solver mosek %works as expected
    cvx_solver gurobi %constraints not fulfilled
    
    variable dp(length(p0))
    minimize norm(A*dp - b)
    subject to
        p0 + dp <= p_range(:,2)
        p0 + dp >= p_range(:,1)
cvx_end

result = p0 + dp;

p_range(:,2) holds 1s p_range(:,1) holds 0s

this gives me result(1,1) = 1.0952.

If you don’t want to paste the data by hand here is the .mat file:

Gurobi got a wrong result when showing "Solved" in a simple question
(Mark L. Stone) #10

This appears to be a bug either in Gurobi or in the CVX/Gurobi interface.

I replicated your results with Gurobi, both with the default of Gurobi presolve enabled, and with it disabled via the command cvx_solver_settings('Presolve',0). Moreover, the objective value using the “optimal” (as reported by CVX) value of dp is 1.249763668404673, as opposed to cvx_optval = 0.

Mosek, SeDuMi, and SDPT3 all appeared to correctly solve the problem. The objective value using the optimal (as reported by CVX) value of dp matches cvx_optval = 0.963881, as it should.

The Gurobi solution actually achieved a worse objective value than the true optimum, while also violating constraints. So double demerits.

1 Like