Characterization of the types of maximum noninteger vertices in the relaxation polyhedron of the four-index axial assignment problem

For the relaxation polyhedron M(4, n) in the four-index axial assignment problem of order n, n ≥ 3, a characterization of all possible types (except for a single case) of maximum noninteger vertices, i.e., vertices with 4n — 3 fractional components is proposed. A formula enumerating all the maximum noninteger vertices of the same type in M(4, n) is derived.     

On the characterization of noninteger vertices of the relaxation polyhedron in the multi-index axial assignment problem

Theorems about the characterization and exponential growth of the denominators of fractional components of noninteger vertices of the relaxation polyhedron in the multi-index axial assignment problem are proved. They made it possible to obtain new lower bounds on the number of noninteger vertices of this polyhedron and to refute the conjecture on the estimate of the ratio of the number of integer vertices to the number of all vertices of the multi-index axial transportation polyhedron determined by integer vectors.     

The Wiener maximum quadratic assignment problem

We investigate a special case of the maximum quadratic assignment problem where one matrix is a product matrix and the other matrix is the distance matrix of a one-dimensional point set. We show that this special case, which we call the Wiener maximum quadratic assignment problem, is NP-hard in the ordinary sense and solvable in pseudo-polynomial time.Our approach also yields a polynomial time solution for the following problem from chemical graph theory: find a tree that maximizes the Wiener index among all trees with a prescribed degree sequence. This settles an open problem from the literature.     

A Branch & Cut algorithm for a four-index assignment problem

In this paper, we examine the orthogonal Latin squares (OLS) problem from an integer programming perspective. The OLS problem has a long history and its significance arises from both theoretical aspects and practical applications. The problem is formulated as a four-index assignment problem whose solutions correspond to OLS. This relationship is exploited by various routines (preliminary variable fixing, branching, etc) of the Branch & Cut algorithm we present. Clique, odd-hole and antiweb inequalities implement the ‘Cut’ component of the algorithm. For each cut type a polynomial-time separation algorithm is implemented. Extensive computational analysis examines multiple aspects concerning the design of our algorithm. The results illustrate clearly the improvement achieved over simple Branch & Bound.     

Finding all vertices of a convex polyhedron

Summary The paper describes an algorithm for finding all vertices of a convex polyhedron defined by a system of linear equations and by non-negativity conditions for variables. The algorithm is described using terminology of the theory of graphs and it seems to provide a computationally effective method. An illustrative example and some experiences with computations on a computer are given.     

Lower bounds for the axial three-index assignment problem

This paper describes new bounding methods for the axial three-index assignment problem (3AP). For calculating 3AP lower bounds, we use a projection method followed by a Hungarian algorithm, based on a new Lagrangian relaxation. We also use a cost transformation scheme, which iteratively transforms 3AP costs in a series of equivalent 3APs, which provides the possibility of improving the 3AP lower bound. These methods produce efficiently computed relatively tight lower bound.     

Adjacent vertices on the b-matching polyhedron

Given a graph G = (V,E) and an integer vector $\text{b?}\text{N}{}^{\mathrm{v}}$, a b-matching is a set of edges F?E such that any vertex v?V is incident to at most b_v edges in F. The adjacency on the convex hull of the incidence vectors of the b-matchings is characterized by a very general adjacency criterion, the coloring criter on, which is at least sufficient for all 0–1-polyhedra and which can be checked in the b-matching case by a linear algorithm.     

On solvability of the axial 8-index assignment problem on single-cycle permutations

Under study is the axial 8-index assignment problem on single-cycle permutations. For a long time the question of solvability of its set of constraints for single-cycle permutations of length n in the case of 8 indices remained open.We prove that the set of constraints have a solution for odd n ≥ 87.     

The auction algorithm: A distributed relaxation method for the assignment problem

We propose a massively parallelizable algorithm for the classical assignment problem. The algorithm operates like an auction whereby unassigned persons bid simultaneously for objects thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. The algorithm can also be interpreted as a Jacobi — like relaxation method for solving a dual problem. Its (sequential) worst — case complexity, for a particular implementation that uses scaling, is O(NAlog(NC)), where N is the number of persons, A is the number of pairs of persons and objects that can be assigned to each other, and C is the maximum absolute object value. Computational results show that, for large problems, the algorithm is competitive with existing methods even without the benefit of parallelism. When executed on a parallel machine, the algorithm exhibits substantial speedup.Work supported by Grant NSF-ECS-8217668. Thanks are due to J. Kennington and L. Hatay of Southern Methodist Univ. for contributing some of their computational experience.     

Cycles containing all vertices of maximum degree

