Previous Next
Scroll down to
explore more

Learning and Intelligent Optimization

From big data to big actions

We realize services for business intelligence, data mining, interactive visualization, Learning and Intelligent OptimizatioN (LION) : a combination of modeling, machine learning (learning from your business data) and automated search for improving solutions (optimization).

Our senior consultants have more than twenty years of experience, 6000 citations in technical applications, 50 citations in international patents, and a track of successful real-world applications.
We solve problems, even the hardest ones, with a speed which will surprise you if you are used to dealing with huge consultancy companies.

Our competitive edge is caused by a unique integration of automated learning and optimization, to support the interaction between domain experts and decision makers for better and data-driven solutions.

Learning and Intelligent OptimizatioN (LION) means combining learning processes with modeling, problem-solving, and optimization. LION is a robust and efficient method for solving difficult problems. The method facilitates creativity and disruptive innovation while alternative solutions are identified and tested. Its strength lies in the introduction of high-level skills often associated to the human brain, such as learning from past experience, learning on the job, rapid analysis of alternatives, ability to cope with incomplete information, quick adaptation to new situations and events.

Real-world problems have a rich structure. While many alternative solutions are tested in the exploration of a search space, patterns and regularities appear. The human brain quickly learns and drives future decisions based on previous observations. This is the main inspiration source for inserting online machine learning into our techniques to search for improving solutions to hard problems.

Big data and data science for business.

Unlock the knowledge hidden in your data.

The Galilean method: experiment and build models.

A data-driven and pragmatic approach, no hand waving.

Realtime and never-stopping improvement.

The LION way (Machine learning and optimization) never sleeps.

Seamless integration and easy self-service (IT-free) usage.

Services and components ready to be connected to your business.

Products

Our latest products and projects

  • Grapheur

    From data to insight
  • LIONlab, University of Trento

    Research lab in partnership with Reactive Search srl
  • LIONbook

    The LION Way: Machine Learning plus Intelligent Optimization
  • LION 8 Conference

    Gainesville, Florida - USA, Feb 16-21, 2014
  • LION 6 Conference

    Paris, Jan 16-20, 2012
  • Postame: the personal bulk email service

    Marketing optimization: bulk email and newsletters
  • CharmOffer:

    The right price, by machine learning

Technology

Learning on the Job

Reactive Search Optimization is a robust and efficient method for solving difficult optimization problems. The word reactive hints at a ready response to events while alternative solutions are tested. Its strength lies in the introduction of high-level skills often associated to the human brain, such as learning from the past experience, learning on the job, rapid analysis of alternatives, ability to cope with incomplete information, quick adaptation to new situations and events.

The more complete LION approach (as described in our book The LION Way: Machine Learning plus Intelligent Optimization) integrates the data-driven construction of models (Machine Learning) and the automated identification of improvements (optimization).
From your business data, to flexible models, to actionable insight and automated and measurable improvements!

The main features of the Reactive Search techniques are:

Learning on the job

Real-world problems have a rich structure. While many alternative solutions are tested in the exploration of a search space, patterns and regularities appear. The human brain quickly learns and drives future decisions based on previous observations. This is the main inspiration source for inserting online machine learning techniques into the optimization engine of Reactive Search.

Rapid generation and analysis of many alternatives

Often, to solve a problem one searches among a large number of alternatives, each requiring the analysis of what-if scenarios. The search speed is improved if alternatives are generated in a strategic manner, so that different solutions are chained along a trajectory in the search space exploring wide areas and rapidly exploiting the most promising solutions.

Flexible decision support

Crucial decisions depend on factors and priorities which are not always easy to describe before starting the solution process. Feedback from the user in the preliminary exploration phase can be incorporated so that a better tuning of the final solutions takes the end user preferences into account.

Diversity of solutions

The final decision is up to you, not the machine. The reason is that not all qualitative factors of a problem can be encoded into a computer program. Having a set of diverse near-best alternatives is often crucial for the decision maker.

Anytime solutions

You decide when to stop searching. A first complete solution is generated rapidly, better and better ones are produced in the following search phases. The more you run, the bigger the possibility to identify excellent solutions, but if you want a solution fast you are going to get it!

The Team

Stefano Odorizzi

Chief Executive Officer

Patrizia Nardon

Executive Assistant

Roberto Battiti

 

Mauro Brunato

 

Mosè Necchio

Marketing

