New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints

We propose a new formulation for the asymmetric traveling salesman problem, with and without precedence relationships, which employs a polynomial number of subtour elimination constraints that imply an exponential subset of certain relaxed Dantzig-Fulkerson-Johnson subtour constraints. Promising computational results are presented, particularly in the presence of precedence constraints.     

A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints

In this paper, we present a new class of polynomial length formulations for the asymmetric traveling salesman problem (ATSP) by lifting an ordered path-based model using logical restrictions in concert with the Reformulation–Linearization Technique (RLT). We show that a relaxed version of this formulation is equivalent to a flow-based ATSP model, which in turn is tighter than the formulation based on the exponential number of Dantzig–Fulkerson–Johnson (DFJ) subtour elimination constraints. The proposed lifting idea is applied to derive a variety of new formulations for the ATSP, and we explore several dominance relationships among these. We also extend these formulations to include precedence constraints in order to enforce a partial order on the sequence of cities to be visited in a tour. Computational results are presented to exhibit the relative tightness of our formulations and the efficacy of the proposed lifting process.     

An efficient genetic algorithm for the traveling salesman problem with precedence constraints

The traveling salesman problem with precedence constraints (TSPPC) is one of the most difficult combinatorial optimization problems. In this paper, an efficient genetic algorithm (GA) to solve the TSPPC is presented. The key concept of the proposed GA is a topological sort (TS), which is defined as an ordering of vertices in a directed graph. Also, a new crossover operation is developed for the proposed GA. The results of numerical experiments show that the proposed GA produces an optimal solution and shows superior performance compared to the traditional algorithms.     

Nonlinear mappings associated with the generalized linear complementarity problem

We show that the Cottle—Dantzig generalized linear complementarity problem (GLCP) is equivalent to a nonlinear complementarity problem (NLCP), a piecewise linear system of equations (PLS), a multiple objective programming problem (MOP), and a variational inequalities problem (VIP). On the basis of these equivalences, we provide an algorithm for solving problem GLCP.Project partially supported by a grant from Oak Ridge Associated Universities, TN, USA.     

Application of the problem of moments to derive bounds on integrals with integral constraints

Recently a lot of results (for a review see Goovaerts et al. (1983)) have been obtained for bounds on stop-loss premiums in case of incomplete information on the claim distribution.As a consequence some extremal distributions (depending on the retention limit) have been characterized. The extremal distributions for the stop-loss ordering in case of fixed values of the retention limit are obtained by means of deep results from the theory of convex analysis. In the present contribution it is shown, by means of some results from the problem of moments, how bounds on integrals with integral constraints can be obtained. We assume only the knowledge of the moments μ₀, μ₁, …, μ_n.     

An algorithm for the linear complementarity problem with upper and lower bounds

In this paper, we adapt the octahedral simplicial algorithm for solving systems of nonlinear equations to solve the linear complementarity problem with upper and lower bounds. The proposed algorithm generates a piecewise linear path from an arbitrarily chosen pointz ⁰ to a solution point. This path is followed by linear programming pivot steps in a system ofn linear equations, wheren is the size of the problem. The starting pointz ⁰ is left in the direction of one of the 2 ⁿ vertices of the feasible region. The ray along whichz ⁰ is left depends on the sign pattern of the function value atz ⁰. The sign pattern of the linear function and the location of the points in comparison withz ⁰ completely govern the path of the algorithm.This research is part of the VF-Program Equilibrium and Disequilibrium in Demand and Supply, approved by the Netherlands Ministry of Education, Den Haag, The Netherlands.     

Linear optimal control problem for discrete 2-D systems with constraints

Optimal control problem for linear two-dimensional (2-D) discrete systems with mixed constraints is investigated. The problem under consideration is reduced to a linear programming problem in appropriate Hubert space. The main duality relations for this problem is derived such that the optimality conditions for the control problem are specified by using methods of the linear operator theory. Optimality conditions are expressed in terms of solutions for conjugate system.     

Computation of lower bounds on the network cost in location problems subject to distance constraints