For a graph G and an integer k, denote by V_k the set {v ∈ V(G) | d(v) ≥ k}. Veldman proved that if G is a 2-connected graph of order n with n ≤ 3k - 2 and |V_k| ≤ k, then G has a cycle containing all vertices of V_k. It is shown that the upper bound k on |V_k| is close to best possible in general. For the special case k = δ(G), it is conjectured that the condition |V_k| ≤ k can be omitted. Using a variation of Woodall's Hopping Lemma, the conjecture is proved under the additional condition that n ≤ 2δ(G) + δ(G) + 1. This result is an almost-generalization of Jackson's Theorem that every 2-connected k-regular graph of order n with n ≤ 3k is hamiltonian. An alternative proof of an extension of Jackson's Theorem is also presented. © 1993 John Wiley & Sons, Inc.     

Cycles through vertices of large maximum degree

Let G be a 2-connected graph on n vertices with maximum degree k where n ≤ 3k - 2. We show that there is a cycle in G that contains all vertices of degree k. © 1995 John Wiley & Sons, Inc.     

Lagrangian relaxation guided problem space search heuristics for generalized assignment problems

We develop and test a heuristic based on Lagrangian relaxation and problem space search to solve the generalized assignment problem (GAP). The heuristic combines the iterative search capability of subgradient optimization used to solve the Lagrangian relaxation of the GAP formulation and the perturbation scheme of problem space search to obtain high-quality solutions to the GAP. We test the heuristic using different upper bound generation routines developed within the overall mechanism. Using the existing problem data sets of various levels of difficulty and sizes, including the challenging largest instances, we observe that the heuristic with a specific version of the upper bound routine works well on most of the benchmark instances known and provides high-quality solutions quickly. An advantage of the approach is its generic nature, simplicity, and implementation flexibility.     

A polyhedron of genus 4 with minimal number of vertices and maximal symmetry

We construct a symmetric polyhedron of genus 4 in R ³ with 11 vertices. This shows that for given genus g the minimal numbers of vertices of combinatorial manifolds and of polyhedra coincide in the first previously unknown case g=4 also. We show that our polyhedron has the maximal symmetry for the given genus and minimal number of vertices.     

Reducing the elastic generalized assignment problem to the standard generalized assignment problem

The elastic generalized assignment problem (eGAP) is a natural extension of the generalized assignment problem (GAP) where the capacities are not fixed but can be adjusted; this adjustment can be expressed by continuous variables. These variables might be unbounded or restricted by a lower or upper bound, respectively. This paper concerns techniques aiming at reducing several variants of eGAP to GAP, which enables us to employ standard approaches for the GAP. This results in a heuristic, which can be customized in order to provide solutions having an objective value arbitrarily close to the optimal.     

A polyhedron with alls—t cuts as vertices,and adjacency of cuts

Consider the polyhedron represented by the dual of the LP formulation of the maximums–t flow problem. It is well known that the vertices of this polyhedron are integral, and can be viewed ass–t cuts in the given graph. In this paper we show that not alls–t cuts appear as vertices, and we give a characterization. We also characterize pairs of cuts that form edges of this polyhedron. Finally, we show a set of inequalities such that the corresponding polyhedron has as its vertices alls–t cuts.Work done at the Department of Computer Science and Engineering, Indian Institute of Technology, Delhi, India.     

On the maximal energy tree with two maximum degree vertices

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all eigenvalues of its adjacent matrix.For Δ?3 and t?3, denote by T_a(Δ,t) (or simply T_a) the tree formed from a path P_t on t vertices by attaching Δ-1P₂’s on each end of the path P_t, and T_b(Δ,t) (or simply T_b) the tree formed from P_t+2 by attaching Δ-1P₂’s on an end of the P_t+2 and Δ-2P₂’s on the vertex next to the end.In Li et al.(2009) [16] proved that among trees of order n with two vertices of maximum degree Δ, the maximal energy tree is either the graph T_a or the graph T_b, where t=n+4-4Δ?3.However, they could not determine which one of T_a and T_b is the maximal energy tree.This is because the quasi-order method is invalid for comparing their energies.In this paper, we use a new method to determine the maximal energy tree.It turns out that things are more complicated.We prove that the maximal energy tree is T_b for Δ?7 and any t?3, while the maximal energy tree is T_a for Δ=3 and any t?3.Moreover, for Δ=4, the maximal energy tree is T_a for all t?3 but one exception that t=4, for which T_b is the maximal energy tree.For Δ=5, the maximal energy tree is T_b for all t?3 but 44 exceptions that t is both odd and 3?t?89, for which T_a is the maximal energy tree.For Δ=6, the maximal energy tree is T_b for all t?3 but three exceptions that t=3,5,7, for which T_a is the maximal energy tree.One can see that for most cases of Δ, T_b is the maximal energy tree,Δ=5 is a turning point, and Δ=3 and 4 are exceptional cases, which means that for all chemical trees (whose maximum degrees are at most 4) with two vertices of maximum degree at least 3, T_a has maximal energy, with only one exception T_a(4,4).