A heuristic based on simulated annealing for solving linear programming problems with logical constraints

Abstract

Several problems such as blending problems, bundle pricing problems, logic design and circuits problems can be formulated as linear programs with logical constraints. It can be shown that the problem of solving a linear program with logical constraints is NP-hard, so there is a need for heuristic solution methods. The concept and the different elements of simulated annealing are described and several critical remarks on the technical parameters of simulated annealing and the consequences of certain choices of these parameters are made. A heuristic method for solving linear programs with logical constraints is then constructed. Each required element is identified, described and its link with simulated annealing is shown. Test results for deciding on the values of the technical parameters are given.