15.4 The CBF Format¶
This document constitutes the technical reference manual of the Conic Benchmark Format with file extension: .cbf
or .CBF
. It unifies linear, secondorder cone (also known as conic quadratic) and semidefinite optimization with mixedinteger variables. The format has been designed with benchmark libraries in mind, and therefore focuses on compact and easily parsable representations. The problem structure is separated from the problem data, and the format moreover facilitates benchmarking of hotstart capability through sequences of changes.
15.4.1 How Instances Are Specified¶
This section defines the spectrum of conic optimization problems that can be formulated in terms of the keywords of the CBF format.
In the CBF format, conic optimization problems are considered in the following form:
Variables are either scalar variables, \(x_j \mbox{ for } j \in \mathcal{J}\), or variables, \(\barX_j \mbox{ for } j \in \mathcal{J}^{PSD}\). Scalar variables can also be declared as integer.
Constraints are affine expressions of the variables, either scalarvalued \(g_i \mbox{ for } i \in \mathcal{I}\), or matrixvalued \(G_i \mbox{ for } i \in \mathcal{I}^{PSD}\)
\[ \begin{align}\begin{aligned}g_i = \sum_{j \in \mathcal{J}^{PSD}} \langle F_{ij}, X_j \rangle + \sum_{j \in \mathcal{J}} a_{ij} x_j + b_i,\\G_i = \sum_{j \in \mathcal{J}} x_j H_{ij} + D_i.\end{aligned}\end{align} \]The objective function is a scalarvalued affine expression of the variables, either to be minimized or maximized. We refer to this expression as \(g^{obj}\)
\[g^{obj} = \sum_{j \in \mathcal{J}^{PSD}} \langle F^{obj}_j, X_j \rangle + \sum_{j \in \mathcal{J}} a^{obj}_j x_j + b^{obj}.\]
CBF format can represent the following cones \(\K\):
Free domain  A cone in the linear family defined by
\[\{ x \in \R^n \}, \mbox{ for } n \geq 1.\]Positive orthant  A cone in the linear family defined by
\[\{ x \in \R^n\;\; x_j \geq 0 \mbox{ for } j = 1,\ldots,n \}, \mbox{ for } n \geq 1.\]Negative orthant  A cone in the linear family defined by
\[\{ x \in \R^n\;\; x_j \leq 0 \mbox{ for } j = 1,\ldots,n \}, \mbox{ for } n \geq 1.\]Fixpoint zero  A cone in the linear family defined by
\[\{ x \in \R^n\;\; x_j = 0 \mbox{ for } j = 1,\ldots,n \}, \mbox{ for } n \geq 1.\]Quadratic cone  A cone in the secondorder cone family defined by
\[\begin{split}\left\lbrace \left(\begin{array}{c}p\\x\end{array}\right) \in \R \times \R^{n1},\; p^2 \geq x^T x,\; p \geq 0 \right\rbrace, \mbox{ for } n \geq 2.\end{split}\]Rotated quadratic cone  A cone in the secondorder cone family defined by
\[\begin{split}\left\lbrace \left(\begin{array}{c}p\\q\\x\end{array}\right) \in \R \times \R \times \R^{n2},\; 2pq \geq x^T x,\; p \geq 0,\; q \geq 0 \right\rbrace, \mbox{ for } n \geq 3.\end{split}\]
15.4.2 The Structure of CBF Files¶
This section defines how information is written in the CBF format, without being specific about the type of information being communicated.
All information items belong to exactly one of the three groups of information. These information groups, and the order they must appear in, are:
File format.
Problem structure.
Problem data.
The first group, file format, provides information on how to interpret the file. The second group, problem structure, provides the information needed to deduce the type and size of the problem instance. Finally, the third group, problem data, specifies the coefficients and constants of the problem instance.
Information items
The format is composed as a list of information items. The first line of an information item is the KEYWORD
, revealing the type of information provided. The second line  of some keywords only  is the HEADER
, typically revealing the size of information that follows. The remaining lines are the BODY
holding the actual information to be specified.
KEYWORD BODY KEYWORD HEADER BODY
The KEYWORD
determines how each line in the HEADER
and BODY
is structured. Moreover, the number of lines in the BODY
follows either from the KEYWORD
, the HEADER
, or from another information item required to precede it.
Embedded hotstartsequences
A sequence of problem instances, based on the same problem structure, is within a single file. This is facilitated via the CHANGE
within the problem data information group, as a separator between the information items of each instance. The information items following a CHANGE
keyword are appending to, or changing (e.g., setting coefficients back to their default value of zero), the problem data of the preceding instance.
The sequence is intended for benchmarking of hotstart capability, where the solvers can reuse their internal state and solution (subject to the achieved accuracy) as warmpoint for the succeeding instance. Whenever this feature is unsupported or undesired, the keyword CHANGE
should be interpreted as the end of file.
File encoding and line width restrictions
The format is based on the USASCII printable character set with two extensions as listed below. Note, by definition, that none of these extensions can be misinterpreted as printable USASCII characters:
A line feed marks the end of a line, carriage returns are ignored.
Commentlines may contain unicode characters in UTF8 encoding.
The line width is restricted to 512 bytes, with 3 bytes reserved for the potential carriage return, line feed and nullterminator.
Integers and floating point numbers must follow the ISO C decimal string representation in the standard C locale. The format does not impose restrictions on the magnitude of, or number of significant digits in numeric data, but the use of 64bit integers and 64bit IEEE 754 floating point numbers should be sufficient to avoid loss of precision.
Commentline and whitespace rules
The format allows singleline comments respecting the following rule:
Lines having first byte equal to ’
#
’ (USASCII 35) are comments, and should be ignored. Comments are only allowed between information items.
Given that a line is not a commentline, whitespace characters should be handled according to the following rules:
Leading and trailing whitespace characters should be ignored.
The seperator between multiple pieces of information on one line, is either one or more whitespace characters.
Lines containing only whitespace characters are empty, and should be ignored. Empty lines are only allowed between information items.
15.4.3 Problem Specification¶
The problem structure
The problem structure defines the objective sense, whether it is minimization and maximization. It also defines the index sets, \(\mathcal{J}\), \(\mathcal{J}^{PSD}\), \(\mathcal{I}\) and \(\mathcal{I}^{PSD}\), which are all numbered from zero, \(\{ 0, 1, \ldots\}\), and empty until explicitly constructed.
Scalar variables are constructed in vectors restricted to a conic domain, such as \((x_0, x_1) \in \real_+^2\), \((x_2, x_3, x_4) \in \Q^3\), etc. In terms of the Cartesian product, this generalizes to
\[x \in \K^{n_1}_1 \times \K^{n_2}_2 \times \cdots \times \K^{n_k}_k\]which in the CBF format becomes:
VAR n k K1 n1 K2 n2 ... Kk nk
where \(\sum_i n_i= n\) is the total number of scalar variables. The list of supported cones is found in Table 15.3. Integrality of scalar variables can be specified afterwards.
PSD variables are constructed onebyone. That is, \(X_j \succeq \textbf{0}^{n_j \times n_j}\) for \(j \in \mathcal{J}^{PSD}\), constructs a matrixvalued variable of size \(n_j \times n_j\) restricted to be symmetric positive semidefinite. In the CBF format, this list of constructions becomes:
PSDVAR N n1 n2 ... nN
where \(N\) is the total number of PSD variables.
Scalar constraints are constructed in vectors restricted to a conic domain, such as \((g_0, g_1) \in \real_+^2\), \((g_2, g_3, g_4) \in \Q^3\), etc. In terms of the Cartesian product, this generalizes to
\[g \in \K^{m_1}_1 \times \K^{m_2}_2 \times \cdots \times \K^{m_k}_k\]which in the CBF format becomes:
CON m k K1 m1 K2 m2 .. Kk mk
where \(\sum_i m_i = m\) is the total number of scalar constraints. The list of supported cones is found in Table 15.3.
PSD constraints are constructed onebyone. That is, \(G_i \succeq \textbf{0}^{m_i \times m_i}\) for \(i \in \mathcal{I}^{PSD}\), constructs a matrixvalued affine expressions of size \(m_i \times m_i\) restricted to be symmetric positive semidefinite. In the CBF format, this list of constructions becomes
PSDCON M m1 m2 .. mM
where \(M\) is the total number of PSD constraints.
With the objective sense, variables (with integer indications) and constraints, the definitions of the many affine expressions follow in problem data.
Problem data
The problem data defines the coefficients and constants of the affine expressions of the problem instance. These are considered zero until explicitly defined, implying that instances with no keywords from this information group are, in fact, valid. Duplicating or conflicting information is a failure to comply with the standard. Consequently, two coefficients written to the same position in a matrix (or to transposed positions in a symmetric matrix) is an error.
The affine expressions of the objective, \(g^{obj}\), of the scalar constraints, \(g_i\), and of the PSD constraints, \(G_i\), are defined separately. The following notation uses the standard trace inner product for matrices, \(\langle X, Y \rangle = \sum_{i,j} X_{ij} Y_{ij}\).
The affine expression of the objective is defined as
\[g^{obj} = \sum_{j \in \mathcal{J}^{PSD}} \langle F^{obj}_j, X_j \rangle + \sum_{j \in \mathcal{J}} a^{obj}_j x_j + b^{obj},\]in terms of the symmetric matrices, \(F^{obj}_j\), and scalars, \(a^{obj}_j\) and \(b^{obj}\).
The affine expressions of the scalar constraints are defined, for \(i \in \mathcal{I}\), as
\[g_i = \sum_{j \in \mathcal{J}^{PSD}} \langle F_{ij}, X_j \rangle + \sum_{j \in \mathcal{J}} a_{ij} x_j + b_i,\]in terms of the symmetric matrices, \(F_{ij}\), and scalars, \(a_{ij}\) and \(b_i\).
The affine expressions of the PSD constraints are defined, for \(i \in \mathcal{I}^{PSD}\), as
\[G_i = \sum_{j \in \mathcal{J}} x_j H_{ij} + D_i,\]in terms of the symmetric matrices, \(H_{ij}\) and \(D_i\).
List of cones
The format uses an explicit syntax for symmetric positive semidefinite cones as shown above. For scalar variables and constraints, constructed in vectors, the supported conic domains and their minimum sizes are given as follows.
Name 
CBF keyword 
Cone family 

