ABSTRACT In this paper, we introduce new Semidefinite Programming (SDP) dual bounding procedures and two Branch‐and‐bound algorithms based on them, BBLAG and BBLAG+ , for solving the ‐Cluster Problem, KCP. The algorithms compute Lagrangian relaxation SDP bounds by relaxing the positive semidefiniteness constraint and attaching conveniently defined matrices of Lagrangian multipliers to it. Operating under a more standard approach found in the literature, BBLAG only requires the matrix of Lagrangian multipliers to be positive semidefinite; symmetry is not required. BBLAG+ , on the other hand, enforces both conditions and, as a result, solves a reformulation of the Lagrangian Dual problem without the need of projecting the matrix of Lagrangian multipliers onto the cone of symmetric positive semidefinite matrices. The positive impact of avoiding the projection step is tremendous, as it is the most CPU time‐consuming operation involved in the computation of our SDP bounds, by means of Lagrangian Relaxation. Because of that, BBLAG+ is four times faster than BBLAG . Additionally, BBLAG+ attained quite competitive results when compared to the existing KCP algorithms from the literature, BiqCrunch and BiqBin , that also rely on SDP bounds. In practice, the SDP bounds computed by BBLAG+ neither dominate nor are dominated by the SDP bounds computed by its competitors. For the densest subgraph problem, one of the five KCP variants tested here, the best results were provided by BiqCrunch followed by BiqBin . For four other sets of KCP instances, BBLAG+ usually provides better results than BiqCrunch and BiqBin , for a wide range of values of and graph densities. In summary, BBLAG+ seems to be a robust approach for a wide range of KCP instances.

A formulation, a heuristic, and branch-and-cut algorithms are investigated for the chordless cycle problem. This is the problem of finding a largest simple cycle for a given graph so that no edge between nonimmediately subsequent cycle vertices is contained in the graph. Leaving aside procedures based on complete enumeration, no previous exact solution algorithm appears to exist for the problem, which is relevant both in theoretical and practical terms. Extensive computational results are reported here for randomly generated graphs and for graphs originating from the literature. Under acceptable CPU times, certified optimal solutions are presented for graphs with as many as 100 vertices. Summary of Contribution: Finding chordless cycles of a graph, also known as holes, is relevant, among others, to graph theory, to the design of polyhedral based exact solution algorithms to integer programming (IP) problems, and to the practical applications that benefit from these algorithms. For instance, perfect graphs do not contain odd holes. Additionally, odd hole inequalities are valid for strengthening the formulations to numerous problems that are directly defined over graphs. Furthermore, these inequalites, in association with applicable conflict graphs, are used by all modern IP solvers to preprocess and strengthen virtually any IP formulation submitted to them.

Given a complete and undirected graph G, the adjacent only quadratic minimum spanning tree problem (AQMSTP) consists of finding a spanning tree that minimizes a quadratic function of its adjacent edges. The strongest AQMSTP linear integer programming formulation in the literature works on an extended variable space, using exponentially many decision variables assigned to the stars of G. In this article, we characterize three families of facet defining inequalities by investigating the projection of that formulation onto the space of the canonical linearization variables. On the algorithmic side, we introduce four new branch‐and‐bound algorithms. Three of them are branch‐and‐cut algorithms based on the inequalities characterized by projection. The fourth is based on a Lagrangian relaxation scheme, also devised for the star reformulation. Two of the branch‐and‐cut algorithms provide very good results, almost always dominating the previously best algorithm for the problem. The Lagrangian relaxation based branch‐and‐bound algorithm provides even better results. It manages to solve all previously solved AQMSTP instances in the literature in about one tenth of the time needed by its competitors. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(1), 31–50 2018

The quadratic minimum spanning tree problem (QMSTP) consists of finding a spanning tree of a graph G such that a quadratic cost function is minimized. In its adjacent only version (AQMSTP), interaction costs only apply for edges that share an endpoint. Motivated by the weak lower bounds provided by formulations in the literature, we present a new linear integer programming formulation for AQMSTP. In addition to decision variables assigned to the edges, it also makes use of variables assigned to the stars of G. In doing so, the model is naturally linear (integer), without the need of implementing usual linearization steps, and its linear programming relaxation better estimates the interaction costs between edges. We also study a reformulation derived from the new model, obtained by projecting out the decision variables associated with the stars. Two exact solution approaches are presented: a branch‐and‐cut‐and‐price algorithm, based on the first formulation, and a branch‐and‐cut algorithm, based on its projection. Our computational results indicate that the lower bounds introduced here are much stronger than previous bounds in the literature. Being designed for the adjacent only case, our duality gaps are one order of magnitude smaller than the Gilmore–Lawler lower bounds for AQMSTP. As a result, the two exact algorithms introduced here outperform the previous exact solution approaches in the literature. In particular, the branch‐and‐cut method we propose managed to solve AQMSTP instances with as many as 50 vertices to proven optimality. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(4), 367–379 2015

The Hamiltonian p‐median problem consists of determining p disjoint cycles of minimum total cost covering all vertices of a graph. We present several new and existing models for this problem, provide a hierarchy with respect to the quality of the lower bounds yielded by their linear programming relaxations, and compare their computational performance on a set of benchmark instances. We conclude that three of the models are superior from a computational point of view, two of which are introduced in this article. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(4), 350–363 2014

This paper proposes two new data clustering approaches using the particle swarm optimization algorithm (PSO). It is shown how the PSO can be used to find centroids of a user specified number of clusters. The proposed approaches are an attempt to improve the Merwe and Engelbrecht method using different fitness functions and considering the situation where data is uniformly distributed. The data clustering PSO algorithm, using the original and proposed fitness functions is evaluated on well known data sets. Notable improvements on the results were achieved by the modifications, this shows the potential of the PSO, not only on data clustering but also on the several areas it can be applied.