1 Foreword

There is a long standing triennial collaboration between 4OR: A Quarterly Journal of Operations Research and Annals of Operations Research (AOR). The Editors-in-Chief of 4OR collect the twelve surveys that appeared in the past three volumes (at four issues each), and, invited by AOR’s Editor-in-Chief, serve as guest editors to a special issue of AOR that collects these surveys.

As such, this volume of AOR collects all surveys from volumes 10–12 (2012–2014) of 4OR. This is the fourth volume of this type, after Bouyssou et al. (2007a, 2010a) and Liberti et al. (2013b).

This decision was taken essentially because of the excellence of 4OR’s surveys: we take great pride in our survey section, and contribute great effort into inviting prestigious authors, covering a large range of topics in great depth, and exploring new “hot” topics in operations research (OR). This re-publication choice makes our surveys more widely available to the OR community at large. The fact that 4OR and AOR are both published by Springer helps with copyright issues.

All our survey authors are approached every 3 years, and asked permission to go forth with re-publication. So far, no-one has rejected our invitation. Quite on the contrary, the authors take this opportunity to correct, revise, update and sometimes substantially improve their past work. We therefore wish to thank all of our past survey authors for agreeing to such an endeavor with such prompt timeliness.

2 About 4OR

In 2002, the Belgian and Italian operations research societies (resp. SOGESCI/BVWB and AIRO) decided to stop publishing their respective journals (JORBEL and Ricerca Operativa). The goal [see Bouyssou et al. (2003)] was to publish a common journal with a better international visibility and to optimize the use of scarce resources. The Belgian and Italian societies were joined by the French operations research society (ROADEF) and they started publishing 4OR in 2002, with Springer. As its name suggests, this journal is ‘for’ operations research (OR). The full name of the journal was originally Quarterly Journal of the Belgian, French and Italian Operations Research Societies, but soon (in 2004) changed to 4OR: A Quarterly Journal of Operations Research to better reflect its growing international impact.

4OR is managed by a group of three editors-in-chief (for the period 2012–2014, the authors of this text), one from each promoting OR society, assisted by a board of area editors. Every third year, the editors-in-chief prepare a report on the latest three years of existence of the journal (see Bouyssou et al. 2003, 2006a, 2009a; Liberti et al. 2012, 2015).

Every year one volume of four issues, each of around 110 pages, is published containing papers in the following five different sections with different frequencies (in parentheses we indicate the number of each of them over volumes 10, 11, and 12):

Invited surveys:

(12): state-of-the-art surveys written by prominent researchers on invitation by the editors, limited to one paper per issue.

Research papers:

(36): original research papers, with a preference for relatively short ones (around 12–15 pages, the limits being fuzzy). The journal publishes papers in all areas of OR. Papers in emerging fields of OR are especially welcomed.

Ph.D. thesis abstracts:

(37): 2-page summaries of Ph.D. theses defended in Belgium, France, and Italy, or by Belgian, French, or Italian students studying abroad, published under the responsibility of their advisors.

Industry:

(2): case studies, state-of-the-art papers on the applications of OR techniques, or reflections on the practice of OR.

Educational papers:

(0): up-to-date expositions of classical OR problems that are frequently used in OR classes, or papers throwing a novel light on such.

All papers are exchanged and processed in electronic form. The refereeing process conforms with the usual standards of academic journals. After having passed a check for plagiarism (using ©iThenticate) and a quick scan for appropriateness and level, it involves at least two independent referee reports and the advice of an appropriate area editor. Except for two cases of plagiarism that were fortunately detected (see Bouyssou et al. 2006b, 2009b), the reviewing process of the papers was rather smooth. The collaboration between the three editors and the area editors proved effective and efficient. Our purely electronic way of handling papers turned out to be swift and economical.

Papers needing a minor revision will not normally be sent back in revised form to the referees and the (area) editors will check their adequacy to the suggestions of the referees. However the journal has an uncommon policy with respect to major revisions. All papers needing a ‘major revision’, i.e., a revision that cannot be reasonably expected to be undertaken within two months and/or that is likely to significantly alter the whole paper, will be rejected. Needless to say, papers rejected because they need a major revision can—after substantial rewriting—be resubmitted to 4OR. They are then considered as new submissions and, thus, evaluated by two, possibly new, referees.

For volumes 10–12, the rejection rate for research papers was 93 %. The mean time between the reception of the paper and the communication of the decision to the authors was 51 days, i.e., less than 2 months. We received submissions coming from 14 different countries.

3 The surveys in this volume

Invited surveys are solicited by one of us and are collectively reviewed by the three of us. We have tried hard to solicit papers dealing with important or emerging fields of OR. Furthermore, we have strived to obtain papers from authors coming from a large variety of countries. Our policy is to solicit surveys written by well-established scholars, presenting the state-of-the-art of relevant operations research areas.

