ABSTRACT Given a simple graph with vertex set and edge set , the minimum biclique cover problem seeks to cover all edges of the graph with a minimum number of bicliques (i.e., complete bipartite subgraphs). This paper proposes two compact mixed integer programming (MIP) formulations for solving the minimum biclique cover problem on general graphs: (i) A natural formulation in the edge space and (ii) an extended formulation in the edge and vertex spaces. While the natural MIP formulation of Cornaz and Fonlupt ( Discrete Mathematics , 2006) has exponentially many constraints, our natural formulation enjoys only a polynomial number of their exponential “no‐good” cuts, along with another set of polynomial valid inequalities. We also employ bounding and variable fixing procedures that help solve most of our social network instances, which are not solvable to optimality in a one‐hour time limit without the bounding and fixing procedures. The instances that are not solved in the one‐hour time limit are submitted to the 2024 Mixed Integer Programming Library (MIPLIB 2024).

We present a new approach for modeling avoidance constraints in 2D environments, in which waypoints are assigned to obstacle-free polyhedral regions. Constraints of this form are often formulated as mixed-integer programming (MIP) problems employing big-M techniques-however, these are generally not the strongest formulations possible with respect to the MIP's convex relaxation (so called ideal formulations), potentially resulting in larger computational burden. We instead model obstacle avoidance as combinatorial disjunctive constraints and leverage the independent branching scheme to construct small, ideal formulations. As our approach requires a biclique cover for an associated graph, we exploit the structure of this class of graphs to develop a fast subroutine for obtaining biclique covers in polynomial time. We also contribute an open-source Julia library named ClutteredEnvPathOpt to facilitate computational experiments of MIP formulations for obstacle avoidance. Experiments have shown our formulation is more compact and remains competitive on a number of instances compared with standard big-M techniques, for which solvers possess highly optimized procedures.

Distributed networked systems form an essential resource for computation and applications ranging from commercial, military, scientific, and research communities. Allocation of resources on a given infrastructure is realized through various mapping systems that are tailored towards specific use cases of the requesting applications. While HPC system requests demand compute resources heavy on processor and memory, cloud applications may demand distributed web services that are composed of networked processing and some memory. All resource requests allocate on the infrastructure with some form of network connectivity. However, during mapping of resources, the features and topology constraints of network components are typically handled indirectly through abstractions of user requests. This paper is on a novel graph representation that enables precise mapping methods for distributed networked systems. The proposed graph representations are demonstrated to allocate specific network components and adjacency requirements of a requested graph on a given infrastructure. Furthermore, we report on application of business policy requirements that resulted in increased utilization and a gradual decrease in idle node count as requests are mapped using our proposed methods.

The minimum rank of a graph G is the minimum of the ranks of all symmetric adjacency matrices of G. We present a new combinatorial bound for the minimum rank of an arbitrary graph G based on enumerating certain subsets of vertices of G satisfying matroid theoretic properties. We also present some computational and theoretical challenges associated with computing the minimum rank. This includes a conjecture that this bound on the minimum rank actually holds with equality for all graphs. History: This “Challenge” paper was invited by the Editor in Chief and based on the topics raised by the author at his plenary address at the 2022 INFORMS Computing Society Conference in Tampa, Florida. Funding: This work was supported by the National Science Foundation [Grant DMS-1720225]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.1219 .

Abstract The minimum k‐core problem asks for the smallest induced subgraph of minimum degree k . It has been shown that this problem is NP‐hard, and thus sophisticated techniques are required to obtain good solutions and approximations. In this article, the minimum k ‐core problem is modeled as a binary integer program and relaxed as a linear program. Since the relaxation may yield a non‐integral solution, a branch‐and‐cut framework is used to find an integral optimal solution. It is shown that the edge and cycle transversals of the graph give valid inequalities for the convex hull of the k ‐core polytope—which can be further generalized to a family of ‐core transversals. Further, a heuristic for the transversal of the minimal ‐cores is given with its associated valid inequality. Additionally, improved valid inequalities are generated using bounds involving the girth of the graph. Multiple heuristics are explored for finding initial bounds for the branching process utilizing the degree distribution of the graph. Finally, numerical results are given comparing the branch‐and‐bound, branch‐and‐cut, and heuristic techniques.

