# Does Gurobi solve QCQMIPs with Quadratic terms faster with then Bi-Linear terms in general?

Based on the color distance function defined here i try to find $$n$$ RGB colors with large inter set color distances and good color distance to white.

using JuMP
using Gurobi

m = Model(Gurobi.Optimizer)
set_optimizer_attribute(m, "NonConvex", 2)

n = 32;

@variable(m, o>=0);

@variable(m, 0 <= r[1:n] <= 255, Int);
@variable(m, 0 <= g[1:n] <= 255, Int);
@variable(m, 0 <= b[1:n] <= 255, Int);

comp = Int(n + (n*(n-1))/2);
c = 0

@variable(m, rmean[1:comp]);
@variable(m, rd[1:comp]);
@variable(m, gd[1:comp]);
@variable(m, bd[1:comp]);

@variable(m, rmeanr[1:comp]);
@variable(m, rmeanb[1:comp]);

@objective(m, Max, o);

for i in 1:n
c += 1
color_dist(o, 0.8, 255,255,255, r[i],g[i],b[i], c);
end

for i in 1:n
for j in (i+1):n
c += 1
color_dist(o, 0.8+0.2*(n-max(i-1,j-1)), r[i],g[i],b[i], r[j],g[j],b[j], c);
end
end

@show m

optimize!(m)

for i in 1:n
println("\"#",string(Int32(256^2*value(r[i]) + 256*value(g[i]) + 1*value(b[i]) ),base=16,pad=6),"\",")
end


If i define color_dist like this:

function color_diff(o,w,r1,g1,b1,r2,g2,b2,i)
@constraint(m, rmean[i] == (r1+r2)/2)
@constraint(m, rd[i] == r1 - r2)
@constraint(m, gd[i] == g1 - g2)
@constraint(m, bd[i] == b1 - b2)

@constraint(m, rmeanr[i] == rd[i]*rd[i]) #square
@constraint(m, rmeanb[i] == bd[i]*bd[i]) #terms

@constraint(m,o*o*(w)^2 <= rmeanr[i]*(512+rmean[i])/256 + 4*gd[i]*gd[i] + rmeanb[i]*(767-rmean[i])/256 )
end


Gurobi (log) performs much better then if i define it like this:

function color_dist(o,w,r1,g1,b1,r2,g2,b2,i)
@constraint(m, rmean[i] == (r1+r2)/2)
@constraint(m, rd[i] == r1 - r2)
@constraint(m, gd[i] == g1 - g2)
@constraint(m, bd[i] == b1 - b2)

@constraint(m, rmeanr[i] == (512+rmean[i])*rd[i]) #bi linear
@constraint(m, rmeanb[i] == (767-rmean[i])*bd[i]) #terms

@constraint(m,o*o*(w)^2 <= rmeanr[i]*rd[i]/256 + 4*gd[i]*gd[i] + rmeanb[i]*bd[i]/256 )
end


as seen in this log.

Gurobi after presolving turns all terms into bi-linear terms (as seen in the logs), yet
$$(( 512 + \text{rmean}_i ) * \text{rd}_i ) * \text{rd}_i$$ has much worse performance then $$(\text{rd}_i * \text{rd}_i ) * ( 512 + \text{rmean}_i)$$

Does that hold in general according to your experience?

• These terms are equivalent! This can also be seen as indicated in the logs by the number of bilinear terms. Try comparing more than two seeds. You can also write the model to a file and compare the presolved models to be sure (you will need to load up gurobi.sh and do m = read("model.lp") then p = m.presolve() then p.write("psolved.lp") and compare with the original). I can't seem to do this as the JuMP write_to_file function doesn't like quadratic terms, also, your code needs revising (missing function definitions and scope variable errors). Aug 24, 2022 at 8:27