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

 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.



References:

[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.