It's a Bum Rap: "Multi-Agent Systems Cannot Find Global Optima"

[Bert . Baker]

I am tired of hearing that multi-agent systems cannot find globally optimal
solutions to discrete optimization problems.  It is a misleading statement.


The issue is not with multi-agent systems but with discrete optimization
problems.

For the vast majority of realistic discrete optimization problems global
optimization is a NP-complete or NP-hard problem, whether the problem is
being solved by a centralized algorithm or agents.  This includes
nonpreemptive job-shop and flow-shop scheduling problems with more than two
machines, Integer Programming problems, the traveling salesman problem, the
general knapsack problem, and bin packing.

Contrary to popular belief, most discrete optimization problems which can
be globally optimally solved, can be globally optimally solved by a
meaningful multi-agent system often in less time than the corresponding
centralized algorithm.  By meaningful I mean in a heterarchical
architecture (i.e. a pure peer-to-peer system) where

        * the computation across agents is substantially balanced and

        * agents represent physical entities in the system which

        * can be dynamically added or subtracted from the system with only
          polynomially sized changes in the algorithms which are being
          executed.

Optimization problems which can be globally optimally solved in a
meaningful multi-agent heterarchy (MAH) include the maximum lateness,
minimum tardiness, minimum number of tardy jobs, minimum average lateness,
and minimum average flow time problems on a single machine, where each job
has its own agent.  The list also includes the minimum weighted average
flow-time problem on identical parallel machines without preemption, many
machine routing problems, and the minimum makespan problem for 2 machine
flow-shops and 2 machine job-shops, where in some cases the machines are
agented and in others the jobs are agented.  The shortest path problem can
also be solved in a meaningful MAH in less time than it can be solved by a
centralized algorithm, in this case agents represent each possible node in
the path.  Polynomially solvable versions of the knapsack problem can also
be solved in a meaningful MAH.  Also, the heuristic algorithms which are
most commonly used in industry can be implemented in a meaningful MAH.
These include all common dispatch algorithms, pull algorithms, and forward
/ backward scheduling algorithms.

There are reasons to believe that recent new suboptimal algorithms for
solving discrete optimization problems can also be solved in a meaningful
MAH.  These include Lagrangian relaxation approaches to Integer
Programming, simulated annealing, and deterministic simulation.

Problems which can be solved by centralized algorithms in polynomial time
but which apparently have unsatisfactory MAH solutions are limited.  These
include the minimum makespan parallel machine problem with preemption and
the minimum average flow-time problem on parallel uniform machines without
preemption.  Also, I know of no meaningful MAH solution to the minimum
average flow-time problem on parallel non-uniform machines whereas a
globally optimum solution can be found in polynomial time using a
centralized algorithm.

In conclusion, it is misleading to say that MAHs can not find theoretical
global optima in discrete optimization problems.  Though the architecture
reduces the number of problems which can be solved, the reduction is small.
In general, problems which can be solved, can be solved in a meaningful
MAH.  This is especially true of the suboptimal algorithms used everyday in
most installed industrial software.  This is probably the most important
class of algorithms to solve in a MAH.

In our emerging multi-agent world, we should expect the broad use of MAHs
addressing discrete optimization problems.  Not only do we lose very
little, but we can gain all the advantages of the agent approach.

For detailed references see http://www.ececs.uc.edu/~abaker/AgentAlgs.ps.


address@hidden
University of Cincinnati







                  ==================================
   Swarm-Modelling is for discussion of Simulation and Modelling techniques
   esp. using Swarm.  For list administration needs (esp. [un]subscribing),
   please send a message to <address@hidden> with "help" in the
   body of the message.
                  ==================================