In this section we briefly introduce each of the surveys collected in this volume. The papers have been kept in their original order of publication, this being the only rational and fair order for such a wide range of subjects. This order may be observed from the 4OR volume/issue number (shown in parentheses) in which they originally appeared.

  1. 1.

    What we can learn from conflicts in propositional satisfiability [4OR 10/1, Hamadi et al. (2012)]: Youssef Hamadi, Saïd Jabbour, and Lakhdar Saïs discuss the application of machine learning techniques to SAT solving.

  2. 2.

    Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications [4OR 10/2, Kellerer and Strusevich (2012)]: Hans Kellerer and Vitaly Strusevich discuss fully polynomial time approximation schemes for the Symmetric Quadratic Knapsack Problem and the Half-Product Problem, and their application to various scheduling problems.

  3. 3.

    Relaxations of mixed integer sets from lattice-free polyhedra [4OR 10/3, Del Pia and Weismantel (2012)]: Alberto Del Pia and Robert Weismantel give an introduction to a recently established link between the geometry of numbers and mixed integer optimization.

  4. 4.

    Semidefinite relaxations for partitioning, assignment and ordering problems [4OR 10/4, Rendl (2012)]: Franz Rendl introduces the field of semidefinite optimization for non-experts. The basic concepts are explained on a mostly intuitive level. A variety of semidefinite optimization models are presented on a selection of graph optimization problems.

  5. 5.

    Bilevel programming and price setting problems [4OR 11/1, Labbé and Violin (2013)]: Martine Labbé and Alessia Violin present the main concepts, models and solution methods of pricing optimization problems that can be modeled as bilevel programs.

  6. 6.

    Combining metaheuristics with mathematical programming, constraint programming and machine learning [4OR 11/2, Talbi (2013)]: El-Ghazali Talbi gives a rational, categorized view of the field of hybrid metaheuristics, discussing in particular the case of hybridization with mathematical programming and constraint programming.

  7. 7.

    Using multi-objective evolutionary algorithms for single-objective constrained and unconstrained optimization [4OR 11/3, Segura et al. (2013)]: Carlos Segura, Carlos A. Coello Coello, Gara Miranda, and Coromoto León present the main methods that allow the use of multi-objective schemes for single-objective optimization, and discuss several open topics and some possible paths of future work in this area.

  8. 8.

    Global optimization based on local searches [4OR 11/4, Locatelli and Schoen (2013)]: Marco Locatelli and Fabio Schoen deal with the use of local searches within global optimization algorithms, and present how the associated issues have been faced in the existing literature.

  9. 9.

    Merit functions: a bridge between optimization and equilibria [4OR 12/1, Pappalardo et al. (2014)]: Massimo Pappalardo, Giandomenico Mastroeni, and Mauro Passacantando review the literature about merit functions for variational inequalities, quasi-variational inequalities and abstract equilibrium problems.

  10. 10.

    On scheduling with the non-idling constraint [4OR 12/2, Chrétienne (2014)]: Philippe Chrétienne gives an overview of the main results obtained on the complexity of scheduling under the non-idling constraint, i.e, when the jobs assigned to each machine must be processed with no intermediate delay.

  11. 11.

    Deriving compact extended formulations via LP-based separation techniques [4OR 12/3 Lancia and Serafini (2014)]: Giuseppe Lancia and Paolo Serafini introduce a unified view of compact extended formulations applied to combinatorial optimization problems.

  12. 12.

    Simulation optimization: a review of algorithms and applications [4OR 12/4 Amaran et al. (2014)]: Simulation optimization refers to the optimization of an objective function subject to constraints, both of which can be evaluated through a stochastic simulation. Satyajith Amaran, Nikolaos V. Sahinidis, Bikram Sharda, and Scott J. Bury review some of the diverse applications that have been tackled by these methods and speculate on future directions in the field.

4 The first three volumes

We believe that the 45 surveys published in the first 12 years of existence of 4OR offer an in-depth coverage of many “hot fields” in operations research. In order to give an overview of the topics the journal has covered, we briefly present here, in chronological order, the surveys that were included in the first three Annals of Operations Research volumes (Bouyssou et al. 2007a, 2010a; Liberti et al. 2013b), referring the reader to Bouyssou et al. (2007b, 2010b) and Liberti et al. (2013a) for a more detailed description.

The omnipresence of Lagrange [4OR 1/1, Lemaréchal (2003)]: Claude Lemaréchal points out that Lagrangean relaxation is not just a technique for handling combinatorial optimization problems, but a basic method in many more optimization issues.