Methods for the computation of lower bounds on the cost of the connecting network for the continuous and discrete variants of the problem of location of interconnected objects subject to minimal or maximal distances between them are proposed. For the continuous variant, the bound is found by solving a linear programming problem. For the discrete variant, an assignment problem with a rectangular matrix containing forbidden entries is constructed. An application of the assignment problem for locating objects of various sizes is described.     

A new approach to the analysis of random methods for detecting necessary linear inequality constraints

A new approach is given for the analysis of random methods for detecting necessary constraints in systems of linear inequality constraints. This new approach directly accounts for the fact that two constraints are detected as necessary (hit) at each iteration of a random method. The significance of this two-hit analysis is demonstrated by comparing it with the usual one-hit analysis.     

The convergence of an interior point method for an elliptic control problem with mixed control-state constraints

The paper addresses a primal interior point method for state-constrained PDE optimal control problems in function space. By a Lavrentiev regularization, the state constraint is transformed to a mixed control-state constraint with bounded Lagrange multiplier. Existence and convergence of the central path are established, and linear convergence of a short-step pathfollowing method is shown. The behaviour of the method is demonstrated by numerical examples. Research supported by the DFG Research Center “Mathematics for key technologies” (Matheon) in Berlin.     

The Tricomi problem for second order linear equations of mixed type with parabolic degeneracy

In Bers, 1958, Mathematical Aspects of Subsonic and Transonic Gas Dynamics (New York: Wiley); Bitsadze, 1988, Some Classes of Partial Differential Equations (New York: Gordon and Breach); Rassias, 1990, Lecture Notes on Mixed Type Partial Differential Equations (Singapore: World Scientific); Salakhitdinov and Islomov, 1987, The Tricomi problem for the general linear equation of mixed type with a nonsmooth line of degeneracy. Soviet Math. Dokl., 34, 133–136; Smirnov, 1978, Equations of Mixed type (Providence, RI: American Mathematical Society), the authors posed and discussed the Tricomi problem of second order equations of mixed type with parabolic degeneracy, which possesses important application to gas dynamics. The present article deals with the Tricomi problem for general second order equations of mixed type with parabolic degeneracy. Firstly the formulation of the problem for the equations is given, next the representations and estimates of solutions for the above problem are obtained, finally the existence of solutions for the problem is proved by the successive iteration and the method of parameter extension. In this article, we use the complex method, namely the complex functions in the elliptic domain and the hyperbolic complex functions in hyperbolic domain are used (see Wen, 2002, Linear and Quasilinear Equations of Hyperbolic and Mixed Types (London: Taylor and Francis)).     

More results on the convergence of iterative methods for the symmetric linear complementarity problem

In an earlier paper, the author has given some necessary and sufficient conditions for the convergence of iterative methods for solving the linear complementarity problem. These conditions may be viewed as global in the sense that they apply to the methods regardless of the constant vector in the linear complementarity problem. More precisely, the conditions characterize a certain class of matrices for which the iterative methods will converge, in a certain sense, to a solution of the linear complementarity problem for all constant vectors. In this paper, we improve on our previous results and establish necessary and sufficient conditions for the convergence of iterative methods for solving each individual linear complementarity problem with a fixed constant vector. Unlike the earlier paper, our present analysis applies only to the symmetric linear complementarity problem. Various applications to a strictly convex quadratic program are also given.The author gratefully acknowledges several stimulating conversations with Professor O. Mangasarian on the subject of this paper. He is also grateful to a referee, who has suggested Lemma 2.2 and the present (stronger) version of Theorem 2.1 as well as several other constructive comments.This research was based on work supported by the National Science Foundation under Grant No. ECS-81-14571, sponsored by the United States Army under Contract No. DAAG29-80-C-0041, and was completed while the author was visiting the Mathematics Research Center at the University of Wisconsin, Madison, Wisconsin.     

The Kalman condition for the boundary controllability of coupled parabolic systems. Bounds on biorthogonal families to complex matrix exponentials

