On lower bounds for a class of quadratic 0,1 programs (Q1072937)

The paper presents a new method to obtain lower bounds for a class of quadratic 0-1 integer program such as \[ \min imize\quad z(x)=\sum^{m}_{i=1}\sum^{m}_{j=1}a_{ij}x_ ix_ j\quad s.t.\quad x=(x_ 1,...,x_ m)\in S\subseteq \{0,1\}^ m \] under the following assumptions: (1) \(\sum^{m}_{i=1}x_ i=K\) for all \(x\in S,\) (2) The linear program Min\(\{\) cx\(| x\in S\}\) can be quickly solved. The feasible set S is any subset of \(\{0,1\}^ m\). This class of problems includes the quadratic assignment problem, the quadratic minimum spanning tree problem and so on. For any parameter \(u=(u_ 1,...,u_ m)\), let \(a_{ij}(u)=a_{ij}+u_ j\) (i\(\neq j)\) and \(a_{ii}(u)=a_{ii}-(K-1)u_ i\). Defining \[ f_ i(u):=Min\{a_{ii}(u)+\sum^{m}_{j=i}a_{ij}(u)x_ j| \quad x_ i=1,\quad x\in S\}\quad and \] \[ \quad PB(u):=Min\{\sum^{m}_{i=1}f_ i(u)x_ i| \quad x\in S\}, \] the authors show that PB(u) is a lower bound for the optimal value of z(x) and that for any u and \(\hat u,\) PB(u)\(\leq PB(\hat u)+K\phi (\hat u)\) is established where \(\phi (u)=Max\{f_ i(u)\}-Min\{f_ i(u)\}\). Hence, if one can select \(u^*\) satisfying \(\phi (u^*)=0\), it brings us the best lower bound in the sense of \(PB^*=_{u}\{PB(u)\}\). To find such a \(u^*\) the authors present an iterative algorithm, the so called leveling algorithm, which is simple and has a monotonical convergency. This algorithm has been tested on the quadratic assignment problem.