Heuristic Algorithms and Scatter Search for the Cardinality Constrained P||Cmax Problem

We consider the generalization of the classical P||C_max problem (assign n jobs to m identical parallel processors by minimizing the makespan) arising when the number of jobs that can be assigned to each processor cannot exceed a given integer k. The problem is strongly NP-hard for any fixed k > 2. We briefly survey lower and upper bounds from the literature. We introduce greedy heuristics, local search and a scatter search approach. The effectiveness of these approaches is evaluated through extensive computational comparison with a depth-first branch-and-bound algorithm that includes new lower bounds and dominance criteria.     

Finding Robust Solutions Using Local Search

This paper investigates how a local search metaheuristic for continuous optimisation can be adapted so that it finds broad peaks, corresponding to robust solutions. This is relevant in problems in which uncertain or noisy data is present. When using a genetic or evolutionary algorithm, it is standard practice to perturb solutions once before evaluating them, using noise from a given distribution. This approach however, is not valid when using population-less techniques like local search and other heuristics that use local search. For those algorithms to find robust solutions, each solution needs to be perturbed and evaluated several times, and these evaluations need to be combined into a measure of robustness. In this paper, we examine how many of these evaluations are needed to reliably find a robust solution. We also examine the effect of the parameters of the noise distribution. Using a simple tabu search procedure, the proposed approach is tested on several functions found in the literature. This revised version was published online in August 2006 with corrections to the Cover Date.     

Flow Search Approach and New Bounds for the m-Step Linear Conjugate Gradient Algorithm

A flow search approach is presented in this paper. In the approach, each iterative process involves a subproblem, whose variables are the stepsize parameters. Every feasible solution of the subproblem corresponds to some serial search stages, the stepsize parameters in different search stages may interact mutually, and their optimal values are determined by evaluating the total effect of the interaction. The main idea of the flow search approach is illustrated via the minimization of a convex quadratic function. Based on the flow search approach, some properties of the m-step linear conjugate gradient algorithm are analyzed and new bounds on its convergence rate are also presented. Theoretical and numerical results indicate that the new bounds are better than the well-known ones.     

Recovering Beam Search: Enhancing the Beam Search Approach for Combinatorial Optimization Problems

A hybrid heuristic method for combinatorial optimization problems is proposed that combines different classical techniques such as tree search procedures, bounding schemes and local search. The proposed method enhances the classic beam search approach by applying to each partial solution corresponding to a node selected by the beam, a further test that checks whether the current partial solution is dominated by another partial solution at the same level of the search tree. If this is the case, the latter solution becomes the new current partial solution. This step allows to partially recover from previous wrong decisions of the beam search procedure and can be seen as a local search step on the partial solution. We present here the application to two well known combinatorial optimization problems: the two-machine total completion time flow shop scheduling problem and the uncapacitated p-median location problem. In both cases the method strongly improves the performances with respect to the basic beam search approach and is competitive with the state of the art heuristics.     

The Attribute Based Hill Climber

In this paper we introduce the Attribute Based Hill Climber, a parameter-free algorithm that provides a concrete, stand-alone implementation of a little used technique from the Tabu Search literature known as regional aspiration. Results of applying the algorithm to two classical optimisation problems, the Travelling Salesman Problem and the Quadratic Assignment Problem, show it to be competitive with existing general purpose heuristics in these areas.     

Augmented Lagrangian Algorithms Based on the Spectral Projected Gradient Method for Solving Nonlinear Programming Problems

The spectral projected gradient method SPG is an algorithm for large-scale bound-constrained optimization introduced recently by Birgin, Martínez, and Raydan. It is based on the Raydan unconstrained generalization of the Barzilai-Borwein method for quadratics. The SPG algorithm turned out to be surprisingly effective for solving many large-scale minimization problems with box constraints. Therefore, it is natural to test its perfomance for solving the sub-problems that appear in nonlinear programming methods based on augmented Lagrangians. In this work, augmented Lagrangian methods which use SPG as the underlying convex-constraint solver are introduced (ALSPG) and the methods are tested in two sets of problems. First, a meaningful subset of large-scale nonlinearly constrained problems of the CUTE collection is solved and compared with the perfomance of LANCELOT. Second, a family of location problems in the minimax formulation is solved against the package FFSQP.     

Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming

In this paper we present a primal-dual inexact infeasible interior-point algorithm for semidefinite programming problems (SDP). This algorithm allows the use of search directions that are calculated from the defining linear system with only moderate accuracy, and does not require feasibility to be maintained even if the initial iterate happened to be a feasible solution of the problem. Under a mild assumption on the inexactness, we show that the algorithm can find an -approximate solution of an SDP in O(n²ln(1/)) iterations. This bound of our algorithm is the same as that of the exact infeasible interior point algorithms proposed by Y. Zhang.Research supported in part by the Singapore-MIT alliance, and NUS Academic Research Grant R-146-000-032-112.Mathematics Subject Classification (1991): 90C05, 90C30, 65K05     

On the Convergence of a Population-Based Global Optimization Algorithm

In global optimization, a typical population-based stochastic search method works on a set of sample points from the feasible region. In this paper, we study a recently proposed method of this sort. The method utilizes an attraction-repulsion mechanism to move sample points toward optimality and is thus referred to as electromagnetism-like method (EM). The computational results showed that EM is robust in practice, so we further investigate the theoretical structure. After reviewing the original method, we present some necessary modifications for the convergence proof. We show that in the limit, the modified method converges to the vicinity of global optimum with probability one.     

Non-classical preference models in combinatorial problems: Models and algorithms for graphs

This is a summary of the most important results presented in the authors PhD thesis (Spanjaard 2003). This thesis, written in French, was defended on 16 December 2003 and supervised by Patrice Perny. A copy is available from the author upon request. This thesis deals with the search for preferred solutions in combinatorial optimization problems (and more particularly graph problems). It aims at conciliating preference modelling and algorithmic concerns for decision aiding.Received: March 2004, MSC classification: 91B06, 90C27, 90B40, 16Y60     

A Hybrid Improvement Heuristic for the One-Dimensional Bin Packing Problem

We propose in this work a hybrid improvement procedure for the bin packing problem. This heuristic has several features: the use of lower bounding strategies; the generation of initial solutions by reference to the dual min-max problem; the use of load redistribution based on dominance, differencing, and unbalancing; and the inclusion of an improvement process utilizing tabu search. Encouraging results have been obtained for a very wide range of benchmark instances, illustrating the robustness of the algorithm. The hybrid improvement procedure compares favourably with all other heuristics in the literature. It improved the best known solutions for many of the benchmark instances and found the largest number of optimal solutions with respect to the other available approximate algorithms.