14.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.

14.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:

(1)\[\begin{split}\begin{array}{lll} \min/\max & g^{obj} &\\ & g_i \in \K_i, & i\in\mathcal{I},\\ \mathrm{s.t.} & G_i \in \K_i, & i\in\mathcal{I}^{PSD},\\ & x_j\in \K_j, & j\in\mathcal{J},\\ & \barX_j \in \K_j, & j\in\mathcal{J}^{PSD}. \end{array}\end{split}\]
  • 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}\]

14.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:

  1. File format.
  2. Problem structure.
  3. 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.

14.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.3. 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.3.

  • 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 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.

Table 14.3 Cones available in the CBF format
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

14.4.4 File Format Keywords

14.4.4.1 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.

14.4.4.2 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.

14.4.4.3 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.

14.4.4.4 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.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.

14.4.4.5 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.

14.4.4.6 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.

14.4.4.7 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.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

14.4.4.8 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.

14.4.4.9 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.

14.4.4.10 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.

14.4.4.11 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.

14.4.4.12 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.

14.4.4.13 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.

14.4.4.14 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.

14.4.4.15 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.

14.4.4.16 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

14.4.5 CBF Format Examples

14.4.5.1 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).

(2)\[\begin{split}\begin{array}{llll} \mbox{minimize} & 5.1 \, x_0 \\ \mbox{subject to} & 6.2 \, x_1 + 7.3 \, x_2 - 8.4 \in \{0\}\\ & x \in \Q^3,\; x_0 \in \mathbb{Z}. \end{array}\end{split}\]

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.

14.4.5.2 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.

(3)\[\begin{split}\begin{array}{llcccccccc} \mbox{minimize} & \left\langle \left[\begin{array}{ccc} 2&1&0\\1&2&1\\0&1&2 \end{array}\right], X_1 \right\rangle + x_1 & & \\ \mbox{subject to} & \left\langle \left[\begin{array}{ccc} 1&0&0\\0&1&0\\0&0&1 \end{array}\right], X_1 \right\rangle + x_1 &=& 1.0 \,, \\ & \left\langle \left[\begin{array}{ccc} 1&1&1\\1&1&1\\1&1&1 \end{array}\right], X_1 \right\rangle + x_0 + x_2 &=& 0.5 \,, \\ & x_1 \geq \sqrt{x_0^2 + x_2^2}\,, & \\ & X_1 \succeq \textbf{0} \,. & \\ \end{array}\end{split}\]

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

 # File written using this version of the Conic Benchmark Format:
 #     | Version 1.
 VER
 1

 # The sense of the objective is:
 #     | Minimize.
 OBJSENSE
 MIN

 # One PSD variable of this size:
 #     | Three times three.
 PSDVAR
 1
 3

 # Three scalar variables in this one conic domain:
 #     | Three are free.
 VAR
 3 1
 F 3

 # Five scalar constraints with affine expressions in two conic domains:
 #     | Two are fixed to zero.
 #     | Three are in conic quadratic domain.
 CON
 5 2
 L= 2
 Q 3

 # Five coordinates in F^{obj}_j coefficients:
 #     | F^{obj}[0][0,0] = 2.0
 #     | F^{obj}[0][1,0] = 1.0
 #     | and more...
 OBJFCOORD
 5
 0 0 0 2.0
 0 1 0 1.0
 0 1 1 2.0
 0 2 1 1.0
 0 2 2 2.0

 # One coordinate in a^{obj}_j coefficients:
 #     | a^{obj}[1] = 1.0
 OBJACOORD
 1
 1 1.0

 # Nine coordinates in F_ij coefficients:
 #     | F[0,0][0,0] = 1.0
 #     | F[0,0][1,1] = 1.0
 #     | and more...
 FCOORD
 9
 0 0 0 0 1.0
 0 0 1 1 1.0
 0 0 2 2 1.0
 1 0 0 0 1.0
 1 0 1 0 1.0
 1 0 2 0 1.0
 1 0 1 1 1.0
 1 0 2 1 1.0
 1 0 2 2 1.0

 # Six coordinates in a_ij coefficients:
 #     | a[0,1] = 1.0
 #     | a[1,0] = 1.0
 #     | and more...
 ACOORD
 6
 0 1 1.0
 1 0 1.0
 1 2 1.0
 2 1 1.0
 3 0 1.0
 4 2 1.0

 # Two coordinates in b_i coefficients:
 #     | b[0] = -1.0
 #     | b[1] = -0.5
 BCOORD
 2
 0 -1.0
 1 -0.5

14.4.5.3 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.

(4)\[\begin{split}\begin{array}{llcccccccc} \mbox{minimize} & \left\langle \left[\begin{array}{cc} 1&0\\0&1 \end{array}\right], X_1 \right\rangle + x_1 + x_2 + 1 & & \\ \mbox{subject to} & \left\langle \left[\begin{array}{cc} 0&1\\1&0 \end{array}\right], X_1 \right\rangle - x_1 - x_2 &\geq& 0.0 \,,\\ & x_1 \left[\begin{array}{cc} 0&1\\1&3 \end{array}\right] + x_2 \left[\begin{array}{cc} 3&1\\1&0 \end{array}\right] - \left[\begin{array}{cc} 1&0\\0&1 \end{array}\right] &\succeq& \textbf{0} \,, \\ & X_1 \succeq \textbf{0} \,. & \\ \end{array}\end{split}\]

