First published 2014 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd
27-37 St George’s Road
London SW19 4EU
UK

www.iste.co.uk

John Wiley & Sons, Inc.
111 River Street
Hoboken, NJ 07030
USA

www.wiley.com

© ISTE Ltd 2014

The rights of Frédéric Gardi, Thierry Benoist, Julien Darlay, Bertrand Estellon and Romain Megel to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2014936489

British Library Cataloguing-in-Publication Data
A CIP record for this book is available from the British Library
ISSN 2051-2481 (Print)
ISSN 2051-249X (Online)
ISBN 978-1-84821-686-0

Acknowledgments

This monograph was originally written as Frédéric Gardi’s Habilitation Thesis in Computer Science, publicly defended on November 25th 2013 at Université Pierre et Marie Curie (Paris, France) before a jury consisting of: Philippe Baptiste, Strategy & Innovation Director, MESR/DGRI (examiner); Yves Caseau, Executive Vice President, Bouygues Telecom (examiner); Philippe Chrétienne, Professor, Université Pierre et Marie Curie (president); Gérard Cornuéjols, Professor, Carnegie Mellon University (examiner); Michel Gendreau, Professor, École Polytechnique de Montréal (referee); Jin-Kao Hao, Professor, Université d’Angers (referee); Geir Hasle, Chief Research Scientist, SINTEF ICT (referee); and Marc Sevaux, Professor, Université de Bretagne-Sud (examiner). Nevertheless, the research advances presented in this monograph emerged from a collective work by the LocalSolver¹ team: Thierry Benoist, Julien Darlay, Bertrand Estellon, Frédéric Gardi, and Romain Megel. The authors thank Antoine Jeanjean, Karim Nouioua and Guillaume Rochart who contributed to part of the work presented here, as well as Thibaud Cavin, Lucile Robin, Saul Pedraza Morales, Sofia Zaourar, Boris Prodhomme and Clément Pajean who worked with us as interns on related topics.

To our families and friends

1 http://www.localsolver.com.

Preface

This book deals with local search for combinatorial optimization and its extension to mixed-variable optimization. Our goal is to present local search in a new light. Although not yet understood from the theoretical point of view, local search is the paradigm of choice for tackling large-scale real-life optimization problems. Today, end users ask for interactivity with decision support systems. For optimization software, it means obtaining good-quality solutions quickly. Fast iterative improvement methods, such as local search, are suitable to satisfy such needs.

When a solution space is gigantic, a complete search becomes impractical. Given a (possibly infeasible) solution to the problem, local search consists of modifying some parts of this one – that is, some decision variables – to reach a new, hopefully better solution. Exploring a so-called neighborhood of the incumbent has a major advantage: the new solution can be evaluated quickly through incremental calculation. Then, local search can be viewed as an incomplete and non-deterministic but efficient way to explore a solution space.

First, an iconoclast methodology is presented to design and engineer local search algorithms. We show that the performance of a local search mainly relies on the richness of the neighborhoods explored, as well as on the efficiency of their exploration. Ultimately, implementing high-performance local search algorithms is a matter of expertise in incremental algorithmics and of dexterity in computer programming. Our concern to industrialize local search approaches will be of particular interest for practitioners. As an example, this methodology is applied to solve two industrial problems with high economic stakes.

Nevertheless, software applications based on local search induce extra costs in development and maintenance in comparison with the direct use of mixed-integer linear programming solvers. We present the LocalSolver project whose goal is to offer the power of local search through a model-and-run solver for large-scale 0–1 nonlinear programming. Having outlined its modeling formalism, the main ideas on which LocalSolver relies are described and some benchmarks are presented to assess its performance. We conclude the book by presenting our ongoing and future works on LocalSolver toward a full mathematical programming solver based on neighborhood search.

Frédéric Gardi
April 2014

Introduction

In this book, we present a survey of our research on local search in combinatorial optimization, from methodological foundations to industrial applications and software. This survey puts into perspective the evolution of our research, from the resolution of specific problems to the design of a general-purpose mathematical programming solver based on local search, namely LocalSolver. After a brief introduction about combinatorial optimization and local search, we outline the book’s plan.

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!

Lesen Sie weiter in der vollständigen Ausgabe!