On the generalized Ritt problem as a computational problem

The Ritt problem asks if there is an algorithm that decides whether one prime differential ideal is contained in another one if both are given by their characteristic sets. We give several equivalent formulations of this problem. In particular, we show that it is equivalent to testing whether a differential polynomial is a zero divisor modulo a radical differential ideal. The technique used in the proof of this equivalence yields algorithms for computing a canonical decomposition of a radical differential ideal into prime components and a canonical generating set of a radical differential ideal. Both proposed representations of a radical differential ideal are independent of the given set of generators and can be made independent of the ranking.     

On the tour planning problem

Increasingly, tourists are planning trips by themselves using the vast amount of information available on the Web. However, they still expect and want trip plan advisory services. In this paper, we study the tour planning problem in which our goal is to design a tour trip with the most desirable sites, subject to various budget and time constraints. We first establish a framework for this problem, and then formulate it as a mixed integer linear programming problem. However, except when the size of the problem is small, say, with less than 20–30 sites, it is computationally infeasible to solve the mixed-integer linear programming problem. Therefore, we propose a heuristic method based on local search ideas. The method is efficient and provides good approximation solutions. Numerical results are provided to validate the method. We also apply our method to the team orienteering problem, a special case of the tour planning problem which has been considered in the literature, and compare our method with other existing methods. Our numerical results show that our method produces very good approximation solutions with relatively small computational efforts comparing with other existing methods.     

ON THE COMPUTATIONAL COMPLEXITY OF THE MAXIMUM TRADE PROBLEM

ＯＮＴＨＥＣＯＭＰＵＴＡＴＩＯＮＡＬＣＯＭＰＬＥＸＩＴＹＯＦＴＨＥＭＡＸＩＭＵＭＴＲＡＤＥＰＲＯＢＬＥＭＺ．－Ｑ．Ｌｕｏ；Ｄ．Ｌ．ＰＡＲＮＡＳ（ＣｏｍｍｕｎｉｃａｔｉｏｎｓＲｅｓｅａｒｃｈＬａｂｏｒａｔｏｃｙＤｅｐａｒｔｍｅｎｔｏｆＥｌｅｃｔｒｉｃａ...     

Algorithms for the quickest path problem and the reliable quickest path problem

The quickest path problem consists of finding a path in a directed network to transmit a given amount of items from an origin node to a destination node with minimal transmission time, when the transmission time depends on both the traversal times of the arcs, or lead time, and the rates of flow along arcs, or capacity. In telecommunications networks, arcs often also have an associated operational probability of the transmission being fault free. The reliability of a path is defined as the product of the operational probabilities of its arcs. The reliability as well as the transmission time are of interest. In this paper, algorithms are proposed to solve the quickest path problem as well as the problem of identifying the quickest path whose reliability is not lower than a given threshold. The algorithms rely on both the properties of a network which turns the computation of a quickest path into the computation of a shortest path and the fact that the reliability of a path can be evaluated through the reliability of the ordered sequence of its arcs. Other constraints on resources consumed, on the number of arcs of the path, etc. can also be managed with the same algorithms.     

A computational study of solution approaches for the resource constrained elementary shortest path problem

We present the results of a computational investigation of solution approaches for the resource constrained elementary shortest path problem ( $\mathcal{RCESPP}$ ). In particular, the best known algorithms are tested on several problem instances taken from literature. The main aims are to provide a detailed state of the art and to evaluate methods that turn out to be the most promising for solving the problem under investigation. This work represents the first attempt to computationally compare solution approaches for the $\mathcal{RCESPP}$ .     

On the computational complexity of a merge recognition problem

A problem arising from the work of C.A.R. Hoare on parallel programming is that of deciding whether a given string ? is a “merge” of two other given strings σ and τ. We describe a polynomial time algorithm for this problem. This algorithm can easily be extended to check, in polynomial time, whether ? is a merge of any fixed number of strings. The problem for an arbitrary number of strings is shown to be NP-complete and so is unlikely to have a polynomial time algorithm.     

On the second point-to-point undirected shortest simple path problem

We address the determination of the second point-to-point shortest simple path in undirected networks. The effective reduced cost concept is introduced to compute the second best solution. This concept is used to prove that a path tree containing the second point-to-point shortest simple path is adjacent to any shortest path tree. Therefore, this result immediately implies a method requiring O(m) time once that the shortest path tree is obtained on an undirected network with n nodes and m edges.     

On the direct path problem of s-elementary frame wavelets

