Dual row modules and polyhedra of blocking group problems

Corresponding to every group problem is a row module. Duality for group problems is developed using the duality or orthogonality of the corresponding row modules. The row module corresponding to a group problem is shown to include Gomory's fractional cuts for the group polyhedron and all the vertices of the polyhedron of the blocking group problem. The polyhedra corresponding to a pair of blocking group problems are shown to have a blocking nature i.e. the vertices of one include some of the facets of the other and mutatis mutandis. The entire development is constructive. The notions of contraction, deletion, expansion and extension are defined constructively and related to homomorphic liftings and suproblems in a dual setting. Roughly speaking a homomorphic lifting is dual to forming a subproblem. A proof of the Gastou-Johnson generalization of Gomory's homomorphic lifting theorem is given, and dual constructions are discussed. A generalization of Gomory's subadditive characterization to subproblems is given. In the binary case, it is closely related to the work of Seymour on cones arising from binary matroids.     

Binary group facets with complete support and non-binary coefficients

We identify binary group facets with complete support and non-binary coefficients. These inequalities can be used to obtain new facets for larger problems using Gomory’s homomorphic lifting.     

中国邮递员问题50年

首先介绍一般邮递员问题, 涉及费用、服务侧、衔接费用、次序等要素. 然后简要综述过去50年来中国邮递员问题、有向图上中国邮递员问题、带风向的邮递员问题、混合图上邮递员问题以及乡村邮递员问题等一般邮递员问题的特殊情况的研究进展, 突出问题的线性规划描述及相应的组合多面体结构, 着重讨论问题的模型、精确算法及其时间复杂度、NP-困难情形下的近似算法及其性能比.     

Four problems on graphs with excluded minors

The four problems we consider are the Chinese postman, odd cut, co-postman, and odd circuit problems. Seymour's characterization of matroids having the max-flow min-cut property can be specialized to each of these four problems to show that the property holds whenever the graph has no certain excluded minor. We develop a framework for characterizing graphs not having these excluded minors and use the excluded minor characterizations to solve each of the four optimization problems. In this way, a constructive proof of Seymour's theorem is given for these special cases. We also show how to solve the Chinese postman problem on graphs having no four-wheel minor, where the max-flow min-cut property need not hold.     

Facets of two Steiner arborescence polyhedra

The Steiner arborescence (or Steiner directed tree) problem concerns the connection of a set of target vertices of a digraph to a given root vertex. This problem is known to be NP-hard. In the present paper we study the facial structure of two polyhedra associated with the problem. Several classes of valid inequalities are considered, and a new class with arbitrarily large coefficients is introduced. All these inequalities are shown to define distinct facets of both the Steiner polyhedra considered. This is achieved by exploiting two lifting theorems which also allow generalization of the new inequalities. Composition theorems are finally given and used to derive large families of new facet-inducing inequalities with exponentially large coefficients.     

Polarity and the complexity of the shooting experiment

We exhibit a polar relationship between two measures that have been proposed to evaluate the importance of TSP facets, the Kuhn–Gomory shooting experiment size and the probability of integrality in an augmented LP relaxation. The polarity establishes the complexity of performing the shooting experiment. We illustrate the resulting relationship on the Chinese postman and minimum spanning set problems.     

Projection, Lifting and Extended Formulation in Integer and Combinatorial Optimization

