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) or Float64 (double precision). Calable functions as described are with T as Float64, but variants (with the additional suffix _s, e.g., rpd_initialize_s) are available with T as Float32.

callable functions#

    function rpd_initialize(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):

0
The initialization was successful.

    function rpd_get_stats(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: 0 The statistics have been recovered successfully. -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.
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: L a linear objective function. D a convex quadratic objective function whose Hessian is a diagonal matrix. C a convex quadratic objective function. Q a quadratic objective function whose Hessian may be indefinite. The second character indicates the types of variables that are present. It will be one of the following: C all the variables are continuous. B all the variables are binary (0-1). M the variables are a mix of continuous and binary. I all the variables are integer. G the variables are a mix of continuous, binary and integer. 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: N there are no constraints. B some of the variables lie between lower and upper bounds (box constraint). L the constraint functions are linear. D the constraint functions are convex quadratics with diagonal Hessians. C the constraint functions are convex quadratics. Q the constraint functions are quadratics whose Hessians may be indefinite. Thus for continuous problems, we would have LCL a linear program. LCC or LCQ a linear program with quadratic constraints. CCB or QCB a bound-constrained quadratic program. CCL or QCL a quadratic program. CCC or CCQ or QCC or QCQ a quadratic program with quadratic constraints. 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(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: 0 The statistics have been recovered successfully. -93 The QPLIB file did not contain the required data.
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 `g`, j = 1, … , n, contains $g_j$.

    function rpd_get_f(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:

0
The statistics have been recovered successfully.
-93
The QPLIB file did not contain the required data.

is a scalar of type T that gives the constant term $f$ from the objective function.

    function rpd_get_xlu(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: 0 The statistics have been recovered successfully. -93 The QPLIB file did not contain the required data.
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_l`, j = 1, … , n, contains $(x_l)_j$.
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 `x_u`, j = 1, … , n, contains $(x_u)_j$.

    function rpd_get_clu(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: 0 The statistics have been recovered successfully. -93 The QPLIB file did not contain the required data.
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_l`, i = 1, … , m, contains $(c_l)_i$.
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 `c_u`, i = 1, … , m, contains $(c_u)_i$.

    function rpd_get_h(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: 0 The statistics have been recovered successfully. -93 The QPLIB file did not contain the required data.
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(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: 0 The statistics have been recovered successfully. -93 The QPLIB file did not contain the required data.
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(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: 0 The statistics have been recovered successfully. -93 The QPLIB file did not contain the required data.
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(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: 0 The statistics have been recovered successfully. -93 The QPLIB file did not contain the required data.
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) = 0 if variable $x_j$ is continuous, 1 if variable $x_j$ is integer, and 2 if variable $x_j$ is binary (0,1)

    function rpd_get_x(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: 0 The statistics have been recovered successfully. -93 The QPLIB file did not contain the required data.
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 `x`, j = 1, … , n, contains $x_j$.

    function rpd_get_y(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: 0 The statistics have been recovered successfully. -93 The QPLIB file did not contain the required data.
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 `y`, j = 1, … , m, contains $y_j$.

    function rpd_get_z(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: 0 The statistics have been recovered successfully. -93 The QPLIB file did not contain the required data.
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 `z`, j = 1, … , n, contains $z_j$.

    function rpd_information(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):

0
The values were recorded successfully

    function rpd_terminate(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

Index

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

function test_rpd()
  # 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(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(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(Float64, n[])
  rpd_get_g(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{Float64}()
  rpd_get_f(data, status, f)
  @printf(" f = %.1f\n", f[])

  # Recover xlu
  x_l = zeros(Float64, n[])
  x_u = zeros(Float64, n[])
  rpd_get_xlu(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(Float64, m[])
  c_u = zeros(Float64, m[])
  rpd_get_clu(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(Float64, h_ne[])
  rpd_get_h(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(Float64, a_ne[])
  rpd_get_a(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(Float64, h_c_ne[])
  rpd_get_h_c(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(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(Float64, n[])
  rpd_get_x(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(Float64, m[])
  rpd_get_y(data, status, m[], y)
  @printf(" y = %.1f %.1f\n", y[1], y[2])

  # Recover z
  z = zeros(Float64, n[])
  rpd_get_z(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(data, control, inform)
  return 0
end

@testset "RPD" begin
  if haskey(ENV, "GALAHAD")
    @test test_rpd() == 0
  end
end