Abstract To monitor electrical activity throughout the power grid and mitigate outages, sensors known as phasor measurement units can installed. Due to implementation costs, it is desirable to minimize the number of sensors deployed while ensuring that the grid can be effectively monitored. This optimization problem motivates the graph theoretic power dominating set problem. In this paper, we propose a method for computing minimum power dominating sets via a set cover IP formulation and a novel constraint generation procedure. The set cover problem's constraints correspond to neighborhoods of zero forcing forts; we study their structural properties and show they can be separated with delayed row generation. In addition, we offer several computation enhancements which be be applied to our methodology as well as existing methods. The proposed and existing methods are evaluated in several computational experiments. In many of the larger test instances considered, the proposed method exhibits an order of magnitude runtime performance improvement.

Abstract We present an integer programming model to compute the strong rainbow connection number, src(G), of any simple graph G. We introduce several enhancements to the proposed model, including a fast heuristic, and a variable elimination scheme. Moreover, we present a novel lower bound for src(G) which may be of independent research interest. We solve the integer program both directly and using an alternative method based on iterative lower bound improvement, the latter of which we show to be highly effective in practice. To our knowledge, these are the first computational methods for the strong rainbow connection problem. We demonstrate the efficacy of our methods by computing the strong rainbow connection numbers of graphs containing up to 379 vertices.

Zero forcing is a graph coloring process based on the following color change rule: all vertices of a graph [Formula: see text] are initially colored either blue or white; in each timestep, a white vertex turns blue if it is the only white neighbor of some blue vertex. A zero forcing set of [Formula: see text] is a set of blue vertices such that all vertices eventually become blue after iteratively applying the color change rule. The zero forcing number [Formula: see text] is the cardinality of a minimum zero forcing set. In this paper, we propose novel exact algorithms for computing [Formula: see text] based on formulating the zero forcing problem as a two-stage Boolean satisfiability problem. We also propose several heuristics for zero forcing based on iteratively adding blue vertices which color a large part of the remaining white vertices. These heuristics are used to speed up the exact algorithms and can also be of independent interest in approximating [Formula: see text]. Computational results on various types of graphs show that, in many cases, our algorithms offer a significant improvement on the state-of-the-art algorithms for zero forcing. Summary of Contribution: This paper proposes novel algorithms and heuristics for an NP-hard graph coloring problem that has numerous applications. Our exact methods combine Boolean satisfiability modeling with a constraint generation framework commonly used in operations research. The paper also includes an analysis of the facets of the polytope associated with this problem and decomposition techniques which can reduce the size of the problem. Our computational approaches are implemented and tested on a wide variety of graphs and are compared with the state-of-the-art algorithms from the literature. We show that our proposed algorithms based on Boolean satisfiability, in conjunction with the heuristics and order-reduction techniques, yield a significant speedup in some cases.

Abstract The concept of branch decomposition was first introduced by Robertson and Seymour in their proof of the Graph Minors Theorem, and can be seen as a measure of the global connectivity of a graph. Since then, branch decomposition and branchwidth have been used for computationally solving combinatorial optimization problems modeled on graphs and matroids. General branchwidth is the extension of branchwidth to any symmetric submodular function defined over a finite set. General branchwidth encompasses graphic branchwidth, matroidal branchwidth, and rankwidth. A tangle basis is related to a tangle, a notion also introduced by Robertson and Seymour; however, a tangle basis is more constructive in nature. It was shown in [I. V. Hicks. Graphs, branchwidth, and tangles! Oh my! Networks, 45:55‐60, 2005] that a tangle basis of order k is coextensive to a tangle of order k. In this paper, we revisit the construction of tangle bases computationally for other branchwidth parameters and show that the tangle basis approach is still competitive for computing optimal branch decompositions for general branchwidth.

