Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh

Hunsaker and Savelsbergh [B. Hunsaker, M. Savelsbergh, Efficient feasibility testing for dial-a-ride problems, Operations Research Letters 30 (2002) 169-173] discussed feasibility testing for a dial-a-ride problem under maximum wait time and maximum ride time constraints. We show that this feasibility test can be expressed as a shortest path problem in vertex-weighted interval graphs, which leads to a simple linear time algorithm.     

A simple version of Karzanov's blocking flow algorithm

Dinic has shown that the classic maximum flow problem on a graph of n vertices and m edges can be reduced to a sequence of at most n ? 1 so-called ‘blocking flow’ problems on acyclic graphs. For dense graphs, the best time bound known for the blocking flow problems is O(n²). Karzanov devised the first O(n²)-time blocking flow algorithm, which unfortunately is rather complicated. Later Malhotra, Kumar and Maheshwari devise another O(n²)-time algorithm, which is conceptually very simple but has some other drawbacks. In this paper we propose a simplification of Karzanov's algorithm that is easier to implement than Malhotra, Kumar and Maheshwari's method.     

An O(mn log (nU)) time algorithm to solve the feasibility problem

The phase I maximum flow and most positive cut methods are used to solve the feasibility problem. Both of these methods take one maximum flow computation. Thus the feasibility problem can be solved using maximum flow algorithms. Let n and m be the number of nodes and arcs, respectively. In this paper, we present an algorithm to solve the feasibility problem with integer lower and upper bounds. The running time of our algorithm is O(mn log (nU)), where U is the value of maximum upper bound. Our algorithm improves the O(m² log (nU))-time algorithm in [12]. Hence the current algorithm improves the running time in [12] by a factor of n. Sleator and Goldberg’s algorithm is one of the well-known maximum flow algorithms, which runs in O(mn log n) time, see [5]. Under similarity assumption [11], our algorithm runs in O(mn log n) time, which is the running time of Sleator and Goldberg’s algorithm. The merit of our algorithm is that, in the case of infeasibility of the given network, it not only diagnoses infeasibility but also presents some information that is useful to modeler in estimating the maximum cost of adjusting the infeasible network.     

极小化总加权完工时间的Dial-a-Ride问题的在线随机算法

讨论一般度量空间上带单服务器的极小化总加权完工时间在线Dial-a-Ride问题.通过应用贪婪区间的技巧,提出了一个一般在线随机算法.根据这个算法,对于容量为1或者任意容量的一般度量空间上的在线Dial-a-Ride问题能得到一个竞争比为(2+√2)/ln(1+√2)的在线随机算法,这个算法不仅具有当前最好的竞争比,而且也改进了Krumke等人的结果.     

A new full-Newton step <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis>) infeasible interior-point algorithm for semidefinite optimization

Interior-point methods for semidefinite optimization have been studied intensively, due to their polynomial complexity and practical efficiency. Recently, the second author designed a primal-dual infeasible interior-point algorithm with the currently best iteration bound for linear optimization problems. Since the algorithm uses only full Newton steps, it has the advantage that no line-searches are needed. In this paper we extend the algorithm to semidefinite optimization. The algorithm constructs strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem, close to their central paths. Two types of full-Newton steps are used, feasibility steps and (ordinary) centering steps, respectively. The algorithm starts from strictly feasible iterates of a perturbed pair, on its central path, and feasibility steps find strictly feasible iterates for the next perturbed pair. By using centering steps for the new perturbed pair, we obtain strictly feasible iterates close enough to the central path of the new perturbed pair. The starting point depends on a positive number ζ. The algorithm terminates either by finding an ε-solution or by detecting that the primal-dual problem pair has no optimal solution (X ^*,y ^*,S ^*) with vanishing duality gap such that the eigenvalues of X ^* and S ^* do not exceed ζ. The iteration bound coincides with the currently best iteration bound for semidefinite optimization problems.     

Global optimization algorithm for a generalized linear multiplicative programming

This article present a branch and bound algorithm for globally solving generalized linear multiplicative programming problems with coefficients. The main computation involve solving a sequence of linear relaxation programming problems, and the algorithm economizes the required computations by conducting the branch and bound search in R ^p , rather than in R ⁿ , where p is the number of rank and n is the dimension of decision variables. The proposed algorithm will be convergent to the global optimal solution by means of the subsequent solutions of the series of linear relaxation programming problems. Numerical results are given to show the feasibility and effectiveness of the proposed algorithm.     

An adaptive <Emphasis Type="Italic">C</Emphasis><Superscript>0</Superscript>IPG method for the Helmholtz transmission eigenvalue problem

