Heuristics based on tabu search and Lagrangean relaxation for the concave production-transportation problem

Recently, strongly polynomial time algorithms have been developed for special concave minimization problems under network constraints and with a fixed number of nonlinear variables. In many cases these algorithms are not computationally efficient unless the number of nonlinear variables is very small. However, the ideas behind these algorithms can be utilized and embedded in heuristics which then will be able to solve large scale problems. This paper presents a tabu search heuristic for a convave production-transportation problem, which based on a strongly polynomial algorithm, searches the domain of feasible solutions to the problem. Tabu search as well as other iterative improvement heuristics lack rigorous termination criteria. In particular no a-posteriori information about the obtained solution is available. Therefore, a bounding procedure based on Lagrangean relaxation is also developed which can be used as a qualifier of the feasible solutions generated.