Quadratic Programming Problem - CPL

jump
optimization

#1

I am trying to solve a convex QP. Let us consider the following example:

using JuMP, CPLEX
m = Model(with_optimizer(CPLEX.Optimizer))
@variable(m,x[1:5],lower_bound=0)
A = rand(5,5).*2 .- 1
c = rand(5,1)
A = A'*A
@objective(m,Min,sum(A[i,j]*x[i]*x[j] for i=1:5, j=1:5)+sum(c[i]*x[i] for i=1:5))
status = optimize!(m)

It is showing me the following error:

The solver does not support an objective function of type MathOptInterface.ScalarQuadraticFunction{Float64}.

As far as my understanding, JuMP and CPLEX support to solve convex QP. Am I missing something here?

I am using Julia 1.1.0 with the following packages:

“Clp” => v"0.6.1"
“Atom” => v"0.7.14"
“CPLEX” => v"0.4.3"
“JuMP” => v"0.19.0"
“Juno” => v"0.5.4"
“Conda” => v"1.2.0"
“ExcelReaders” => v"0.10.3"
“MathProgBase” => v"0.7.7"
“XLSX” => v"0.4.6"
“Cbc” => v"0.6.0"
“DataFrames” => v"0.17.1".


#2

I don’t know the CPLEX.jl wrapper in detail, but maybe quadratic objectives are not supported directly, but require an auxiliary variable with a bounding constraint. At least that is true for SCIP.jl.

See also the discussion in this issue for a generic solution: https://github.com/JuliaOpt/MathOptInterface.jl/issues/529


#3

The CPLEX wrapper hasn’t implemented the quadratic objectives yet. Pull requests accepted :slight_smile:

It shouldn’t be too hard because you can copy the Gurobi implementation (it’s more or less just matching up the different C names).

You would need to edit the CPLEX/src/MOI_wrapper.jl and add the functions beginning with LQOI. and containing quadratic in the Gurobi wrapper:

You also have to add these lines to the list of supported objectives


and constraints

Issue: https://github.com/JuliaOpt/CPLEX.jl/issues/217


#4

It is giving me the following error:

delq! not defined

Line 361 in https://github.com/JuliaOpt/Gurobi.jl/blob/f1418b5c470fb91b417e3424241a3440078c9212/src/MOI_wrapper.jl#L311-L367


#5

You will need to replace Gurobi-specific functions like delq!(model.inner) with the appropriate CPLEX one.

Looking through the CPLEX API, it seems that the following should be sufficient (I haven’t tested this):

function LQOI.set_quadratic_objective!(model::Optimizer, I::Vector{Int}, J::Vector{Int}, V::Vector{Float64})
    @assert length(I) == length(J) == length(V)
    scalediagonal!(V, I, J, 0.5)
    CPLEX.add_qpterms!(model.inner, I, J, V)
    scalediagonal!(V, I, J, 2.0)
    return
end

You don’t need delq or _require_update.


#6

I think it is still broken.

When I am trying to solve the following problem:

using JuMP, CPLEX
function Opti_model(A,b)
m = Model(with_optimizer(CPLEX.Optimizer))
@variable(m,x[1:5],lower_bound=0,upper_bound=1)
@objective(m,Min,sum(A[i,j]*x[i]*x[j] for i=1:5, j=1:5)+sum(c[i]*x[i] for i=1:5))
JuMP.optimize!(m)
return (JuMP.value.(x))
end
B = rand(5,5).*2 .- 1
c = rand(5,1)
Primal_sol = Opti_model(B’*B,c)

it is giving me the following error:

LoadError: MethodError: no method matching solve_quadratic_problem!(::CPLEX.Optimizer)
Closest candidates are:
solve_quadratic_problem!(!Matched::LinQuadOptInterface.MockLinQuadOptimizer) at C:\Users\Administrator.julia\packages\LinQuadOptInterface\ZMx9f\src\mockoptimizer.jl:766

Another instance, I am trying to solve which is basically a QIP problem (convex), that is,

using JuMP, CPLEX
function Opti_model(A,b)
m = Model(with_optimizer(CPLEX.Optimizer))
@variable(m,x[1:5],lower_bound=0,upper_bound=1)
@variable(m,y[1:5],Bin)
@objective(m,Min,sum(A[i,j]*x[i]*x[j] for i=1:5, j=1:5)+sum(c[i]*y[i] for i=1:5))
JuMP.optimize!(m)
return (JuMP.value.(x))
end
B = rand(5,5).*2 .- 1
c = rand(5,1)
Primal_sol = Opti_model(B’*B,c)

it is throwing me the following error message:

CPLEX.CplexError(5002, “CPLEX Error 5002: %s is not convex.\n”)

I understand that y is a binary variable which makes the optimization problem non-convex, but CPLEX (I am using CPLEX 12.8.0) still should solve it. [CPLEX 12.6.0 Documentation]

Any input from you would be very helpful.


#8

You will also need to define the solve_quadratic_problem function (and possibly some others as well). Do you have the changes somewhere? Please make a pull request to CPLEX.jl and we can point you in the right direction. The JuMP contributing guide has links to Git tutorials if you aren’t sure how to make a pull request. Otherwise, I might find some time to implement the quadratic interface next week at JuMP-dev.


#9

Thanks. Your help is much appreciated. I am also trying to accustomed myself with Git.