OR 2025 Bielefeld

Hexaly is a mathematical optimization solver based on various operations research techniques, combining both exact and approximate methods such as linear programming, non-linear programming, constrained programming and primal heuristics. Knowing model features and recognizing special cases is imperative to selecting the right methods for solving the problem as fast as possible. One such model feature is convexity. Recognizing a convex model as such allows selecting more efficient algorithms under Hexaly’s hood. In this talk we will present how Hexaly determines a user model’s convexity. Convexity analysis typically examines the expression tree of the continuous relaxation of the model constraint by constraint. Combining knowledge of convexity-preserving operations with known properties of basic functions allows evaluating the curvature of complicated constraints and objectives. This can be straightforward to compute, e.g. positive sums of convex functions are convex. However, already for quadratic programmes convexity detection by this method can be ineffective: depending on the formulation of the functions as well as how they are translated into the expression tree it may not be possible to determine a convex problem as such. Of course, in the case of quadratic programming, spectral analysis can be applied. However, this is computationally expensive, and can sometimes be avoided, e.g. by application of Gershgorin’s circle theorem. We will present data from numerical experiments about the reliability of our implementation of convexity detection in Hexaly.

This talk presents an industrial application for workforce planning in a network of daycare centers and animal care facilities. The schedules are optimized for a week and aim to plan the activities of several hundred employees, considering about ten different functions. Each employee has specific availability constraints, work hour limits, and role qualifications. The demand for each function is determined by legal requirements regarding staff-to-child ratios and operational needs.

The problem is modeled with boolean decision variables representing employee-shift assignments, where shifts are generated based on minimum/maximum durations and time increments. The optimization model minimizes understaffing and overstaffing while respecting all operational constraints (legal requirements, employee work hour limits, and specific scheduling rules).

This highly combinatorial optimization problem has been efficiently solved using Hexaly, a global optimization solver combining exact and heuristic methods. The solver provides optimal solutions within minutes for real-world instances. Based on this optimization model, a web application has been developed. A demonstration of this application will be presented during the talk.