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.     

Matching,Euler tours and the Chinese postman

The solution of the Chinese postman problem using matching theory is given. The convex hull of integer solutions is described as a linear programming polyhedron. This polyhedron is used to show that a good algorithm gives an optimum solution. The algorithm is a specialization of the more generalb-matching blossom algorithm. Algorithms for finding Euler tours and related problems are also discussed.     

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.     

Surrogate-RLT cuts for zero–one integer programs

In this paper, we consider the class of 0–1 integer problems and develop an effective cutting plane algorithm that gives valid inequalities called surrogate-RLT cuts (SR cuts). Here we implement the surrogate constraint analysis along with the reformulation–linearization technique (RLT) to generate strong valid inequalities. In this approach, we construct a tighter linear relaxation by augmenting SR cuts to the problem. The level-\(d\) SR closure of a 0–1 integer program is the polyhedron obtained by intersecting all the SR cuts obtained from RLT polyhedron formed over each set of \(d\) variables with its initial formulation. We present an algorithm for approximately optimizing over the SR closure. Finally, we present the computational result of SR cuts for solving 0–1 integer programming problems of well-known benchmark instances from MIPLIB 3.0.     

Packing Steiner trees: a cutting plane algorithm and computational results

In this paper we describe a cutting plane algorithm for the Steiner tree packing problem. We use our algorithm to solve some switchbox routing problems of VLSI-design and report on our computational experience. This includes a brief discussion of separation algorithms, a new LP-based primal heuristic and implementation details. The paper is based on the polyhedral theory for the Steiner tree packing polyhedron developed in our companion paper (this issue) and meant to turn this theory into an algorithmic tool for the solution of practical problems.     

Solution of real-world postman problems

The paper presents the results of a study performed by the Deutsche post endowed chair of optimization of distribution networks in collaboration with Deutsche Post World Net with the aim of improving the planning of letter mail delivery. Modelling and solution methods for real-world postman problems are presented which extend one of the most general postman problems studied in the literature, the windy rural postman problem, with regard to several aspects. The discussed extensions include turn and street crossing restrictions, cluster constraints, the option to have alternative service modes (including ‘zigzag deliveries’), and the use of public transport to reach the postal district. The solution method is based on a transformation to the asymmetric TSP and uses non-standard neighbourhood search techniques. Extensive computational experiments show that the solution method clearly and consistently outperforms standard TSP heuristics on real-world instances.     

Solving real-world linear ordering problems using a primal-dual interior point cutting plane method

Cutting plane methods require the solution of a sequence of linear programs, where the solution to one provides a warm start to the next. A cutting plane algorithm for solving the linear ordering problem is described. This algorithm uses the primaldual interior point method to solve the linear programming relaxations. A point which is a good warm start for a simplex-based cutting plane algorithm is generally not a good starting point for an interior point method. Techniques used to improve the warm start include attempting to identify cutting planes early and storing an old feasible point, which is used to help recenter when cutting planes are added. Computational results are described for some real-world problems; the algorithm appears to be competitive with a simplex-based cutting plane algorithm.Research partially supported by ONR Grant number N00014-90-J-1714.     

基于松弛策略解半无限规划模型的显式修正算法

讨论了一类线性半无限最优规划模型的求解算法.采用松弛方法解其系列子问题LP(T_k)及DLP(T_k),基于松弛策略和在适当的假设条件下,提出了一个我们称之为显式算法的新型算法.新算法的主要改进之处是算法在每一步迭代计算时,允许丢弃一些不必要的约束.在这种方式下,算法避免了求解系列太大规模的子问题.最后,基于提出的显式修正算法,并与传统割平面方法和已有文献中的松弛修正算法、对同一问题作了初步的数值比较实验.     

A cutting plane procedure for the travelling salesman problem on road networks

A cutting plane algorithm for the exact solution of the symmetric travelling salesman problem (TSP) is proposed. The real tours on a usually incomplete road network, which are in general non-Hamiltonian, are characterized directly by an integer linear programming model. The algorithm generates special cutting planes for this model. Computational results for real road networks with up to 292 visiting places are reported, as well as for classical problems of the literature with up to 120 cities. Some of the latter problems have been solved for the first time with a pure cutting plane approach.     

L-shaped decomposition of two-stage stochastic programs with integer recourse

We consider two-stage stochastic programming problems with integer recourse. The L-shaped method of stochastic linear programming is generalized to these problems by using generalized Benders decomposition. Nonlinear feasibility and optimality cuts are determined via general duality theory and can be generated when the second stage problem is solved by standard techniques. Finite convergence of the method is established when Gomory’s fractional cutting plane algorithm or a branch-and-bound algorithm is applied.     

Estimation of failure probability using semi-definite logit model

We will propose a new and practical method for estimating the failure probability of a large number of small to medium scale companies using their balance sheet data. We will use the maximum likelihood method to estimate the best parameters of the logit function, where the failure intensity function in its exponent is represented as a convex quadratic function instead of a commonly used linear function. The reasons for using this type of function are : (i) it can better represent the observed nonlinear dependence of failure probability on financial attributes, (ii) the resulting likelihood function can be maximized using a cutting plane algorithm developed for nonlinear semi-definite programming problems.We will show that we can achieve better prediction performance than the standard logit model, using thousands of sample companies.Revised: December 2002,     

Lexicography and degeneracy: can a pure cutting plane algorithm work?

We discuss an implementation of the lexicographic version of Gomory’s fractional cutting plane method for ILP problems and of two heuristics mimicking the latter. In computational testing on a battery of MIPLIB problems we compare the performance of these variants with that of the standard Gomory algorithm, both in the single-cut and in the multi-cut (rounds of cuts) version, and show that they provide a radical improvement over the standard procedure. In particular, we report the exact solution of ILP instances from MIPLIB such as stein15, stein27, and bm23, for which the standard Gomory cutting plane algorithm is not able to close more than a tiny fraction of the integrality gap. We also offer an explanation for this surprising phenomenon.     

Convergence and Computational Analyses for Some Variable Target Value and Subgradient Deflection Methods

We consider two variable target value frameworks for solving large-scale nondifferentiable optimization problems. We provide convergence analyses for various combinations of these variable target value frameworks with several direction-finding and step-length strategies including the pure subgradient method, the volume algorithm, the average direction strategy, and a generalized Polyak-Kelley cutting plane method. In addition, we suggest a further enhancement via a projected quadratic-fit line-search whenever any of these algorithmic procedures experiences an improvement in the objective value. Extensive computational results on different classes of problems reveal that these modifications and enhancements significantly improve the effectiveness of the algorithms to solve Lagrangian duals of linear programs, even yielding a favorable comparison against the commercial software CPLEX 8.1.     

Quasi-concave minimization subject to linear constraints

A finite algorithm is presented for solving the quasi-concave minimization problem subject to linear constraints. The concept of an extreme point is generalized to that of an extreme facet of a polyhedron. Then a search routine is developed for the detection of an extreme facet of the feasible region relative to the polyhedron defined by the current set of cuts. After identifying an extreme facet we cut it off by a cut developed for this purpose. We call this cut the facet cut. The method is both compatible with other cutting procedures and is finite..