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

Josef Kallrath (), Robert Blackburn () and Julius Näumann ()
Additional contact information
Josef Kallrath: University of Florida, Department of Astronomy
Robert Blackburn: Karlsruhe Institute of Technology, Discrete Optimization and Logistics
Julius Näumann: Technical University of Darmstadt

A chapter in Modeling, Simulation and Optimization of Complex Processes HPSC 2018, 2021, pp 83-96 from Springer

Abstract: Abstract 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.

Date: 2021
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-030-55240-4_4

Ordering information: This item can be ordered from
http://www.springer.com/9783030552404

DOI: 10.1007/978-3-030-55240-4_4

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().