Free domain 

linear 
Positive orthant 

linear 
Negative orthant 

linear 
Fixpoint zero 

linear 
Quadratic cone 

secondorder 
Rotated quadratic cone 

secondorder 
15.4.4 File Format Keywords¶
VER¶
Description: The version of the Conic Benchmark Format used to write the file.
HEADER
: None
BODY
: One line formatted as:
INT
This is the version number.
Must appear exactly once in a file, as the first keyword.
OBJSENSE¶
Description: Define the objective sense.
HEADER
: None
BODY
: One line formatted as:
STR
having MIN
indicates minimize, and MAX
indicates maximize. Capital letters are required.
Must appear exactly once in a file.
PSDVAR¶
Description: Construct the PSD variables.
HEADER
: One line formatted as:
INT
This is the number of PSD variables in the problem.
BODY
: A list of lines formatted as:
INT
This indicates the number of rows (equal to the number of columns) in the matrixvalued PSD variable. The number of lines should match the number stated in the header.
VAR¶
Description: Construct the scalar variables.
HEADER
: One line formatted as:
INT INT
This is the number of scalar variables, followed by the number of conic domains they are restricted to.
BODY
: A list of lines formatted as:
STR INT
This indicates the cone name (see Table 15.3), and the number of scalar variables restricted to this cone. These numbers should add up to the number of scalar variables stated first in the header. The number of lines should match the second number stated in the header.
INT¶
Description: Declare integer requirements on a selected subset of scalar variables.
HEADER
: one line formatted as:
INT
This is the number of integer scalar variables in the problem.
BODY
: a list of lines formatted as:
INT
This indicates the scalar variable index \(j \in \mathcal{J}\). The number of lines should match the number stated in the header.
Can only be used after the keyword VAR
.
PSDCON¶
Description: Construct the PSD constraints.
HEADER
: One line formatted as:
INT
This is the number of PSD constraints in the problem.
BODY
: A list of lines formatted as:
INT
This indicates the number of rows (equal to the number of columns) in the matrixvalued affine expression of the PSD constraint. The number of lines should match the number stated in the header.
Can only be used after these keywords: PSDVAR
, VAR
.
CON¶
Description: Construct the scalar constraints.
HEADER
: One line formatted as:
INT INT
This is the number of scalar constraints, followed by the number of conic domains they restrict to.
BODY
: A list of lines formatted as:
STR INT
This indicates the cone name (see Table 15.3), and the number of affine expressions restricted to this cone. These numbers should add up to the number of scalar constraints stated first in the header. The number of lines should match the second number stated in the header.
Can only be used after these keywords: PSDVAR
, VAR
OBJFCOORD¶
Description: Input sparse coordinates (quadruplets) to define the symmetric matrices \(F^{obj}_j\), as used in the objective.
HEADER
: One line formatted as:
INT
This is the number of coordinates to be specified.
BODY
: A list of lines formatted as:
INT INT INT REAL
This indicates the PSD variable index \(j \in \mathcal{J}^{PSD}\), the row index, the column index and the coefficient value. The number of lines should match the number stated in the header.
OBJACOORD¶
Description: Input sparse coordinates (pairs) to define the scalars, \(a^{obj}_j\), as used in the objective.
HEADER
: One line formatted as:
INT
This is the number of coordinates to be specified.
BODY
: A list of lines formatted as:
INT REAL
This indicates the scalar variable index \(j \in \mathcal{J}\) and the coefficient value. The number of lines should match the number stated in the header.
OBJBCOORD¶
Description: Input the scalar, \(b^{obj}\), as used in the objective.
HEADER
: None.
BODY
: One line formatted as:
REAL
This indicates the coefficient value.
FCOORD¶
Description: Input sparse coordinates (quintuplets) to define the symmetric matrices, \(F_{ij}\), as used in the scalar constraints.
HEADER
: One line formatted as:
INT
This is the number of coordinates to be specified.
BODY
: A list of lines formatted as:
INT INT INT INT REAL
This indicates the scalar constraint index \(i \in \mathcal{I}\), the PSD variable index \(j \in \mathcal{J}^{PSD}\), the row index, the column index and the coefficient value. The number of lines should match the number stated in the header.
ACOORD¶
Description: Input sparse coordinates (triplets) to define the scalars, \(a_{ij}\), as used in the scalar constraints.
HEADER
: One line formatted as:
INT
This is the number of coordinates to be specified.
BODY
: A list of lines formatted as:
INT INT REAL
This indicates the scalar constraint index \(i \in \mathcal{I}\), the scalar variable index \(j \in \mathcal{J}\) and the coefficient value. The number of lines should match the number stated in the header.
BCOORD¶
Description: Input sparse coordinates (pairs) to define the scalars, \(b_i\), as used in the scalar constraints.
HEADER
: One line formatted as:
INT
This is the number of coordinates to be specified.
BODY
: A list of lines formatted as:
INT REAL
This indicates the scalar constraint index \(i \in \mathcal{I}\) and the coefficient value. The number of lines should match the number stated in the header.
HCOORD¶
Description: Input sparse coordinates (quintuplets) to define the symmetric matrices, \(H_{ij}\), as used in the PSD constraints.
HEADER
: One line formatted as:
INT
This is the number of coordinates to be specified.
BODY
: A list of lines formatted as
INT INT INT INT REAL
This indicates the PSD constraint index \(i \in \mathcal{I}^{PSD}\), the scalar variable index \(j \in \mathcal{J}\), the row index, the column index and the coefficient value. The number of lines should match the number stated in the header.
DCOORD¶
Description: Input sparse coordinates (quadruplets) to define the symmetric matrices, \(D_i\), as used in the PSD constraints.
HEADER
: One line formatted as
INT
This is the number of coordinates to be specified.
BODY
: A list of lines formatted as:
INT INT INT REAL
This indicates the PSD constraint index \(i \in \mathcal{I}^{PSD}\), the row index, the column index and the coefficient value. The number of lines should match the number stated in the header.
CHANGE¶
Start of a new instance specification based on changes to the previous. Can be interpreted as the end of file when the hotstartsequence is unsupported or undesired.
BODY
: None
Header
: None
15.4.5 CBF Format Examples¶
Minimal Working Example¶
The conic optimization problem (15.11) , has three variables in a quadratic cone  first one is integer  and an affine expression in domain \(0\) (equality constraint).
Its formulation in the Conic Benchmark Format begins with the version of the CBF format used, to safeguard against later revisions.
VER
1
Next follows the problem structure, consisting of the objective sense, the number and domain of variables, the indices of integer variables, and the number and domain of scalarvalued affine expressions (i.e., the equality constraint).
OBJSENSE
MIN
VAR
3 1
Q 3
INT
1
0
CON
1 1
L= 1
Finally follows the problem data, consisting of the coefficients of the objective, the coefficients of the constraints, and the constant terms of the constraints. All data is specified on a sparse coordinate form.
OBJACOORD
1
0 5.1
ACOORD
2
0 1 6.2
0 2 7.3
BCOORD
1
0 8.4
This concludes the example.
Mixing Linear, Secondorder and Semidefinite Cones¶
The conic optimization problem (15.12), has a semidefinite cone, a quadratic cone over unordered subindices, and two equality constraints.
The equality constraints are easily rewritten to the conic form, \((g_0 , g_1) \in \{0\}^2\), by moving constants such that the righthandside becomes zero. The quadratic cone does not fit under the VAR
keyword in this variable permutation. Instead, it takes a scalar constraint \((g_2, g_3, g_4) = (x_1, x_0, x_2) \in \Q^3\), with scalar variables constructed as \((x_0, x_1, x_2) \in \real^3\). Its formulation in the CBF format is reported in the following list
Mixing Semidefinite Variables and Linear Matrix Inequalities¶
The standard forms in semidefinite optimization are usually based either on semidefinite variables or linear matrix inequalities. In the CBF format, both forms are supported and can even be mixed as shown in.
Its formulation in the CBF format is written in what follows
Optimization Over a Sequence of Objectives¶
The linear optimization problem (15.14), is defined for a sequence of objectives such that hotstarting from one to the next might be advantages.
given,
\(g^{obj}_0 = x_0 + 0.64 x_1\).
\(g^{obj}_1 = 1.11 x_0 + 0.76 x_1\).
\(g^{obj}_2 = 1.11 x_0 + 0.85 x_1\).
Its formulation in the CBF format is reported in Listing 15.5.