Optimizing External Applications

Sometimes it is not possible to directly write a new problem for HeuristicLab and integrate it through the plugin system. Some people already have an application of which at least a part represents a NP hard problem that they'd like to solve. This guide explains how to use the ExternalEvaluationProblem that is available in HeuristicLab 3.3 to optimize problems written in a language other than C# or written using different frameworks, to name just a few possibilities. First the architecture is described, then a more detailed look into the API is given and finally a short tutorial should give the reader an idea of how to apply this to his/her case.

The most important part in any optimization problem is the evaluation function. Without knowing about the quality of a certain solution configuration the algorithm is not able to come close to an optimal solution. In NP hard problems evaluating a solution is usually a rather simple task, whereas finding the best solution is extremely difficult. Of course there can be complex problems which require high computational effort to calculate the quality of a solution, but in many cases the evaluation of a solution is rather straight forward. So, if the problem is not a HeuristicLab plugin we assume that it is available in another kind of executable format, either in an application itself or as part of another framework for example. We thus have a situation where we need inter-process communication (IPC). There are several possibilities of how to do IPC, in the following we will explain the approach we offer in HeuristicLab 3.3.

Architecture Overview

Technology & Background

Among the many possibilities and technologies that have emerged to provide a base for performing "distributed computing" in a wide sense, one of the first technologies was Remote Procedure Call (RPC). The idea is very simple: Instead of calling a local procedure to do some kind of calculation, a procedure is called that is not defined within the same executable or one of its dependencies. The client thus is in some ways hands the parameters of the method to another program or server, waits for the computation and then reads back the return value. In such a broad sense this is how most web applications nowadays work and indeed it is not until the invention of Representational State Transfer (REST) that there was a revolutionary change from this early RPC paradigm.

Recently ​Google, one of the biggest players in the world wide web released parts of their core technologies to the general public. The framework that they call ​Protocol Buffers combines a domain specific language (DSL) for describing messages with an RPC framework that is used to pass these messages among different servers. The RPC framework itself is not released, but the DSL for describing messages and translating them to objects of several supported programming languages was released under the BSD license. Google directly supports C++, Java, and Python, but many developers have programmed ports of protocol buffers to different languages such as C#, Visual Basic, Objective C, Perl, Haskell, and ​many more. The ​documentation on protocol buffers is extremely helpful in understanding the framework. A similar framework called Thrift has evolved that backs the operation of ​Facebook and was also released to the public. These technologies provide convenient ways to define messages, manipulate them, and serialize them to small sizes at high speeds.

In HeuristicLab using remote procedure calls seems to fit very well with what we are trying to achieve in "exporting" the problem definition. The problem, to an optimizer, is basically the evaluation function and the solution representation is their common knowledge. A client is provided in HeuristicLab as well as a framework that enables developers to write a service which exposes the evaluation function to HeuristicLab. Using this service foreign language applications and problems can effectively communicate with HeuristicLab and have their parameters optimized by HeuristicLab's powerful optimization library. Please note that while we're talking about RPC, the provided frameworks are not compatible with the RPC standard, but are rather simplified to ease application. Think of RPC as a paradigm rather than a standard.

Communication however also requires a given media over which to exchange the information. So far HeuristicLab offers two choices for the underlying media:

1. The external program can be started as a process from HeuristicLab and the communication occurs via the process' stdin and stdout. This requires that the external program can be executed under Windows. If the developer controls the standard input and output streams and does not need to write or read other data through them, this might be a simple solution.
2. The external program is started independently from HeuristicLab and opens a TCP/IP port for communicating over a network. This is independent of the platform and a universal solution that should work in most cases.

Regardless of the chosen media, the solution receiving and quality sending processes are abstracted from the developer through our service framework. For writing services, generally two types of services are supported by our framework: Push Service and Poll Service. It depends on the application which one of these is more suitable. If the developer is in charge of the control flow the push service seems plausible, if however the application flow cannot be fully controlled by the developer the poll service is the better suited option.

Push Service

As the name suggests when implementing a push service the solutions are pushed into the evaluation method. The developer has to provide a class that is able to perform the evaluation task. This class specifies a method that takes a SolutionMessage and returns a double value indicating the quality of the given solution. The method is called in a new thread whenever a new solution is received by the framework.

Poll Service

In this type the received solutions have to be polled. The service receives solutions in its own thread and puts them into a queue, waiting for the developer to process them. It provides two public methods, one that returns the next solution from the queue and blocks until a solution becomes available and another that sends the quality back to HeuristicLab.

Application Scenarios

One of the application scenarios that we had in mind when designing this interface is the field of simulation-based optimization. There, a simulation model defines a number of parameters which need to be adjusted such that a measured output of the model improves. This can be inventory sizes in a supply-chain scenario, or similarly buffer sizes in an assembly line, or training the weights in a neural network simulator. There are numerous optimization problems that are implemented as simulation models and one of the main problems is talking to them. Many different frameworks exist with which one can conveniently build, run, and test a simulation model, and most of them already have some support for optimization. However that support often is of proprietary nature and little information is available on how these methods perform. HeuristicLab aims to provide an open source alternative and the means of this interface allows simulation experts to use HeuristicLab in the optimization tasks.

Naturally, there exist several more reasons why a problem cannot be modeled in HeuristicLab, such as language or platform dependency and for these purposes this interface should provide a solution.

Architecture Details

The following class diagram displays the classes and interfaces present in the java service framework. There is an abstract base class Channel on the one hand which provides methods for sending and receiving messages and several concrete implementations and on the other hand an abstract base class Service that provides the concrete PollService and PushService. Each Channel has a corresponding factory which implements IChannelFactory.

Tutorial