In this paper, we present a method to determine if a lift-and-project cut for a mixed-integer linear program is irregular, in which case the cut is not equivalent to any intersection cut from the bases of the linear relaxation. This is an important question due to the intense research activity for the past decade on cuts from multiple rows of simplex tableau as well as on lift-and-project cuts from nonsplit disjunctions. Although it has been known for a while that lift-and-project cuts from split disjunctions are always equivalent to intersection cuts and consequently to such multirow cuts, it has been recently shown that there is a necessary and sufficient condition in the case of arbitrary disjunctions: a lift-and-project cut is regular if, and only if, it corresponds to a regular basic solution of the Cut Generating Linear Program (CGLP). This paper has four contributions. First, we state a result that simplifies the verification of regularity for basic CGLP solutions. Second, we provide a mixed-integer formulation that checks whether there is a regular CGLP solution for a given cut that is regular in a broader sense, which also encompasses irregular cuts that are implied by the regular cut closure. Third, we describe a numerical procedure based on such formulation that identifies irregular lift-and-project cuts. Finally, we use this method to evaluate how often lift-and-project cuts from simple t-branch split disjunctions are irregular, and thus not equivalent to multirow cuts, on 74 instances of the Mixed Integer Programming Library (MIPLIB) benchmarks.

Split cuts constitute a class of cutting planes that has been successfully employed by the majority of branch-and-cut solvers for mixed-integer linear programs. Given a basis of the linear programming (LP) relaxation and a split disjunction, the corresponding split cut can be computed with a closed-form expression. In this paper, we use the lift-and-project framework introduced by Balas and Perregaard to provide the basis, and the reduce-and-split algorithm as described by Cornuéjols and Nannicini to compute the split disjunction. We propose a cut generation algorithm that starts from a Gomory mixed-integer cut and alternates between lift-and-project and reduce-and-split in order to strengthen it. This paper has two main contributions. First, we extend the Balas and Perregaard procedure for strengthening cuts arising from split disjunctions involving one variable to split disjunctions on multiple variables. Second, we apply the reduce-and-split algorithm to nonoptimal bases of the LP relaxation. We provide detailed computational testing of the proposed methods.

Abstract We continue the investigation of the cycle polytope of a digraph begun by Balas and Oosten (Networks 36 (2000), 34–46) and derive a rich family of facets that cut off the origin and are not related to facets of the traveling salesman polytope. This disproves a claim in (Balas and Oosten 36 (2000), 34–46) that the only such facets are those defined by the linear ordering inequalities. After examining the relationship between the cycle polytope, its dominant, and the upper cycle polyhedron, we turn to the polar relationship between cycles and permutations or transitive tournaments. Our central result is a characterization of the relationship between facets of the dominant of the cycle polytope, facets of the cycle polytope that cut off the origin, and vertices of the linear relaxation of the transitive tournament polytope. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

Consider the following restricted (symmetric or asymmetric) traveling-salesman problem (TSP): given an initial ordering of the n cities and an integer k > 0, find a minimum-cost feasible tour, where a feasible tour is one in which city i precedes city j whenever j ≥ i + k in the initial ordering. Balas (1996) has proposed a dynamic-programming algorithm that solves this problem in time linear in n, though exponential in k. Some important real-world problems are amenable to this model or some of its close relatives. The algorithm of Balas (1996) constructs a layered network with a layer of nodes for each position in the tour, such that source-sink paths in this network are in one-to-one correspondence with tours that satisfy the postulated precedence constraints. In this paper we discuss an implementation of the dynamic-programming algorithm for the general case when the integer k is replaced with city-specific integers k(j), j = 1, . . ., n. We discuss applications to, and computational experience with, TSPs with time windows, a model frequently used in vehicle routing as well as in scheduling with setup, release and delivery times. We also introduce a new model, the TSP with target times, applicable to Just-in-Time scheduling problems. Finally for TSPs that have no precedence restrictions, we use the algorithm as a heuristic that finds in linear time a local optimum over an exponential-size neighborhood. For this case, we implement an iterated version of our procedure, based on contracting some arcs of the tour produced by a first application of the algorithm, then reapplying the algorithm to the shrunken graph with the same k.

We give a partial description of the cycle polytope of a directed graph G, that is, the convex hull of the incidence vectors of simple directed cycles of G. First, we show how to obtain facets of the cycle polytope from facets of the asymmetric traveling salesman polytope. This involves lifting and facet projection. We discuss several lifting procedures. Next, we obtain facets that have a different source. In particular, we give a complete characterization of the facets that cut off the origin. No such characterization is known for the cycle polytope of an undirected graph. Finally, we introduce a useful equivalence class among the inequalities defining the cycle polytope. © 2000 John Wiley & Sons, Inc.

Abstract The task of developing daily schedules for a steel rolling mill has been formulated as a Prize Collecting Traveling Salesman (PCTS) Problem, in which a salesman who gets a prize for every city he visits seeks a minimum‐cost tour including enough cities to collect a required amount of prize money. This paper addresses the facial structure of the PCTS polytope, the convex hull of solutions to the PCTS problem. In an earlier paper, we generalized to the PCTS polytope the subtour elimination inequalities for the Asymmetric Traveling Salesman (ATS) polytope. Here, we give a general method for deriving a facet defining inequality for the PCTS polytope from any facet defining inequality for the ATS polytope. We apply the procedure to several well‐known families of facet inducing inequalities for the ATS polytope: comb, odd CAT, SD, clique tree, and lifted cycle inequalities. We also extend the cloning and clique lifting procedure for the ATS polytope to the PCTS polytope.