Its formulation in the CBF format is written in what follows

 # File written using this version of the Conic Benchmark Format:
 #     | Version 1.
 VER
 1

 # The sense of the objective is:
 #     | Minimize.
 OBJSENSE
 MIN

 # One PSD variable of this size:
 #     | Two times two.
 PSDVAR
 1
 2

 # Two scalar variables in this one conic domain:
 #     | Two are free.
 VAR
 2 1
 F 2

 # One PSD constraint of this size:
 #     | Two times two.
 PSDCON
 1
 2

 # One scalar constraint with an affine expression in this one conic domain:
 #     | One is greater than or equal to zero.
 CON
 1 1
 L+ 1

 # Two coordinates in F^{obj}_j coefficients:
 #     | F^{obj}[0][0,0] = 1.0
 #     | F^{obj}[0][1,1] = 1.0
 OBJFCOORD
 2
 0 0 0 1.0
 0 1 1 1.0

 # Two coordinates in a^{obj}_j coefficients:
 #     | a^{obj}[0] = 1.0
 #     | a^{obj}[1] = 1.0
 OBJACOORD
 2
 0 1.0
 1 1.0

 # One coordinate in b^{obj} coefficient:
 #     | b^{obj} = 1.0
 OBJBCOORD
 1.0

 # One coordinate in F_ij coefficients:
 #     | F[0,0][1,0] = 1.0
 FCOORD
 1
 0 0 1 0 1.0

 # Two coordinates in a_ij coefficients:
 #     | a[0,0] = -1.0
 #     | a[0,1] = -1.0
 ACOORD
 2
 0 0 -1.0
 0 1 -1.0

 # Four coordinates in H_ij coefficients:
 #     | H[0,0][1,0] = 1.0
 #     | H[0,0][1,1] = 3.0
 #     | and more...
 HCOORD
 4
 0 0 1 0 1.0
 0 0 1 1 3.0
 0 1 0 0 3.0
 0 1 1 0 1.0

 # Two coordinates in D_i coefficients:
 #     | D[0][0,0] = -1.0
 #     | D[0][1,1] = -1.0
 DCOORD
 2
 0 0 0 -1.0
 0 1 1 -1.0

14.4.5.4 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.

(5)\[\begin{split}\begin{array}{llcccccccc} \mbox{maximize}_k & g^{obj}_k & & \\ \mbox{subject to} & 50 \, x_0 + 31 &\leq& 250 \,, \\ & 3 \, x_0 - 2 x_1 &\geq& -4 \,, \\ & x \in \R^2_+, & \end{array}\end{split}\]

given,

  1. \(g^{obj}_0 = x_0 + 0.64 x_1\).
  2. \(g^{obj}_1 = 1.11 x_0 + 0.76 x_1\).
  3. \(g^{obj}_2 = 1.11 x_0 + 0.85 x_1\).

Its formulation in the CBF format is reported in Listing 14.5.

Listing 14.5 Problem (5) in CBF format.
 # File written using this version of the Conic Benchmark Format:
 #     | Version 1.
 VER
 1

 # The sense of the objective is:
 #     | Maximize.
 OBJSENSE
 MAX

 # Two scalar variables in this one conic domain:
 #     | Two are nonnegative.
 VAR
 2 1
 L+ 2

 # Two scalar constraints with affine expressions in these two conic domains:
 #     | One is in the nonpositive domain.
 #     | One is in the nonnegative domain.
 CON
 2 2
 L- 1
 L+ 1

 # Two coordinates in a^{obj}_j coefficients:
 #     | a^{obj}[0] = 1.0
 #     | a^{obj}[1] = 0.64
 OBJACOORD
 2
 0 1.0
 1 0.64

 # Four coordinates in a_ij coefficients:
 #     | a[0,0] = 50.0
 #     | a[1,0] = 3.0
 #     | and more...
 ACOORD
 4
 0 0 50.0
 1 0 3.0
 0 1 31.0
 1 1 -2.0

 # Two coordinates in b_i coefficients:
 #     | b[0] = -250.0
 #     | b[1] = 4.0
 BCOORD
 2
 0 -250.0
 1 4.0

 # New problem instance defined in terms of changes.
 CHANGE

 # Two coordinate changes in a^{obj}_j coefficients. Now it is:
 #     | a^{obj}[0] = 1.11
 #     | a^{obj}[1] = 0.76
 OBJACOORD
 2
 0 1.11
 1 0.76

 # New problem instance defined in terms of changes.
 CHANGE

 # One coordinate change in a^{obj}_j coefficients. Now it is:
 #     | a^{obj}[0] = 1.11
 #     | a^{obj}[1] = 0.85
 OBJACOORD
 1
 1 0.85