Mathematical Programming Solver Based on Local Search E-Book

Frédéric Gardi

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 112

Veröffentlichungsjahr: 2014

Beschreibung

This book covers local search for combinatorial optimization and its extension to mixed-variable optimization. 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's end-users demand interactivity with decision support systems. For optimization software, this means obtaining good-quality solutions quickly. Fast iterative improvement methods, like local search, are suited to satisfying such needs. Here the authors show local search in a new light, in particular presenting a new kind of mathematical programming solver, namely LocalSolver, based on neighborhood search. First, an iconoclast methodology is presented to design and engineer local search algorithms. The authors' concern regarding industrializing local search approaches is of particular interest for practitioners. This methodology is applied to solve two industrial problems with high economic stakes. Software based on local search induces extra costs in development and maintenance in comparison with the direct use of mixed-integer linear programming solvers. The authors then move on to 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. They conclude by presenting their ongoing and future work on LocalSolver toward a full mathematical programming solver based on local search.

Leseprobe

Contents

Acknowledgments

Preface

Introduction

1 Local Search: Methodology and Industrial Applications

1.1. Our methodology: back to basics

1.2. Car sequencing for painting and assembly lines

1.3. Vehicle routing with inventory management

2 Local Search for 0–1 Nonlinear Programming

2.1. The LocalSolver project

2.2. State-of-the-art

2.3. Enriching modeling standards

2.4. The core algorithmic ideas

2.5. Benchmarks

3 Toward an Optimization Solver Based on Neighborhood Search

3.1. Using neighborhood search as global search strategy

3.2. Extension to continuous and mixed optimization

3.3. Separating the computation of solutions and bounds

3.4. A new-generation, hybrid mathematical programming solver

Bibliography

Lists of Figures and Tables

Index

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 Ltd27-37 St George’s RoadLondon SW19 4EUUK

www.iste.co.uk

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

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 DataA CIP record for this book is available from the British LibraryISSN 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 LocalSolver1 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

1http://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 GardiApril 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.