# 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, second-order cone (also known as conic quadratic) and semidefinite optimization with mixed-integer 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 scalar-valued \(g_i \mbox{ for } i \in \mathcal{I}\), or matrix-valued \(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 scalar-valued 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 second-order cone family defined by\[\begin{split}\left\lbrace \left(\begin{array}{c}p\\x\end{array}\right) \in \R \times \R^{n-1},\; 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 second-order cone family defined by\[\begin{split}\left\lbrace \left(\begin{array}{c}p\\q\\x\end{array}\right) \in \R \times \R \times \R^{n-2},\; 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 hotstart-sequences

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 US-ASCII printable character set with two extensions as listed below. Note, by definition, that none of these extensions can be misinterpreted as printable US-ASCII characters:

- A line feed marks the end of a line, carriage returns are ignored.
- Comment-lines may contain unicode characters in UTF-8 encoding.

The line width is restricted to 512 bytes, with 3 bytes reserved for the potential carriage return, line feed and null-terminator.

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 64-bit integers and 64-bit IEEE 754 floating point numbers should be sufficient to avoid loss of precision.

Comment-line and whitespace rules

The format allows single-line comments respecting the following rule:

- Lines having first byte equal to ’
`#`

’ (US-ASCII 35) are comments, and should be ignored. Comments are only allowed between information items.

Given that a line is not a comment-line, 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 14. Integrality of scalar variables can be specified afterwards.

**PSD variables**are constructed one-by-one. That is, \(X_j \succeq \textbf{0}^{n_j \times n_j}\) for \(j \in \mathcal{J}^{PSD}\), constructs a matrix-valued 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 14.

**PSD constraints**are constructed one-by-one. That is, \(G_i \succeq \textbf{0}^{m_i \times m_i}\) for \(i \in \mathcal{I}^{PSD}\), constructs a matrix-valued affine expressions of size \(m_i \times m_i\) restricted to be symmetric positive semidefinite. In the CBF format, this list of constructions becomesPSDCON 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 | `F` |
linear |

Positive orthant | `L+` |
linear |

Negative orthant | `L-` |
linear |

Fixpoint zero | `L=` |
linear |

Quadratic cone | `Q` |
second-order |

Rotated quadratic cone | `QR` |
second-order |

## 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 matrix-valued 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 14), 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 matrix-valued 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 14), 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 hotstart-sequence is unsupported or undesired.

`BODY`

: None

`Header`

: None

## 15.4.5 CBF Format Examples¶

### Minimal Working Example¶

The conic optimization problem (2) , 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 scalar-valued 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, Second-order and Semidefinite Cones¶

The conic optimization problem (3), 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 right-hand-side 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 (5), 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 38.