Complexity indices for the multidimensional knapsack problem

Abstract

In this article, the concept of conditioning in integer programming is extended to the concept of a complexity index. A complexity index is a measure through which the execution time of an exact algorithm can be predicted. We consider the multidimensional knapsack problem with instances taken from the OR-library and MIPLIB. The complexity indices we developed correspond to the eigenvalues of a Dikin matrix placed in the center of a polyhedron defined by the constraints of the problem relaxed from its binary variable formulation. The lower and higher eigenvalues, as well as their ratio, which we have defined as the slenderness, are used as complexity indices. The experiments performed show a good linear correlation between these indices and a low execution time of the Branch and Bound algorithm using the standard version of CPLEX^® 12.2. The correlation coefficient obtained ranges between 39 and 60% for the various data regressions, which proves a medium to strong correlation.

1 Introduction

The multidimensional knapsack problem (MKP) is known to be one of the most difficult problems in the knapsack problems class. Kellerer et al. (2004) developed a recent and complete review of this problem. The MKP applies to different applied areas such as production planning, transportation or communications networks (Mansini and Speranza 2002). The MKP specifies a set of elements that are placed in a container to maximize its value, considering a set of restrictions that limit their placement. Although the formulation of the problem is simple, complex real-world situations can be represented. The MKP has been used extensively to solve classical operations management problems such as stock reduction, budgeting, project selection and military communications problems (Song et al. 2008). In industrial applications, the MKP solution has a direct impact on production efficiency. The problem becomes harder when it is necessary to define a production schedule for the assembly of different models of the same product in a production line. Bolat (2003) modeled such a situation as a MKP and efficiently found the optimal solution for small problem instances. Cherbaka and Meller (2008) considered an MKP to distribute the production of parts at different plants of a company. However, these are applications in which only low-dimensional problems can be solved.

The multidimensional knapsack problem can be formulated as follows. Let $N = \left\{ {1, \ldots ,n} \right\}$ sets of items, each with an associate profit $p_{j} \ge 0,$ where $j = 1, \ldots ,n$, and the set of resources $M = \left\{ {1, \ldots ,m} \right\}$ with availability $c_{i } \ge 0,$ where $i = 1, \ldots ,m.$ Each item j requires an amount $w_{ij} \ge 0$, of each resource i. The amount $w_{ij}$ can be 0 for any i, j, while $\sum\nolimits_{i = 1}^{n} {w_{ij} } \ge 1$ for every $j = 1, \ldots ,n.$ Throughout the paper, coefficients m and n will be referred to in terms of “size” as the number of variables and number of constraints, respectively. Additionally, $w_{ij} < c_{i} ;\;i = 1, \ldots ,m; \;j = 1, \ldots ,n,\;{\text{and}}\; \sum\nolimits_{j = 1}^{n} {w_{ij} } \ge c_{i} ;\;i = 1, \ldots ,m$. It is assumed that all $p_{i}$, $w_{ij}$ and $c_{i}$ values are integers. The MKP can be defined as a search problem of an A subset of items whose sum of benefits is maximized without exceeding the available resources.

$$ \hbox{max} \mathop \sum \limits_{j = 1}^{n} p_{j} x_{j} $$

(1.1)

$$ \mathop \sum \limits_{j = 1}^{n} w_{ij} x_{j} \le c_{j} , \quad i \in M $$

(1.2)

$$ x_{j} \in \left\{ {0,1} \right\} $$

(1.3)

Despite the NP-hardness of the MKP, several attempts to obtain an exact solution for every instance of the problem have appeared in the literature. James and Nakagawa (2005) developed a method that solves repeatedly arranged subproblems of the MKP with exact solutions at the expense of intensive memory use. Boussier et al. (2010) combined an arrangement method with the branch and cut method, finding new optimal values of the public library OR-Library instances for the MKP with sizes of 500 variables and 10 constraints; see Beasley (1990). Additionally, Mansini and Speranza (2012) reported an exact algorithm based on the exploration of subproblems constructed with subsets of variables. From the studied cases, it was determined that as soon as the number of dimensions increases, the exact algorithms are unable to provide an optimal solution for instances of moderate size in a reasonable amount of time. For example, one of the versions of CPLEX^® 6.5.2 could not solve problems with 100 elements and 5 dimensions due to the memory requirements of the search tree (Martello et al. 2000).

