GENO: Generic Optimization

Optimization, i.e. the maximization or minimization of an objective function under constraints, is at the center of many applications. So it is not surprising that optimization plays an important role in our Software decídalo. The Text-to-Skills feature would be just as inconceivable without suitable optimization algorithms as the project planning module.

The benefits of generic optimization can be well understood using the example of project scheduling for consultants, since here the target function and constraints change with changing requirements. As a result, the software must also be adapted to solve the resulting optimization problems.

Let’s introduce the variables x(i,j,k) to represent the assigned times of Consultant i on project j on day k. An obvious goal is to maximize the consultants’ total assigned time (his utilization). In a very simple model, consultants can be booked on projects for a maximum of eight hours per day. In this case the variables can take all values between 0 and 8 and the sum of the variables x(i,j,k) must not exceed 8 for each consultant and each day for all projects. The problem becomes more interesting if we add more constraints. In most cases, a limited budget d(j) of hours is available for each project j, i.e. the sum of the variables x(i,j,k) over all days and all consultants may take at most the value d(j). In practice, there are many other constraints that make the problem more complex. For example, if consultant i is on vacation at day k, he cannot work on any project on that day and accordingly x(i,j,k)=0 must apply to all projects j. In the target function, we now maximize the sum of the variables under all constraints. The resulting optimization problem for the above example is a so-called linear program. A wide range of efficient algorithms and software libraries are available for solving linear programs.

In a more complex scenario, we assume that Consultant i has a special skill that is in demand in many projects. The objective could now be to distribute the consultant’s time evenly across all projects that require his qualifications. This can be achieved by maximizing an entropy function. Here we do not want to describe the entropy function in more detail. The only important thing for us is that the function is non-linear, but convex. Convex optimization problems can be solved efficiently, but software for solving convex problems is much less available than software for solving linear programs. Often you have no choice but to write your own software to solve the problem. If the problem changes, e.g. by adding additional constraints, the software must be adapted, which is time-consuming.

That’s why we implemented an efficient solution algorithm for a very general class of optimization problems. We make this algorithm available using a simple modeling language. With this approach we can dramatically shorten the development time for many optimization methods. It is enough to specify the underlying problems in the modeling language. The optimization software is automatically generated from the specification.

The combination of modeling language and solution algorithms is called generic optimization. Generic optimization has been successfully used in operations research for many years.  However, the available solutions do not scale up to the problem sizes occurring in machine learning, which is why we have developed our own approach to generic optimization. The approach is based on our Matrix Calculus Algorithm (www.matrixcalculus.org) for the symbolic calculation of gradients and is several orders of magnitude more efficient for machine learning applications than the methods previously used. We presented this approach at this year’s Conference on Neural Information Processing Systems (NeurIPS) in Vancouver.

Publication: GENO — GENeric Optimization for Classical Machine Learning. Proceedings of the 33d Annual Conference on Neural Information Processing Systems (NeurIPS), (2019)