Efficient interval partitioning for constrained global optimization

A new efficient interval partitioning approach to solve constrained global optimization problems is proposed. This involves a new parallel subdivision direction selection method as well as an adaptive tree search. The latter explores nodes (intervals in variable domains) using a restricted hybrid depth-first and best-first branching strategy. This hybrid approach is also used for activating local search to identify feasible stationary points. The new tree search management technique results in improved performance across standard solution and computational indicators when compared to previously proposed techniques. On the other hand, the new parallel subdivision direction selection rule detects infeasible and suboptimal boxes earlier than existing rules, and this contributes to performance by enabling earlier reliable deletion of such subintervals from the search space.     

A two pass heuristic algorithm for scheduling ‘blocked out’ units in continuous process industry

This paper addresses the problem of scheduling cascaded ‘blocked out’ continuous processing units separated by finite capacity storage tanks. The raw materials for the product lines arrive simultaneously on the input side of the first unit. But every unit can process only one product line at a time, thus giving rise to the possibility of spillage of raw material due to limited storage capacity. The need to process multiple product lines and the added constraint of multiple intermediate upliftment dates aggravate the problem. This problem is quite common in petrochemical industry. The paper provides a MINLP (Mixed Integer Non-Linear Programming) formulation of the problem. However, for any realistic scheduling horizon, the size of the problem is too large to be solved by standard packages. We have proposed a depth first branch and bound algorithm, guided by heuristics, to help planners in tackling the problem. The suggested algorithm could output near optimal solutions for scheduling horizons of 30 time periods when applied to real life situations involving 3 units and 3 product lines. Preliminary version of the paper appeared in the proceedings of MISTA, 2005.     

A general model for cyclic machine scheduling problems

A general framework for modeling and solving cyclic scheduling problems is presented. The objective is to minimize the cycle time. The model covers different cyclic versions of the job-shop problem found in the literature, robotic cell problems, the single hoist scheduling problem and tool transportation between the machines.It is shown that all these problems can be formulated as mixed integer linear programs which have a common structure. Small instances are solved with CPLEX. For larger instances tabu search procedures have been developed. The main ideas of these methods are indicated.     

A descent method with inexact linear search for nonsmooth equilibrium problems

A descent method with respect to the gap function is formulated and justified for the nonsmooth equilibrium problem. It uses the procedure of inexact linear search of the Armijo type. The proposed method converges under the same assumptions as the methods with exact linear search.     

Backtracking and exchange of information: Methods to enhance a beam search algorithm for assembly line scheduling

Beam search (BS) is used as a heuristic to solve various combinatorial optimization problems, ranging from scheduling to assembly line balancing. In this paper, we develop a backtracking and an exchange-of-information (EOI) procedure to enhance the traditional beam search method. The backtracking enables us to return to previous solution states in the search process with the expectation of obtaining better solutions. The EOI is used to transfer information accumulated in a beam to other beams to yield improved solutions.     

A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows

This paper presents a solution methodology for the heterogeneous fleet vehicle routing problem with time windows. The objective is to minimize the total distribution costs, or similarly to determine the optimal fleet size and mix that minimizes both the total distance travelled by vehicles and the fixed vehicle costs, such that all problem’s constraints are satisfied. The problem is solved using a two-phase solution framework based upon a hybridized Tabu Search, within a new Reactive Variable Neighborhood Search metaheuristic algorithm. Computational experiments on benchmark data sets yield high quality solutions, illustrating the effectiveness of the approach and its applicability to realistic routing problems. This work is supported by the General Secretariat for Research and Technology of the Hellenic Ministry of Development under contract GSRT NM-67.     

Adaptive nonmonotone line search method for unconstrained optimization

In this paper, an adaptive nonmonotone line search method for unconstrained minimization problems is proposed. At every iteration, the new algorithm selects only one of the two directions: a Newton-type direction and a negative curvature direction, to perform the line search. The nonmonotone technique is included in the backtracking line search when the Newton-type direction is the search direction. Furthermore, if the negative curvature direction is the search direction, we increase the steplength under certain conditions. The global convergence to a stationary point with second-order optimality conditions is established. Some numerical results which show the efficiency of the new algorithm are reported.      

Two local search approaches for solving real-life car sequencing problems

The NP-hard problem of car sequencing appears as the heart of the logistic process of many car manufacturers. The subject of the ROADEF’2005 challenge addressed a car sequencing problem proposed by the car manufacturer RENAULT, more complex than the academic problem generally addressed in the literature. This paper describes two local search approaches for this problem. In the first part, a new approach by very large-scale neighborhood search is presented. This approach, designed during the qualification stage preceding the final, is based on an original integer linear programming formulation. The second part is dedicated to the approach which enabled us to win the ROADEF’2005 challenge. Inspired by the latest works on the subject, this one is based on very fast explorations of small neighborhoods. Our contribution here is mainly algorithmic, in particular by showing how much exploiting invariants speeds up the neighborhood evaluation and contributes to the diversification of the search. Finally, the two approaches are compared and discussed through an extensive computational study on RENAULT’s benchmarks. The main conclusion drawn at this point is that sophisticated metaheuristics are useless to solve car sequencing problems. More generally, our victory on ROADEF’2005 challenge demonstrates that algorithmic aspects, sometimes neglected, remain the key ingredients for designing and engineering high-performance local search heuristics.     

A variable neighborhood search for the capacitated arc routing problem with intermediate facilities

The capacitated arc routing problem (CARP) focuses on servicing edges of an undirected network graph. A wide spectrum of applications like mail delivery, waste collection or street maintenance outlines the relevance of this problem. A realistic variant of the CARP arises from the need of intermediate facilities (IFs) to load up or unload the service vehicle and from tour length restrictions. The proposed Variable Neighborhood Search (VNS) is a simple and robust solution technique which tackles the basic problem as well as its extensions. The VNS shows excellent results on four different benchmark sets. Particularly, for all 120 instances the best known solution could be found and in 71 cases a new best solution was achieved.     

Simple ingredients leading to very efficient heuristics for the maximum clique problem

Starting from an algorithm recently proposed by Pullan and Hoos, we formulate and analyze iterated local search algorithms for the maximum clique problem. The basic components of such algorithms are a fast neighbourhood search (not based on node evaluation but on completely random selection) and simple, yet very effective, diversification techniques and restart rules. A detailed computational study is performed in order to identify strengths and weaknesses of the proposed algorithms and the role of the different components on several classes of instances. The tested algorithms are very fast and reliable: most of the DIMACS benchmark instances are solved within very short CPU times. For one of the hardest tests, a new putative optimum was discovered by one of our algorithms. Very good performances were also shown on recently proposed and more difficult instances. It is important to remark that the heuristics tested in this paper are basically parameter free (the appropriate value for the unique parameter is easily identified and was, in fact, the same value for all problem instances used in this paper).