Several heuristic methods have been proposed for the MKP, with the aim of dealing with larger instances than those that can be solved by exact methods with shorter computational times. Senju and Toyoda (1968) proposed a heuristic that starts with an initial solution, $x_{j} ,\;\forall j$, and successively sets the variables at zero, according to an efficiency equation, until a feasible solution is found. This heuristic has also been combined with an approach based on Lagrangian multipliers (Magazine and Oguz 1984). This method has also been improved by including more than one multiplier value at each step, readjusting these values at the end of the algorithm and adding a partial arrangement, yielding good results when compared with the previous approach (Volgenant and Zwiers 2007). Other ideas that work on the core set or on the dynamic fixing of variables have led to various ad hoc heuristic algorithms for the problem (Wilbaut et al. 2009; Angelelli et al. 2010; Grandón and Derpich 2011; Lalami et al., 2012). A pioneering public library of this problem and several others is the OR-library introduced by Chu and Beasley (1998). There are some articles that have studied measures of the computational complexity of the algorithms used in mathematical programming; however, it has not been possible to find an analytical theory that allows for estimating the running time of an inaccuracy in terms of CPU time or the number of nodes used. Ko et al. (1986) and Reyck and Herroelen (1996) considered empirical and theoretical approaches to obtain running time indices; however, a complete theory of such phenomena is still lacking. A complexity index is a measure that can predict the execution time of an exact algorithm for a given problem such as the MKP.

In this manuscript, we propose a measure of complexity for integer programming that is based on the eigenvalues of an inner ellipsoid to the polyhedron given by linear programming relaxation. For this approach, a Dikin ellipsoid is used, which maintains the geometric shape of the polyhedron. The objective is to prove that the eigenvalues of the ellipsoid, in particular the maximum and minimum eigenvalues, are related to the execution time of the B&B algorithm for solving the multidimensional knapsack problem.

2 Materials and methods

2.1 Complexity index

A complexity index of the instance I of problem C using algorithm A is a real number r by which the execution time of the algorithm can be effectively predicted and the results are statistically significant (Cvetkovic 2012). The efficiency of the complexity index of an algorithm can be estimated by measuring the linear correlation between the value of the index and the execution time of the algorithm for the instances considered. The linear correlation coefficient is given by the following expression:

$$ \rho = \frac{{\mathop \sum \nolimits_{i = 1}^{n} \left( {t_{i} - \bar{t}} \right)\left( {x_{i} - \bar{x}} \right)}}{{ \sigma_{t}^{2} \sigma_{x}^{2} }} $$

(2.1)

The values of $x_{i}$ and $t_{i }$ correspond to the various complexity indices that are tested in this manuscript. For instance, $t_{i }$ could be the execution time of the algorithm and ${\text{x}}_{\text{i}}$ could correspond to a geometric measure of the polyhedron, such as the maximum eigenvalue of a certain ellipsoid. In this manuscript, linear regressions between proposed complexity indices will be performed, and measures of the natural difficulty of these problems, such as the processing times and the number of nodes executed by the B&B algorithm, will be evaluated.

2.2 Conditioning in integer programming

Integer programming algorithms may have some sort of exponential running time in the worst case. However, similar instances may have different running times when solved by different computational algorithms. This fact shows that there is an intrinsic difficulty, which can be measured, and such measurements could serve as predictors for future cases. The notion of conditioning in integer programming developed by Vera and Derpich (2006) and Freund and Vera (2003) is based on the relationship between this intrinsic difficulty and the shape of the polyhedron formed by the constraints of the associated linear problem as well as the spatial orientation of the polyhedron. To characterize the shape of the polyhedron, a Dikin ellipsoid will be used, since it has the particular feature of tending to follow the shape of the polyhedron, thus rounding the vertices. Therefore, the matrix associated with the interior ellipsoid can be used to estimate the shape of the polyhedron. For this purpose, the eigenvalues of this matrix will be used, which relate to the semi-axes of the ellipsoid. In the following section, the mathematical form of the Dikin ellipsoid and two theorems that relate the eigenvalues of a Dikin ellipsoid matrix to the respective polyhedron are presented.

2.3 Proposed complexity indices

Dikin ellipsoids will be used according to the following definition. Let $P = \left\{ {x:\sum\nolimits_{j = 1}^{n} {a_{iji} } x \le b_{i} ,i = 1, \ldots ,m} \right\}$ be a polyhedron associated with the general integer problem, and let E and E’ be a pair of concentric ellipsoids defined by the form: $E = \left\{ {x \in {\mathbb{R}}^{n} : \left( {x - x_{0} } \right)^{T} Q\left( {x - x_{0} } \right) \le 1} \right\}$ and $E^{\prime } = \left\{ {x \in {\mathbb{R}}^{n} : \left( {x - x_{0} } \right)^{T} Q\left( {x - x_{0} } \right) \le \gamma^{ } } \right\}$, where $x_{0}$ is the center of the ellipsoid, such that $E \subset P \subset E^{\prime } \;{\text{and}}\;Q = \nabla^{2} \rho \left( {x_{0} } \right) = A^{T} D^{ - 2} \left( {x_{0} } \right)A$, with $D\left( {x_{0} } \right) = diag\left( {b_{i} - A_{i}^{{}} x_{0} } \right)$. Assuming a value of $\gamma = m + 1$ ensures that the ellipsoid $E^{\prime \prime }$ is external and includes the polyhedron.

Where $A_{i }$ is the row $i$ of the matrix $A, \;{\text{with}}\; i = 1, \ldots ,m$.

