The following information was submitted:
Transactions: WSEAS TRANSACTIONS ON MATHEMATICS
Transactions ID Number: 53-401
Full Name: Ivan Depich
Position: Professor
Age: ON
Sex: Male
Address: Avda Ecuador 3769 Santiago
Country: CHILE
Tel: 56 2 7184208
Tel prefix:
Fax:
E-mail address: ivan.derpich@usach.cl
Other E-mails: iderpich@gmail.com
Title of the Paper: A Heuristic for the Multi-knapsack Problem based in interior ellipses
Authors as they appear in the Paper: Jose Grandon and Ivan Derpich
Email addresses of all the authors: grandonjose@gmail.com, ivan.derpich@usach.cl
Number of paper pages: 10
Abstract: - In this work a heuristic for the problem multi-knapsack , based on directions of ascent is presented. These directions are generated from a center of the polyhedron and they conduct to good approximations of the integer solutions. For it a center of the polyhedron of the relaxed problem is obtained. Then an interior ellipse is constructed in this polyhedron and those eigenvectors of the ellipse that present the best objective ascent of the function are selected as ascent direction. For determine how many eigenvectors to use, an angle that relate the eigenvector with the objective function, was used. The heuristic algorithm has been proved with problems from the OR-library. Four groups of problems were proved with 30 instances every one, combining 100 and 250 variables with 5 and 10 constraints. The results show process time that are from a little seconds for little problems, to 400 seconds for bigger problems. The Cpu time average is 190 seconds.
Keywords: Heuristics, Integer Programming, Multi-knapsack
EXTENSION of the file: .doc
Special (Invited) Session:
Organizer of the Session:
How Did you learn about congress: optimization, Heuristics, Integer Programming, Multi-knapsack
IP ADDRESS: 158.170.168.194
