A primal-dual approximation algorithm for generalized steiner network problems

We present the first polynomial-time approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the generalized Steiner network problem, also called the survivable network design problem. Ifk is the maximum cut requirement of the problem, our solution comes within a factor of 2k of optimal. Our algorithm is primal-dual and shows the importance of this technique in designing approximation algorithms.Research supported by an NSF Graduate Fellowship, DARPA contracts N00014-91-J-1698 and N00014-92-J-1799, and AT&T Bell Laboratories.Research supported in part by Air Force contract F49620-92-J-0125 and DARPA contract N00014-92-J-1799.Part of this work was done while the author was visiting AT&T Bell Laboratories and Bellcore.     

Minimizing submodular functions over families of sets

We consider the problem of characterizing the minimum of a submodular function when the minimization is restricted to a family of subsets. We show that, for many interesting cases, there exist two elementsa andb of the groundset such that the problem is equivalent to the problem of minimizing the submodular function over the sets containinga but notb. This leads to a polynomial-time algorithm for minimizing a submodular function over these families of sets. Our results apply, for example, to the families of odd cardinality subsets or even cardinality subsets separating two given vertices, or to the complement of a lattice family of subsets. We also derive that the second smallest value of a submodular function over a lattice family can be computed in polynomial-time. These results generalize and unify several known results.Research partially supported by NSF contract 9302476-CCR, Air Force contract F49620-92-J-0125 and DARPA contract N00014-92-J-1799.     

An analysis of the composite step biconjugate gradient method

Summary The composite step biconjugate gradient method (CSBCG) is a simple modification of the standard biconjugate gradient algorithm (BCG) which smooths the sometimes erratic convergence of BCG by computing only a subset of the iterates. We show that 2×2 composite steps can cure breakdowns in the biconjugate gradient method caused by (near) singularity of principal submatrices of the tridiagonal matrix generated by the underlying Lanczos process. We also prove a best approximation result for the method. Some numerical illustrations showing the effect of roundoff error are given.The work of this author was supported by the Office of Naval Research under contract N00014-89J-1440.The work of this author was supported by the Office of Naval Research under contracts N00014-90-J-1695 and N00014-92-J-1890, the Department of Energy under, contract DE-FG03-87ER25307, the National Science Foundation under contracts ASC 90-03002 and ASC 92-01266, and the Army Research Office under contract DAAL03-91-G-0150. Part of this work was completed during a visit to the Computer Science Dept. The Chinese University of Hong Kong.     

On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint

In this paper we consider the problem of partitioning large sparse graphs, such as finite element meshes. The heuristic which is proposed allows to partition into connected and quasi-balanced subgraphs in a reasonable amount of time, while attempting to minimize the number of edge cuts. Here the goal is to build partitions for graphs containing large numbers of nodes and edges, in practice at least 10⁴. Basically, the algorithm relies on the iterative construction of connected subgraphs. This construction is achieved by successively exploring clusters of nodes called fronts. Indeed, a judicious use of fronts ensures the connectivity of the subsets at low cost: it is shown that locally, i.e. for a given subgraph, the complexity of such operations grows at most linearly with the number of edges. Moreover, a few examples are given to illustrate the quality and speed of the heuristic.The work of this author was partially supported by the DGA/DRET under contract 93-1192 and by the Army Research Office under contract DAAL03-91-C-0047 (Univ. Tenn. subcontract ORA4466.04 Amendment 1).The work of this author was partially supported by the National Science Foundation under contract ASC 92-01266, the Army Research Office under contract DAAL03-91C-0047 (Univ. Tenn. subcontract ORA4466.04 Amendment 1), and ONR under contract ONR-N00014-92-J-1890.     

Additive Schwarz domain decomposition methods for elliptic problems on unstructured meshes

We give several additive Schwarz domain decomposition methods for solving finite element problems which arise from the discretizations of elliptic problems on general unstructured meshes in two and three dimensions. Our theory requires no assumption (for the main results) on the substructures which constitute the whole domain, so each substructure can be of arbitrary shape and of different size. The global coarse mesh is allowed to be non-nested to the fine grid on which the discrete problem is to be solved and both the coarse meshes and the fine meshes need not be quasi-uniform. In this general setting, our algorithms have the same optimal convergence rate of the usual domain decomposition methods on structured meshes. The condition numbers of the preconditioned systems depend only on the (possibly small) overlap of the substructures and the size of the coares grid, but is independent of the sizes of the subdomains.Revised version on Sept. 20, 1994. Original version: CAM Report 93-40, Dec. 1993, Dept. of Math., UCLA.The work of this author was partially supported by the National Science Foundation under contract ASC 92-01266, the Army Research Office under contract DAAL03-91-G-0150, and ONR under contract ONR-N00014-92-J-1890.The work of this author was partially supported by the National Science Foundation under contract ASC 92-01266, the Army Research Office under contract DAAL03-91-G-0150, and subcontract DAAL03-91-C-0047.     

