A graph is an interval graph if its vertex set corresponds to a family of intervals on the real line, called a model, such that two distinct vertices are adjacent in the graph if and only if their corresponding intervals intersect each other. The minimum number of interval lengths that suffices to represent a model of a given interval graph is its interval count. The use of mathematical optimization techniques for solving interval count problems was first explored by Joos et al.[1]. In more detail, given a bipartition of vertices into classes of lengths, the authors propose an efficient linear programming based algorithm for solving the interval count two problem. However, so far, no mathematical formulation exists in the literature for general interval count. As a contribution in that direction, we introduce a mixed integer programming formulation for the exact value of interval count, parameterized by the largest interval length. Additionally, we also propose a quadratic formulation for a valid upper bound on interval count. Solution algorithms for these formulations were tested on interval count instances found in the literature. As an outcome of these experiments, the algorithm for the upper bound formulation was shown to run much faster than its exact solution counterpart. Furthermore, the upper bounds thus obtained were frequently certified as optimal by the exact algorithm.

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.

Abstract Scheduling by Edge Reversal provides an order of operation for nodes in a graph, but maximizing or minimizing the resulting concurrency is hard. In this paper, we discuss a series of real‐world applications for this technique and propose algorithms for both problems. For maximum concurrency, we prove its general inapproximability and introduce approximation algorithms for classes of graphs. For minimum concurrency, we use hardness and inapproximability results to establish its relation to longest cycles, while also introducing a novel application for assembling musical phrases.

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

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.

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

Abstract Assume that a rectangle R is given on the Euclidean plane together with a finite set P of points that are interior to R. A rectangular partition of R is a partition of the surface of R into smaller rectangles. The length of such a partition equals the sum of the lengths for the line segments that define it. The partition is said to be feasible if no point of P is interior to a partition rectangle. The Rectangular Partitioning Problem (RPP) seeks a feasible rectangular partition of R with the least length. Computational evidence from the literature indicates that RPPs with noncorectilinear points in P, denoted NCRPPs, are the hardest to solve to proven optimality. In this paper, some structural properties of optimal feasible NCRPP partitions are presented. These properties allow substantial reductions in problem input size to be carried out. Additionally, a stronger formulation of the problem is also made possible. Based on these ingredients, a hybrid Lagrangian Relaxation—Linear Programming Relaxation exact solution algorithm is proposed. Such an algorithm has proved capable of solving NCRPP instances more than twice as large as those found in the literature. © 2002 Wiley Periodicals, Inc.

In this paper, we consider the Steiner problem in graphs, which is the problem of connecting together, at minimum cost, a number of vertices in an undirected graph with nonnegative edge costs. We use the formulation of this problem as a shortest spanning tree (SST) problem with additional constraints given previously in the literature. We strengthen this SST formulation and present a branch and cut algorithm to solve the problem to optimality. This algorithm incorporates reduction tests and is used to solve a number of problems drawn from the literature. A number of general issues relating to branch and cut algorithms are also highlighted. © 1998 John Wiley & Sons, Inc. Networks 31: 39–59, 1998

Abstract We consider a scheme to derive lower bounds for the time‐dependent traveling salesman problem. It involves splitting lower bounds into a number of components and optimizing each of these components. The lower bounds thus derived are shown to be at least as sharp as the ones previously suggested for the problem. We describe a branch‐and‐bound algorithm based on our lower bounding scheme and computationally test it for an instance of the problem known as the traveling deliveryman problem.