Several possible centers for the Dikin ellipsoid are tested, including the center of maximum volume. The center of maximum volume is defined by the following expression:

$$ Max\left\{ {r:A_{i} x_{0} + rA_{i} \le b_{i} ,\;\forall i, \;r \ge 0} \right\} . $$

The 2n center corresponds to the following approach.

Solve $2{\text{n}}$ problems $x_{max}^{j} = \hbox{max} \left\{ {x_{j} : A_{i} x_{j} \le b_{i} ,\,i = 1, \ldots ,m} \right\}$ and $x_{min}^{j} = \hbox{min} \left\{ {x_{j} :A_{i} x_{j} \le b_{i} ,\;i = 1, \ldots ,m} \right\}$, $\forall j = 1, \ldots ,n$. Then, $x_{2n} = \frac{{\left( {x_{max} - x_{min} } \right)}}{n}$

Where $A_{i}$ is the row $i$ of the matrix A, with $i = 1, \ldots ,m$.

The expression of the analytical center corresponds to the following equation:

$$ Minimize\quad \rho = - \mathop \sum \limits_{i = 1}^{m} \log \left( {b_{i} - A_{i} x_{0} } \right) $$

(2.2)

From the experiments developed with the test problems taken from the OR-library, the analytical center showed the best results, while in the experiments developed with the problems of the MIPLIB public library, both the analytical center and the center of maximum volume showed the best results.

We first analyze the eigenvalues of a matrix of the form $A^{T} H^{ - 2} A$, where $A \in {\mathbb{R}}^{m \times n}$ and $H \in {\mathbb{R}}^{m \times m}$ is a diagonal matrix with positive elements $h_{1} , \ldots ,h_{m}$. Let $\lambda_{1} , \ldots , \lambda_{n}$ be the eigenvalues that provide information about the intrinsic difficulty of this type of problem. Let us start with a result that will provide information about the eigenvalues of $A^{T} H^{ - 2} A$ in terms of the elements of the matrix.

Theorem 1

(Vera and Derpich 2006) Let P be the following linear programming problem: P = $\mathop {\hbox{max} }\limits_{ } \left\{ {c^{T} x:Ax \le b} \right\}$, in which $c \in {\mathbb{R}}^{n} ,A \in {\mathbb{R}}^{m \times n}$ and $b \in {\mathbb{R}}^{m}$. Let $h_{i} \left( {x_{0} } \right) = b_{i} - A_{i} x, \;\forall i = 1 \ldots m$ be the slacks corresponding to the constraints of the problem P for the feasible point $x_{0 }$, where $a_{ij}$ are the coefficients of the matrix A. Let $\lambda_{1} , \ldots , \lambda_{n}$ be the eigenvalues of $A^{T} H\left( {x_{0} } \right)^{ - 2} A$ and $\uplambda_{ \hbox{min} } ,\;\uplambda_{ \hbox{max} }$ the minimum and maximum eigenvalues of $A^{T} H\left( {x_{0} } \right)^{ - 2} A$, respectively. Let $\beta_{\hbox{min} }$ and $\beta_{max}$ be the minimum and maximum values of $A^{T} A$, respectively. Let $h_{max} = \mathop {\hbox{max} }\nolimits_{i} \left\{ {h_{i} } \right\}$ and $h_{min} = \mathop {\hbox{min} }\nolimits_{i} \left\{ {h_{i} } \right\}$. Then, it holds that

$$ \lambda_{min} \ge \frac{{\beta_{min} }}{{h_{max}^{2} }} $$

(2.3)

and

$$ \lambda_{max} \le \frac{{\beta_{max} }}{{h_{min}^{2} }} $$

(2.4)

Proof

We begin decomposing the term $A^{T} H\left( {x_{0} } \right)^{ - 2} A$ by its components:

$$ A^{T} H\left( {x_{0} } \right)^{ - 2} A = \mathop \sum \limits_{j = 1}^{m} h_{j}^{ - 2} \mathop \sum \limits_{i = 1}^{n} a_{ij} a_{ji} $$

(2.5)

Next, we introduce $h_{min}^{ - 2}$, and we have the next expression:

$$ A^{T} H\left( {x_{0} } \right)^{ - 2} A = h_{min}^{ - 2} \mathop \sum \limits_{j = 1}^{m} \mathop \sum \limits_{i = 1}^{n} a_{ij} a_{ji} - \mathop \sum \limits_{j = 1}^{m} \left( {h_{min}^{ - 2} - h_{j}^{ - 2} } \right) \mathop \sum \limits_{i = 1}^{n} a_{ij} a_{ji} $$

(2.6)

Then, we define F1 and F2 in the next form:

$$ F_{1} = h_{min}^{ - 2} \mathop \sum \limits_{j = 1}^{m} \mathop \sum \limits_{i = 1}^{n} a_{ij} a_{ji} \quad {\text{and}}\quad F_{2} = - \mathop \sum \limits_{j = 1}^{m} \left( {h_{min}^{ - 2} - h_{j}^{ - 2} } \right) \mathop \sum \limits_{i = 1}^{n} a_{ij} a_{ji} $$

