Conference Agenda

We present a new algorithm, the Parallel Enumeration Algorithm (PEA), for enumerating the nondominated set of tri-objective integer optimization problems. PEA only requires solving a linear number of lexicographic epsilon-constraint scalarization problems. Furthermore, PEA is easy to implement and easy to parallelize: A novel order on the nondominated set, induced by the structure of the parameter space of the lexicographic epsilon-constraint scalarization is utilized to split the computation into a number of independent parallel tasks, such that no communication between different tasks is required. Consequently, the communication overhead, one of the main factors of diminishing speedups, is minimal.

The performance of the algorithm was evaluated and compared to the CPLEX parallelization of a state-of-the-art sequential algorithm for tri-objective integer optimization problems on benchmark knapsack and assignment problems for up to 16 threads. Additionally, we investigated the scaling of PEA with up to 128 threads. The results of the computational study demonstrate the effectiveness of the proposed algorithm and the computational advantage of its parallelization, as it achieves an almost linear speed-up in the number of threads. Furthermore, the new algorithm outperforms the CPLEX parallelization of the state-of-the-art algorithm as soon as more than two threads are available.

Solving mixed-integer nonlinear problems by means of piecewise linear relaxations can be a reasonable alternative to the commonly used spatial branch-and-bound. These relaxations have been modeled by various mixed-integer models in recent decades. The idea is to exploit the availability of mature solvers for mixed-integer problems. In this work, we compare different reformulations in terms of behavior and runtime to determine which method to apply in practice. To this end, we implement eight different mixed-integer representations for piecewise linear relaxations and evaluate them on a benchmark set from the MINLPLib consisting of over 300 instances. We utilize existing expression trees to reformulate all nonlinearities to one-dimensional functions and afterwards compute a set of interpolation breakpoints for each function based on a given maximum error per segment. Our analysis includes a comprehensive comparison of the number of problems solved, runtimes, and optimality gaps. Overall, the classical incremental method Markowitz and Manne 1957 has the best performance, leading to a general recommendation of this method for solving nonlinear problems by piecewise linear relaxations.

Solving mixed-integer programming instances can be a time-consuming endeavor. Acceleration techniques include the exploitation of the problem's underlying structure. By decomposing the problem into subproblems it may be easier, sometimes even computationally efficient to solve. To that end, methods like Benders decomposition or Dantzig-Wolfe reformulation can lead to significant speedups in the solving process. However, the development and evaluation of algorithms that make use of a problem's structure require representative sets of test instances and their structure.

The structured integer programming library (strIPlib) is a public collection of about 40.000 instances and decompositions. Due to its size, it is impractical to use all instances, and the selection of instances can introduce bias and difficulties in the comparability of approaches.

To facilitate meaningful and reproducible research, we compile a benchmark and collection test set, using instance data, decomposition data, and data on the solving behavior, generated by the Generic Column Generation (GCG) solver. Additionally, we present a method to compile customized test sets based on user-defined filters on static and runtime data. The method aims to preserve diversity within filter arguments.

Preliminary results indicate that the benchmark and collection sets are representative (according to our metrics) of the full strIPlib to expected degrees and that the custom test set generation is a powerful tool for targeted experimentation.

At the beginning of each semester, all university students need to plan the courses they want to take this semester. In the process, they need to take into account the rules of their degree program. Those might, for example, regulate that some courses are compulsory, that one needs to complete a certain number of credits from a group of courses, or that one needs to choose a study focus from some given options. Also, there are additional considerations, such as the preferences of the student for certain subjects, the times when the courses are scheduled, or that some courses need to be taken in a certain order. In particular, it is a good idea to not just plan the courses of the upcoming semester, but all courses in all future semesters.

This leads to an optimization problem with multiple objectives that include, for example, minimizing the time until graduation and maximizing the satisfaction of the student with the selected courses. We propose an integer programming (IP) formulation for this problem and apply it to the Bachelor and Master degree in Mathematics at the Technical University of Munich (TUM). In our computational experiments, we could solve most of the tested instances in about one second using the non-commercial IP solver SCIP, and even faster with Gurobi. We made our planning tool available to the students of the Department of Mathematics at TUM. It is publicly accessible at https://studyplanner.co.cit.tum.de.