This is an overview of the significance and main uses of projection, lifting and extended formulation in integer and combinatorial optimization. Its first two sections deal with those basic properties of projection that make it such an effective and useful bridge between problem formulations in different spaces, i.e. different sets of variables. They discuss topics like projection and restriction, the integrality-preserving property of projection, the dimension of projected polyhedra, conditions for facets of a polyhedron to project into facets of its projections, and so on. The next two sections describe the use of projection for comparing the strength of different formulations of the same problem, and for proving the integrality of polyhedra by using extended formulations or lifting. Section 5 deals with disjunctive programming, or optimization over unions of polyhedra, whose most important incarnation are mixed 0-1 programs and their partial relaxations. It discusses the compact representation of the convex hull of a union of polyhedra through extended formulation, the connection between the projection of the latter and the polar of the convex hull, as well as the sequential convexification of facial disjunctive programs, among them mixed 0-1 programs, with the related concept of disjunctive rank. Section 6 reviews lift-and-project cuts, the construction of cut generating linear programs, and techniques for lifting and for strengthening disjunctive cuts. Section 7 discusses the recently discovered possibility of solving the higher dimensional cut generating linear program without explicitly constructing it, by a sequence of properly chosen pivots in the simplex tableau of the linear programming relaxation. Finally, section 8 deals with different ways of combining cuts with branch and bound, and briefly discusses computational experience with lift-and-project cuts. This is an updated and extended version of the paper published in LNCS 2241, Springer, 2001 (as given in Balas, 2001). Research was supported by the National Science Foundation through grant #DMI-9802773 and by the Office of Naval Research through contract N00014-97-1-0196.     

Convex polyhedra of doubly stochastic matrices—IV

Basic geometrical properties of general convex polyhedra of doubly stochastic matrices are investigated. The faces of such polyhedra are characterized, and their dimensions and facets are determined. A connection between bounded faces of doubly stochastic polyhedra and faces of transportation polytopes is established, and it is shown that there exists an absolute bound for the number of extreme points of d-dimensional bounded faces of these polyhedra.     

Another complete invariant for Steiner triple systems of order 15

In this note, the 80 non‐isomorphic triple systems on 15 points are revisited from the viewpoint of the convex hull of the characteristic vectors of their blocks. The main observation is that the numbers, of facets of these 80 polyhedra are all different, thus producing a new proof of the non‐isomorphism of these triple systems. The space dimension of these polyhedra is also discussed. Finally, we observe the large number of facets of some of these polyhedra with few vertices, in relation with the upper bound problem for combinatorial polyhedra. © 2005 Wiley Periodicals, Inc. J Combin Designs.     

Generalized skew bisubmodularity: A characterization and a min–max theorem

Huber, Krokhin, and Powell (2013) introduced a concept of skew bisubmodularity, as a generalization of bisubmodularity, in their complexity dichotomy theorem for valued constraint satisfaction problems over the three-value domain. In this paper we consider a natural generalization of the concept of skew bisubmodularity and show a connection between the generalized skew bisubmodularity and a convex extension over rectangles. We also analyze the dual polyhedra, called skew bisubmodular polyhedra, associated with generalized skew bisubmodular functions and derive a min–max theorem that characterizes the minimum value of a generalized skew bisubmodular function in terms of a minimum-norm point in the associated skew bisubmodular polyhedron.     

Finding Postal Carrier Walk Paths in Mixed Graphs

The postman problem requires finding a lowest cost tour in a connected graph that traverses each edge at least once. In this paper we first give a brief survey of the literature on postman problems including, the original Chinese postman problem on undirected graphs, the windy Chinese postman problem on graphs where the cost of an arc depends on the direction the arc is transversed, the directed postman problem on graphs with directed edges, and the mixed postman problem on graphs in which there are some directed and some undirected arcs.We show how the mixed postman problem can be solved as an integer program, using the formulation of Gendreau, Laporte and Zhao, by a new row addition branch and bound algorithm, which is a modification of the column subtraction algorithm for set partitioning problems of Harche and Thompson. Computational experience shows that a slack variable heuristic is very effective in finding good solutions that are frequently optimal for these problems.     

On the generalized directed rural postman problem

The generalized directed rural postman problem (GDRPP) is a generic type of arc routing problem. In the present paper, it is described how many types of practically relevant single-vehicle routing problems can be modelled as GDRPPs. This demonstrates the versatility of the GDRPP and its importance as a unified model for postman problems. In addition, an exact and a heuristic solution method are presented. Computational experiments using two large sets of benchmark instances are performed. The results show high solution quality and thus demonstrate the practical usefulness of the approach.     

On the equivalence between some local and global Chinese postman and traveling salesman graphs

