Grid-Enhanced Polylithic Modeling and Solution Approaches for Hard Optimization Problems

We present a grid enhancement approach (GEA) for hard mixed integer or nonlinear non-convex problems to improve and stabilize the quality of the solution if only short time is available to compute it, e.g., in operative planning or scheduling problems. Branch-and-bound algorithms and polylithic modeling & solution approaches (PMSA)—tailor-made techniques to compute primal feasible points—usually involve problem-specific control parameters $$\mathbf {p}$$ p . Depending on data instances, different choices of $$\mathbf {p}$$ p may lead to variations in run time or solution quality. It is not possible to determine optimal settings of $$\mathbf {p}$$ p a priori. The key idea of the GEA is to exploit parallelism on the application level and to run the polylithic approach on several cores of the CPU, or on a cluster of computers in parallel for different settings of $$\mathbf {p}$$ p . Especially scheduling problems benefit strongly from the GEA, but it is also useful for computing Pareto fronts of multi-criteria problems or computing minimal convex hulls of circles and spheres. In addition to improving the quality of the solution, the GEA helps us maintain a test suite of data instances for the real world optimization problem, to improve the best solution found so far, and to calibrate the tailor-made polylithic approach.