A simulated annealing code for general integer linear programs

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