(12f) Mip in Agent Systems: Algorithmic Collaboration or the Lack Thereof | AIChE

(12f) Mip in Agent Systems: Algorithmic Collaboration or the Lack Thereof


Siirola, J. D. - Presenter, Carnegie Mellon University
Hauan, S., Carnegie Mellon University

Historically, process optimization has focused on two primary areas of research: development of optimization algorithms and development of problem formulations. Both of these areas focus primarily on the single-threaded optimization of a single problem using a single computer processor. In contrast, the emerging standard for high-performance computing is the distributed computing cluster. While clusters excel at both high-throughput single-threaded batch processing and large-scale parallel computations, general optimization does not lend itself well to either of these approaches. Instead, we propose the use of collaborative agent-based systems and parallelism at the method level as a promising third approach for leveraging parallel resources for general optimization.

In previous work, we demonstrated how combining rigorous, stochastic, and heuristic algorithms in a collaborative environment could solve single [1] and multi-objective [2] optimization problems that none of the individual algorithms could solve in isolation. We further showed how to combine multiple problem formulations through an extension to the collaborative system we termed, "Polymorphic Optimization" [3,4]. In these systems, diverse sets of transient algorithms interact asynchronously by sharing intermediate and final solutions to the problem through a centralized database of problem information. Through this interaction, the system as a whole substantially outperforms any of the individual algorithms working in isolation. However, these applications were all linked by the absence of a single algorithm that could provide a guarantee of optimality, and consequently, the multi-agent optimization system was unable to provide a guarantee of optimality.

In this work, we address the integration of branch-and-bound optimization algorithms into a collaborative optimization system. These algorithms can provide a guaranteed optimal solution and require a fundamentally different collaborative structure compared to the transient local optimization and stochastic search algorithms used in our previous work. We present a candidate collaborative structure and illustrate its application to both synthetic mixed-integer linear (MILP) and general batch scheduling problems. Our results indicate that, while the collaborative multi-agent system is able to identify the optimal solution significantly faster, there are instances where standard off-the-shelf MILP solvers can take significantly longer to prove the solution optimality. This suggests new directions for developing improved branch-and-bound algorithms designed explicitly to operate in collaborative environments.


[1] J.D. Siirola, S. Hauan, and A.W. Westerberg. "Toward Agents-Based Process Systems Engineering: Proposed Framework and Application to Non-convex Optimization." Comp.Chem.Engng. 27(12), pp. 1801-1811 (2003). [2] J.D. Siirola, S. Hauan, and A.W. Westerberg. "Computing Pareto Fronts using Distributed Agents". Comp.Chem.Engng. 29(1), pp. 113-126 (2004). [3] A.J. Pfeiffer, J.D. Siirola, and S. Hauan. "Optimal design of microscale separation systems using distributed agents." In the Proceedings of FOCAPD 2004, pp. 381-384 (2004). [4] J.D. Siirola and S. Hauan. "Polymorphic Optimization." Submitted to Comp.Chem.Engng. May, 2005.