Giuseppe Pezzica

Sales

Danilo Tomasoni

Software Developer

Enrico Sartori

Software Developer

Scientific Advisory Board

Fred Glover

OptTek Systems, Inc.
Boulder, USA

Nathan Brixius

Nielsen Marketing Analytics
Chicago, USA

Xin Yao

Director, Centre of Excellence for Research in Computational Intelligence and Applications
University of Birmingham, UK

Holger Hoos

Computer Science Department
University of British Columbia, Canada

Pablo Moscato

Centre for Bioinformatics, Biomarker discovery and Information-based medicine
University of Newcastle, Australia

Raffaele Giancarlo

Department of Mathematics, Computer Science Section
Università di Palermo, Italy

Roberto Franzosi

Department of Sociology
Emory University, USA

Youssef Hamadi

Constraint Reasoning Group
Microsoft Research Cambridge, UK

Christian Blum

Dept. Llenguatges i Sistemes Informátics
Universitat Politècnica de Catalunya, Spain

Qingfu Zhang

School of Computer Science and Electronic Engineering
University of Essex, UK

Software services and API

Consultancy

Software development

Training

bg

Grapheur 2.0

Data analysis for your business
From data to insight.

img

Did you try or business intelligence software?

Contact us

WE LOOK FORWARD TO HEARING FROM YOU

Send us a message

Info

Address: Reactive Search, Via della Stazione 27
Mattarello - 38123 Trento - Italy

Telephone: +39 0461 979 576

Email: nardon ((AT)) reactive-search.com

OUR HEADQUARTERS

img


Applications of Reactive Search Optimization (RSO)


Reactive Search Optimization is not a rigid algorithm but a general framework: specific algorithms have been introduced for unconstrained and constrained tasks, with different stochastic mechanisms and rules for selecting neighbors. As it usually happens in heuristics, the more specific knowledge about a problem is used, the better the results. Nonetheless, it was often the case that simple RSO versions realized with very limited effort could duplicate the performance of more complex schemes because of their simple embedded feedback loop, and without intensive parameter and algorithm tuning. A long-term goal of RSO is the progressive shift of the learning capabilities from the algorithm user to the algorithm itself, through machine learning techniques.

The RSO framework and related algorithms and tools have been and are being applied to a growing number of ``classical'' discrete optimization problems, continuous optimization tasks, and real-world problems arising in widely different contexts. The Web, see for example Google scholar, lists thousands of citations to the seminal papers, the following list is a selection of some applications we are aware of. We are always happy to hear from users and developers interested in RSO principles and applications.

If you have a new application, we will be happy to know about it and to list it here, contact us .

Classic combinatorial tasks

The seminal paper about RSO for Tabu Search (Reactive Tabu Search) presented preliminary experimental results on the 0-1 Knapsack Problem, and on the Quadratic Assignment Problem [BT94a]. A comparison with Simulated Annealing on QAP tasks is contained in [BT94b]. An early experimental comparison of Reactive Search Optimization with alternative heuristics (Repeated Local Minima Search, Simulated Annealing, Genetic Algorithms and Mean Field Neural Networks) is presented in [BT95a]. An application of a self-controlling software approach to Reactive Tabu Search is presented in [FUK08] with results on the QAP problem.

Knapsack and related problems

A reactive local search-based algorithm (adaptive memory search) for the 0/1-Multidemand Multidimensional knapsack problem (0/1-MDMKP) is proposed in [AHL06]. The 0/1-MDMKP represents a large class of important real-life problems, including portfolio selection, capital budgeting, and obnoxious and semi-obnoxious facility location problems. A different application is considered in [HM06] for the disjunctively constrained knapsack problem (DCKP), a variant of the standard knapsack problem with special disjunctive constraints. A disjunctive constraint is a couple of items for which only one item is packed.

Problems on graphs

A reactive tabu search algorithm for Minimum Labeling Spanning Tree is considered in [CFGV05,CFGV06], together with other meta-heuristics. The problem is as follows: Given a graph G with a color (label) assigned to each edge one looks for a spanning tree of G with the minimum number of different colors. The problem has several applications in telecommunication networks, electric networks, multi-modal transportation networks, among others, where one aims at ensuring connectivity by means of homogeneous connections.

