Search

• A bi-objective optimization approach is introduced for biclustering with binary data. • Integer programming formulations are provided for bi-objective biclustering. • We propose and implement an efficient heuristic based on set intersection operations. • Experimental testing yields very good results and significantly reduced CPU time. Clustering consists of partitioning data objects into subsets called clusters according to some similarity criteria. This paper addresses a structure for generating overlapping clusters, where data objects can belong to more than one subset, which we join with bi-objective optimization and link to biclustering for problems with binary data. Biclustering simultaneously groups the objects and features so that a specific group of objects has a special group of features. In recent years, biclustering has received a lot of attention in several practical applications. First we present an integer programing formulations for the bi-objective optimization of biclustering. Next we propose a constructive heuristic based on the set intersection operation and its efficient implementation for solving a series of mono-objective problems used inside the ε-constraint method (obtained by keeping only one objective function and the other objective function is integrated into constraints). Finally, our experimental results show that our proposed heuristic provides very good results and significantly reduces the computational expense compared to using the CPLEX solver as an exact algorithm for finding an optimal solution, which drastically increases the computational cost for large instances. [ABSTRACT FROM AUTHOR]

In this paper we present an algorithm for generating quadratic assignment problem (QAP) instances with known provably optimal solution. The flow matrix of such instances is constructed from the matrices corresponding to special graphs whose size may reach the dimension of the problem. In this respect, the algorithm generalizes some existing algorithms based on the iterative selection of triangles only. The set of instances which can be produced by the algorithm is NP-hard. Using multi-start descent heuristic for the QAP, we compare experimentally such test cases against those created by several existing generators and against Nugent-type problems from the QAPLIB as well.

This paper briefly reviews some of the recent results on the problems and algorithms for their solution in quadratic 0-1 optimization. First, the complexity of problems is discussed. Next, some exact algorithms and heuristics are mentioned. Finally, results in the analysis of the algorithms for 0-1 quadratic problems are summarized. The papers written in Russian are considered more thoroughly here.

In this paper, we present two heuristics for solving the unconstrained quadratic 0–1 programming problem. First heuristic realizes the steepest ascent from the centre of the hypercube, while the second constructs a series of solutions and chooses the best of them. In order to evaluate their worst-case behaviour We define the performance ratio K which uses the objective function value at the reference point x=1/2. We show for both heuristics that K is bounded by 1 from above and this bound is sharp. Finally, we report on the results of a computational study with proposed and local improvement heuristics.

In this paper we define a class of edge-weighted graphs having nonnegatively valued bisections. We show experimentally that complete such graphs with more than three vertices and also some special graphs with only positive edges can be applied to improve the existing lower bounds for a version of the quadratic assignment problem, namely with a matrix composed of rectilinear distances between points in the Euclidean space.