Therefore, $A^{T} H\left( {x_{0} } \right)^{ - 2} A = F_{1} + F_{2}$

Since $F_{2}$ is a negative semidefinite matrix, it holds that

$$ \lambda \le \lambda \left( {F_{1} } \right) $$

Therefore,

$$ \lambda_{max} \le \lambda_{max} \left( {h_{min}^{ - 2} \mathop \sum \limits_{j = 1}^{m} \mathop \sum \limits_{i = 1}^{n} a_{ij} a_{ji} } \right) $$

and finally,

$$ \lambda_{max} \le \frac{{\lambda_{max} \left( { A^{T} A } \right)}}{{h_{min}^{2} }} = \frac{{\beta_{max} }}{{h_{min}^{2} }} $$

We have executed the first part of the proof corresponding to expression (2.4).

Following with the proof, we again use expression (2.3):

$$ A^{T} H\left( {x_{0} } \right)^{ - 2} A = \mathop \sum \limits_{j = 1}^{m} h_{j}^{ - 2} \mathop \sum \limits_{i = 1}^{n} a_{ij} a_{ji} $$

Again, we decompose the term $A^{T} H\left( {x_{0} } \right)^{ - 2} A$ by its components

$$ A^{T} H\left( {x_{0} } \right)^{ - 2} A = h_{max}^{ - 2} \mathop \sum \limits_{j = 1}^{m} \mathop \sum \limits_{i = 1}^{n} a_{ij} a_{ji} - \mathop \sum \limits_{j = 1}^{m} \left( {h_{max}^{ - 2} - h_{j}^{ - 2} } \right) \mathop \sum \limits_{i = 1}^{n} a_{ij} a_{ji} $$

Next, we define G1 and G2 in the next form:

$$ G_{1} = h_{max}^{ - 2} \mathop \sum \limits_{j = 1}^{m} \mathop \sum \limits_{i = 1}^{n} a_{ij} a_{ji} $$

and

$$ G_{2} = - \mathop \sum \limits_{j = 1}^{m} \left( {h_{max}^{ - 2} - h_{j}^{ - 2} } \right) \mathop \sum \limits_{i = 1}^{n} a_{ij} a_{ji} $$

Therefore, $A^{T} H\left( {x_{0} } \right)^{ - 2} A = G_{1} + G_{2}$

Note that $G_{2}$ is a positive semidefinite matrix; then, it holds that

$$ \lambda_{min} = \lambda_{min} \left( {G_{1} + G_{2} } \right)_{ } $$

Therefore,

$$ \lambda_{min} \ge \lambda_{min} \left( {G_{1} } \right)_{ } = h_{max}^{ - 2} \beta_{min} $$

and finally

$$ \lambda_{min} \ge h_{max}^{ - 2} \beta_{min} . $$

We have executed the second part of the proof corresponding to expression (2.3), and with this, the proof is concluded.$\square$

These expressions show a relationship between the eigenvalues of matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$ and the maximum and minimum slacks. For this reason, it is reasonable to believe that the maximum and minimum eigenvalues are related to the shape of the polyhedron. In addition, other associated measures, such as the slenderness, defined by the ratio between $\lambda_{max}$ and $\lambda_{min}$, are related to the polyhedron.

Theorem 2

(From Vera and Derpich 2006) The number of sub-problems solved by the B&B algorithm can be bounded by

$$ 2^{n} \left( {m + 1} \right)^{n} n^{{{\raise0.7ex\hbox{$n$} \!\mathord{\left/ {\vphantom {n 2}}\right.\kern-0pt} \!\lower0.7ex\hbox{$2$}}}} \left( {\frac{1}{{\sqrt {\lambda_{min} } }}} \right)^{n} $$

(2.7)

Proof

Suppose we construct a pair of Ellipsoids, with center ${\text{x}}_{0}$, of the form

$$ E = \left\{ {x \in {\Re }^{n} :\left( {x - x_{0} } \right)^{T} Q\left( {x - x_{0} } \right) \le 1} \right\} $$

and

$$ E^{\prime } = \left\{ {x \in {\Re }^{n} :\left( {x - x_{0} } \right)^{T} Q\left( {x - x_{0} } \right) \le \gamma^{2} } \right\} $$

such that

$$ E \subset \left\{ {x:Ax \le b} \right\} \subset E^{\prime} $$

where Q is a positive-definite matrix.

Let $w\left( {\mu ,Ax \le b} \right)$ be the width of the polyhedron $Ax \le b$ according to a vector $\upmu$. This is calculated as follows:

$$ w\left( {\mu ,Ax \le b} \right) = \mathop {\hbox{max} }\limits_{ } \left\{ {\mu^{T} x:Ax \le b} \right\} - \mathop {\hbox{min} }\limits_{ } \left\{ {\mu^{T} x:Ax \le b} \right\} $$