This paper is devoted to prove the controllability to trajectories of a system of n one-dimensional parabolic equations when the control is exerted on a part of the boundary by means of m controls. We give a general Kalman condition (necessary and sufficient) and also present a construction and sharp estimates of a biorthogonal family in L²(0,T;C) to {tje−Λkt}.     

Global solutions with shock waves to the generalized Riemann problem for a system of hyperbolic conservation laws with linear damping

It is proven that a class of the generalized Riemann problem for quasilinear hyperbolic systems of conservation laws with the uniform damping term admits a unique global piecewise C¹ solution u=u(t,x) containing only n shock waves with small amplitude on t?0 and this solution possesses a global structure similar to that of the similarity solution of the corresponding homogeneous Riemann problem. As an application of our result, we prove the existence of global shock solutions, piecewise continuous and piecewise smooth solution with shock discontinuities, of the flow equations of a model class of fluids with viscosity induced by fading memory with a single jump initial data. We also give an example to show that the uniform damping mechanism is not strong enough to prevent the formation of shock waves.     

Global existence of classical solutions to the Cauchy problem on a semi-bounded initial axis for a nonhomogeneous quasilinear hyperbolic system

It is proven that if the leftmost eigenvalue is weakly linearly degenerate, then the Cauchy problem for a class of nonhomogeneous quasilinear hyperbolic systems with small and decaying initial data given on a semi-bounded axis admits a unique global C¹ solution on the domain , where x=xn(t) is the fastest forward characteristic emanating from the origin. As an application of our result, we prove the existence of global classical, C¹ solutions of the flow equations of a model class of fluids with viscosity induced by fading memory with small smooth initial data given on a semi-bounded axis.     

Solution for a problem of linear plane elasticity with mixed boundary conditions on an ellipse by the method of boundary integrals

A numerical boundary integral scheme is proposed for the solution of the system of field equations of plane, linear elasticity in stresses for homogeneous, isotropic media in the domain bounded by an ellipse under mixed boundary conditions. The stresses are prescribed on one half of the ellipse, while the displacements are given on the other half. The method relies on previous analytical work within the Boundary Integral Method [1], [2].The considered problem with mixed boundary conditions is replaced by two subproblems with homogeneous boundary conditions, one of each type, having a common solution. The equations are reduced to a system of boundary integral equations, which is then discretized in the usual way and the problem at this stage is reduced to the solution of a rectangular linear system of algebraic equations. The unknowns in this system of equations are the boundary values of four harmonic functions which define the full elastic solution inside the domain, and the unknown boundary values of stresses or displacements on proper parts of the boundary.On the basis of the obtained results, it is inferred that the tangential stress component on the fixed part of the boundary has a singularity at each of the two separation points, thought to be of logarithmic type. A tentative form for the singular solution is proposed to calculate the full solution in bulk directly from the given boundary conditions using the well-known Boundary Collocation Method. It is shown that this addition substantially decreases the error in satisfying the boundary conditions on some interval not containing the singular points.The obtained results are discussed and boundary curves for unknown functions are provided, as well as three-dimensional plots for quantities of practical interest. The efficiency of the used numerical schemes is discussed, in what concerns the number of boundary nodes needed to calculate the approximate solution.     

The boundary-contact problem of elasticity for homogeneous anisotropic media with a contact on some part of the boundaries

The existence and uniqueness of solutions of the boundary-contact problem of elasticity for homogeneous anisotropic media with a contact on some part of their boundaries are investigated in the Besov and Bessel potential classes using the methods of the potential theory and the theory of pseudodifferential equations on manifolds with boundary. The smoothness of the solutions obtained is studied.     

Construction of a stabilizing control and solution to a problem about the center and the focus for differential systems with a polynomial part on the right side

The stationary differential systems with polynomial right sides are considered. Necessary and sufficient conditions are formulated when a given domain is a domain of asymptotic stability and the origin of coordinates is either the focus or the center. The problem of construction of a stabilizing control in a form of polynomial is studied.