An efficient approximation algorithm for the survivable network design problem

The survivable network design problem (SNDP) is to construct a minimum-cost subgraph satisfying certain given edge-connectivity requirements. The first polynomial-time approximation algorithm was given by Williamson et al. (Combinatorica 15 (1995) 435–454). This paper gives an improved version that is more efficient. Consider a graph ofn vertices and connectivity requirements that are at mostk. Both algorithms find a solution that is within a factor 2k – 1 of optimal fork 2 and a factor 2 of optimal fork = 1. Our algorithm improves the time from O(k ³n⁴) to O ). Our algorithm shares features with those of Williamson et al. (Combinatorica 15 (1995) 435–454) but also differs from it at a high level, necessitating a different analysis of correctness and accuracy; our analysis is based on a combinatorial characterization of the redundant edges. Several other ideas are introduced to gain efficiency. These include a generalization of Padberg and Rao's characterization of minimum odd cuts, use of a representation of all minimum (s, t) cuts in a network, and a new priority queue system. The latter also improves the efficiency of the approximation algorithm of Goemans and Williamson (SIAM Journal on Computing 24 (1995) 296–317) for constrained forest problems such as minimum-weight matching, generalized Steiner trees and others. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.A preliminary version of this paper has appeared in the Proceedings of the Third Mathematical Programming Society Conference on Integer Programming and Combinatorial Optimization, 1993, pp. 57–74.Research supported in part by NSF Grant No. CCR-9215199 and AT & T Bell Laboratories.Research supported in part by Air Force contracts AFOSR-89-0271 and F49620-92-J-0125 and DARPA contracts N00014-89-J-1988 and N00014-92-1799.This research was performed while the author was a graduate student at MIT. Research supported by an NSF Graduate Fellowship, Air Force contract F49620-92-J-0125, DARPA contracts N00014-89-J-1988 and N00014-92-J-1799, and AT & T Bell Laboratories.     

Numerical methods for controlled and uncontrolled multiplexing and queueing systems

We deal with a very useful numerical method for both controlled and uncontrolled queuing and multiplexing type systems. The basic idea starts with a heavy traffic approximation, but it is shown that the results are very good even when working far from the heavy traffic regime. The underlying numerical method is a version of what is known as the Markov chain approximation method. It is a powerful methodology for controlled and uncontrolled stochastic systems, which can be approximated by diffusion or reflected diffusion type systems, and has been used with success on many other problems in stochastic control. We give a complete development of the relevant details, with an emphasis on multiplexing and particular queueing systems. The approximating process is a controlled or uncontrolled Markov chain which retains certain essential features of the original problem. This problem is generally substantially simpler than the original physical problem, and there are associated convergence theorems. The non-classical associated ergodic cost problem is derived, and put into a form such that reliable and good numerical algorithms, based on multigrid type ideas, can be used. Data for both controlled and uncontrolled problems shows the value of the method.Supported by ARO contract DAAL-03-92-G-0115, AFOSR contract F49620-92-J-0081, and DARPA contract AFOSR-91-0375.Formerly at Brown University. Supported by DARPA contract AFOSR-91-0375.     

The symmetric quadratic traveling salesman problem

In the quadratic traveling salesman problem a cost is associated with any three nodes traversed in succession. This structure arises, e.g., if the succession of two edges represents energetic conformations, a change of direction or a possible change of transportation means. In the symmetric case, costs do not depend on the direction of traversal. We study the polyhedral structure of a linearized integer programming formulation of the symmetric quadratic traveling salesman problem. Our constructive approach for establishing the dimension of the underlying polyhedron is rather involved but offers a generic path towards proving facetness of several classes of valid inequalities. We establish relations to facets of the Boolean quadric polytope, exhibit new classes of polynomial time separable facet defining inequalities that exclude conflicting configurations of edges, and provide a generic strengthening approach for lifting valid inequalities of the usual traveling salesman problem to stronger valid inequalities for the symmetric quadratic traveling salesman problem. Applying this strengthening to subtour elimination constraints gives rise to facet defining inequalities, but finding a maximally violated inequality among these is NP-complete. For the simplest comb inequality with three teeth the strengthening is no longer sufficient to obtain a facet. Preliminary computational results indicate that the new cutting planes may help to considerably improve the quality of the root relaxation in some important applications.     

A time indexed formulation of non-preemptive single machine scheduling problems