The dial-a-ride problem: models and algorithms [4OR 1/2, Cordeau and Laporte (2003)]: Jean-François Cordeau and Gilbert Laporte present an exhaustive introduction to door-to-door delivery problems arising in social services.

Lifting, superadditivity, mixed integer rounding and single node flow sets revisited [4OR 1/3, Louveaux and Wolsey (2003)]: Quentin Louveaux and Laurence Wolsey show that a combination of integer rounding and lifting techniques provides a unified way to obtain many of the valid inequalities for mixed 0–1 sets that have been proposed in the literature.

Models and solution techniques for frequency assignment problems [4OR 1/4, Aardal et al. (2003)]: Karen Aardal, Stan van Hoesel, Arie Koster, Carlo Mannino, and Antonio Sassano give a thorough overview of the different modeling ideas developed for the various situations in which a frequency assignment problem arises in wireless communication.

Combinatorial auctions [4OR 2/1, Abrache et al. (2004)]: Jawad Abrache, Teodor Gabriel Crainic, Michel Gendreau, and Monia Rekik review several contributions from the operations research literature on a particular type of auctions in which participants are allowed to bid on bundles of multiple heterogeneous items.

Ethics in OR/MS: past, present and future [4OR 2/2, Brans and Gallo (2004)]: Jean-Pierre Brans and Giorgio Gallo discuss fundamental questions on the social role of operations research / management science tools and the new challenges posed by the growing complexity of the problems humanity is facing today.

Combinatorial optimization and hierarchical classifications [4OR 2/3, Barthélemy et al. (2004)]: Jean-Pierre Barthélemy, François Brucker, and Christophe Osswald review several extensions of traditional hierarchical classification techniques from a combinatorial optimization point of view, and study the complexity of the underlying optimization problems.

Counting and enumeration complexity with application to multicriteria scheduling [4OR 3/1, T’kindt et al. (2005)]: Vincent T’kindt, Karima Bouibede-Hocine, and Carl Esswein study several aspects of multicriteria scheduling, with special emphasis on the complexity of problems linked with counting and enumerating optimal solutions.

An overview of bilevel optimization [4OR 3/2, Colson et al. (2005)]: Benoît Colson, Patrice Marcotte, and Gilles Savard review the good progress that is being made in handling special classes of problems in which the objective involves the optimal solution to another second level problem, or admit even more levels.

Complexity and algorithms for nonlinear optimization problems [4OR 3/3, Hochbaum (2005)]: Dorit Hochbaum analyzes the effort needed to produce optimal solutions with pre-specified accuracy for nonlinear continuous optimization problems, and presents polynomial-time methods for several nonlinear network problems.

Production planning with load dependent lead times: an update of research [4OR 3/4, Pahl et al. (2005)]: Julia Pahl, Stefan Voß, and David L. Woodruff give a detailed account of techniques for supply chain management in contexts where it is required to produce goods in a timely manner so as to be able to meet a demand varying in time and space.

Some operations research methods for analyzing protein sequences and structures [4OR 4/2, Błażewicz et al. (2006)]: Piotr Łukasiak, Jacek Błażewicz, and Maciej Miłostan review operations research techniques that were recently introduced in biology, especially in the protein analysis area, to support biologists.

Integrating operations research in constraint programming [4OR 4/3, Milano and Wallace (2006)]: Michela Milano and Mark Wallace describe how constraint programming, viewed as a natural formalism for modeling problems, allows linear programming to be combined with propagation and novel and varied search techniques.

Ejection chain and filter-and-fan methods in combinatorial optimization [4OR 4/4, Glover and Rego (2006)]: César Rego and Fred Glover present the general framework of the ejection chain and filter-and-fan methods, powerful neighborhood structures fundamental to the performance of local search and metaheuristic algorithms for combinatorial optimization.

An updated survey on the linear ordering problem for weighted or unweighted tournaments [4OR 5/1, Charon and Hudry (2007)]: Irène Charon and Olivier Hudry survey results, conjectures, and open problems dealing with the combinatorial and algorithmic aspects of the linear ordering problem.

Combinatorial optimization and green logistics [4OR 5/2, Sbihi and Eglese (2007)]: Abdelkader Sbihi and Richard W. Eglese introduce the area of green logistics and describe the main topics in this field that can be formulated as combinatorial optimization problems.

Generalized Nash equilibrium problems [4OR 5/3, Facchinei and Kanzow (2007)]: Francisco Facchinei and Christian Kanzow discuss the main properties and solution algorithms for the generalized Nash equilibrium problem, an important model that has its roots in the economic sciences but is being fruitfully used in many different fields.

