Monte Carlo Method for Multiple Knapsack Problem

摘要

This paper describes Monte Carlo (MC) method for Multiple Knapsack Problem (MKP). The MKP can be defined as economical problem like resource allocation and capital budgeting problems. The Ant Colony Optimization (ACO) is a MC method, created to solve Combinatorial Optimization Problems (COPs). The paper proposes a Local Search (LC) procedure which can be coupled with the ACO algorithm to improve the efficiency of the solving of the MKP. This will provide optimal or near optimal solutions for large problems with an acceptable amount of computational effort. Computational results have been presented to assess the performance of the proposed technique.