A dual temperature simulated annealing approach for solving bilevel programming problems

This paper presents a dual temperature simulated annealing approach to bilevel programming problems. Bilevel programming problems arise when one optimization problem, the inner problem, is a constraint of a second optimization problem, the outer problem. In this paper, the inner problem is stochastically relaxed with a parameter that can be used as a temperature scale in simulated annealing. Solving the outer problem with simulated annealing as well leads to the dual temperature approach. The technique is demonstrated with several linear, nonlinear, and mixed integer nonlinear bilevel programming problems, including a safe plant layout problem that simultaneously minimizes cost and the damage caused during a worst case scenario accident. (C) 1998 Elsevier Science Ltd. All rights reserved.