The graph partitioning problem has been a test case for advanced local search heuristics starting at least from the seminal Kernighan and Lin paper [KL70], which proposes a variable-depth scheme. This is is fact a simple prohibition-based (tabu) scheme where swaps of nodes among the two sets of the partitions are applied, and the just swapped nodes are kept fixed during a sequence of tentative moves in search of an improving chain. Greedy, Prohibition-based, and Reactive Search Optimization Heuristics for Graph Partitioning are proposed and compared in [BB99], Multilevel Reactive Tabu Search techniques, based on producing coarse versions of very large graphs are considered for Graph Partitioning in [BBC99].

An RSO scheme is applied to the Maximum Clique Problem (MCP) in graphs in [BP97a,BP01]. A clique is a subset of nodes which are mutually interconnected, the problem is related to identifying densely interconnected communities and, in general, to clustering issues. A relaxed quasi-clique version of the problem where some edged may be missing is addressed in [BHB08].

The work in [YE04] introduces a new algorithm that combines the stigmergic capabilities of Ant Colony Optimization (ACO) with local search heuristics to solve the maximum and maximum-weighted clique problem. The introduced Reactive Prohibition-based Ant Colony Optimization for MCP (RPACOMCP) complements the intelligent ant colony search with a prohibition-based diversification technique, where the amount of diversification is determined in an automated way through a feedback (history-sensitive) scheme.

In [SSSG06] the authors address the problem of computing a graph similarity measure which is generic in the sense that other well known graph similarity measures can be viewed as special cases of it. They propose and compare two algorithms, an Ant Colony Optimization based algorithm and a Reactive Search Optimization, and show that they obtain complementary results: while the RSO technique achieves good solutions in shorter times, the proposed ACO method eventually attains a better quality.

A classification of methods to manage the prohibition period (Tabu tenure) in the literature is presented in [DMC08] together with a new reactive Tabu tenure adaptation mechanism. The generic method is tested on the k-coloring problem.

A Reactive Tabu Search algorithm with variable clustering for the unicost Set Covering Problem (SCP) is proposed in [KBC07]. Unicost SCPs arise in graph theory when one must select a minimum covering of edges by nodes or nodes by cliques. In addition, in many practical applications (crew scheduling, political redistricting, conservation biology, etc.) the relative variation in the weights may be small enough to warrant a unicost model.

Vehicle routing problems

A reactive tabu search version for the vehicle routing problem with time windows is designed in [CR97], while a version of the Vehicle Routing Problem with Backhauls (VRPB) is considered in [CB01,OW02].

A heuristic approach based on a hybrid operation of RTS and Adaptive Memory Programming (AMP) is proposed in [LA07] to solve the VRPB. One is given a set of customers, some of which are linehauls (delivery points) and some are backhauls (collection points), a set of homogeneous vehicles and a depot. A distinguishing feature of this model is that all backhaul customers must be visited after all linehaul customers are served on each route. RTS is used with an escape mechanism which manipulates different neighborhood schemes in order to continuously balance intensification and diversification during the search process. The adaptive memory strategy takes the search back to the unexplored regions of the search space by maintaining a set of elite solutions and using them strategically with the RTS. The authors in [NWB00] address the pickup and delivery problem with time windows using reactive tabu search.

A reactive VNS technique for VRPTW is also proposed in [Bra03]. Vehicle routing with soft time windows and Erlang travel times is studied in [RU07].

Satisfiability and related problems

Maximum satisfiability is considered in [BP97b,BP97c,MG04], reactive Scaling and Probabilistic Smoothing (SAPS) in [TH02], constraint satisfaction in [NI98]. Reactive local search techniques for the Maximum k-Conjunctive Constraint Satisfaction Problem (MAX-k-CCSP) in [BP99]. A worst-case analysis of tabu search as a function of the tabu list length for the MAX-TWO-SAT problem is presented in [MG04], with applications also to a reactive determination of the prohibition.


Neural networks and VLSI systems with learning capabilities

While derivative-based methods for training from examples have been used with success in many contexts (error back-propagation is an example in the field of neural networks), they are applicable only to differentiable performance functions and are not always appropriate in the presence of local minima. In addition, the calculation of derivatives is expensive and error-prone, especially if special-purpose VLSI hardware is used. A radically different approach is used in [BT95b]: the task is transformed into a combinatorial optimization problem (the points of the search space are binary strings), and solved with the Reactive Search Optimization algorithm. To speed up the neighborhood evaluation phase a stochastic sampling of the neighborhood is adopted and a ``smart'' iterative scheme is used to compute the changes in the performance function caused by changing a single weight. RSO escapes rapidly from local minima, it is applicable to non-differentiable and even discontinuous functions and it is very robust with respect to the choice of the initial configuration. In addition, by fine-tuning the number of bits for each parameter one can decrease the size of the search space, increase the expected generalization and realize cost-effective VLSI.

