Computing inter-site distances for routing and scheduling problems

Routing and scheduling problems have received considerable attention in the literature in terms of model building and algorithm development. On these fronts, progress has been substantial. However, one often neglected (yet critical) aspect concerning the use of these models and algorithms is their data requirements. In particular, the distance matrix yielding the shortest distance between each pair of sites (nodes) represents a major portion of the data required by all such problems. Yet, such data are seldom available with the degree of accuracy desired and often are not available at all.This paper describes an efficient method for obtaining this distance matrix that is based on the underlying road structure for the geographic region in question. Thus, the distances obtained reflect ‘actual’ distances. Finally, the paper presents some brief computational experience and discusses an implementation concerning the routing of environmental inspectors in the state of Pennsylvania.     

Pressure and time treatment for Chebyshev spectral solution of a Stokes problem

To investigate the influences of time scheme, pressure treatment and initial conditions in incompressible fluid dynamics, a Stokes problem is solved numerically on a slab geometry within the framework of spectral approximation in space. Four algorithms are examined: splitting schemes, influence matrix method, penalty formulation and pseudo-spectral space-time technique. It is shown that splitting schemes are less accurate than the other processes. Furthermore, the initial field should respect a compatibility condition to avoid singularities at the initial time. If it is not possible to build such a compatible field, the numerical procedure has to present good damping properties at the first steps of the time integration.     

Proper,reflecting and absorbing facts of complementary cones

A common approach in studying the linear complementarity problem is via the geometry of the complementary cones. In the case of nondegeneracy, the concept of a ‘proper facet’ and a ‘reflecting facet’ have proven useful. This paper extends these concepts to the degenerate case. Under degeneracy, a facet may turn out to be neither proper nor reflecting, but, a third type which we designate as ‘absorbing’. Previous results in this area can be easily extended using these more general definitions.     

Dynamical systems and variational inequalities

The variational inequality problem has been utilized to formulate and study a plethora of competitive equilibrium problems in different disciplines, ranging from oligopolistic market equilibrium problems to traffic network equilibrium problems. In this paper we consider for a given variational inequality a naturally related ordinary differential equation. The ordinary differential equations that arise are nonstandard because of discontinuities that appear in the dynamics. These discontinuities are due to the constraints associated with the feasible region of the variational inequality problem. The goals of the paper are two-fold. The first goal is to demonstrate that although non-standard, many of the important quantitative and qualitative properties of ordinary differential equations that hold under the standard conditions, such as Lipschitz continuity type conditions, apply here as well. This is important from the point of view of modeling, since it suggests (at least under some appropriate conditions) that these ordinary differential equations may serve as dynamical models. The second goal is to prove convergence for a class of numerical schemes designed to approximate solutions to a given variational inequality. This is done by exploiting the equivalence between the stationary points of the associated ordinary differential equation and the solutions of the variational inequality problem. It can be expected that the techniques described in this paper will be useful for more elaborate dynamical models, such as stochastic models, and that the connection between such dynamical models and the solutions to the variational inequalities will provide a deeper understanding of equilibrium problems.     

关于陷门背包公开钥密码系统的注记

利用不定方程理论及中国剩余定理,我们设计了一类陷门背包公开钥密码系统,它们具有更好的安全性.     

A decomposition algorithm for linear relaxation of the weightedr-covering problem

In this paper the linear relaxation of the weightedr-covering problem (r-LCP) is considered. The dual problem (c-LMP) is the linear relaxation of the well-knownc-matching problem and hence can be solved in polynomial time. However, we describe a simple, but nonpolynomial algorithm in which ther-LCP is decomposed into a sequence of 1-LCP’s and its optimal solution is obtained by adding the optimal solutions of these 1-LCP’s. An 1-LCP can be solved in polynomial time by solving its dual as a max-flow problem on a bipartite graph. An accelerated algorithm based on this decomposition scheme to solve ar-LCP is also developed and its average case behaviour is studied.     

Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality

The multiconstraint 0–1 knapsack problem is encountered when one has to decide how to use a knapsack with multiple resource constraints. Even though the single constraint version of this problem has received a lot of attention, the multiconstraint knapsack problem has been seldom addressed. This paper deals with developing an effective solution procedure for the multiconstraint knapsack problem. Various relaxation of the problem are suggested and theoretical relations between these relaxations are pointed out. Detailed computational experiments are carried out to compare bounds produced by these relaxations. New algorithms for obtaining surrogate bounds are developed and tested. Rules for reducing problem size are suggested and shown to be effective through computational tests. Different separation, branching and bounding rules are compared using an experimental branch and bound code. An efficient branch and bound procedure is developed, tested and compared with two previously developed optimal algorithms. Solution times with the new procedure are found to be considerably lower. This procedure can also be used as a heuristic for large problems by early termination of the search tree. This scheme was tested and found to be very effective.     

Supports and convex envelopes

The construct of anL ₁-Support is extended to the environment of a lower semicontinuous function over a solid, finite union of polytopes by utilizing the convex envelope of the function. The existence of and a characterization for theL ₁-Support of the convex envelope are established. The characterization is solely dependent upon the original function’s characteristics and thus the need to calculate the functional form of the convex envelope explicity is eliminated.     

On the acyclic subgraph polytope

The acyclic subgraph problem can be formulated as follows. Given a digraph with arc weights, find a set of arcs containing no directed cycle and having maximum total weight. We investigate this problem from a polyhedral point of view and determine several classes of facets for the associated acyclic subgraph polytope. We also show that the separation problem for the facet defining dicycle inequalities can be solved in polynomial time. This implies that the acyclic subgraph problem can be solved in polynomial time for weakly acyclic digraphs. This generalizes a result of Lucchesi for planar digraphs.     

Recovering signals from inner products involving prolate spheroidals in the presence of jitter

The paper deals with recovering band- and energy-limited signals from a finite set of perturbed inner products involving the prolate spheroidal wavefunctions. The measurement noise (bounded by ) and jitter meant as perturbation of the ends of the integration interval (bounded by ) are considered. The upper and lower bounds on the radius of information are established. We show how the error of the best algorithms depends on and . We prove that jitter causes error of order , where is a bandwidth, which is similar to the error caused by jitter in the case of recovering signals from samples.