Previous article Addendum: Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary GraphsEgon Balas and Jue XueEgon Balas and Jue Xuehttps://doi.org/10.1137/0221058PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout"Addendum: Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs." SIAM Journal on Computing, 21(5), p. 1000[1] Egon Balas and , Jue Xue, Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs, SIAM J. Comput., 20 (1991), 209–221 10.1137/0220012 92h:68069 0722.68086 LinkISIGoogle Scholar[2] Egon Balas, A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring, Discrete Appl. Math., 15 (1986), 123–134 10.1016/0166-218X(86)90036-3 88e:05037 0633.05039 CrossrefISIGoogle Scholar[3] J. Xue, Ph.D. Thesis, Fast Algorithms for Vertex Packing and Related Problems, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1991 Google Scholar Previous article FiguresRelatedReferencesCited byDetails Clique, Independent Set, and Vertex Cover12 October 2021 Cross Ref Edge-maximal triangulated subgraphs and heuristics for the maximum clique problemNetworks, Vol. 24, No. 2 Cross Ref Volume 21, Issue 5| 1992SIAM Journal on Computing History Submitted:28 July 1992Accepted:28 July 1992Published online:13 July 2006 InformationCopyright © 1992 Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0221058Article page range:pp. 1000-1000ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics

A parallel version of the shortest augmenting path algorithm for the assignment problem 1s described.Although generating the initial dual solution and partial assignment in parallel does not require substantive changes in the sequential algorlthm, using several augmenting paths in parallel does require a new dual variable recalculation Graph Theory -graph algorithms; network problems: path and cmcmt problems: I. 1.

Efficient algorithms are known for finding a maximum weight stable set, a minimum weighted clique covering, and a maximum weight clique of a vertex-weighted triangulated graph. However, there is no comparably efficient algorithm in the literature for finding a minimum weighted vertex coloring of such a graph. This paper gives an $O(|V|^2 )$ procedure for the problem (Algorithm 1). It then extends the procedure to the problem of finding in an arbitrary graph $G = (V,E)$ a maximal induced subgraph $G(W)$ color-equivalent (as defined in § 3) to a maximal triangulated subgraph $G(T)$ (Algorithm 2). Finally, it uses this latter algorithm as the main ingredient of a branch-and-bound procedure for the maximum weight clique problem in an arbitrary graph. Computational experience is presented on arbitrary random graphs with up to 2,000 vertices.

Abstract The following is a valid model for an important class of scheduling and routing problems. A salesman who travels between pairs of cities at a cost depending only on the pair, gets a prize in every city that he vitis and pays a penalty to every city that he fails to visit, wishes to minimize his travel costs and net penalties, while visiting enough cities to collect a prescribed amount of prize money. We call this problem the Prize Collecting Traveling Salesman Problem (PCTSP). This paper discusses structural properties of the PCTS polytope, the convex hull of solutions to the PCTSP. In particular, it identifies several families of facet defining inequalities for this polytope. Some of these inequalities are related to facets of the ordinary TS polytope, others to facets of the knapsack polytope. They can be used in algorithms for the PCTSP either as cutting planes or as ingredients of a Lagrangean optimand.

Abstract We give a new bound on the number of maximal cliques in a graph, along with a bound on the length of odd antiholes that the graph can contain. Based on these bounds we then identify a family of graphs with polynomially solvable maximum weight clique problem, using the edgebicoloring approach developed in a recent paper by Balas, Chvatal, and Nesetril.

An assignment (spanning union of node-disjoint dicycles) in a directed graph is called asymmetric if it contains at most one arc of each pair $(i, j)$, $( j,i)$. The asymmetric assignment polytope is the convex hull of the incidence vectors of all asymmetric assignments. A class of facets is described for this polytope defined on a complete digraph, associated with certain odd-length closed alternating trails. The inequalities defining these facets are also facet inducing for the traveling salesman polytope defined on the same digraph. Furthermore, this class of facets is distinct from each of the classes identified earlier.

We describe a new type of branch and bound procedure for finding a maximum clique in an arbitrary graph $G = (V,E)$. The two main ingredients, both of $O(|V| + |E|)$ time complexity, are (i) an algorithm for finding a maximal triangulated induced subgraph of G; and (ii) an algorithm for finding a maximal k-chromatic induced subgraph of G. We discuss computational experience on randomly generated graphs with up to 400 vertices and 30,000 edges.

Abstract The following type of problem arises in practice: in a node‐weighted graph G, find a minimum‐weight node set that satisfies certain conditions and, in addition, induces a perfectly matchable subgraph of G. This has led us to study the convex hull of incidence vectors of node sets that induce perfectly matchable subgraphs of a graph G, which we call the perfectly matchable subgraph polytope of G. For the case when G is bipartite, we give a linear characterization of this polytope, i.e., specify a system of linear inequalities whose basic solutions are the incidence vectors of perfectly matchable node sets of G. We derive this result by three different approaches, using linear programming duality, projection, and lattice polyhedra, respectively. The projection approach is used here for the first time as a proof method in polyhedral combinatorics, and seems to have many similar applications. Finally, we completely characterize the facets of our polytope; i.e., we separate the essential inequalities of our linear defining system from the redundant ones.

Abstract Facets of the set packing polytope provide strong cutting planes for set packing and partitioning problems. Set packing polytopes are in a one‐to‐one correspondence with graphs. The facets of P(G), the set packing polytope associated with the graph G, are related to certain subgraphs of G. Of particular interest are those subgraphs G′ which are facet producing, i.e., which give rise to facets of P(G′) that cannot be obtained by lifting a facet of P(G′ ‐ {x}), for any vertex x of G′. In this paper we characterize the facets of the set packing polytopes associated with the class of graphs obtained by Chvátal's substitution procedure, and give necessary and sufficient conditions for these graphs to be facet‐producing.