The interior penalty methods using C⁰ Lagrange elements (C⁰IPG) developed in the recent decade for the fourth order problems are an interesting topic in academia at present. In this paper, we discuss the adaptive fashion of C⁰IPG method for the Helmholtz transmission eigenvalue problem. We give the a posteriori error indicators for primal and dual eigenfunctions, and prove their reliability and efficiency. We also give the a posteriori error indicator for eigenvalues and design a C⁰IPG adaptive algorithm. Numerical experiments show that this algorithm is efficient and can get the optimal convergence rate.     

Exact algorithms for dominating set

The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems like Dominating Set and Independent Set. This approach is used in this paper to obtain a faster exact algorithm for Dominating Set. We obtain this algorithm by considering a series of branch and reduce algorithms. This series is the result of an iterative process in which a mathematical analysis of an algorithm in the series with measure and conquer results in a convex or quasiconvex programming problem. The solution, by means of a computer, to this problem not only gives a bound on the running time of the algorithm, but can also give an indication on where to look for a new reduction rule, often giving a new, possibly faster algorithm. As a result, we obtain an O(1.4969ⁿ) time and polynomial space algorithm.     

A weighted independent even factor algorithm

An even factor in a digraph is a vertex-disjoint collection of directed cycles of even length and directed paths. An even factor is called independent if it satisfies a certain matroid constraint. The problem of finding an independent even factor of maximum size is a common generalization of the nonbipartite matching and matroid intersection problems. In this paper, we present a primal-dual algorithm for the weighted independent even factor problem in odd-cycle-symmetric weighted digraphs. Cunningham and Geelen have shown that this problem is solvable via valuated matroid intersection. Their method yields a combinatorial algorithm running in O(n ³ γ +? n ⁶ m) time, where n and m are the number of vertices and edges, respectively, and γ is the time for an independence test. In contrast, combining the weighted even factor and independent even factor algorithms, our algorithm works more directly and runs in O(n ⁴ γ?+?n ⁵) time. The algorithm is fully combinatorial, and thus provides a new dual integrality theorem which commonly extends the total dual integrality theorems for matching and matroid intersection.     

A new algorithm for minimizing makespan, <Emphasis Type="Italic">C</Emphasis><Subscript>max</Subscript>, in blocking flow-shop problem through slowing down the operations

In this paper, a new algorithm with complexity O(nm²) is presented, which finds the optimal makespan, C_max, for a blocking flow-shop problem by slowing down the operations of a no-wait flow-shop problem, F _m ∣no-wait∣C_max, for a given sequence where restriction on the slowing down is committed. However, the problem with performance measure makespan, C_max, in a non-cyclic environment, is a special case of cyclic problem with cycle time, C _t , as its performance measure. This new algorithm is much faster than the previously developed algorithms for cyclical scheduling problems.     

On some algorithmic problems regarding the hairpin completion

We consider a few algorithmic problems regarding the hairpin completion. The first problem we consider is the membership problem of the hairpin and iterated hairpin completion of a language. We propose an O(nf(n)) and O(n²f(n)) time recognition algorithm for the hairpin completion and iterated hairpin completion, respectively, of a language recognizable in O(f(n)) time. We show that the n factor is not needed in the case of hairpin completion of regular and context-free languages. The n² factor is not needed in the case of iterated hairpin completion of context-free languages, but it is reduced to n in the case of iterated hairpin completion of regular languages. We then define the hairpin completion distance between two words and present a cubic time algorithm for computing this distance. A linear time algorithm for deciding whether or not the hairpin completion distance with respect to a given word is connected is also discussed. Finally, we give a short list of open problems which appear attractive to us.     

Simulated annealing for the unconstrained quadratic pseudo-Boolean function

In this paper, we develop a simulated annealing (SA) based heuristic for the unconstrained quadratic pseudo-Boolean function. An algorithm that solves the problem in O(n²) at each temperature of the cooling schedule is given. The performance of SA based heuristic is compared with existing bounding algorithms for this problem. Computational results and comparisons on several hundred test problems demonstrate the efficiency of our heuristic in terms of solution quality and computational time. A new set of hard test problems with their best solution is provided to facilitate future comparison.     

A fast boundary element algorithm for time-dependant potential problems

The numerical solution of time-dependant potential problems via the boundary element has been crippled by the high computational cost due to the inherent time history constraint in the integral representation. Using a boundary-only formulation, the time integrations, at any instant in time, have to be evaluated starting from the initial time. This time-history dependence becomes impractical and inadequate for problems where computations are to be performed for extended times. This also made the boundary element uncompetitive compared to the domain-mesh based methods, such as finite difference and finite element methods, for the solution of transient potential problems. Generally, the evaluation of the potential at N domain points using M boundary points at the Kth time step requires an amount of computer operations of the order O(KM²+KNM). This paper presents an algorithm which requires a computational cost of the order of only O(M²+NM), where the dependence from the past K-steps is removed. The algorithm combines the boundary element method and a scheme, which uses virtual collocation points and radial basis functions to approximate the domain integral.     

