A simulated annealing code for general integer linear programs

A simulated annealing code for general integer linear programs

0.00 Avg rating0 Votes
Article ID: iaor2000448
Country: Netherlands
Volume: 86
Issue: 1
Start Page Number: 3
End Page Number: 21
Publication Date: Mar 1999
Journal: Annals of Operations Research
Authors: ,
Keywords: programming: integer, combinatorial optimization
Abstract:

This paper explores the use of simulated annealing (SA) for solving arbitrary combinatorial optimisation problems. It reviews an existing code called GPSIMAN for solving 0–1 problems, and evaluates it against a commercial branch-and-bound code, OSL. The problems tested include travelling salesman, graph colouring, bin packing, quadratic assignment and generalised assignment. The paper then describes a technique for representing these problems using arbitary integer variables, and shows how a general simulated annealing algorithm can also be applied. This new code, INTSA, outperforms GPSIMAN and OSL on almost all of the problems tested.

Reviews

Required fields are marked *. Your email address will not be published.