We consider the formulation of non-preemptive single machine scheduling problems using time-indexed variables. This approach leads to very large models, but gives better lower bounds than other mixed integer programming formulations. We derive a variety of valid inequalities, and show the role of constraint aggregation and the knapsack problem with generalised upper bound constraints as a way of generating such inequalities. A cutting plane/branch-and-bound algorithm based on these inequalities has been implemented. Computational experience on small problems with 20/30 jobs and various constraints and objective functions is presented.The research of this author was partially supported by JNICT/INVOTAN under grant No. 30/A/85/PO and by the PAC, contract No. 87/92-106, for computation.     

The asymmetric travelling salesman problem and a reformulation of the Miller–Tucker–Zemlin constraints

In this paper we compare the linear programming (LP) relaxations of several old and new formulations for the asymmetric travelling salesman problem (ATSP). The main result of this paper is the derivation of a compact formulation whose LP relaxation is characterized by a set of circuit inequalities given by Grotschel and Padberg (In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A., Shmoys, D.B. (Eds.), The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley, New York, 1985). The new compact model is an improved and disaggregated version of a well-known model for the ATSP based on the subtour elimination constraints (Miller et al., Journal of ACM 7 (1960) 326–329). The circuit inequalities are weaker than the subtour elimination constraints given by Dantzig et al. However, each one of these circuit inequalities can be lifted into several different facet defining inequalities which are not dominated by the subtour elimination inequalities. We show that some of the inequalities involved in the previously mentioned compact formulation can be lifted in such a way that, by projection, we obtain a small subset of the so-called D_k^← and D_k^→ inequalities. This shows that the LP relaxation of our strongest model is not dominated by the LP relaxation of the model presented by Dantzig et al. (Operations Research 2 (1954) 393–410). The new models motivate a new classification of formulations for the ATSP.     

On the monotonization of polyhedra

In polyhedral combinatorics one often has to analyze the facial structure of less than full dimensional polyhedra. The presence of implicit or explicit equations in the linear system defining such a polyhedron leads to technical difficulties when analyzing its facial structure. It is therefore customary to approach the study of such a polytopeP through the study of one of its (full dimensional) relaxations (monotonizations) known as the submissive and the dominant ofP. Finding sufficient conditions for an inequality that induces a facet of the submissive or the dominant of a polyhedron to also induce a facet of the polyhedron itself has been posed in the literature as an important research problem. Our paper goes a long way towards solving this problem. We address the problem in the framework of a generalized monotonization of a polyhedronP, g-mon(P), that subsumes both the submissive and the dominant, and give a sufficient condition for an inequality that defines a facet of g-mon(P) to define a facet ofP. For the important cases of the traveling salesman (TS) polytope in both its symmetric and asymmetric variants, and of the linear ordering polytope, we give sufficient conditions trivially easy to verify, for a facet of the monotone completion to define a facet of the original polytope itself. Research supported by grant DMI-9201340 of the National Science Foundation and contract N00014-89-J-1063 of the Office of Naval Research. Research supported by MURST, Italy.     

Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph

An upper bound is given on the number of acyclic orientations of a graph, in terms of the spectrum of its Laplacian. It is shown that this improves upon the previously known bound, which depended on the degree sequence of the graph. Estimates on the new bound are provided.A lower bound on the number of acyclic orientations of a graph is given, with the help of the probabilistic method. This argument can take advantage of structural properties of the graph: it is shown how to obtain stronger bounds for small-degree graphs of girth at least five, than are possible for arbitrary graphs. A simpler proof of the known lower bound for arbitrary graphs is also obtained.Both the upper and lower bounds are shown to extend to the general problem of bounding the chromatic polynomial from above and below along the negative real axis.Partially supported by the NSF under grant CCR-9404113. Most of this research was done while the author was at the Massachusetts Institute of Technology, and was supported by the Defense Advanced Research Projects Agency under Contracts N00014-92-J-1799 and N00014-91-J-1698, the Air Force under Contract F49620-92-J-0125, and the Army under Contract DAAL-03-86-K-0171.Supported by an ONR graduate fellowship, grants NSF 8912586 CCR and AFOSR 89-0271, and an NSF postdoctoral fellowship.     

Analysis of heuristics for the design of tree networks

We analyze the tour partitioning heuristics for the Capacitated Minimum Spanning Tree problem. Lower bounds for the worst-case performance ratios of these heuristics are obtained by using worst-case examples. We also generalize the heuristics to the multi-center case with the same worst-case bounds.The work of the first author was supported by a Dean Summer Research Grant from Owen Graduate School of Management, Vanderbilt University.Work done in part in the Department of Industrial Engineering and Operations Research at Columbia University.The work of the last two authors was supported in part by ONR contract N00014-90-J-1649, NSF contract DDM-8922712 and the Center for Telecommunications Research under NSF contract CDR 84-21402.     

On the facets of the mixed–integer knapsack polyhedron