where $\mu \in {\Re }^{n}\;\;{\text{and }}\mu \ne 0$

It is also known that the width of the ellipsoid ${\text{E}}$ according to vector $\upmu$ is bounded by the expression $\sqrt {\mu^{T} Q^{ - 1} \mu }$. Therefore, taking a value from $\gamma^{2} = m + 1$ in order to ensure an expansion of ${\text{E}}$ that contains the polyhedron $Ax \le b$ and considering a vector $\upmu$ such that the diameter of the ellipsoid E’ is given by twice the width $w\left( {u,Ax \le b} \right)$, it holds that $w\left( {\mu ,Ax \le b} \right) \le 2\left( {m + 1} \right)\sqrt {\mu^{T} Q^{ - 1} \mu }$ is the maximum width of a polyhedron according to vector $\mu$. In (Vera and Derpich 2006) the following expression was tested:

$$ \sqrt {\mu^{T} Q^{ - 1} \mu } \le \sqrt n \left( { \frac{{h_{max} }}{\rho \left( d \right)}} \right) $$

(2.8)

where

$$ \rho \left( d \right) = inf \left\{ {\left\| {\Delta d} \right\|:P\left( {d + \Delta d} \right) \in {\mathcal{F}}^{C} } \right\} $$

which can be interpreted as the distance to ill conditioning and

$$ \bar{\sigma } = \mathop {\hbox{max} }\limits_{x \in Ax \le b} b - Ax_{\infty } $$

which can be interpreted as the maximum distance from the point $x$ to the constraints defining the polyhedron. In our case,

$$ \bar{\sigma } = h_{max} $$

(2.9)

From Vera and Derpich (2006), $\rho \left( d \right)$ can be bounded as $\rho \left( d \right)^{2} \le \beta_{min}$

From Theorem 1, it holds that

$$ \beta_{min} \le h_{max}^{2} \lambda_{min} $$

Then, we have

$$ \rho \left( d \right)^{ } \le \sqrt {\beta_{min} } = _{ } h_{max}^{ } \sqrt {\lambda_{min} }_{ } $$

(2.10)

Finally, replacing (2.11) and (2.12) in (2.10), we have

$$ \sqrt {\mu^{T} Q^{ - 1} \mu } \le \sqrt {\frac{n}{{\lambda_{min} }}} $$

(2.11)

Using the expansion of $E$ to contain the polyhedron $Ax \le b$ and considering a vector $\mu$ such that the diameter of the ellipsoid $E^{\prime }$ is given by twice the width $w\left( {u,Ax \le b} \right)$, we have

$$ w\left( {u,Ax \le b} \right) \le 2\left( {m + 1} \right)\sqrt {\mu^{T} Q^{ - 1} \mu } \le 2\left( {m + 1} \right)\sqrt {\frac{n}{{\lambda_{min} }}} $$

(2.12)

The number of sub-problems solved by the B&B algorithm can bounded by the width in every dimension of the problem. The dimension of the problem is n; therefore, the number of sub-problems solved by the B&B algorithm can bounded by

$$ \left[ {w\left( {u,Ax \le b} \right)} \right]^{n} $$

and this may be bounded by $2^{n} \left( {m + 1} \right)^{n} n^{{{\raise0.7ex\hbox{$n$} \!\mathord{\left/ {\vphantom {n 2}}\right.\kern-0pt} \!\lower0.7ex\hbox{$2$}}}} \left( {\frac{1}{{\sqrt {\lambda_{min} } }}} \right)^{n}$. Therefore, the proof is concluded.□

This result shows a certain correlation between the eigenvalues of a Dikin ellipsoid matrix associated with the polyhedron and the number of iterations of the B&B algorithm.

3 Description of experiments

According to the theorems and their respective proofs presented in the previous section, the maximum and minimum eigenvalues of a certain matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$, are related to an inner Dikin ellipsoid and thus are related to the geometric shape of the polyhedron $\left\{ {x:Ax \le b} \right\}$. Additionally, the ratio K between the two eigenvalues has also been included, which we have defined as the slenderness. These measures are summarized below:

• Minimum eigenvalue of the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$ associated with an inner Dikin ellipsoid to the polyhedron $Ax \le b$.

• Maximum eigenvalue of the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$ associated with an inner Dikin ellipsoid to the polyhedron $Ax \le b$.

• Slenderness, defined as the ratio between the maximum and minimum eigenvalue, called K.

These variables were used as explanatory variables in regression models to evaluate their correlation. Two public libraries were used to create test instances of the multidimensional knapsack problem. In all cases, the analytical center was used as the center of the ellipsoid. To obtain the analytical center, an implementation of the Newton method was used, using Python 2.7 and CPLEX^® 12.2.

3.1 Regression models estimated

The following regression models were estimated, and their respective regressors and explanatory variables were as follows:

• Regressor: minimum eigenvalue of the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$ associated with the Daikin ellipsoid versus the execution time of the B&B algorithm using CPLEX^® 12.2 (response variable).

• Regressor: maximum eigenvalue of the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$ associated with the Dikin ellipsoid versus the execution time of the B&B algorithm using CPLEX^® 12.2 (response variable).

• Regressor: slenderness (ratio between the maximum and minimum eigenvalue) of the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$ associated with the Dikin ellipsoid versus the execution time of the B&B algorithm using CPLEX^® 12.2 (response variable).

• Regressors: maximum and minimum eigenvalues of the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$ associated with the Dikin ellipsoid versus the execution time of the B&B algorithm using CPLEX^® 12.2 (response variable).

• Regressor: minimum eigenvalue of the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$ associated with the Dikin ellipsoid versus the number of nodes visited by the B&B algorithm using CPLEX^® 12.2 (response variable).

• Regressor: maximum eigenvalue of the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$ associated with the Dikin ellipsoid versus the number of nodes visited by the B&B algorithm using CPLEX^® 12.2 (response variable).

• Regressor: slenderness (ratio between the maximum and minimum eigenvalue) of the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$, related to the Dikin ellipsoid versus the number of nodes visited by the B&B algorithm using CPLEX^® 12.2 (response variable).

• Regressors: maximum and minimum eigenvalues of the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$ associated with the Dikin ellipsoid versus the number of nodes visited of the B&B algorithm using CPLEX^® 12.2 (response variable).

3.2 Test instances

To test the relationship between the proposed measures of complexity and the response variables (number of nodes and execution time), test instances of the MKP were used from the OR-library and MIPLIB public libraries.

Instances taken from the OR-Library are in batches of 30 problems each, consisting of 100 × 5 (variables × constraints), 100 × 5, 250 × 10, 100 × 10, 100 × 30 and 500 × 5. These instances are characterized by being constructed using a complexity index $\tau = \tau_{i} , \forall i$ (the same coefficient for all constraints) which is defined by the following equation:

$$ \tau_{ } = \frac{{\mathop \sum \nolimits_{j = 1}^{n} w_{ij} }}{{p_{i} }}, \forall i $$

(3.1)

In the selected instances, this index takes three cases $: \tau = 0.25$ for the first 10 values, $\tau = 0.5$ for the second 10 values and $\uptau = 0.75$ for the last 10 values. The first 10 values are the most complex to solve because they have fewer values $x_{j} = 1$; on average, only 2.5 values of $x_{j}$ correspond to 1, and the rest correspond to 0. For the second case, 5 values correspond to 1, and the rest correspond to 0. For the third case, 7.5 values correspond to 1, and the rest correspond to 0. Table 1 presents the selected MKP instances of the MIPLIB library. These problems are of greater computational complexity than those of the OR-library. In Table 2, we present the instances solved of the OR-library.

Table 1 Benchmarking instances taken from the MIPLIB 2010 library

Table 2 Benchmarking instances taken from the OR-Library

4 Computational results

The results are presented in the same order that the proposed regression models were explained.

4.1 Model 1: $\varvec{T} = \varvec{ \beta }_{0} + \varvec{ \beta }_{1} \varvec{ \lambda }_{{\varvec{min}}}$

$\lambda_{min}$: minimum eigenvalue of the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$ associated with the Dikin ellipsoid.

$T$: execution time of the B&B algorithm using CPLEX^® 12.2 (response variable) in seconds.

4.1.1 Results for the OR-Library instances

The ${\text{F}}$-statistic of the ANOVA in Table 3 shows that the experiment performed is statistically significant for an $\alpha$ of 5% for almost all cases. In addition, the best correlation coefficient values $\rho$ are 0.445; 0.383 and 0.439. These values show that in most of the cases, there is a correlation between the $\lambda_{min}$ and the execution time of the B&B algorithm.

Table 3 Regression model between the minimum eigenvalue and the CPU time (Y)

4.1.2 Results for the MIPLIB instances

It can be observed in Table 4 that the greater the number of threads, the greater the correlation between the variables. The F-test was not applied since the sample size is low and therefore gives non-significant values.

Table 4 Estimated models for minimum eigenvalue versus CPU time with 1, 4 and 12 CPLEX^® 12.2 threads

4.2 Model 2: $\varvec{T} =\varvec{\beta}_{0} + \varvec{ \beta }_{1}\varvec{\lambda}_{{\varvec{max}}}$

$\lambda_{max}$: maximum eigenvalue of the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$ associated with the Dikin ellipsoid.

$T$: execution time of the B&B algorithm using CPLEX^® 12.2 (response variable), in seconds.

4.2.1 Results for the OR-Library instances

The ${\text{F}}$-statistic of the ANOVA in Table 5 shows that the experiment performed is statistically significant for an $\alpha$ of 5% for almost all cases. In addition, the best correlation coefficient values $\uprho$ are 0.445; 0.400 and 0.622. These values show that in most cases, there is a correlation between the $\lambda_{max}$ and the execution time of the B&B algorithm.

