Agent Based Decomposition of Optimization Problems

Document type: Conference Papers
Peer reviewed: Yes
Full text:
Author(s): Johan Holmgren, Jan A. Persson, Paul Davidsson
Title: Agent Based Decomposition of Optimization Problems
Conference name: First International Workshop on Optimization in Multi-Agent Systems
Year: 2008
City: Estoril, Portugal
Organization: Blekinge Institute of Technology
Department: School of Engineering - Dept. of Systems and Software Engineering (Sektionen för teknik – avd. för programvarusystem)
School of Engineering S- 372 25 Ronneby
+46 455 38 50 00
Authors e-mail:,,
Language: English
Abstract: In this paper, we present an agent-based approach for solving an optimization problem using a Dantzig-Wolfe column generation scheme, i.e., a decomposition approach. It has
been implemented and tested on an integrated production, inventory, and distribution routing problem. We developed a decomposition model for this optimization problem, which
was implemented in the Java programming language, using the Java Agent DEvelopment Framework (JADE) and the ILOG CPLEX mixed integer linear problem solver. The
model was validated on a realistic scenario and based on the results, we present estimates of the potential performance gain by using a completely distributed implementation. We
also analyze the overhead, in terms of communication costs, imposed by an agent based approach. Further we discuss the advantages and the disadvantages that comes with an
agent-based decomposition approach.
Subject: Computer Science\Artificial Intelligence
Computer Science\General