We study the mixed–integer knapsack polyhedron, that is, the convex hull of the mixed–integer set defined by an arbitrary linear inequality and the bounds on the variables. We describe facet–defining inequalities of this polyhedron that can be obtained through sequential lifting of inequalities containing a single integer variable. These inequalities strengthen and/or generalize known inequalities for several special cases. We report computational results on using the inequalities as cutting planes for mixed–integer programming.Supported, in part, by NSF grants DMII–0070127 and DMII–0218265.Mathematics Subject Classification (2000): 90C10, 90C11, 90C57     

Packing directed circuits

We prove a conjecture of Younger, that for every integern0 there exists an integert0 such that for every digraphG, eitherG hasn vertex-disjoint directed circuits, orG can be made acyclic by deleting at mostt vertices.Research partially supported by DONET ECHM contract CHRXCT930090.Research partially supported by DIMACS, by NSF grant DMS-9401981 and by ONR grant N00014-92-J-1965, and partially performed under a consulting agreement with Bellcore.Research partially supported by DIMACS, by Université de Paris VI, by NSF grant DMS-9303761 and by ONR grant N00014-93-1-0325, and partially performed under a consulting agreement with Bellcore.     

On a generalization of the master cyclic group polyhedron

We study the master equality polyhedron (MEP) which generalizes the master cyclic group polyhedron (MCGP) and the master knapsack polyhedron (MKP). We present an explicit characterization of the polar of the nontrivial facet-defining inequalities for MEP. This result generalizes similar results for the MCGP by Gomory (1969) and for the MKP by Araóz (1974). Furthermore, this characterization gives a polynomial time algorithm for separating an arbitrary point from MEP. We describe how facet-defining inequalities for the MCGP can be lifted to obtain facet-defining inequalities for MEP, and also present facet-defining inequalities for MEP that cannot be obtained in such a way. Finally, we study the mixed-integer extension of MEP and present an interpolation theorem that produces valid inequalities for general mixed integer programming problems using facets of MEP.     

A simple LP relaxation for the asymmetric traveling salesman problem

It is a long-standing open question in combinatorial optimization whether the integrality gap of the subtour linear program relaxation (subtour LP) for the asymmetric traveling salesman problem (ATSP) is a constant. The study on the structure of this linear program is important and extensive. In this paper, we give a new and simpler LP relaxation for the ATSP. Our linear program consists of a single type of constraints that combine both the subtour elimination and the degree constraints in the traditional subtour LP. As a result, we obtain a much simpler relaxation. In particular, it is shown that the extreme solutions of our program have at most 2n ? 2 non-zero variables, improving the bound 3n ? 2, proved by Vempala and Yannakakis, for the ones obtained by the subtour LP. Nevertheless, the integrality gap of the new linear program is larger than that of the traditional subtour LP by at most a constant factor.     

A note on the prize collecting traveling salesman problem

We study the version of the prize collecting traveling salesman problem, where the objective is to find a tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. We present an approximation algorithm with constant bound. The algorithm is based on Christofides' algorithm for the traveling salesman problem as well as a method to round fractional solutions of a linear programming relaxation to integers, feasible for the original problem.Research supported in part by ONR contract N00014-90-J-1649 and NSF contract DDM-8922712.     

A restricted Lagrangean approach to the traveling salesman problem

We describe an algorithm for the asymmetric traveling salesman problem (TSP) using a new, restricted Lagrangean relaxation based on the assignment problem (AP). The Lagrange multipliers are constrained so as to guarantee the continued optimality of the initial AP solution, thus eliminating the need for repeatedly solving AP in the process of computing multipliers. We give several polynomially bounded procedures for generating valid inequalities and taking them into the Lagrangean function with a positive multiplier without violating the constraints, so as to strengthen the current lower bound. Upper bounds are generated by a fast tour-building heuristic. When the bound-strengthening techniques are exhausted without matching the upper with the lower bound, we branch by using two different rules, according to the situation: the usual subtour breaking disjunction, and a new disjunction based on conditional bounds. We discuss computational experience on 120 randomly generated asymmetric TSP's with up to 325 cities, the maximum time used for any single problem being 82 seconds. This is a considerable improvement upon earlier methods. Though the algorithm discussed here is for the asymmetric TSP, the approach can be adapted to the symmetric TSP by using the 2-matching problem instead of AP.Research supported by the National Science Foundation through grant no. MCS76-12026 A02 and the U.S. Office of Naval Research through contract no. N0014-75-C-0621 NR 047-048.     

Partial linear characterizations of the asymmetric travelling salesman polytope

We consider the linear programming formulation of the asymmetric travelling salesman problem. Several new inequalities are stated which yield a sharper characterization in terms of linear inequalities of the travelling salesman polytope, i.e., the convex hull of tours. In fact, some of the new inequalities as well as some of the well-known subtour elimination constraints are indeed facets of the travelling salesman polytope, i.e., belong to the class of inequalities that uniquely characterize the convex hull of tours to an-city problem.