Local search and suffix tree for car-sequencing problem with colors

This paper describes an approximation solution method for the car sequencing problem with colors. Firstly, we study the optimality of problems with a single ratio constraint. This study also introduces a data structure for efficient calculation of the penalties related to ratio constraints. We describe the constructive greedy algorithm and variable neighborhood search adjusted for the problem with colors. Tabu metaheuristic is used to improve the results obtained by VNS. We then represent the cars with their constraints as letters over an alphabet and apply the algorithm to spell the motifs in order to improve the number of batch colors without decreasing the costs associated to the set of ratio constraints. The algorithm achieves 19 out of the 64 best results for instance sets A and B. These instances are the reference instances for Challenge ROADEF.     

A column generation approach to train timetabling on a corridor

We propose heuristic and exact algorithms for the (periodic and non-periodic) train timetabling problem on a corridor that are based on the solution of the LP relaxation of an ILP formulation in which each variable corresponds to a full timetable for a train. This is in contrast with previous approaches to the same problem, which were based on ILP formulations in which each variable is associated with a departure and/or arrival of a train at a specific station in a specific time instant, whose LP relaxation is too expensive to be solved exactly. Experimental results on real-world instances of the problem show that the proposed approach is capable of producing heuristic solutions of better quality than those obtained by these previous approaches, and of solving some small-size instances to proven optimality.      

A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems

This paper presents a hybrid multi-objective model that combines integer programming (IP) and variable neighbourhood search (VNS) to deal with highly-constrained nurse rostering problems in modern hospital environments. An IP is first used to solve the subproblem which includes the full set of hard constraints and a subset of soft constrains. A basic VNS then follows as a postprocessing procedure to further improve the IP’s resulting solutions. The satisfaction of the excluded constraints from the preceding IP model is the major focus of the VNS. Very promising results are reported compared with a commercial genetic algorithm and a hybrid VNS approach on real instances arising in a Dutch hospital. The comparison results demonstrate that our hybrid approach combines the advantages of both the IP and the VNS to beat other approaches in solving this type of problems. We also believe that the proposed methodology can be applied to other resource allocation problems with a large number of constraints.     

Hybrid variable neighbourhood approaches to university exam timetabling

In this paper, we investigate variable neighbourhood search (VNS) approaches for the university examination timetabling problem. In addition to a basic VNS method, we introduce variants of the technique with different initialisation methods including a biased VNS and its hybridisation with a Genetic Algorithm. A number of different neighbourhood structures are analysed. It is demonstrated that the proposed technique is able to produce high quality solutions across a wide range of benchmark problem instances. In particular, we demonstrate that the Genetic Algorithm, which intelligently selects appropriate neighbourhoods to use within the biased VNS, produces the best known results in the literature, in terms of solution quality, on some of the benchmark instances. However, it requires relatively large amount of computational time. Possible extensions to this overall approach are also discussed.     

Lower bounds for the ITC-2007 curriculum-based course timetabling problem

This paper describes an approach for generating lower bounds for the curriculum-based course timetabling problem, which was presented at the International Timetabling Competition (ITC-2007, Track 3). So far, several methods based on integer linear programming have been proposed for computing lower bounds of this minimization problem. We present a new partition-based approach that is based on the “divide and conquer” principle. The proposed approach uses iterative tabu search to partition the initial problem into sub-problems which are solved with an ILP solver. Computational outcomes show that this approach is able to improve on the current best lower bounds for 12 out of the 21 benchmark instances, and to prove optimality for 6 of them. These new lower bounds are useful to estimate the quality of the upper bounds obtained with various heuristic approaches.     

Neighborhood Portfolio Approach for Local Search Applied to Timetabling Problems

A recent trend in local search concerns the exploitation of several different neighborhoods so as to increase the ability of the algorithm to navigate the search space. In this work we investigate a hybridization technique, that we call Neighborhood Portfolio Approach, that consists in the interleave of local search techniques based on various combinations of neighborhoods. In particular, we are able to select the most effective search technique through a systematic analysis of all meaningful combinations built upon a set of basic neighborhoods. The proposed approach is applied to two practical problems belonging to the timetabling family, and systematically tested and compared on real-world instances. The experimental analysis shows that our approach leads to automatic design of new algorithms that provide better results than basic local search techniques.     

The Parallel Variable Neighborhood Search for the p-Median Problem

The Variable Neighborhood Search (VNS) is a recent metaheuristic that combines series of random and improving local searches based on systematically changed neighborhoods. When a local minimum is reached, a shake procedure performs a random search. This determines a new starting point for running an improving search. The use of interchange moves provides a simple implementation of the VNS algorithm for the p-Median Problem. Several strategies for the parallelization of the VNS are considered and coded in C using OpenMP. They are compared in a shared memory machine with large instances.     

A combined local search and integer programming approach to the traveling tournament problem

