# QPLIB

## A Library of Quadratic Programming Instances

Home // browse instances // view statistics // read documentation // download QPLIB archive [ 694M ]

### Documentation

QPLIB consists of quadratic optimization problems of the form \begin{align*} \textrm{sense} \;\; & \frac{1}{2} x^\top Q^0 x + b^0 x + q^0 \\ \textrm{such that}\;\; & c^i_l \leq \frac{1}{2} x^\top Q^i x + b^i x \leq c^i_u & i \in \mathcal{M} \\ % & l_j \leq x_j \leq u_j & j \in \mathcal{N} \\ % & x_j \in \mathbb{Z} & j \in \mathcal{Z} \end{align*} where

• $$\mathcal{N} = \{ 1, \ldots, n \}$$ is the set of (indices) of variables,
• $$\mathcal{M} = \{ 1, \ldots, m \}$$ is the set of (indices) of constraints,
• $$x = [x_j]_{j = 1}^n \in \mathbb{R}^n$$ is a finite vector of variables,
• $$\textrm{sense}\in\{\min,\max\}$$ is the objective sense,
• $$Q^i\in\mathbb{R}^{n\times n}$$ for $$i \in \{ 0 \} \cup \mathcal{M}$$ are lower-left triangle(i) ($$Q^i_{row,col}=0$$ for $$row < col$$) matrices holding the coefficients of quadratic terms,
• $$b^i\in\mathbb{R}^n$$ for $$i \in \{0\}\cup\mathcal{M}$$ are vectors holding the coefficients of linear terms,
• $$q^0\in\mathbb{R}$$ is the constant term in the objective,
• $$c_l^i\in\mathbb{R}\cup\{-\infty\}, c_u^i\in\mathbb{R}\cup\{+\infty\}$$, $$c_l^i\leq c_u^i$$, for $$i \in \mathcal{M}$$ are the left- and right-hand side, respectively, of each constraint,
• $$l_j\in\mathbb{R}\cup\{-\infty\}, u_j\in\mathbb{R}\cup\{+\infty\}$$, $$l_j\leq u_j$$, for $$j \in \mathcal{N}$$ are the lower and upper bounds, respectively, on each variable $$x_j$$,
• $$\mathcal{Z} \subseteq \mathcal{N}$$ are the variables restricted to only attain integer values.

Further, let

