Expensive Optimization with Production-Graph Resource Constraints: A First Look at a New Problem Class

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

  • External authors:
  • Stefan Pricopie
  • Clyde Fare
  • Matt Benatan


We consider a new class of expensive, resource-constrained optimization problems (here arising from molecular discovery) where costs are associated with the experiments (or evaluations) to be carried out during the optimization process. In the molecular discovery problem, candidate compounds to be optimized must be synthesized in an iterative process that starts from a set of purchasable items and builds up to larger molecules. To produce target molecules, their required resources are either used from alreadysynthesized items in storage or produced themselves on-demand at an additional cost. Any remaining resources from the production process are stored for reuse for the next evaluations.We model these resource dependencies with a directed acyclic production graph describing the development process from granular purchasable
items to evaluable target compounds. Moreover, we develop several resource-efficient algorithms to address this problem. In particular, we develop resource-aware variants of Random Search heuristics and of Bayesian Optimization and analyze their performance in terms of anytime behavior. The experimental results were obtained from a real-world molecular optimization problem. Our results suggest that algorithms that encourage exploitation by reusing existing resources achieve satisfactory results while using fewer resources overall.

• Theory of computation→Random search heuristics; • Mathematics of computing→Probabilistic algorithms.

molecular discovery, production costs, resource constraints, expensive optimization

Bibliographical metadata

Original languageEnglish
Title of host publicationGECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference
Publication statusAccepted/In press - 25 Mar 2022