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 general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem

We present a variable neighborhood search approach for solving the one-commodity pickup-and-delivery travelling salesman problem. It is characterized by a set of customers such that each of the customers either supplies (pickup customers) or demands (delivery customers) a given amount of a single product, and by a vehicle, whose given capacity must not be exceeded, that starts at the depot and must visit each customer only once. The objective is to minimize the total length of the tour. Thus, the considered problem includes checking the existence of a feasible travelling salesman’s tour and designing the optimal travelling salesman’s tour, which are both NP-hard problems. We adapt a collection of neighborhood structures, k-opt, double-bridge and insertion operators mainly used for solving the classical travelling salesman problem. A binary indexed tree data structure is used, which enables efficient feasibility checking and updating of solutions in these neighborhoods. Our extensive computational analysis shows that the proposed variable neighborhood search based heuristics outperforms the best-known algorithms in terms of both the solution quality and computational efforts. Moreover, we improve the best-known solutions of all benchmark instances from the literature (with 200 to 500 customers). We are also able to solve instances with up to 1000 customers.     

Harmonic Properties of the Logarithmic Potential and the Computability of Elliptic Fekete Points

We investigate the properties of the function sending each N-tuple of points to minus the logarithm of the product of their mutual distances. We prove that, as a function defined on the product of N spheres, this function is subharmonic, and indeed its (Riemannian) Laplacian is constant. We also prove a mean value equality and an upper bound on the derivative of the function. We use these results to get sharp upper bounds for the precision needed to describe an approximation to elliptic Fekete points (in the sense demanded by Smale’s 7th problem). We also conclude that Smale’s 7th problem has solutions given by rational spherical points of bounded (small) bit length, proving that there exists an exponential running time algorithm which solves it on the Turing machine model.     

Elliptic logarithms,diophantine approximation and the Birch and Swinnerton-Dyer conjecture

Most, if not all, unconditional results towards the abc-conjecture rely ultimately on classical Baker’s method. In this article, we turn our attention to its elliptic analogue. Using the elliptic Baker’s method, we have recently obtained a new upper bound for the height of the S-integral points on an elliptic curve. This bound depends on some parameters related to the Mordell-Weil group of the curve. We deduce here a bound relying on the conjecture of Birch and Swinnerton-Dyer, involving classical, more manageable quantities. We then study which abc-type inequality over number fields could be derived from this elliptic approach.     

Integrating heuristic information into exact methods: The case of the vertex p-centre problem

We solve the vertex p-centre problem optimally using an exact method that considers both upper and lower bounds as part of its search engine. Tight upper bounds are generated quickly via an efficient three-level heuristic, which are then used to derive potential ‘lower bounds’ accordingly. These two pieces of information when used together make our chosen exact method more efficient at obtaining optimal solutions relatively quickly. The proposed implementation produced excellent results when tested on the OR Library data set. This integrated approach can be adopted for those exact methods that consider both upper and lower bounds within their search engine and hence provide a wider spectrum of applicability in other hard combinatorial problems.     

Optimal allocation and processing time decisions on non-identical parallel CNC machines: ϵ-constraint approach

When the processing times of jobs are controllable, selected processing times affect both the manufacturing cost and the scheduling performance. A well known example for such a case that this paper specifically deals with is the turning operation on a CNC machine. Manufacturing cost of a turning operation is a nonlinear convex function of its processing time. In this paper, we deal with making optimal machine-job assignments and processing time decisions so as to minimize total manufacturing cost while the makespan being upper bounded by a known value, denoted as ?-constraint approach for a bicriteria problem. We then give optimality properties for the resulting single criterion problem. We provide alternative methods to compute cost lower bounds for partial schedules, which are used in developing an exact (branch and bound) algorithm. For the cases where the exact algorithm is not efficient in terms of computation time, we present a recovering beam search algorithm equipped with an improvement search procedure. In order to find improving search directions, the improvement search algorithm uses the proposed cost bounding properties. Computational results show that our lower bounding methods in branch and bound algorithm achieve a significant reduction in the search tree size that we need to traverse. Also, our recovering beam search and improvement search heuristics achieve solutions within 1% of the optimum on the average while they spent much less computational effort than the exact algorithm.     