Abstract Positive semidefinite (PSD) zero forcing is a dynamic graph process in which an initial subset of vertices are colored and may cause additional vertices to become colored through a set of color changing rules. Subsets which cause all other vertices to become colored are called PSD zero forcing sets; the PSD zero forcing number of a graph is the minimum cardinality attained by its PSD zero forcing sets. The PSD zero forcing number is of particular interest as it bounds solutions for the minimum rank and PSD min rank problems, both popular in linear algebra. This paper introduces blocking sets for PSD zero forcing sets which are used to formulate the first integer program (IP) for computing PSD zero forcing numbers of general graphs. It is shown that facets of the feasible region of this IP's linear relaxation correspond to zero forcing forts which induce connected subgraphs, but that identifying min cardinality connected forts is ‐hard in general. Auxiliary IPs used to find these blocking sets are also given, enabling the master IP to be solved via constraint generation. Experiments comparing the proposed methods and existing algorithms are provided demonstrating improved runtime performance, particularly so in dense and sparse graphs.

In this paper, we use a branch decomposition technique to improve approximations to the p-median problem. Starting from a support graph produced either by a combination of heuristics or by linear programming, we use dynamic programming guided by a branch decomposition of that support graph to find the best p-median solution on the support graph. Our results show that when heuristics are used to build the support graph and the support graph has branchwidth at most 7, our algorithm is able to provide a solution of lower cost than any of the heuristic solutions. When linear programming is used to build the support graph and the support graph has branchwidth at most 7, then our algorithm provides better solutions than popular heuristics and is faster than integer programming. Thus, our algorithm is a useful practical tool when support graphs have branchwidth at most 7.

In this paper, we present a set covering problem (SCP) formulation to compute the degree of redundancy of linear systems. Computing the degree of redundancy of a linear system allows for the evaluation of the quality of the sensor network. The formulation is equivalent to solving the linear matroid cogirth problem, finding the cardinality of the smallest cocircuit of a matroid. We also discuss existing methods developed to solve the matroid cogirth problem and the SCP. Computational results are provided to validate a branch-and-cut algorithm that addresses the SCP formulation.

In 2007, W. H. Cunningham and J. Geelen describe an algorithm for solving [Formula: see text], where [Formula: see text], [Formula: see text], and [Formula: see text], which utilizes a branch-decomposition of the matrix A and techniques from dynamic programming. In this paper, we report on the first implementation of the CG algorithm and compare our results with the commercial integer programming software Gurobi. Using branch-decomposition trees produced by heuristics and optimal trees produced by algorithms developed in our previous studies, we test both a memory-intensive and low-memory version of the CG algorithm on problem instances such as graph 3-coloring, set partition, market split, and knapsack. We isolate a class of set partition instances where the CG algorithm runs twice as fast as Gurobi, and demonstrate that certain infeasible market split and knapsack instances with width ≤6 range from running twice as fast as Gurobi, to running in a matter of minutes versus a matter of hours.

k-plexes are cohesive subgraphs which were introduced to relax the structure of cliques. A co-k-plex is the complement of a k-plex and is therefore similar to a stable set. This paper derives the co-2-plex analogue for certain properties of the stable set polytope. We also describe a class of 0-1 matrices A for which the polytope $\{x\in\mathbf{R}^n_+\mid Ax\leq 2,$ $x\leq 1\}$ is integral.

