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

Given a connected and undirected graph G, the degree preserving spanning tree problem (DPSTP) asks for a spanning tree of G with the maximum number of vertices having the same degree in the tree and in G. These are called full degree vertices. We introduce integer programming formulations, valid inequalities and four exact solution approaches based on different formulations. Two branch‐and‐bound procedures, a branch‐and‐cut (BC) algorithm and an iterative probing combinatorial Benders decomposition method are introduced here. The problem of optimally lifting one of the classes of valid inequalities proposed here is equivalent to solving a DPSTP instance, for a conveniently defined subgraph of G. We thus apply one of the proposed methods to optimally lift these cuts, within the other solution methods. In doing so, two additional algorithms, a hybrid Benders decomposition and a hybrid BC are proposed. Extensive computational experiments are conducted with the solution algorithms introduced in this study. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(4), 329–343 2015

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

We present exact algorithms for solving the minimum connected dominating set problem in an undirected graph. The algorithms are based on two approaches: a Benders decomposition algorithm and a branch-and-cut method. We also develop a hybrid algorithm that combines these two approaches. Two variants of each of the three resulting algorithms are considered: a stand-alone version and an iterative probing variant. The latter variant is based on a simple property of the problem, which states that if no connected dominating set of a given cardinality exists, then there are no connected dominating sets of lower cardinality. We present computational results on a large set of instances from the literature.

In this paper, we propose optimization algorithms for the problem of multiple mobile sinks route planning in Wireless Sensor Networks (WSN). Our aim is to reduce the length of the sink routes, in order to reduce the message delivery delay. Our approach differs from others in the literature since clustering and route planning are dealt simultaneously. We compare the proposed algorithms and the best of them are used to perform WSNs simulations. By comparing our approaches to others in the literature, significant gains in terms of message delivery delay rates are attained.

Abstract In this paper, we propose a Lagrangian Non‐Delayed Relax‐and‐Cut algorithm for the Degree‐Constrained Minimum Spanning Tree Problem (DCMSTP). Since degree‐constrained trees are the common vertices of the Spanning Tree and the b‐Matching polytopes, strengthened DCMSTP lower bounds are generated through the use of Blossom Inequalities (BIs). BIs are facet defining for the b‐Matching Polytope and, to the best of our knowledge, have never been used before for DCMSTP. Lagrangian information is also used here, in a Kruskal style algorithm (followed by local search) to obtain valid DCMSTP upper bounds. Whenever optimality could not be proven by Relax‐and‐Cut alone, Lagrangian lower bounds are carried over to a cutting plane algorithm, without the need for solving any separation problem. This is accomplished after identifying, at Relax‐and‐Cut, a small set of attractive Subtour Elimination Constraints and BIs. Computational results, on Euclidean and on random cost DCMSTP instances, indicate that our Relax‐and‐Cut lower bounds either dominate or else are competitive with linear programming and Lagrangian relaxation lower bounds found in the literature. Furthermore, our upper bounds appear competitive with the best in the literature. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(1), 55–66 2007