It is an important task to obtain optimal solutions for multidimensional linear integer problems with multiple constraints. The surrogate constraint method translates a multidimensional problem into an one dimensional problem using a suitable set of surrogate multipliers. In general, there exists a gap between the optimal solution of the surrogate problem and the original multidimensional problem. Moreover, computing suitable surrogate constraints is a computationally difficult task. In this paper we propose a method for computing surrogate constraints of linear problems that evolves sets of surrogate multipliers coded in floating point and uses as fitness function the value of the ε-approximate solution of the corresponding surrogate problem. This method allows the user to adjust the quality of the obtained multipliers by means of parameter ε. Solving 0-1 multidimensional knapsack problems we test the effectiveness of our methodology. Experimental results show that our method for computing surrogate constraints for linear 0-1 integer problems is at least as effective as other strategies based on Linear Programming as that proposed by Chu and Beasley in [6].
展开▼