Abstract This study describes certain facet classes for the planar subgraph polytope. These facets are extensions of Kuratowski facets and are of the form 2x(U) + x(E(G)\U) ≤ 2|U| + |E(G)\U| − 2 where the edge set U varies and can be empty. Two of the new types of facets complete the class of extended subdivision facets, explored by Jünger and Mutzel. In addition, the other types of facets consist of a new class of facets for the polytope called 3‐star subdivisions. It is also shown that the extended and 3‐star subdivision facets are also equivalent to members of the class of facets with coefficients in {0, 1, 2} for the set covering polytope. Computational results displaying the effectiveness of the facets in a branch‐and‐cut scheme for the maximum planar subgraph problem are presented. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008

The notion of branch decompositions and its related connectivity invariant for graphs, branchwidth, were introduced by Robertson and Seymour in their series of papers that proved Wagner's conjecture. Branch decompositions can be used to solve NP-hard problems modeled on graphs, but finding optimal branch decompositions of graphs is also NP-hard. This is the first of two papers dealing with the relationship of branchwidth and planar graphs. A practical implementation of an algorithm of Seymour and Thomas for only computing the branchwidth (not optimal branch decomposition) of any planar hypergraph is proposed. This implementation is used in a practical implementation of an algorithm of Seymour and Thomas for computing the optimal branch decompositions for planar hypergraphs that is presented in the second paper. Since memory requirements can become an issue with this algorithm, two other variations of the algorithm to handle larger hypergraphs are also presented.

This is the second of two papers dealing with the relationship of branchwidth and planar graphs. Branchwidth and branch decompositions, introduced by Robertson and Seymour, have been shown to be beneficial for both proving theoretical results on graphs and solving NP-hard problems modeled on graphs. The first practical implementation of an algorithm of Seymour and Thomas for computing optimal branch decompositions of planar hypergraphs is presented. This algorithm encompasses another algorithm of Seymour and Thomas for computing the branchwidth of any planar hypergraph, whose implementation is discussed in the first paper. The implementation also includes the addition of a heuristic to decrease the run times of the algorithm. This method, called the cycle method, is an improvement on the algorithm by using a “divide-and-conquer” approach.

Branch decomposition-based algorithms have been used in practical settings to solve some NP-hard problems like the travelling salesman problem (TSP) and general minor containment. The notions of branch decompositions and branchwidth were introduced by Robertson and Seymour to assist in proving the Graph Minors Theorem. Given a connected graph G and a branch decomposition of G of width k where k is at least 3, a practical branch decomposition-based algorithm to test whether a graph has branchwidth at most k − 1 is given. The algorithm either constructs a branch decomposition of G of width at most k − 1 or constructs a tangle basis of order k, which offers a lower bound on the branchwidth of G. The algorithm is utilized repeatedly in a practical setting to find an optimal branch decomposition of a connected graph, whose branchwidth is at least 2, given an input branch decomposition of the graph from a heuristic. This is the first algorithm for the optimal branch decomposition problem for general graphs that has been shown to be practical. Computational results are provided to illustrate the effectiveness of finding optimal branch decompositions. A tangle basis is related to a tangle, a notion also introduced by Robertson and Seymour; however, a tangle basis is more constructive in nature. Furthermore, it is shown that a tangle basis of order k is coextensive to a tangle of order k. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(2), 55–60 2005

The maximum weight-independent set problem (MWISP) is one of the most well-known and well-studied problems in combinatorial optimization. This article presents a novel approach to solve MWISP exactly by decomposing the original graph into vertex-induced subgraphs. The approach solves MWISP for the original graph by solving MWISP on the subgraphs to generate columns for a branch-and-price framework. The authors investigate different implementation techniques that can be associated with the approach, and offer computational results to identify the strengths and weaknesses of each implementation technique. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(4), 198–209 2005

Abstract Given a simple graph G , a simple connected graph H , and a branch decomposition of G of width k , we present a practical algorithm to test if H is a minor of G . The notion of branch decompositions and its related connectivity invariant for graphs, branchwidth, were introduced by Robertson and Seymour. The algorithm that we present follows the general framework for such an algorithm sketched by Robertson and Seymour with the addition of pruning techniques for runtime speedup. © 2003 Wiley Periodicals, Inc.