Particle swarm optimization for integer programming.pdf

Particle Swarm Optimization for Integer Programming E.C. Laskari, K.E. Parsopoulos and M.N. Vrahatis Department of Mathematics, University of Patras Articial Intelligence Research Center (UPAIRC), GR-26110 Patras, Greece felena, kostasp, vrahatisg@math.upatras.gr Abstract - The investigation of the performance of the Particle Swarm Optimization (PSO) method in Integer Programming problems, is the main theme of the present paper. Three variants of PSO are compared with the widely used Branch and Bound technique, on several Integer Programming test prob- lems. Results indicate that PSO handles eciently such problems, and in most cases it outperforms the Branch and Bound technique. I. INTRODUCTION A remarkably wide variety of problems can be rep- resented as discrete optimization models [17]. An im- portant area of application concerns the ecient man- agement of a limited number of resources so as to in- crease productivity and/or prot. Such applications are encountered in Operational Research problems such as goods distribution, production scheduling, and machine sequencing. There are applications in mathematics to the subjects of combinatorics, graph theory and logic. Statistical applications include problems of data analy- sis and reliability. Recent scientic applications involve problems in molecular biology, high energy physics and x{ray crystallography. A political application concerns the division of a region into election districts [17]. Cap- ital budgeting, portfolio analysis, network and VLSI cir- cuit design, as well as automated production systems are some more applications in which Integer Programming problems are met [17]. Yet another, recent, and promising application is the training of neural networks with integer weights, where the activation function and weight values are conned in a narrow band of integers. Such neural networks are better suited for hardware implementations compared to real weight ones [26]. The Unconstrained Integer Programmin