Table 5 Regression model between the maximum eigenvalue and the CPU time (Y)

4.2.2 Results for the MIPLIB instances

As seen in Table 6, there are high correlation values for the different variables. It can be observed that the greater the number of threads, the greater the correlation between the variables. The F-test was not applied since the sample size is low and therefore gives non-significant values.

Table 6 Estimated models for maximum eigenvalue versus CPU time with 1, 4 and 12 CPLEX^® 12.2 threads

4.3 Model 3: $\varvec{T} =\varvec{\beta}_{0} + \varvec{ \beta }_{1} \varvec{K}$

${\text{K}}$: Slenderness (ratio between the maximum and minimum eigenvalue) of the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$.

$T$: Execution time of the B&B algorithm using CPLEX^® 12.2.

4.3.1 Results for the OR-Library instances

The ${\text{F}}$-statistic of the ANOVA in Table 7 shows that the experiment performed is statistically significant for an $\alpha$ of 5% for almost all cases. In addition, the best correlation coefficient values $\rho$ are 0.448; 0.441 and 0.634. These values show that in most of the cases, there is a correlation between the value of ${\text{K}}$ and the execution time of the B&B algorithm.

Table 7 Regression model for the slenderness (X) versus CPU time (T)

4.3.2 Results for the MIPLIB instances

As seen in Table 8, there are low correlation values for the different variables.

Table 8 Estimated models for the slenderness versus CPU time with 1, 4 and 12 CPLEX^® 12.2 threads

4.4 Model 4: $\varvec{T} =\varvec{\beta}_{0} + \varvec{ \beta }_{1} \varvec{ \lambda }_{{\varvec{min}}} +\varvec{\beta}_{2}\varvec{\lambda}_{{\varvec{max}}} \varvec{ }_{\varvec{ }}$

$\lambda_{min}$: minimum eigenvalue of the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$

$\lambda_{max}$: maximum eigenvalue of the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$

${\text{T}}:$ solving time of B&B using CPLEX^® 12.2.

4.4.1 Results for the OR-Library instances

The F statistics of the ANOVA results presented in Table 9 show that the experiment is statistically significant for almost all cases for an $\upalpha$ of 5%. It only fails in the experiment with 100 variables and 5 constraints. Similar to previous experiments, high values are observed for the correlation coefficient ρ; these are 0.6618; 0.446; 0.447 and 0.409. These values show that there is a correlation between the values of $\lambda_{min}$ and $\lambda_{max}$ and the execution time of the B&B algorithm.

Table 9 Regression model between the maximum and the minimum eigenvalues CPU time (Y)

4.4.2 Results for the MIPLIB instances

As seen in Table 10, there are high correlation values for the different variables.

Table 10 Estimated models for maximum and minimum eigenvalues versus CPU time with 1, 4 and 12 CPLEX^® 12.2 threads

4.5 Model 5: $\varvec{N} =\varvec{\beta}_{0} \varvec{ }_{\varvec{ }} + \varvec{ \beta }_{1} \varvec{ }$ $\varvec{\lambda}_{{\varvec{min}}}$

$\lambda_{min}$: minimum eigenvalue of the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$ associated with the Dikin ellipsoid matrix.

$N$: number of nodes visited by the B&B algorithm using CPLEX^® 12.2.

4.5.1 Results for the OR-Library instances

The F statistics of the ANOVA results presented in Table 11 show that the experiment is statistically significant for almost all cases for an $\upalpha$ of 5%. It fails in the experiment with 100 variables and 5 constraints and in the experiment with 250 variables and 5 constraints. Similar to previous experiments, high values are observed for the correlation coefficient $\uprho$; these are 0.462; 0.433 and 0.329. These values show that there is a correlation between the values of $\lambda_{min}$ and the number of nodes visited by the B&B algorithm.

Table 11 Regression model between the minimum eigenvalue and the number of nodes visited by the B&B algorithm

4.5.2 Results for the MIPLIB instances

As seen in Table 12, there are high correlation values for the different variables. It can be observed that the greater the number of threads, the greater the correlation between the variables. The F-test was not applied since the sample size is low and therefore gives non-significant values.

Table 12 Regression model between the minimum eigenvalue and the number of nodes visited by the B&B algorithm

4.6 Model 6: $\varvec{N} =\varvec{\beta}_{0} + \varvec{ \beta }_{1}$ $\varvec{\lambda}_{{\varvec{max}}}$

$\lambda_{max}$: maximum eigenvalue for the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$ associated with the Dikin ellipsoid matrix.

N: number of nodes visited by the B&B algorithm using CPLEX^® 12.2.

4.6.1 Results for the OR-Library instances