Branch and bound crossed with GA to solve hybrid flowshops

This article deals with an optimal methods for solving a k-stage hybrid flowshop scheduling problem. This problem is known to be NP-hard. In 1991, Brah and Hunsucker proposed a branch and bound algorithm to solve this problem. However, for some medium size problems, the computation time is not acceptable. The aim of this article is to present an improvement of this algorithm. As a matter of fact, we prove that the value of their lower bound (LB) may decrease along a path of the search tree. First of all, we present an improvement of their LB. Then, we introduce several heuristics at the beginning of the search in order to compute an initial upper bound and genetic algorithm (GA) to improve during the search the value of the upper bound. More precisely, our GA takes into account the set of partial decisions made by the branch and bound and builds a series of populations of complete solutions with the aim of improving the upper bound (the best found criterion value corresponding to a complete solution). Experimentation show that the optimality of branch and bound is more often reached and the value of criterion is improved when our improvements are taken into account.     

A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem

We present a new general variable neighborhood search approach for the uncapacitated single allocation p-hub median problem in networks. This NP hard problem is concerned with locating hub facilities in order to minimize the traffic between all origin-destination pairs. We use three neighborhoods and efficiently update data structures for calculating new total flow in the network. In addition to the usual sequential strategy, a new nested strategy is proposed in designing a deterministic variable neighborhood descent local search. Our experimentation shows that general variable neighborhood search based heuristics outperform the best-known heuristics in terms of solution quality and computational effort. Moreover, we improve the best-known objective values for some large Australia Post and PlanetLab instances. Results with the new nested variable neighborhood descent show the best performance in solving very large test instances.     

An effective VNS for the capacitated p-median problem

In the capacitated p-median problem (CPMP), a set of n customers is to be partitioned into p disjoint clusters, such that the total dissimilarity within each cluster is minimized subject to constraints on maximum cluster capacity. Dissimilarity of a cluster is the sum of the dissimilarities between each customer who belongs to the cluster and the median associated with the cluster. An effective variable neighbourhood search heuristic for this problem is proposed. The heuristic is characterized by the use of easily computed lower bounds to assess whether undertaking computationally expensive calculation of the worth of moves, within the neighbourhood search, is necessary. The small proportion of moves that need to be assessed fully are then evaluated by an exact solution of a relatively small subproblem. Computational results on five standard sets of benchmark problem instances show that the heuristic finds all the best-known solutions. For one instance, the previously best-known solution is improved, if only marginally.     

An upper bound on the number of high-dimensional permutations

What is the higher-dimensional analog of a permutation? If we think of a permutation as given by a permutation matrix, then the following definition suggests itself: A d-dimensional permutation of order n is an n×n×...×n=[n] ^d+1 array of zeros and ones in which every line contains a unique 1 entry. A line here is a set of entries of the form {(x ₁,...,x _i?1,y,x _i+1,...,x _d+1)|n≥y≥1} for some index d+1≥i≥1 and some choice of x _j ∈ [n] for all j ≠ i. It is easy to observe that a one-dimensional permutation is simply a permutation matrix and that a two-dimensional permutation is synonymous with an order-n Latin square. We seek an estimate for the number of d-dimensional permutations. Our main result is the following upper bound on their number $$\left( {(1 + o(1))\frac{n} {{e^d }}} \right)^{n^d } .$$ We tend to believe that this is actually the correct number, but the problem of proving the complementary lower bound remains open. Our main tool is an adaptation of Brégman’s [1] proof of the Minc conjecture on permanents. More concretely, our approach is very close in spirit to Schrijver’s [11] and Radhakrishnan’s [10] proofs of Brégman’s theorem.     

Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: properties and algorithms