The traveling tournament problem is a well-known combinatorial optimization problem with direct applications to sport leagues scheduling, that sparked intensive algorithmic research over the last decade. With the Challenge Traveling Tournament Instances as an established benchmark, the most successful approaches to the problem use meta-heuristics like tabu search or simulated annealing, partially heavily parallelized. Integer programming based methods on the other hand are hardly able to tackle larger benchmark instances. In this work we present a hybrid approach that draws on the power of commercial integer programming solvers as well as the speed of local search heuristics. Our proposed method feeds the solution of one algorithm phase to the other one, until no further improvements can be made. The applicability of this method is demonstrated experimentally on the galaxy instance set, resulting in currently best known solutions for most of the considered instances.     

MIP approaches for the integrated berth allocation and quay crane assignment and scheduling problem

In this paper we consider an integrated berth allocation and quay crane assignment and scheduling problem motivated by a real case where a heterogeneous set of cranes is considered. A first mathematical model based on the relative position formulation (RPF) for the berth allocation aspects is presented. Then, a new model is introduced to avoid the big-M constraints included in the RPF. This model results from a discretization of the time and space variables. For the new discretized model several enhancements, such as valid inequalities, are introduced. In order to derive good feasible solutions, a rolling horizon heuristic (RHH) is presented. A branch and cut approach that uses the enhanced discretized model and incorporates the upper bounds provided by the RHH solution is proposed. Computational tests are reported to show (i) the quality of the linear relaxation of the enhanced models; (ii) the effectiveness of the exact approach to solve to optimality a set of real instances; and (iii) the scalability of the RHH based on the enhanced mathematical model which is able to provide good feasible solutions for large size instances.     

Hybrid Modelling for Robust Solving

We study a balanced academic curriculum problem and an industrial steel mill slab design problem. These problems can be modelled in different ways, using both Integer Linear Programming (ILP) and Constraint Programming (CP) techniques. We consider the utility of each model. We also propose integrating the models to create hybrids that benefit from the complementary strengths of each model. Experimental results show that hybridization significantly increases the domain pruning and decreases the run-time on many instances. Furthermore, a CP/ILP hybrid model gives a more robust performance in the face of varying instance data.     

The maximum cut problem on blow-ups of multiprojective spaces

The maximum cut problem for a quintic del Pezzo surface Bl₄(?²) asks: Among all partitions of the 10 exceptional curves into two disjoint sets, what is the largest possible number of pairwise intersections? In this article we show that the answer is 12. More generally, we obtain bounds for the maximum cut problem for the minuscule varieties X _a,b,c :=Bl _b+c ((? ^c?1) ^a?1) studied by Mukai and Castravet-Tevelev and show that these bounds are asymptotically sharp for infinite families and exact in some cases. The key to our results is the fact that certain natural embeddings of the classes of (?1)-divisors on these varieties are optimal for the semidefinite relaxation of the maximum cut problem on graphs proposed by Goemans and Williamson. These results are a new optimality property of Weyl orbits of root systems of type A,D and E. Motivated by our results on the varieties X _a,b,c we show that the Goemans–Williamson maxcut stochastic approximation algorithm has provably optimal asymptotic performance in symmetric strongly regular graphs of bounded spectra, in marked contrast with its worst-case behavior.     

Alternating local search based VNS for linear classification

We consider the linear classification method consisting of separating two sets of points in d-space by a hyperplane. We wish to determine the hyperplane which minimises the sum of distances from all misclassified points to the hyperplane. To this end two local descent methods are developed, one grid-based and one optimisation-theory based, and are embedded into a VNS metaheuristic scheme. Computational results show these approaches to be complementary, leading to a single hybrid VNS strategy which combines both approaches to exploit the strong points of each. Extensive computational tests show that the resulting method can always be expected to approach the global optimum close enough that any deviations from the global optimum are irrelevant with respect to the classification power.     

Variable neighbourhood search heuristics for the probabilistic multi-source Weber problem

The Multi-source Weber Problem (MWP) is concerned with locating m facilities in the Euclidean plane, and allocating these facilities to n customers at minimum total cost. The deterministic version of the problem, which assumes that customer locations and demands are known with certainty, is a non-convex optimization problem and difficult to solve. In this work, we focus on a probabilistic extension and consider the situation where customer locations are randomly distributed according to a bivariate distribution. We first present a mathematical programming formulation for the probabilistic MWP called the PMWP. For its solution, we propose two heuristics based on variable neighbourhood search (VNS). Computational results obtained on a number of test instances show that the VNS heuristics improve the performance of a probabilistic alternate location-allocation heuristic referred to as PALA. In its original form, the applicability of the new heuristics depends on the existence of a closed-form expression for the expected distances between facilities and customers. Unfortunately, such an expression exists only for a few distance function and probability distribution combinations. We therefore use two approximation methods for the expected distances, which make the VNS heuristics applicable for any distance function and bivariate distribution of customer locations.     

