Probing the Pareto front of a large-scale multiobjective problem with a MIP solver

The rapid growth of computing power and the development of highly effective optimization solvers build the appetite for solving increasingly extensive problems. However, despite all these efforts, resource constraints (time, memory) often strike back. The ”curse of dimensionality” haunts primarily combinatorial problems, but not only. The issue is even more acute in multiobjective optimization, where several Pareto optimal solutions have to be derived. In our earlier works, we developed a general methodology for multiobjective optimization that allows representing the outcome of a Pareto optimal solution by a hyperrectangle. The sides of the hyperrectangle are defined by lower and upper bounds on the outcome components, i.e., intervals of possible objective function values. Such a representation makes sense if the Pareto optimal solution cannot be derived with the available computation resources. Beyond the research interest, to be of practical value, methodologies of that kind have to be computationally effective and scalable. In this work, we show that our methodology can be effectively coupled with any MIP optimization solver. With that, as long as an analyst is willing to accept a (sufficiently tight) interval representation of the Pareto optimal solution outcome instead of its exact outcome, our methodology scales multiobjective-based analyses well beyond the reach of the MIP solver itself. We operationalize our methodology in the form of a workflow (we nicknamed it Crescent Workflow). We illustrate the workflow working on several large-scale instances of the multiobjective multidimensional 0–1 knapsack problem with three objectives.