Repository of the B&B algorithm to solve Nonconvex Quadratic problems with general linear constraints. N.B. the code uses the external solvers CPLEX, Gurobi and Ipopt plus the JuMP package. The code has been tested with the following versions of the above solvers:
- CPLEX v. 12.10
- Gurobi v. 9.1.1
- Ipopt v. 0.6.4
- JuMP v. 0.21.5
Hence, prior of using the code you must install these solvers along with their respective Julia interfaces.
Codes have been developed and run on a Julia environment with the following packages installed:
julia> Pkg.status()
Status `C:\Users\giamp\.julia\environments\v1.5\Project.toml`
[a076750e] CPLEX v0.7.3
[0a46da34] CSDP v0.7.0
[336ed68f] CSV v0.8.2
[9961bab8] Cbc v0.7.1
[a93c6f00] DataFrames v0.22.2
[60bf3e95] GLPK v0.14.3
[2e9cd046] Gurobi v0.8.0
[b6b21f68] Ipopt v0.6.4
[4076af6c] JuMP v0.21.5
[e5e0dc1b] Juno v0.8.4
[23992714] MAT v0.9.2
All the codes must be run from within folder codes. There are basically two ways of running the codes.
- edit file main.jl to suit your needs. Then, from a command prompt execute
$ julia -p <nproc> main.jl
- edit file main1.jl to suit your needs. Then, from a julia REPL execute
julia> include("main1.jl")
- randqp - this is were random QP instances are stored. Problems are provided as .mat Matlab® files
- codes - this is were the codes are stored
- results - this is were results related to the OPTL paper [1] are stored
The following figures show comparison of our B&T(Mix) method with state of the art solvers on problems in the randqp folder.
Fraction of problems with n=20,30,40,50 solved (y-axis) versus computing time (x-axis) for the different tested solvers.
Fraction of problems with n=20 solved (y-axis) versus computing time (x-axis) for the different tested solvers.
Fraction of problems with n=30 solved (y-axis) versus computing time (x-axis) for the different tested solvers.
Fraction of problems with n=40 solved (y-axis) versus computing time (x-axis) for the different tested solvers.
Fraction of problems with n=50 solved (y-axis) versus computing time (x-axis) for the different tested solvers.
[1] G.Liuzzi, M.Locatelli, V.Piccialli "A computational study on QP problems with general linear constraints". Submitted to Optimization Letters (2021)
1 Department of Computer, Control and Management Engineering, "Sapienza" University of Rome (giampaolo.liuzzi@uniroma1.it, veronica.piccialli@uniroma1.it)
2 Department of Engineering and Architecture, University of Parma (marco.locatelli@unipr.it)
Copyright 2021