Minimizing the Sum of Absolute Deviations

In some applications, we are given several linear objective functions of the decision variables,

               z_t(x)  =  c^t₁x₁ + . . . . +  c^t_nx_n  =  d_t  ,         t = 1  to  k             (1)

             where  d_t  is the desired values. In addition may be required to satisfied a specified system of linear constraints constraints, which we denote by ( P ).

The problem is than to find a solution  x  satisfying the constraints in ( P ) and the ( 1 ).

Now if there is a solution than it is the best solution for this problem. However, it may possible that ( P ) and ( 1 ) together may not have feasible solution. In this case, a feasible solution of ( P ) which minimizes

                 a(x) =    ∑₁^k  | c^t₁x₁ + . . . . +  c^t_nx_n  -  d_t  |                    (2)

known as a minimum absolute deviation solution, could be considered as the best solution for this problem.

                 u_t =   c^t₁x₁ + . . . . +  c^t_nx_n  -  d_t   =  u_t⁺ - u_t^-                 (3)          .

                                                                   u_t⁺ ,  u_t^-  ≥  0   

 u_t   is the deviation in the objective function   z_t(x)    from its desired value of   at the point x, any be positive, negative or zero, and it can always be expressed as the difference of two non-negative variables which we denote u_t⁺(positive part),  u_t^- (negative part) .

and

                         a(x)  =   ∑₁^k  | u_t |                                                                         (4)

is the sum of absolute deviations.         

We are defining         

                   

                         u_t⁺      =    0                    if   u_t  ≤  0

                    u_t⁺      =    u_t                      if   u_t  >  0 

 

                    u_t^-       =   0                     if   u_t   ≥  0

                    u_t^-       =   -u_t                   if   u_t   <  0                           (5)

        

 

we guarantee that

                    u_t⁺ u_t^-    =  0                                                                (6)

 

Now, we have the LP as follows

           Minimize     ∑₁^k  ( u_t⁺ + u_t^- )                             .

           subject to     c^t₁x₁ + . . . . +  c^t_nx_n  -  u_t⁺ + u_t^-  =   d_t  ,      t = 1 to k

                                                                   u_t⁺ ,  u_t^-  ≥  0           for all t

            and the constraints in ( P )                                                                           (7)

 

 

Suppose we are given positive weights   w_t   corresponding to   z_t(x)   for  t = 1 to k. The higher the weight of an objective function, the higher its priority, i.e. , the more important it is that its value be closure to its desired value.

In this case the best solution to the problem that minimizes the weighted cost function

                                               ∑₁^k w_t( u_t⁺ + u_t^- )           subject to constraint (7).

Goal Programming