QPLIB

A Library of Quadratic Programming Instances

Home // browse instances // view statistics // read documentation // download QPLIB archive

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

Further, let

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|\)




Website © 2017-2023 by Zuse Institute Berlin and GAMS. All rights reserved. Imprint. QPLIB is licensed under CC-BY 4.0.