An effective linear approximation method for separable programming problems

Chia-Hui Huang

doi:10.1016/j.amc.2009.07.007

Return

An effective linear approximation method for separable programming problems

2009-10-01

PRE

Chia-Hui Huang *

DOI：10.1016/j.amc.2009.07.007

Original

Original request for help

Save

Abstract

En 中文

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 [log(2)(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. (C) 2009 Elsevier Inc. All rights reserved.

Keywords:

Separable function

Linear approximation

Piecewise linearization

Concave function