The F-statistics of the ANOVA results presented in Table 13 show that the experiment is statistically significant for almost all cases for an $\upalpha$ of 5%. It only fails in two experiments, first in the experiment with 100 variables and 5 constraints, and then in the experiment with 250 variables and 5 constraints. Similar to previous experiments, high values are observed for the correlation coefficient $\rho$; these are 0.645; 0.431 and 0.344. These values show that there is a correlation between the values of $\lambda_{max}$ and the number of nodes visited by the B&B algorithm.

Table 13 Regression model between the maximum eigenvalue and the number of nodes visited by the B&B algorithm

4.6.2 Results for the MIPLIB instances

As seen in Table 14, there are high correlation values for the different variables. It can be observed that the greater the number of threads, the greater the correlation between the variables. The F-test was not applied since the sample size is low and therefore gives non-significant values.

Table 14 Regression model between the maximum eigenvalue and the number of nodes visited by the B&B algorithm

4.7 Model 7: $\varvec{ N} =\varvec{\beta}_{0} + \varvec{ \beta }_{1} \;\varvec{K}$

K: Slenderness (ratio between the maximum and minimum eigenvalues)

N: number of nodes visited by the B&B algorithm using CPLEX^® 12.2

4.7.1 Results for the OR-Library instances

The ${\text{F}}$-statistic of the ANOVA in Table 15 shows that the experiment performed is statistically significant for an $\alpha$ of 5% for almost all cases. It only fails in two experiments, first in the experiment with 100 variables and 5 constraints, and then in the experiment with 250 variables and 5 constraints. In addition, the best correlation coefficient values $\rho$ are 0.657; 0.432 and 0.389. These values show that there is a correlation between the value of ${\text{K}}$ and the number of nodes visited by the B&B algorithm.

Table 15 Regression model for the slenderness (K) and the number of nodes visited by the B&B algorithm. $F_{0.95;1;28} = 4.195$

4.7.2 Results for the MIPLIB instances

See Table 16.

Table 16 Regression model for the slenderness (K) and the number of threads used by the solver

4.8 Model 8: $\varvec{N} =\varvec{\beta}_{0} + \varvec{ \beta }_{1} \varvec{ \lambda }_{{\varvec{min}}} +\varvec{\beta}_{2}\varvec{\lambda}_{{\varvec{max}}} \varvec{ }_{\varvec{ }}$

$\lambda_{min}$: minimum eigenvalue of the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$

$\lambda_{max}$: maximum eigenvalue of the matrix $A^{T} H\left( {x_{0} } \right)^{ - 2} A$

N: number of nodes visited by the B&B algorithm using CPLEX^® 12.2

4.8.1 Results for the OR-Library instances

The F statistic of the ANOVA results presented in Table 17 show that the experiment is statistically significant for almost all cases for an $\alpha$ of 10%. It only fails in the experiment with 100 variables and 5 constraints. Similar to previous experiments, high values are observed for the correlation coefficient $\uprho$; these are 0.682; 0.4349; 0.422 and 0.3542. These values show that there is a correlation between the values of $\lambda_{min}$ and $\lambda_{max}$ and the number of nodes for the B&B algorithm.

Table 17 Regression model between the maximum and the minimum eigenvalues and the number of nodes visited by the B&B algorithm

5 Discussion

A total of 40 experiments were performed, using instances of the OR-library, corresponding to eight models and five instances for every model at 100 × 5, 250 × 5, 100 × 10, 100 × 30 and 500 × 5. Each experiment consisted of calculating the eigenvalues of a Dikin ellipsoid obtained based on a coefficient matrix A and the analytical center. For each experiment, linear regressions were performed using one or two explanatory variables. The majority of the results obtained from the experiments are statistically significant at a 95% confidence interval according to the ANOVA tests performed. For the test instances of the MIPLIB 2010 library, 17 problems corresponding to the MKP were studied. The analytic center was obtained in only 12 instances; therefore, the eigenvalues were calculated, and of these instances, only 9 were solved to optimality. The correlation coefficients obtained for these problems are summarized in Table 18. Good correlation coefficients were obtained in general, highlighting the 4th model, which relates the slenderness with the CPU time of the B&B algorithm. The results obtained for the OR-Library instances show good correlation coefficients in almost all cases, all very similar and approximately 0.44. Instances where the experiments were not statistically significant at 95% were included in the tables. These coefficients are summarized in Table 19. These results suggest that the independent variable is a good predictor.

Table 18 Regression model for the slenderness (K) and the number of nodes visited by the B&B algorithm for the MIPLIB instances

Table 19 Summary of the regression correlation coefficients for the OR-library instances

6 Conclusion

The results of this manuscript suggest that it is possible to correlate certain complexity measures of integer programming problems with the CPU time and the number of nodes visited by the B&B algorithm. These measures were developed on the basis of geometric properties of the polyhedron, such as the eigenvalues and the relation between the highest and lowest eigenvalue, which in this work was defined as the slenderness. This suggests that these measures can be used to estimate the complexity of such problems in the future. Future work should focus on finding simpler ways to calculate these complexity measures. In particular, the calculation could be simplified if we could avoid the calculation of the analytical center or use a simpler computational method.