The problem (P) addressed here is a special set partitioning problem with two additional non-trivial constraints. A Lagrangean Relaxation (LR_u) is proposed to provide a lower bound to the optimal solution to this problem. This Lagrangean relaxation is accomplished by a subgradient optimization procedure which solves at each iteration a special 0–1 knapsack problem (KP-k). We give two procedures to solve (KP-k), namely an implicity enumeration algorithm and a column generation method. The approach is promising for it provides feasible integer solutions to the side constraints that will hopefully be optimal to most of the instances of the problem (P). Properties of the feasible solutions to (KP-k) are highlighted and it is shown that the linear programming relaxation to this problem has a worst case time bound of order O(n³).     

Two phased hybrid local search for the periodic capacitated arc routing problem

The periodic capacitated arc routing problem (PCARP) is a challenging general model with important applications. The PCARP has two hierarchical optimization objectives: a primary objective of minimizing the number of vehicles (F_v) and a secondary objective of minimizing the total cost (F_c). In this paper, we propose an effective two phased hybrid local search (HLS) algorithm for the PCARP. The first phase makes a particular effort to optimize the primary objective while the second phase seeks to further optimize both objectives by using the resulting number of vehicles of the first phase as an upper bound to prune the search space. For both phases, combined local search heuristics are devised to ensure an effective exploration of the search space. Experimental results on 63 benchmark instances demonstrate that HLS performs remarkably well both in terms of computational efficiency and solution quality. In particular, HLS discovers 44 improved best known values (new upper bounds) for the total cost objective F_c while attaining all the known optimal values regarding the objective of the number of vehicles F_v. To our knowledge, this is the first PCARP algorithm reaching such a performance. Key components of HLS are analyzed to better understand their contributions to the overall performance.     

Computing the lower and upper bounds of Laplace eigenvalue problem: by combining conforming and nonconforming finite element methods

We introduce some ways to compute the lower and upper bounds of the Laplace eigenvalue problem.By using the special nonconforming finite elements,i.e.,enriched Crouzeix-Raviart element and extended Q1ro t,we get the lower bound of the eigenvalue.Additionally,we use conforming finite elements to do the postprocessing to get the upper bound of the eigenvalue,which only needs to solve the corresponding source problems and a small eigenvalue problem if higher order postprocessing method is implemented.Thus,we can obtain the lower and upper bounds of the eigenvalues simultaneously by solving eigenvalue problem only once.Some numerical results are also presented to demonstrate our theoretical analysis.     

On the deque conjecture for the splay algorithm

Splay is a simple, efficient algorithm for searching binary search trees, devised by Sleator and Tarjan, that reorganizes the tree after each search by means of rotations. An open conjecture of Sleator and Tarjan states that Splay is, in essence, the fastest algorithm for processing any sequence of search operations on a binary search tree, using only rotations to reorganize the tree. Tarjan proved a basic special case of this conjecture, called theScanning Theorem, and conjectured a more general special case, called theDeque Conjecture. The Deque Conjecture states that Splay requires linear time to process sequences of deque operations on a binary tree. We prove the following results:

1. Almost tight lower and upper bounds on the maximum numbers of occurrences of various types of right rotations in a sequence of right rotations performed on a binary tree. In particular, the lower bound for right 2-turns refutes Sleator's Right Turn Conjecture.
2. A linear times inverse Ackerman upper bound for the Deque Conjecture. This bound is derived using the above upper bounds.
3. Two new proofs of the Scanning Theorem, one, a simple potential-based proof that solves Tarjan's problem of finding a potential-based proof for the theorem, the other, an inductive proof that generalizes the theorem.

     

A powerful route minimization heuristic for the vehicle routing problem with time windows

