Preface. Volume 1

Marc Wallace, Yves Caseau, Eric Jacquet-Lagreze, Helmut Simonis, Gilles Pesant

Research output: Contribution to journalEditorialResearchpeer-review


The workshop will be held in conjunction with the, Fourth International Conference on Principles and Practice of Constraint Programming (CP98), October 26 - 30, 1998. Program: This workshop will explore hybrid algorithms for complex optimisation problems. These will be based on the integration of different approaches, viz. constraint programming, mathematical programming and stochastic repair techniques. These approaches have sometimes been perceived as competitors, but more recently they have come to be seen as complementary. The need for such algorithms in solving optimisation problems arises from the fact that different techniques are suited to solving different aspects of the problem. Among the key techniques are constraint propagation, Lagrangean relaxation, linear programming, randomised search and local optimisation. Constraint propagation is ideal for customising an algorithm with domain-dependent constraints. Lagrangean relaxation is the technique of choice for obtaining lower bounds in a branch and bound approach. Linear programming is the only technique that can solve to optimiality large linear problems. Randomised search is necessary for problems that are too large for branch and bound. Local optimisation is the preferred technique for problems that have a specific neighbourhood structure, such as routing problems. Many optimisation problems are hybrid, embracing several different requirements. For example real-life dispatching problems involve both matching, routing and scheduling. For such problems there is a clear need to mix techniques. This mixing can take different forms. On one hand generic methods, such as tabu search or constraint propagation can be significantly enhanced by importing techniques developed for branch and bound (such as edge-finding) or for local optimisation (such as neighbourhood structure). On the other hand different techniques can be applied at different stages of the search. For instance initial solutions can be found using constructive search with constraint propagation, and the solution can then be improved through local optimisation. Organisation: • Mark Wallace IC-Parc William Penney Laboratory Imperial College London SW7 2BZ UK Tel: (+44)171.594834 Fax: (+44)171.5948432 • Yves Caseau Bouygues Challenger, 1 Av Eugene Freyssinet, 78061 St-Quentin-Yvelines Cedex FRANCE Tel: (+33)1 30 60 51 57 Fax: (+33)1 30 60 27 27 • Eric Jacquet-Lagreze EuroDecision • Helmut Simonis Cosytec • Gilles Pesant Centre for Research on Transportation, Univ. Montreal. Further information: Additional information will be available at the CP98 web site:

Original languageEnglish
Pages (from-to)85-86
Number of pages2
JournalElectronic Notes in Discrete Mathematics
Publication statusPublished - 1 Jan 1999

Cite this

Wallace, M., Caseau, Y., Jacquet-Lagreze, E., Simonis, H., & Pesant, G. (1999). Preface. Volume 1. Electronic Notes in Discrete Mathematics, 1, 85-86.