A faster algorithm for a due date assignment problem with tardy jobs

The single-machine due date assignment problem with the weighted number of tardy jobs objective, (the TWNTD problem), and its generalization with resource allocation decisions and controllable job processing times have been solved in O(n⁴) time by formulating and solving a series of assignment problems. In this note, a faster O(n²) dynamic programming algorithm is proposed for the TWNTD problem and for its controllable processing times generalization in the case of a convex resource consumption function.     

Dynamic programming based metaheuristics for the dial-a-ride problem

The organization of a specialized transportation system to perform transports for elderly and handicapped people is usually modeled as dial-a-ride problem. Users place transportation requests with specified pickup and delivery locations and times. The requests have to be completed under user inconvenience considerations by a specified fleet of vehicles. In the dial-a-ride problem, the aim is to minimize the total travel times respecting the given time windows, the maximum user ride times, and the vehicle restrictions. This paper introduces a dynamic programming algorithm for the dial-a-ride problem and demonstrates its effective application in (hybrid) metaheuristic approaches. Compared to most of the works presented in literature, this approach does not make use of any (commercial) solver. We present an exact dynamic programming algorithm and a dynamic programming based metaheuristic, which restricts the considered solution space. Then, we propose a hybrid metaheuristic algorithm which integrates the dynamic programming based algorithms into a large neighborhood framework. The algorithms are tested on a given set of benchmark instances from the literature and compared to a state-of-the-art hybrid large neighborhood search approach.     

An O(n2) simplex algorithm for a class of linear programs with tree structure

In connection with the optimal design of centralized circuit-free networks linear 0–1 programming problems arise which are related to rooted trees. For each problem the variables correspond to the edges of a given rooted tree T. Each path from a leaf to the root of T, together with edge weights, defines a linear constraint, and a global linear objective is to be maximized. We consider relaxations of such problems where the variables are not restricted to 0 or 1 but are allowed to vary continouosly between these bounds. The values of the optimal solutions of such relaxations may be used in a branch and bound procedure for the original 0–1 problem. While in [10] a primal algorithm for these relaxations is discussed, in this paper, we deal with the dual linear program and present a version of the simplex algorithm for its solution which can be implemented to run in time O(n²). For balanced trees T this time can be reduced to O(n log n).     

The just-in-time scheduling problem in a flow-shop scheduling system

We study the problem of maximizing the weighted number of just-in-time (JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O(n³) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP-hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O(n³) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O(n log n) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O(mn²) time optimization algorithm.     

An algorithm for minimizing flow time and maximum earliness on a single machine

This study presents an algorithm for efficient scheduling in terms of total flow time and maximum earliness. All the algorithms in the literature for solving this problem are based on heuristic procedures, and cannot necessarily generate all efficient schedules. This study shows that this problem can actually be solved in pseudo-polynomial time, and develops an algorithm for so doing. The complexity of the algorithm is O (n²p? log n). Its computational performance in solving problems of various sizes is determined.     

Scheduling linear deteriorating jobs to minimize the number of tardy jobs

In this paper a problem of scheduling a single machine under linear deterioration which aims at minimizing the number of tardy jobs is considered. According to our assumption, processing time of each job is dependent on its starting time based on a linear function where all the jobs have the same deterioration rate. It is proved that the problem is NP-hard; hence a branch and bound procedure and a heuristic algorithm with O(n ²) is proposed where the heuristic one is utilized for obtaining the upper bound of the B&B procedure. Computational results for 1,800 sample problems demonstrate that the B&B method can solve problems with 28 jobs quickly and in some other groups larger problems are also solved. Generally, B&B method can optimally solve 85% of the samples which shows high performance of the proposed method. Also it is shown that the average value of the ratio of optimal solution to the heuristic algorithm result with the objective ??(1 ? Ui) is at most 1.11 which is more efficient in comparison to other proposed algorithms in related studies in the literature.     

Adaptive Itô-Taylor algorithm can optimally approximate the Itô integrals of singular functions

We deal with numerical approximation of stochastic Itô integrals of singular functions. We first consider the regular case of integrands belonging to the Hölder class with parameters r and ?. We show that in this case the classical Itô-Taylor algorithm has the optimal error Θ(n^−(r+?)). In the singular case, we consider a class of piecewise regular functions that have continuous derivatives, except for a finite number of unknown singular points. We show that any nonadaptive algorithm cannot efficiently handle such a problem, even in the case of a single singularity. The error of such algorithm is no less than n^{−min{1/2,r+?}}. Therefore, we must turn to adaptive algorithms. We construct the adaptive Itô-Taylor algorithm that, in the case of at most one singularity, has the optimal error O(n^−(r+?)). The best speed of convergence, known for regular functions, is thus preserved. For multiple singularities, we show that any adaptive algorithm has the error Ω(n^{−min{1/2,r+?}}), and this bound is sharp.