Quadratic Programming Problem - CPL

Specific Domains Optimization (Mathematical)
,
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

1 Like
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:
https://github.com/JuliaOpt/Gurobi.jl/blob/f1418b5c470fb91b417e3424241a3440078c9212/src/MOI_wrapper.jl#L311-L367

You also have to add these lines to the list of supported objectives
https://github.com/JuliaOpt/Gurobi.jl/blob/f1418b5c470fb91b417e3424241a3440078c9212/src/MOI_wrapper.jl#L9
and constraints
https://github.com/JuliaOpt/Gurobi.jl/blob/f1418b5c470fb91b417e3424241a3440078c9212/src/MOI_wrapper.jl#L17-L19

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

1 Like
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.

1 Like
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.

1 Like
9

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

10

Hi,

I am trying to add quadratic support to CPLEX.jl with MOI.

I use this test example from matlab doc (the first one with numerical results):
[Quadratic programming - MATLAB quadprog - MathWorks France](qp example)

My test code is the following :

using JuMP, CPLEX

m = Model(with_optimizer(CPLEX.Optimizer))

@variable(m, x)
@variable(m, y)
@constraint(m, x+y <= 2)
@constraint(m, -x+2*y <= 2)
@constraint(m, 2*x+y <= 3)

@objective(m, Min, 0.5*x*x + y*y - x*y - 2*x - 6*y)

optimize!(m)

value(x), value(y), objective_value(m)

And I added the following code as suggested above in MOI_wrapper.jl of the CPLEX.jl package :

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

LQOI.solve_quadratic_problem!(model::Optimizer) = LQOI.solve_linear_problem!(model)

I commented the scalediagonal! function @odow as CPLEX kept returning that the matrix Q was not positive semi definite in my test case (which is absurd).

Now CPLEX seems to solve the problem properly. I obtain the same objective value as the matlab page, that is, -8.222 in the CPLEX log.

Now I have to define the get_quadratic_primal_solution! in MOI_wrapper as the call to optimize! returns

ERROR: LoadError: MethodError: no method matching get_quadratic_primal_solution!(::CPLEX.Optimizer, ::Array{Float64,1})

after the CPLEX output.

I tried this

function LQOI.get_quadratic_primal_solution!(model::Optimizer, dest)
    dest = CPLEX.get_solution(model.inner)
    return
end

function LQOI.get_quadratic_dual_solution!(model::Optimizer, dest)
    dest = CPLEX.get_constr_duals(model.inner)
    return
end

and the test example runs perfectly.
BUT the inconsistency with the definitions of LQOI.get_linear_primal_solution! LQOI.get_linear_dual_solution! is troubling me. I wonder if I miss some MOI feature.
Could you check my implementation?

Finally everything works fine with small QP and QCP examples from MOIT.contquadratictest written with JuMP macros.
However I added the MOIT.contquadratictest tests in the Tests of CPLEX.jl and 6 out of 42 quadratic tests do not pass. Should I do a pull request to get some help?

Thanks

11

Yes, make a PR.

get_quadratic_primal_solution and get_quadratic_dual_solution are the solutions associated with the quadratic constraints, not the primal variables.