A connected graph G=(V,E), a vertex in V and a non-negative weight function defined on E can be used to induce Chinese postman and traveling salesman (cooperative) games. A graph G=(V,E) is said to be locally (respectively, globally) Chinese postman balanced (respectively, totally balanced, submodular) if for at least one vertex (respectively, for all vertices) in V and any non-negative weight function defined on E, the corresponding Chinese postman game is balanced (respectively, totally balanced, submodular). Local and global traveling salesman balanced (respectively, totally balanced, submodular) graphs are similarly defined.In this paper, we study the equivalence between local and global Chinese postman balanced (respectively, totally balanced, submodular) graphs, and between local and global traveling salesman submodular graphs.     

On ternary problems

We consider ternary matrices, i.e., integer matrices having all entries 0, 1 or 2. Three associated problems—the group problem, covering, and packing—are studied. General classes of vertices and facets are discussed in each case. Certain lifting procedures are also described. For all three problems techniques used are natural extensions of those used in the binary case.     

Series-parallel graphs are windy postman perfect

The windy postman problem is the NP-hard problem of finding the minimum cost of a tour traversing all edges of an undirected graph, where the cost of an edge depends on the direction of traversal. Given an undirected graph G, we consider the polyhedron O(G) induced by a linear programming relaxation of the windy postman problem. We say that G is windy postman perfect if O(G) is integral. There exists a polynomial-time algorithm, based on the ellipsoid method, to solve the windy postman problem for the class of windy postman perfect graphs. By considering a family of polyhedra related to O(G), we prove that series-parallel graphs are windy postman perfect, therefore solving a conjecture of Win.     

GIS technology as an environment for testing an advanced mathematical model for optimization of road maintenance

In the paper, we consider a Chinese postman problem and show how integration of an advanced mathematical model with GIS technology can be beneficial providing a powerful tool for developing, testing and applying sophisticated heuristics for arc routing problems. We give details of an implementation of several recently developed heuristics for the Chinese postman problem with priority nodes that are integrated with GIS software. In the end, we show how a GIS visualization can be helpful in finding and presenting the results.     

Vertex-Disjoint Packing of Two Steiner Trees: polyhedra and branch-and-cut

Consider the problem of routing the electrical connections among two large terminal sets in circuit layout. A realistic model for this problem is given by the vertex-disjoint packing of two Steiner trees (2VPST), which is known to be NP-complete. This work presents an investigation on the 2VPST polyhedra. The main idea is to start from facet-defining inequalities for a vertex-weighted Steiner tree polyhedra. Some of these inequalities are proven to also define facets for the packing polyhedra, while others are lifted to derive new important families of inequalities, including proven facets. Separation algorithms are provided. Branch-and-cut implementation issues are also discussed, including some new practical techniques to improve the performance of the algorithm. The resulting code is capable of solving problems on grid graphs with up to 10000 vertices and 5000 terminals in a few minutes. Received: August 1999 / Accepted: January 2001?Published online April 12, 2001     

Polyhedra related to a lattice

Without using the l.p. duality theorem, we give a new and direct proof that Hoffman's lattice polyhedra, polyhedra from problems of Edmonds and Giles, and others, are integer. These polyhedra are intersections of more simple polyhedra such that every vertex of the initial polyhedron is a vertex of some simple polyhedron. In many cases encountered in combinatorics the simple polyhedra have a totally unimodular constraint matrix. This implies that all vertices of the initial polyhedron are integral. The proof is based on a theorem on submodular functions, which was not known earlier. The method of this paper can be applied to the consideration of the matching polyhedron.     

A generalized proximal-point method for convex optimization problems in Hilbert spaces

We deal with a generalization of the proximal-point method and the closely related Tikhonov regularization method for convex optimization problems. The prime motivation behind this is the well-known connection between the classical proximal-point and augmented Lagrangian methods, and the emergence of modified augmented Lagrangian methods in recent years. Our discussion includes a formal proof of a corresponding connection between the generalized proximal-point method and the modified augmented Lagrange approach in infinite dimensions. Several examples and counterexamples illustrate the convergence properties of the generalized proximal-point method and indicate that the corresponding assumptions are sharp.