An effective linear approximation method for separable programming problems

摘要

Among the numerous applications of piecewise linearization methods include data fitting, network analysis, logistics, and statistics. In the early 1950s, a concave function was found to be able to be linearized by introducing 0–1 variables. Most textbooks in Operations Research offer such methods for expressing linear approximations. Various methods of linearization have also been developed in recent literature. Nevertheless, the transformed linear scheme has a severe shortcoming: most standard procedures for linearizing typically involve a large increase in the number of binary variables. Consequently, the gains to be derived from dealing with linear functions are quite likely to be nullified by the increase in the size of the problem.Conventional methods for linearizing a concave function with m break points require m-1 binary variables. However, when m becomes large, the computation will be very time-consuming and may cause a heavy computational burden.This study proposes an effective approach in which only ⌈log2(m-1)⌉ binary variables are used. The proposed method has the following features: (i) it offers more convenient and efficient means of expressing a piecewise linear function; (ii) fewer 0–1 variables are used; (iii) the computational results show that the proposed method is much more efficient and faster than the conventional one, especially when the number of break points becomes large.