A hybrid heuristic for a multi-objective real-life car sequencing problem with painting and assembly line constraints

We address a multi-objective version of the car sequencing problem, which consists in sequencing a given set of cars to be produced in a single day, minimizing the number of violations of assembly constraints and the number of paint color changes in the production line. We propose a set of heuristics for approximately solving this problem, based on the paradigms of the VNS and ILS metaheuristics, to which further intensification and diversification strategies have been added. Computational results on real-life test instances are reported. The work presented in this paper obtained the second prize in the ROADEF challenge 2005 sponsored by Renault.     

Combining VNS with constraint programming for solving anytime optimization problems

This paper presents an hybrid search method for solving on-line optimization problems that are modelled using the vcspValued Constraint Satisfaction Problems framework. To each constraint is associated a valuation representing the “cost to pay” when this constraint will be violated by a solution. Our method (VNS/LDS+CP) uses principles of VNS (Variable Neighborhood Search) and combines a partial tree search (Limited Discrepancy Search) with Constraint Propagation in order to compute local optima. Experiments on the CELAR benchmarks demonstrate significant improvements on other competing methods: LNS/CP/GR [Lobjois, L., Lemaitre, M., Verfaillie, G., 2000. Large neighbourhood search using constraint propagation and greedy reconstruction for valued csp resolution. In: Proceedings of the ECAI2000 Workshop on Modelling and Solving Problems with Constraints], another hybrid method using vcsps, and two standard versions of Simulated-Annealing [Li, Y.H., 1997. Directed annealing search in constraint satisfaction and optimization. Ph.D. thesis, Imperial College of Science, Department of Computing]: Quick and Medium. Moreover, VNS/LDS+CP clearly satisfies the key properties of anytime algorithms. Finally, VNS/LDS+CP has been successfully applied to a real-life on-line resource allocation problem in computer networks.     

Traveling waves for non-local delayed diffusion equations via auxiliary equations

In this paper, we study the existence of traveling wave solutions for a class of delayed non-local reaction-diffusion equations without quasi-monotonicity. The approach is based on the construction of two associated auxiliary reaction-diffusion equations with quasi-monotonicity and a profile set in a suitable Banach space by using the traveling wavefronts of the auxiliary equations. Under monostable assumption, by using the Schauder's fixed point theorem, we then show that there exists a constant c_∗>0 such that for each c>c_∗, the equation under consideration admits a traveling wavefront solution with speed c, which is not necessary to be monotonic.     

A “reduce and solve” approach for the multiple-choice multidimensional knapsack problem

The multiple-choice multidimensional knapsack problem (MMKP) is a well-known NP-hard combinatorial optimization problem with a number of important applications. In this paper, we present a “reduce and solve” heuristic approach which combines problem reduction techniques with an Integer Linear Programming (ILP) solver (CPLEX). The key ingredient of the proposed approach is a set of group fixing and variable fixing rules. These fixing rules rely mainly on information from the linear relaxation of the given problem and aim to generate reduced critical subproblem to be solved by the ILP solver. Additional strategies are used to explore the space of the reduced problems. Extensive experimental studies over two sets of 37 MMKP benchmark instances in the literature show that our approach competes favorably with the most recent state-of-the-art algorithms. In particular, for the set of 27 conventional benchmarks, the proposed approach finds an improved best lower bound for 11 instances and as a by-product improves all the previous best upper bounds. For the 10 additional instances with irregular structures, the method improves 7 best known results.     

Branch-and-cut algorithms for the split delivery vehicle routing problem

In this paper we present two exact branch-and-cut algorithms for the Split Delivery Vehicle Routing Problem (SDVRP) based on two relaxed formulations that provide lower bounds to the optimum. Procedures to obtain feasible solutions to the SDVRP from a feasible solution to the relaxed formulations are presented. Computational results are presented for 4 classes of benchmark instances. The new approach is able to prove the optimality of 17 new instances. In particular, the branch-and-cut algorithm based on the first relaxed formulation is able to solve most of the instances with up to 50 customers and two instances with 75 and 100 customers.     

SVM classification for imbalanced data sets using a multiobjective optimization framework

Classification of imbalanced data sets in which negative instances outnumber the positive instances is a significant challenge. These data sets are commonly encountered in real-life problems. However, performance of well-known classifiers is limited in such cases. Various solution approaches have been proposed for the class imbalance problem using either data-level or algorithm-level modifications. Support Vector Machines (SVMs) that have a solid theoretical background also encounter a dramatic decrease in performance when the data distribution is imbalanced. In this study, we propose an L ₁-norm SVM approach that is based on a three objective optimization problem so as to incorporate into the formulation the error sums for the two classes independently. Motivated by the inherent multi objective nature of the SVMs, the solution approach utilizes a reduction into two criteria formulations and investigates the efficient frontier systematically. The results indicate that a comprehensive treatment of distinct positive and negative error levels may lead to performance improvements that have varying degrees of increased computational effort.     

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.