• $$\mathcal{B} := \{j\in\mathcal{Z} \,:\, \{l_j,u_j\}=\{0,1\}\}$$ be the set of binary variables,
• $$\mathcal{N}^Q := \{j\in\mathcal{N} \,:\, \exists i\in\mathcal{M}\cup\{0\}, k\in\mathcal{N} : Q^i_{j,k}+Q^i_{k,j} \neq 0\}$$ be the set of nonlinear variables (that is, variables appearing in at least one quadratic term),
• $$\mathcal{L} := \{i\in\mathcal\{M\} \,:\, Q^i = 0\}$$ be the set of linear constraints,
• $$\mathcal{Q} := \mathcal{M} \setminus \mathcal{L}$$ be the set of (truely) quadratic constraints, and
• $$P := \{P_k\}_{k\in\mathcal{P}}$$, $$\mathcal{P} := \{1,\ldots,p\}$$, be the finest partitioning of $$\mathcal{N}^Q$$ (i.e., $$P_k\subseteq\mathcal{N}^Q, P_k \cap P_k' = \emptyset, k,k'\in\mathcal{P}, k\neq k'$$), such that $$\forall i\in\mathcal{Q}\cup\{0\}\; \forall j,k\in\mathcal{N}^Q, Q_{j,k}^i \neq 0\; \exists p\in\mathcal{P} : j,k\in P_p$$. That is, $$P$$ describes the block structure of the Hessian of the Lagrangian.

Additionally, one solution point $$x^* \in \mathbb{R}^n$$ might be available for each instance.

For each instance, we collect the following information:

Identifier Meaning Definition
PROBTYPE Problem Type OVC, where O is
 – L, if $$Q^0=0$$, else – D, if $$Q^0\succeq 0, \textrm{sense}=\min, Q^0 = {Q^0}^\top$$, else – D, if $$Q^0\preceq 0, \textrm{sense}=\max, Q^0 = {Q^0}^\top$$, else – C, if $$Q^0\succeq 0, \textrm{sense}=\min$$, else – C, if $$Q^0\preceq 0, \textrm{sense}=\max$$, else – Q;

V is
 – C, if $$\mathcal{Z} = \emptyset$$, else – B, if $$\mathcal{N} = \mathcal{B}$$, else – M, if $$\mathcal{Z} \setminus \mathcal{B} = \emptyset$$, else – I, if $$\mathcal{N} = \mathcal{Z}$$, else – G;

C is
 – N, if $$\mathcal{M} = \emptyset$$, $$l_j=-\infty, u_j=+\infty, j\in\mathcal{N}\setminus\mathcal{B}$$, else – B, if $$\mathcal{M} = \emptyset$$, else – L, if $$\mathcal{Q} = \emptyset$$, else – D, if $$\forall i\in\mathcal{Q}: Q^i\succeq 0 \textrm{ if } c_l^i\neq-\infty$$ and $$Q^i\preceq 0 \textrm{ if } c_u^i\neq+\infty$$ and $$Q^i={Q^i}^\top$$, else – C, if $$\forall i\in\mathcal{Q}: Q^i\succeq 0 \textrm{ if } c_l^i\neq-\infty$$ and $$Q^i\preceq 0 \textrm{ if } c_u^i\neq+\infty$$, else – Q.
SOLOBJVALUE Solution point objective value $$\frac{1}{2} (x^*)^\top Q^0 x^* + b^0 x^* + q^0$$
SOLINFEASIBILITY Solution point infeasibility The maximum of
• $$\max\{c_l^i - \frac{1}{2}(x^*)^\top Q^i x^* - b^i x^*, \frac{1}{2}(x^*)^\top Q^i x^* + b^i x^* - c_u^i\}, i\in\mathcal{M}$$,
• $$\max\{l_j - x_j^*, x_j^* - u_j\}, j\in\mathcal{N}$$,
• $$|x_j^* - \text{round} (x_j^*)|, j\in\mathcal{Z}$$, and
• 0.
DONOR Donor of instance Name of person who submitted this instance to QPLIB.
NVARS Number of Variables $$|\mathcal{N}|$$
NCONS Number of Constraints $$|\mathcal{M}|$$
NBINVARS Number of Binary Variables $$|\mathcal{B}|$$
NINTVARS Number of (General) Integer Variables $$|\mathcal{Z} \setminus \mathcal{B}|$$
NNLVARS Number of Nonlinear Variables $$|\mathcal{N}^Q|$$
NNLBINVARS Number of Nonlinear Binary Variables $$|\mathcal{N}^Q\cap\mathcal{B}|$$
NNLINTVARS Number of Nonlinear Integer Variables $$|\mathcal{N}^Q\cap\mathcal{Z}|$$
NBOUNDEDVARS Number of Bounded Non-Binary Variables $$|\{j\in \mathcal{N}\setminus\mathcal{B} : l_j \neq -\infty, u_j \neq \infty\}|$$
NSINGLEBOUNDEDVARS Number of Variables with only one bound $$|\{j\in \mathcal{N} : \textrm{either}\; l_j = -\infty \;\textrm{or}\; u_j = \infty\}|$$
OBJSENSE Objective sense $$\textrm{sense}$$
OBJTYPE Objective type linear if $$Q^0=0$$
quadratic if $$Q^0\neq 0$$
NLINCONS Number of linear constraints $$|\mathcal{L}|$$
NQUADCONS Number of quadratic constraints $$|\mathcal{Q}|$$
NDIAGQUADCONS Number of diagonal quadratic constraints $$|\{i\in\mathcal{Q} : \forall j,k\in\mathcal{N},j\neq k: Q^i_{j,k} = 0\}|$$
NOBJNZ Number of nonzeros in objective $$|\{j\in\mathcal{N} \,:\, b^0_j\neq 0 \;\textrm{or}\; \exists k\in\mathcal{N} : Q^0_{j,k}+Q^0_{k,j} \neq 0\}|$$
NOBJNLNZ Number of nonlinear nonzeros in objective $$|\{j\in\mathcal{N} \,:\, \exists k\in\mathcal{N} : Q^0_{j,k}+Q^0_{k,j} \neq 0\}|$$
NOBJQUADNZ Number of quadratic terms in objective $$|\{(j,k)\in\mathcal{N}\times\mathcal{N} \,:\, Q^0_{j,k}\neq 0\}|$$
NOBJQUADDIAGNZ Number of square terms in objective $$|\{j\in\mathcal{N} \,:\, Q^0_{j,j}\neq 0\}|$$
OBJQUADDENSITY Density of $$Q^0$$ $$\frac{2\times\textrm{NOBJQUADNZ}-\textrm{NOBJQUADDIAGNZ}}{\textrm{NOBJNLNZ}^2}$$, if $$Q^0\neq 0$$, otherwise 0
NJACOBIANNZ Number of nonzeros in Jacobian $$\sum_{i\in\mathcal{M}} |\{j\in\mathcal{N} \,:\, b^i_j\neq 0 \;\textrm{or}\; \exists k\in\mathcal{N} : Q^i_{j,k}+Q^i_{k,j} \neq 0\}|$$
NJACOBIANNLNZ Number of nonlinear nonzeros in Jacobian $$\sum_{i\in\mathcal{M}} |\{j\in\mathcal{N} \,:\, \exists k\in\mathcal{N} : Q^i_{j,k}+Q^i_{k,j} \neq 0\}|$$
NZ Number of nonzeros in Objective Gradient and Jacobian $$\textrm{NOBJNZ} + \textrm{NJACOBIANNZ}$$
NLNZ Number of nonlinear nonzeros in Objective Gradient and Jacobian $$\textrm{NOBJNLNZ} + \textrm{NJACOBIANNLNZ}$$
NLAGHESSIANNZ Number of nonzeros in Hessian of Lagrangian $$|\{(j,k)\in\mathcal{N}\times\mathcal{N} \,:\, \exists i\in\mathcal{M}\cup\{0\} : Q^i_{j,k}\neq 0\}|$$
NLAGHESSIANDIAGNZ Number of nonzeros in diagonal of Hessian of Lagrangian $$|\{j\in\mathcal{N} \,:\, \exists i\in\mathcal{M}\cup\{0\} : Q^i_{j,j}\neq 0\}|$$
OBJCURVATURE Convexity/Concavity of objective function linear, if $$Q^0=0$$, else
convex, if $$Q^0\succeq 0$$, else
concave, if $$Q^0\preceq 0$$, else
indefinite.
NOBJQUADNEGEV Number of negative eigenvalues in $$Q^0$$ $$|\{\lambda \leq -10^{-12} \,:\, \exists v\neq 0 : Q^0v = \lambda v\}|$$
NOBJQUADPOSEV Number of positive eigenvalues in $$Q^0$$ $$|\{\lambda \geq 10^{-12} \,:\, \exists v\neq 0 : Q^0v = \lambda v\}|$$
OBJQUADPROBLEVFRAC Fraction of problematic eigenvalues of $$Q^0$$ $$\frac{\textrm{NOBJQUADNEGEV}}{|\mathcal{N}|}$$, if $$\textrm{sense}=\min$$;
$$\frac{\textrm{NOBJQUADPOSEV}}{|\mathcal{N}|}$$, if $$\textrm{sense}=\max$$
CONSCURVATURE Convexity/Concavity of constraints
 linear, if $$\mathcal{L}=\mathcal{M}$$, else convex, if $$\forall i\in\mathcal{Q}, c_u^i\neq+\infty: Q^i\succeq 0$$ and $$\forall i\in\mathcal{Q}, c_l^i\neq-\infty: Q^i\preceq 0$$, else concave, if $$\forall i\in\mathcal{Q}, c_u^i\neq+\infty: Q^i\preceq 0$$ and $$\forall i\in\mathcal{Q}, c_l^i\neq-\infty: Q^i\succeq 0$$, else indefinite.
CONVEX Convexity of continuous relaxation
 True, if $$\textrm{CONSCURVATURE}$$ = convex and $$\textrm{OBJCURVATURE}$$ = convex, and $$\textrm{sense}=\min$$, else True, if $$\textrm{CONSCURVATURE}$$ = convex and $$\textrm{OBJCURVATURE}$$ = concave, and $$\textrm{sense}=\max$$, else False.
NCONVEXNLCONS Number of convex nonlinear constraints $$|\{i\in\mathcal{Q} \;:\; Q^i\succeq 0 \textrm{ if } c_u^i\neq+\infty \textrm{ and } Q^i\preceq 0 \textrm{ if } c_l^i\neq-\infty\}|$$
NCONCAVENLCONS Number of concave nonlinear constraints $$|\{i\in\mathcal{Q} \;:\; Q^i\preceq 0 \textrm{ if } c_u^i\neq+\infty \textrm{ and } Q^i\succeq 0 \textrm{ if } c_l^i\neq-\infty\}|$$
NINDEFINITENLCONS Number of indefinite nonlinear constraints $$|\{i\in\mathcal{Q} \;:\; Q^i\not\succeq 0 \textrm{ and } Q^i\not\preceq 0 \}|$$
NLAGHESSIANBLOCKS Number of blocks in Hessian of Lagrangian $$|\mathcal{P}|$$
LAGHESSIANMINBLOCKSIZE Minimal blocksize in Hessian of Lagrangian $$\min\{|P_k| \;:\; k\in\mathcal{P}\}$$
LAGHESSIANMAXBLOCKSIZE Maximal blocksize in Hessian of Lagrangian $$\max\{|P_k| \;:\; k\in\mathcal{P}\}$$
LAGHESSIANAVGBLOCKSIZE Average blocksize in Hessian of Lagrangian $$\frac{1}{|\mathcal{P}|}\sum_{k\in\mathcal{P}} |P_k|$$