Exact algorithms for routing problems under vehicle capacity constraints [4OR 5/4, Baldacci et al. (2007)]: Roberto Baldacci, Paolo Toth, and Daniele Vigo review the most recent developments that had a major impact in the current state-of-the-art of exact algorithms for the capacitated vehicle routing problem.

A decade of application of the Choquet and Sugeno integrals in multi-criteria decision aid [4OR 6/1, Grabisch and Labreuche (2008)]: Michel Grabisch and Christophe Labreuche examine the main advances on the use of the Choquet and Sugeno integrals in multi-criteria decision aid over the last decade.

On the use of graphs in discrete tomography [4OR 6/2, de Werra et al. (2008)]: Dominique de Werra, Marie-Christine Costa, Christophe Picouleau, and Bernard Ries present a tutorial paper on a graph theoretical model for the basic image reconstruction problem which stems from discrete tomography.

Mathematical optimization in intensity modulated radiation therapy [4OR 6/3, Ehrgott et al. (2008)]: Matthias Ehrgott, Çiğdem Güler, Horst W. Hamacher, and Lizhen Shao survey optimization models, methods, and theories in mathematical optimization which were recently successfully introduced in the design of intensity modulated radiotherapy treatments.

Variable neighborhood search: methods and applications [4OR 6/4, Hansen et al. (2008)]: Pierre Hansen, Nenad Mladenović, and José Moreno Pérez review the main aspects of variable neighborhood search metaheuristics, a framework based upon systematic changes of neighborhoods.

Constraint programming-based column generation [4OR 7/2, Gualandi and Malucelli (2009)]: Stefano Gualandi and Federico Malucelli survey recent applications and advances of the constraint programming-based column generation framework, where the master subproblem is solved by traditional OR techniques, while the pricing subproblem is solved by constraint programming.

The core of games on ordered structures and graphs [4OR 7/3, Grabisch (2009)]: Michel Grabisch gives a unified view of the results that have been obtained by defining a game on a subcollection of the power set of the set of players, examining the implications on the mathematical structure of the core.

Intra-domain traffic engineering with shortest path routing protocols [4OR 7/4, Altın et al. (2009)]: Aysegül Altın, Bernard Fortz, Mikkel Thorup, and Ümit Hakan review optimization techniques that have been developed for managing intra-domain routing in networks operated with shortest path routing protocols, and the state-of-the-art research that has been carried out in this direction.

Extended formulations in combinatorial optimization [4OR 8/1, Conforti et al. (2010)]: Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli survey the size of perfect formulations for combinatorial optimization problems, with special emphasis on situations where the addition of a polynomial number of extra variables allows a formulation with a polynomial number of inequalities.

Robust portfolio asset allocation and risk measures [4OR 8/2, Scutellà and Recchia (2010)]: Maria Grazia Scutellà and Raffaella Recchia discuss the mathematical models, and related algorithmic approaches, that have recently been proposed to address uncertainty in portfolio asset allocation, focusing on robust optimization methodology.

Recent progress of local search in handling the time window constraints of the vehicle routing problem [4OR 8/3, Hashimoto et al. (2010)]: Hideki Hashimoto, Mutsunori Yagiura, Shinji Imahori and Toshihide Ibaraki review recent results on how to handle hard and soft time window constraints of the vehicle routing problem, putting emphasis on its different definitions and algorithms.

Makespan minimization in online scheduling with machine eligibility [4OR 8/4, Lee et al. (2010)]: Kangbok Lee, Joseph Y.-T. Leung, and Michael L. Pinedo examine online scheduling problems in parallel machine environments with various types of machine eligibility constraints, and the makespan as objective function.

Probabilistic decision graphs for optimization under uncertainty [4OR 9/1, Jensen and Nielsen (2011)]: Finn Jensen and Thomas Nielsen survey probabilistic decision graphs for modeling and solving decision problems under uncertainty, providing an introduction to influence diagrams and to alternative representation languages.

Airport runway scheduling [4OR 9/2, Bennell et al. (2011)]: Julia Bennell, Mohammad Mesgarpour and Chris Potts review the main solution techniques (dynamic programming, branch and bound, heuristics and meta-heuristics) that are used for scheduling aircraft landings and take-offs.

Political districting: from classical models to recent approaches [4OR 9/3, Ricca et al. (2011)]: Federica Ricca, Andrea Scozzari, and Bruno Simeone introduce and discuss selected optimization models and algorithms for political districting, that gave rise to the main lines of research on this topic in the operations research literature of the last five decades.

Mixed integer nonlinear programming tools: a practical overview [4OR 9/4, D’Ambrosio and Lodi (2011)]: Claudia D’Ambrosio and Andrea Lodi review available tools for solving mixed integer nonlinear programming problems, with the aim of giving the reader a flavor of the difficulties one can face in this field.