In this paper, we discuss the path-connectivity between two s-elementary normalized tight frame wavelets via the so-called direct paths. We show that the existence of such a direct path is equivalent to the non-existence of an atom of a σ-algebra defined over the defining sets of the corresponding frame wavelets, using a mapping defined by the natural translation and dilation operations between the sets. In particular, this gives an equivalent condition for the existence of a direct path between two s-elementary wavelets.     

On the K shortest path trees problem

We address the problem of finding the K best path trees connecting a source node with any other non-source node in a directed network with arbitrary lengths. The main result in this paper is the proof that the kth shortest path tree is adjacent to at least one of the previous (k-1) shortest path trees. Consequently, we design an O(f(n,m,C_max)+Km) time and O(K+m) space algorithm to determine the K shortest path trees, in a directed network with n nodes, m arcs and maximum absolute length C_max, where O(f(n,m,C_max)) is the best time needed to solve the shortest simple paths connecting a source node with any other non-source node.     

On the problem of dynamic contact angle

Plane motion of a viscous incompressible fluid bounded by a rectangular rigid wall and a free boundary of constant form is investigated. The free boundary is in contact with the rigid wall at a point which moves along the wall, coming into contact with it at a constant rate. The asymptotics of the velocity field near the point of contact is computed under the assumption that the motion is stationary in the coordinate system attached to the moving free boundary and, that the energy is dissipated as a finite rate.     

Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

When vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the vertices. A common solution technique for this problem is dynamic programming. In this paper we illustrate how the basic dynamic programming algorithm can be improved by bounded bi-directional search and we experimentally evaluate the effectiveness of the enhancement proposed. We consider as benchmark problems the elementary shortest path problems arising as pricing subproblems in branch-and-price algorithms for the capacitated vehicle routing problem, the vehicle routing problem with distribution and collection and the capacitated vehicle routing problem with time windows.     

动态最小费用路在L1模下的逆问题讨论

考察动态最小费用路在L_1模下的逆问题,其中在弧费用的定义中,将弧(i,j)上的运行时间d_(ij)(t)分成最小可能运行时间d_(ij)~*和超出的运行时间(excess time)e_(ij)(t)两部分,弧(i,j)上费用即为两者赋权之和.在逆问题的讨论中考虑先将动态网络中的问题通过时间扩张网络G~T转化为静态问题,然后再利用解线性规划的逆问题的方法来解该动态最短路问题的逆问题.     

Capacity planning by the dynamic multi-resource generalized assignment problem (DMRGAP)

The allocation of available capacity among competing demand and users is a problem encountered in areas such as job shop scheduling, the trucking industry and distributed computer systems. In all these areas a model known as the Multi-Resource Generalized Assignment Problem (MRGAP) has been proposed as a tool to assign available capacity among the competing applications. In this paper we extend the MRGAP model to the case where demand varies over time and capacity assignments are dynamic. We show that the extended model can be used for strategic capacity planning and we develop efficient solution procedures to solve the dynamic version of MRGAP.     

A note on the minimum instantaneous cost path of the dynamic traffic assignment problem

We consider an example to show that the minimum instantaneous cost path principle, as suggested in Friesz et al. [1] for generalising Wardrop's first principle to the dynamic state, may cause some drivers' routes to loop. These looping routes traverse the same link more than once - indeed, in our example six times.The work reported in this paper has been partly funded by the Science and Engineering Research Council of the United Kingdom.     

Hierarchical approach to the process planning problem

A hierarchical approach to the process planning problem in manufacturing systems is presented. The model developed consists of the following three subproblems: (1) the tool path selection, (2) the tool path sequencing and (3) the process selection. These problems lead to three distinct combinatorial optimization problems which are characterized and for which solution procedures are discussed.     

Equivalence of the two-dimensional directed animal problem to a one-dimensional path problem

We introduce a one-to-one correspondence between directed animals on a square lattice and a class of one-dimensional paths. We derive very simply the formulae giving the exact number of directed animals of given size and the average width of such animals. The more surprising result is the fact that the number of compactrooted directed animals of size n is 3^{n− 1}.     

On computational complexity of the electric power flow optimization problem in market environment

Under consideration is the electric power flow optimization problem for an electric power system which typically arises in calculation of electrical power auctions in the “day-ahead” and balancing markets. It was established that the problem of finding a feasible flow in the balancing market is NP-hard in the strong sense even in case of one generator. The problem of finding an optimal flow in the day-ahead market is proved to be NP-hard even with one generator and without controlled cuts.