The Quadratic Knapsack Problem (QKP) is a well-known combinatorial optimization problem which has many applications in finance, logistics, telecommunications, facility location problems, etc. The QKP is NP-hard in the strong sense and the existing state-of-the-art algorithms can only handle problems of small and moderate sizes. This presentation is mainly aimed at discussing some recent contributions in the development of heuristic solution methods for large scale and challenging QKP instances. The strengths as well as the weaknesses of each of those methods will be discussed.

We study a family of discrete optimization problems asking for the maximization of the expected value of a concave, strictly increasing, and differentiable function composed with a set-union operator. The expected value is computed concerning a set of coefficients taking values from a discrete set of scenarios. The function models the utility function of the decision maker, while the set-union operator models a covering relationship between two ground sets, a set of items, and a set of metaitems. This problem and it can be modeled as a mixed integer nonlinear program involving binary decision variables associated with the items and metaitems. Its goal is to find a subset of metaitems that maximizes the total utility corresponding to the items it covers. It has applications to, among others, maximal covering, location of critical infrastructures and influence maximization problems.

Despite wide application domains, significant optimisation potential, and tremendous advancements in solving mathematical programs over the last decades, it appears that mathematical programming still faces difficulties with regard to wider adoption in many organisations. Moreover, its importance in the perception of the general public appears to fall short in comparison with other approaches, e.g. those subsumed under the term artificial intelligence. One obstacle to wider adoption of mathematical programming is the widespread lack of mathematical proficiency in many organisations. Consequently, developing and maintaining mathematical models of decision problems is a time- and cost-consuming challenge with a large upfront investment and unknown return. On the other hand, many organisations have already developed substantial modelling skills in terms of business process modelling due to the immediate benefit that can be obtained even without optimisation. With BPMN 2.0 an industry standard for business process modelling has evolved with a growing toolset supporting the standard. Leveraging the growing software ecosystems and modelling capabilities concerning BPMN 2.0, this presentation proposes a new class of mathematical programs allowing domain experts to formulate mathematical programs without the need to learn how to model a linear program, mixed integer program, constraint program and many others. Instead, the new class of mathematical programs allows modellers to specify so-called processual programs by a set of process models with additional data relevant for process execution. Examples show how classical optimisation problems, e.g., the assignment problem, the knapsack problem, the bin packing problem, job shop scheduling problems, vehicle routing problems, etc. can be formulated as processual programs. With the graphical representation of business problems, processual programs can build an important communication tool between domain experts and optimisation experts. Moreover, general-purpose solvers for processual programs can be developed, allowing domain experts to model and solve optimisation problems without the need to consult optimisation experts as long as no special-purpose approach exploiting the specific characteristics of the application case is necessary. The development of powerful general-purpose processual programming solvers, however, is still a challenge that requires future research. To facilitate such research, a modular open source framework allowing to simulate and optimise processual programs has been developed. The framework allows to easily replace modules responsible for making decisions during process execution and, thus, allows module developers to focus on the decision-making approaches without the need to implement process execution logic.