Reactive Tabu Search in Semi-supervised Classification is proposed in [ZEcL07]. With a linear kernel their RTS implementation can effectively find optimal global solutions for the primal Mixed Integer Programming Transductive Support Vector Machine (MIP-TSVM) with relatively large problem dimension.

In contrast to the exhaustive design of systems for pattern recognition, control, and vector quantization, an appealing possibility consists of specifying a general architecture, whose parameters are then tuned through Machine Learning (ML). ML becomes a combinatorial task if the parameters assume a discrete set of values: the RTS algorithm permits the training of these systems with low number of bits per weight, low computational accuracy , no local minima ``trapping'', and limited sensitivity to the initial conditions [BLST94a,BLST94b].

Special-purpose VLSI modules have been developed to be used as components of fully autonomous massively-parallel systems for real-time adaptive applications. In contrast to many ``emulation'' approaches, the developed VLSI completely reflects the combinatorial structure used in the learning algorithms.

Applications considered are in the area of pattern recognition (Optical Character Recognition), event triggering in High Energy Physics [ABL+95a], control of non-linear systems [BT95a], compression of EEG signals [BST+95]. The first product was the TOTEM chip [BLST94a,BLST95], and more general special-purpose VLSI realizations are described in [ABL+95a,ABL+95b]. A parallel neurochip for neural networks implementing the Reactive Tabu Search algorithm and application case studies are presented in [DDLL+01]. A Fast Programmable Gate Array (FPGA) implementation of the TOTEM chip is presented in [ABD+04].

Continuous optimization

A simple benchmark on a function with many suboptimal local minima is considered in [BT95b], where a straightforward discretization of the domain is used. A novel algorithm for the global optimization of functions (C-RTS) is presented in [BT96], in which a combinatorial optimization method cooperates with a stochastic local minimizer. The combinatorial optimization component, based on Reactive Search Optimization, locates the most promising boxes, where starting points for the local minimizer are generated. In order to cover a wide spectrum of possible applications with no user intervention, the method is designed with adaptive mechanisms: in addition to the reactive adaptation of the prohibition period, the box size is adapted to the local structure of the function to be optimized (boxes are larger in ``flat'' regions, smaller in regions with a ``rough'' structure). An application of intelligent prohibition-based strategies to continuous optimization is presented in [CS00].

A Reactive Affine Shaker method for continuous optimization is studied in [BB08,BBP06]. The work presents an adaptive stochastic search algorithm for the optimization of functions of continuous variables where the only hypothesis is the pointwise computability of the function. The main design criterion consists of the adaptation of a search region by an affine transformation which takes into account the local knowledge derived from trial points generated with uniform probability. Heuristic adaptation of the step size and direction allows the largest possible movement per function evaluation. The experimental results show that the proposed technique is, in spite of its simplicity, a promising building block to consider for the development of more complex optimization algorithms, particularly in those cases where the objective function evaluation is expensive.

A Gregarious Particle Swarm Optimizer (GPSO) is proposed in [PB06]. The particles (the different local searchers) adopt a reactive determination of the step size, based on feedback from the last iterations. This is in contrast to the basic particle swarm algorithm, in which no feedback is used for the self-tuning of algorithm parameters. The novel scheme presented, when tested on a benchmark for continuous optimization, besides generally improving the average optimal values found, reduces the computation effort.

Real-world applications

Reactive search schemes have been applied to a significant number of ``real-world'' problems; this term refers to applications where domain-specific knowledge is required. Rather than defining classes with properties common to many problems, these applications aim at the ``pointwise'' solution of a specific issue with detailed modeling, therefore providing an essential benchmark for optimization techniques.

Power distribution networks

A real-world application in the area of electric power distribution, service restoration in distribution systems, is studied in [TFG+02]. Fast optimal setting for voltage control equipment considering interconnection of distributed generators is proposed in [OGY+02], service restoration in distribution systems in [GOM+03] and distribution load transfer operation in [Fuk00].

Industrial production and delivery