We suggest an efficient route minimization heuristic for the vehicle routing problem with time windows. The heuristic is based on the ejection pool, powerful insertion and guided local search strategies. Experimental results on the Gehring and Homberger’s benchmarks demonstrate that our algorithm outperforms previous approaches and found 18 new best-known solutions.     

A competition between Fujita and Strauss type exponents for blow-up of semi-linear wave equations with scale-invariant damping and mass

We obtain a blow-up result for solutions to a semi-linear wave equation with scale-invariant dissipation and mass and power non-linearity, in the case in which the model has a “wave like” behavior. We perform a change of variables that transforms our starting equation in a strictly hyperbolic semi-linear wave equation with time-dependent speed of propagation. Applying Kato's lemma we prove a blow-up result for solutions to the transformed equation under some assumptions on the initial data. The limit case, that is, when the exponent p is exactly equal to the upper bound of the range of admissible values of p yielding blow-up needs special considerations. In this critical case an explicit integral representation formula for solutions of the corresponding linear Cauchy problem in 1d is derived. Finally, carrying out the inverse change of variables we get a non-existence result for global (in time) solutions to the original model.     

Job-shop local-search move evaluation without direct consideration of the criterion’s value

This article focuses on the evaluation of moves for the local search of the job-shop problem with the makespan criterion. We reason that the omnipresent ranking of moves according to their resulting value of a criterion function makes the local search unnecessarily myopic. Consequently, we introduce an alternative evaluation that relies on a surrogate quantity of the move’s potential, which is related to, but not strongly coupled with, the bare criterion. The approach is confirmed by empirical tests, where the proposed evaluator delivers a new upper bound on the well-known benchmark test yn2. The line of the argumentation also shows that by sacrificing accuracy the established makespan estimators unintentionally improve on the move evaluation in comparison to the exact makespan calculation, in contrast to the belief that the reliance on estimation degrades the optimization results.     

Pareto optima for total weighted completion time and maximum lateness on a single machine

We consider the single-machine bicriterion scheduling problem of enumerating the Pareto-optimal sequences with respect to the total weighted completion time and the maximum lateness objectives. We show that the master sequence concept originally introduced for 1|r_j|∑w_jU_j by Dauzère-Pérès and Sevaux is also applicable to our problem and a large number of other sequencing problems. Our unified development is based on exploiting common order-theoretic structures present in all these problems. We also show that the master sequence implies the existence of global dominance orders for these scheduling problems. These dominance results were incorporated into a new branch and bound algorithm, which was able to enumerate all the Pareto optima for over 90% of the 1440 randomly generated problems with up to n=50 jobs. The identification of each Pareto optimum implicitly requires the optimal solution of a strongly NP-hard problem. The instances solved had hundreds of these Pareto solutions and to the best of our knowledge, this is the first algorithm capable of completely enumerating all Pareto sequences within reasonable time and space for a scheduling problem with such a large number of Pareto optima.     

Upper bounds for the first zeros of Bessel functions

An upper bound for the first positive zero of the Bessel functions of first kind J_μ(z) for μ > −1 is given. This upper bound is better than a number of upper bounds found recently by several authors. The upper bound given in this paper follows from a step of the Ritz's approximation method, applied to the eigenvalue problem of a compact self-adjoint operator, defined on an abstract separable Hilbert space. Some advantages of this method in comparison with other approximation methods are presented.     

On the structure of solutions to a class of quasilinear elliptic Neumann problems

We study the structure of positive solutions to the equation ?^mΔ_mu-u^m-1+f(u)=0 with homogeneous Neumann boundary condition. First, we show the existence of a mountain-pass solution and find that as ?→0⁺ the mountain-pass solution develops into a spike-layer solution. Second, we prove that there is an uniform upper bound independent of ? for any positive solution to our problem. We also present a Harnack-type inequality for the positive solutions. Finally, we show that if 1<m?2 holds and ? is sufficiently large, any positive solution must be a constant.