GALAHAD RPD package#
purpose#
The rpd package reads and writes quadratic programming
(and related) problem data to and from a QPLIB-format data file.
Variables may be continuous, binary or integer.
Currently only the options and inform dictionaries are exposed; these are provided and used by other GALAHAD packages with Python interfaces. Please contact us if you would like full functionality!
See Section 4 of $GALAHAD/doc/rpd.pdf for additional details.
reference#
The QPBLIB format is defined in
F. Furini, E. Traversi, P. Belotti, A. Frangioni, A. Gleixner, N. Gould, L. Liberti, A. Lodi, R. Misener, H. Mittelmann, N. V. Sahinidis, S. Vigerske and A. Wiegele, ``QPLIB: a library of quadratic programming instances’’, Mathematical Programming Computation 11 (2019) 237-–265.
matrix storage#
The \(n\) by \(n\) objective Hessian matrix \(H\), the \(n\) by \(n\) constraint Hessians \((H_c)_i\), \(i = 1, \ldots, m\) and the \(m\) by \(n\) constraint Jacobian \(A\) will be available in a sparse co-ordinate storage format.
Only the nonzero entries of the matrices are stored. For the \(l\)-th entry of \(A\), its row index \(i\), column index \(j\) and value \(a_{ij}\) are stored in the \(l\)-th components of the integer arrays A_row, A_col and real array A_val, respectively. The order is unimportant, but the total number of entries A_ne is also required.
The same scheme is applicable to \(H\) (thus requiring integer arrays H_row, H_col, a real array H_val and an integer value H_ne), except that only the entries in the lower triangle need be stored.
For the constraint Hessians, a third index giving the constraint involved is required for each entry, and is stored in the integer array H_ptr. Once again, only the lower traingle is stored.
introduction to function calls#
To solve a given problem, functions from the rpd package must be called in the following order:
rpd_initialize - provide default control parameters and set up initial data structures
rpd_get_stats - read a given QPLIB file into internal data structures, and report vital statistics
(optionally, and in any order, where relevant)
rpd_get_g - get the objective gradient term \(g\)
rpd_get_f - get the objective constant term \(f\)
rpd_get_xlu - get the variable bounds \(x_l\) and \(x_u\)
rpd_get_xlu - get the constraint bounds \(c_l\) and \(c_u\)
rpd_get_h - get the objective Hessian term \(H\)
rpd_get_a - get the constrain Jacobian term \(A\)
rpd_get_h_c - get the constraint Hessian terms \(H_c\)
rpd_get_x_type - determine the type of each variable \(x\)
rpd_get_x - get initial value of the variable \(x\)
rpd_get_y - get initial value of Lagrange multipliers \(y\)
rpd_get_z - get initial value of the dual variables \(z\)
rpd_terminate - deallocate data structures
See the examples section for illustrations of use.
parametric real type T#
Below, the symbol T refers to a parametric real type that may be Float32 (single precision), Float64 (double precision) or, if supported, Float128 (quadruple precision).
callable functions#
function rpd_initialize(T, data, control, status)
Set default control values and initialize private data
Parameters:
data |
holds private internal data |
control |
is a structure containing control information (see rpd_control_type) |
status |
is a scalar variable of type Int32 that gives the exit status from the package. Possible values are (currently):
|
function rpd_get_stats(T, qplib_file, qplib_file_len, control, data, status, p_type, n, m, h_ne, a_ne, h_c_ne)
Read the data from a specified QPLIB file into internal storage, and report the type of problem encoded, along with problem-specific dimensions.
Parameters:
qplib_file |
is a one-dimensional array of type Vararg{Cchar} that specifies the name of the QPLIB file that is to be read. |
qplib_file_len |
is a scalar variable of type Int32 that gives the number of characters in the name encoded in qplib_file. |
control |
is a structure whose members provide control parameters for the remaining procedures (see rpd_control_type) |
data |
holds private internal data |
status |
is a scalar variable of type Int32 that gives the exit status from the package. Possible values are:
|
p_type |
is a one-dimensional array of size 4 and type Vararg{Cchar} that specifies the type of quadratic programming problem encoded in the QPLIB file. The first character indicates the type of objective function used. It will be one of the following:
The second character indicates the types of variables that are present. It will be one of the following:
The third character indicates the type of the (most extreme) constraint function used; other constraints may be of a lesser type. It will be one of the following:
Thus for continuous problems, we would have
For integer problems, the second character would be I rather than C, and for mixed integer problems, the second character would by M or G. |
n |
is a scalar variable of type Int32 that holds the number of variables. |
m |
is a scalar variable of type Int32 that holds the number of general constraints. |
h_ne |
is a scalar variable of type Int32 that holds the number of entries in the lower triangular part of \(H\) stored in the sparse symmetric co-ordinate storage scheme. |
a_ne |
is a scalar variable of type Int32 that holds the number of entries in \(A\) stored in the sparse co-ordinate storage scheme. |
h_c_ne |
is a scalar variable of type Int32 that holds the number of entries in the lower triangular part of \(H_c\) stored in the joint sparse co-ordinate storage scheme. |
function rpd_get_g(T, data, status, n, g)
Recover the linear term \(g\) from in objective function
Parameters:
data |
holds private internal data |
status |
is a scalar variable of type Int32 that gives the exit status from the package. Possible values are:
|
n |
is a scalar variable of type Int32 that holds the number of variables. |
g |
is a one-dimensional array of size n and type T that gives the linear term \(g\) of the objective function. The j-th component of |
function rpd_get_f(T, data, status, f)
Recover the constant term \(f\) in the objective function.
Parameters:
data |
holds private internal data |
status |
is a scalar variable of type Int32 that gives the exit status from the package. Possible values are:
|
f |
is a scalar of type T that gives the constant term \(f\) from the objective function. |
function rpd_get_xlu(T, data, status, n, x_l, x_u)
Recover the variable lower and upper bounds \(x_l\) and \(x_u\).
Parameters:
data |
holds private internal data |
status |
is a scalar variable of type Int32 that gives the exit status from the package. Possible values are:
|
n |
is a scalar variable of type Int32 that holds the number of variables. |
x_l |
is a one-dimensional array of size n and type T that gives the lower bounds \(x_l\) on the variables \(x\). The j-th component of |
x_u |
is a one-dimensional array of size n and type T that gives the upper bounds \(x_u\) on the variables \(x\). The j-th component of |
function rpd_get_clu(T, data, status, m, c_l, c_u)
Recover the constraint lower and upper bounds \(c_l\) and \(c_u\).
Parameters:
data |
holds private internal data |
status |
is a scalar variable of type Int32 that gives the exit status from the package. Possible values are:
|
m |
is a scalar variable of type Int32 that holds the number of general constraints. |
c_l |
is a one-dimensional array of size m and type T that gives the lower bounds \(c_l\) on the constraints \(A x\). The i-th component of |
c_u |
is a one-dimensional array of size m and type T that gives the upper bounds \(c_u\) on the constraints \(A x\). The i-th component of |
function rpd_get_h(T, data, status, h_ne, h_row, h_col, h_val)
Recover the Hessian term \(H\) in the objective function.
Parameters:
data |
holds private internal data |
status |
is a scalar variable of type Int32 that gives the exit status from the package. Possible values are:
|
h_ne |
is a scalar variable of type Int32 that holds the number of entries in the lower triangular part of the Hessian matrix \(H\). |
h_row |
is a one-dimensional array of size h_ne and type Int32 that gives the row indices of the lower triangular part of \(H\) in the sparse co-ordinate storage scheme. |
h_col |
is a one-dimensional array of size h_ne and type Int32 that gives the column indices of the lower triangular part of \(H\) in the sparse co-ordinate storage scheme. |
h_val |
is a one-dimensional array of size h_ne and type T that holds the values of the entries of the lower triangular part of the Hessian matrix \(H\) in the sparse co-ordinate storage scheme. |
function rpd_get_a(T, data, status, a_ne, a_row, a_col, a_val)
Recover the Jacobian term \(A\) in the constraints.
Parameters:
data |
holds private internal data |
status |
is a scalar variable of type Int32 that gives the exit status from the package. Possible values are:
|
a_ne |
is a scalar variable of type Int32 that holds the number of entries in the constraint Jacobian matrix \(A\). |
a_row |
is a one-dimensional array of size a_ne and type Int32 that gives the row indices of \(A\) in the sparse co-ordinate storage scheme. |
a_col |
is a one-dimensional array of size a_ne and type Int32 that gives the column indices of \(A\) in the sparse co-ordinate, storage scheme. |
a_val |
is a one-dimensional array of size a_ne and type T that gives the values of the entries of the constraint Jacobian matrix \(A\) in the sparse co-ordinate scheme. |
function rpd_get_h_c(T, data, status, h_c_ne, h_c_ptr, h_c_row, h_c_col, h_c_val)
Recover the Hessian terms \(H_c\) in the constraints.
Parameters:
data |
holds private internal data |
status |
is a scalar variable of type Int32 that gives the exit status from the package. Possible values are:
|
h_c_ne |
is a scalar variable of type Int32 that holds the number of entries in the lower triangular part of the Hessian matrix \(H\). |
h_c_ptr |
is a one-dimensional array of size h_c_ne and type Int32 that gives the constraint indices of the lower triangular part of \(H_c\) in the joint sparse co-ordinate storage scheme. |
h_c_row |
is a one-dimensional array of size h_c_ne and type Int32 that gives the row indices of the lower triangular part of \(H_c\) in the joint sparse co-ordinate storage scheme. |
h_c_col |
is a one-dimensional array of size h_c_ne and type Int32 that gives the column indices of the lower triangular part of \(H_c\) in the sparse co-ordinate storage scheme. |
h_c_val |
is a one-dimensional array of size h_c_ne and type T that holds the values of the entries of the lower triangular part of the Hessian matrix \(H_c\) in the sparse co-ordinate storage scheme. |
function rpd_get_x_type(T, data, status, n, x_type)
Recover the types of the variables \(x\).
Parameters:
data |
holds private internal data |
status |
is a scalar variable of type Int32 that gives the exit status from the package. Possible values are:
|
n |
is a scalar variable of type Int32 that holds the number of variables. |
x_type |
is a one-dimensional array of size n and type Int32 that specifies the type of each variable \(x\). Specifically, for j = 1, … , n, x(j) =
|
function rpd_get_x(T, data, status, n,
Recover the initial values of the variables \(x\).
Parameters:
data |
holds private internal data |
status |
is a scalar variable of type Int32 that gives the exit status from the package. Possible values are:
|
n |
is a scalar variable of type Int32 that holds the number of variables. |
x |
is a one-dimensional array of size n and type T that gives the initial values \(x\) of the optimization variables. The j-th component of |
function rpd_get_y(T, data, status, m, y)
Recover the initial values of the Lagrange multipliers \(y\).
Parameters:
data |
holds private internal data |
status |
is a scalar variable of type Int32 that gives the exit status from the package. Possible values are:
|
m |
is a scalar variable of type Int32 that holds the number of general constraints. |
y |
is a one-dimensional array of size n and type T that gives the initial values \(y\) of the Lagrange multipliers for the general constraints. The j-th component of |
function rpd_get_z(T, data, status, n, z)
Recover the initial values of the dual variables \(z\).
Parameters:
data |
holds private internal data |
status |
is a scalar variable of type Int32 that gives the exit status from the package. Possible values are:
|
n |
is a scalar variable of type Int32 that holds the number of variables. |
z |
is a one-dimensional array of size n and type T that gives the initial values \(z\) of the dual variables. The j-th component of |
function rpd_information(T, data, inform, status)
Provides output information
Parameters:
data |
holds private internal data |
inform |
is a structure containing output information (see rpd_inform_type) |
status |
is a scalar variable of type Int32 that gives the exit status from the package. Possible values are (currently):
|
function rpd_terminate(T, data, control, inform)
Deallocate all internal private storage
Parameters:
data |
holds private internal data |
control |
is a structure containing control information (see rpd_control_type) |
inform |
is a structure containing output information (see rpd_inform_type) |
available structures#
rpd_control_type structure#
struct rpd_control_type f_indexing::Bool qplib::Int32 error::Int32 out::Int32 print_level::Int32 space_critical::Bool deallocate_error_fatal::Bool
detailed documentation#
control derived type as a Julia structure
components#
Bool f_indexing
use C or Fortran sparse matrix indexing
Int32 qplib
QPLIB file input stream number.
Int32 error
error and warning diagnostics occur on stream error
Int32 out
general output occurs on stream out
Int32 print_level
the level of output required is specified by print_level
\(\leq\) 0 gives no output,
\(\geq\) 1 gives increasingly verbose (debugging) output
Bool space_critical
if .space_critical true, every effort will be made to use as little space as possible. This may result in longer computation time
Bool deallocate_error_fatal
if .deallocate_error_fatal is true, any array/pointer deallocation error will terminate execution. Otherwise, computation will continue
rpd_inform_type structure#
struct rpd_inform_type status::Int32 alloc_status::Int32 bad_alloc::NTuple{81,Cchar} io_status::Int32 line::Int32 p_type::NTuple{4,Cchar}
detailed documentation#
inform derived type as a Julia structure
components#
Int32 status
return status. Possible values are:
0
The call was successful.
-1
An allocation error occurred. A message indicating the offending array is written on unit control.error, and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively.
-2
A deallocation error occurred. A message indicating the offending array is written on unit control.error and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively.
-22
An input/outpur error occurred.
-25
The end of the input file was reached prematurely.
-29
The problem type was not recognised.
Int32 alloc_status
the status of the last attempted allocation or deallocation
NTuple{81,Cchar} bad_alloc
the name of the array for which an allocation or deallocation error occurred
Int32 io_status
status from last read attempt
Int32 line
number of last line read from i/o file
char p_type[4]
problem type
example calls#
This is an example of how to use the package to read and write a QP; the code is available in $GALAHAD/src/rpd/Julia/test_rpd.jl . A variety of supported Hessian and constraint matrix storage formats are shown.
# test_rpd.jl
# Simple code to test the Julia interface to RPD
using GALAHAD
using Test
using Printf
using Accessors
using Quadmath
function test_rpd(::Type{T}) where T
# Derived types
data = Ref{Ptr{Cvoid}}()
control = Ref{rpd_control_type}()
inform = Ref{rpd_inform_type}()
# extend the qplib_file string to include the actual position of the
# provided ALLINIT.qplib example file provided as part GALAHAD
qplib_file = joinpath(ENV["GALAHAD"], "examples", "ALLINIT.qplib")
qplib_file_len = length(qplib_file)
status = Ref{Cint}()
n = Ref{Cint}()
m = Ref{Cint}()
h_ne = Ref{Cint}()
a_ne = Ref{Cint}()
h_c_ne = Ref{Cint}()
p_type = Vector{Cchar}(undef, 4)
@printf(" Fortran sparse matrix indexing\n\n")
@printf(" basic tests of storage formats\n\n")
# Initialize RPD */
rpd_initialize(T, data, control, status)
# Set user-defined control options */
@reset control[].f_indexing = true # fortran sparse matrix indexing
# Recover vital statistics from the QPLIB file
rpd_get_stats(T, qplib_file, qplib_file_len, control, data, status, p_type, n, m, h_ne, a_ne,
h_c_ne)
@printf(" QPLIB file is of type %s\n", mapreduce(x -> Char(x), *, p_type))
@printf(" n = %i, m = %i, h_ne = %i, a_ne = %i, h_c_ne = %i\n", n[], m[], h_ne[], a_ne[],
h_c_ne[])
# Recover g
g = zeros(T, n[])
rpd_get_g(T, data, status, n[], g)
@printf(" g = %.1f %.1f %.1f %.1f %.1f\n", g[1], g[2], g[3], g[4], g[5])
# Recover f
f = Ref{T}()
rpd_get_f(T, data, status, f)
@printf(" f = %.1f\n", f[])
# Recover xlu
x_l = zeros(T, n[])
x_u = zeros(T, n[])
rpd_get_xlu(T, data, status, n[], x_l, x_u)
@printf(" x_l = %.1f %.1f %.1f %.1f %.1f\n", x_l[1], x_l[2], x_l[3], x_l[4], x_l[5])
@printf(" x_u = %.1f %.1f %.1f %.1f %.1f\n", x_u[1], x_u[2], x_u[3], x_u[4], x_u[5])
# Recover clu
c_l = zeros(T, m[])
c_u = zeros(T, m[])
rpd_get_clu(T, data, status, m[], c_l, c_u)
@printf(" c_l = %.1f %.1f\n", c_l[1], c_l[2])
@printf(" c_u = %.1f %.1f\n", c_u[1], c_u[2])
# Recover H
h_row = zeros(Cint, h_ne[])
h_col = zeros(Cint, h_ne[])
h_val = zeros(T, h_ne[])
rpd_get_h(T, data, status, h_ne[], h_row, h_col, h_val)
@printf(" h_row, h_col, h_val =\n")
for i in 1:h_ne[]
@printf(" %i %i %.1f\n", h_row[i], h_col[i], h_val[i])
end
# Recover A
a_row = zeros(Cint, a_ne[])
a_col = zeros(Cint, a_ne[])
a_val = zeros(T, a_ne[])
rpd_get_a(T, data, status, a_ne[], a_row, a_col, a_val)
@printf(" a_row, a_col, a_val =\n")
for i in 1:a_ne[]
@printf(" %i %i %.1f\n", a_row[i], a_col[i], a_val[i])
end
# Recover H_c
h_c_ptr = zeros(Cint, h_c_ne[])
h_c_row = zeros(Cint, h_c_ne[])
h_c_col = zeros(Cint, h_c_ne[])
h_c_val = zeros(T, h_c_ne[])
rpd_get_h_c(T, data, status, h_c_ne[], h_c_ptr, h_c_row, h_c_col, h_c_val)
@printf(" h_c_row, h_c_col, h_c_val =\n")
for i in 1:h_c_ne[]
@printf(" %i %i %i %.1f\n", h_c_ptr[i], h_c_row[i], h_c_col[i], h_c_val[i])
end
# Recover x_type
x_type = zeros(Cint, n[])
rpd_get_x_type(T, data, status, n[], x_type)
@printf(" x_type = %i %i %i %i %i\n", x_type[1], x_type[2], x_type[3], x_type[4],
x_type[5])
# Recover x
x = zeros(T, n[])
rpd_get_x(T, data, status, n[], x)
@printf(" x = %.1f %.1f %.1f %.1f %.1f\n", x[1], x[2], x[3], x[4], x[5])
# Recover y
y = zeros(T, m[])
rpd_get_y(T, data, status, m[], y)
@printf(" y = %.1f %.1f\n", y[1], y[2])
# Recover z
z = zeros(T, n[])
rpd_get_z(T, data, status, n[], z)
@printf(" z = %.1f %.1f %.1f %.1f %.1f\n", z[1], z[2], z[3], z[4], z[5])
# Delete internal workspace
rpd_terminate(T, data, control, inform)
return 0
end
@testset "RPD" begin
if haskey(ENV, "GALAHAD")
@test test_rpd(Float32) == 0
@test test_rpd(Float64) == 0
@test test_rpd(Float128) == 0
end
end