A continuation of the previously mentioned work on VRPTW [CR97] is proposed in [RCZ08] to aid in the coordination and synchronization of the production and delivery of multi-product newspapers to bulk delivery locations. The problem is modeled as an open vehicle routing problem with time windows and zoning constraints. The methodology is applied to the newspaper production and distribution problem in a major metropolitan area.

In the field of industrial production planning, [FV99] studies applications of modern heuristic search methods to pattern sequencing problems. Flexible job-shop scheduling is studied in [CB96,CB98]. The plant location problem is studied in [DDFO99]. The work in [FV03] is dedicated to solving the continuous flow-shop scheduling problem. Adaptive self-tuning neurocontrol is considered in [PG00]. The objective is to construct an adaptive control scheme for unknown time-dependent nonlinear plants.

Telecommunication networks

Various applications of RSO focused on problems arising in the design and management of telecommunication networks. RSO for traffic grooming in optical WDM networks is considered in [BB01]. Optimal conformance test selection is studied in [CKZS02]. Conformance testing is used to increase the reliability of telecommunication applications. Locating hidden groups in communication networks is addressed in [MIGWS03] by using hidden Markov models. A communication network is a collection of social groups that communicate via an underlying communication medium. In such a network, a hidden group may try to camouflage its communications amongst the typical communications of the network. The task of increasing Internet capacity is considered in [FT04]. The Multiple-choice Multi-dimensional Knapsack Problem (MMKP) with applications to service level agreements and multimedia distribution is studied in [HM06,HMS06], where the dynamic adaptation of the resource allocation model is considered for multi-session multimedia. High quality solutions, reaching the optimum for several instances, are obtained through a reactive local search scheme. In the area of wireless and cellular communication networks, the work in [BBD03] considers the optimal wireless access point placement for location-dependent services, and the work in [FHJ03] proposes a tabu search heuristic for the dimensioning of 3G multi-service networks.

Vehicle routing and dispatching

Real-time dispatch of trams in storage yards is studied in [WZ00].

In the military sector, simple versions of Reactive Tabu Search are considered in [KJHM05] in a comparison of techniques dedicated to designing an unmanned aerial vehicle (UAV) routing system. Hierarchical Tabu Programming is used in [Bal07] for finding underwater vehicle trajectories. Aerial reconnaissance simulations is the topic of [RBMC98]. The authors in [BWMR04] use an adaptive tabu search approach for solving the aerial fleet refueling problem.

Industrial and architectural design

In the automotive sector, RSO is used in [HSN03] for improving vehicle safety: a mixed reactive tabu search method is used to optimize the design of a vehicle B-pillar subjected to roof crush.

Reactive Tabu Search and sensor selection in active structural acoustic control problems is considered in [KL98].

The solution of the engineering roof truss design problem is discussed in [HMS03] An application of reactive tabu search for designing barrelled cylinders and domes of generalized elliptical profile is studied in [Bla07]. The cylinders and domes are optimized for their buckling resistance when loaded by static external pressure by using a structural analysis tool.

Biology

A reactive stochastic local search algorithm is used in [LSS+08] to solve the Genomic Median Problem (GMP), an optimization problem inspired by a biological issue. It aims at finding the chromosome organization of the common ancestor of multiple living species. It is formulated as the search for a genome that minimizes a rearrangement distance measure among given genomes. Additional applications in bio-informatics include for example [SH07], which proposes an adaptive bin framework search method for a beta-sheet protein homopolymer model. A novel approach is studied based on the use of a bin framework for adaptively storing and retrieving promising locally optimal solutions. Each bin holds a set of conformations within a certain energy range and one uses an adaptive strategy for restarting a given search process with a conformation retrieved from these bins when the search stagnates. An adaptive mechanism chooses which conformations should be stored, based on the set of conformations already stored in memory, and biases choices when retrieving conformations from memory in order to overcome search stagnation. The energy and diversity thresholds for each bin are dynamically modified during the search process.

An adaptive meta-search method that alternates between two distinct modes of the search process at different levels is proposed in [Shm06,Shm07] for protein folding. The high level process ensures that unexplored promising parts of the search landscape are visited and the low-level search provides the thorough exploration of local neighborhoods. Multiple search processes are used in an intelligent way.

Finally, visual representation of data through clustering is considered in [CDDG+08].


Documents

Publications about RSO technology and Grapheur