Maximizing value of objective function containing absolute values

[bps...@g.rit.edu]

Hi All,

I am supposed to maximize the value of the objective function consisting of two absolute values. I adopted the approach of writing the variable as difference of two positive numbers (z=x-y where x>=0,y>=0) and then replacing objective by x+y. This gives me an unbounded solution, and this seems to be valid only for minimization problems.  Is there a way to maximize sum of two absolute values?

[Robert Fourer]

To maximize the absolute value, you need to add a constraint that explicitly states "x = 0 or y = 0". You could write x * y = 0 but that makes your problem into a difficult nonlinear one. Instead the common practice is to introduce a binary (zero-one) variable b and some constraints that force x to be zero when b is 0, and y to be zero when b is 1. For instance if U is an upper limit on z, you can write

x <= U * b
y <= U * (1-b)

For CPLEX and Gurobi 7.0 you can instead write an "indicator" constraint,

b = 0 ==> x = 0 else y = 0

which describes the constraint more directly and doesn't require you to choose U. Or you can use AMPL's piecewise-linear notation for the absolute value,

<<0; -1,+1>> z

and let AMPL add all of the auxiliary variables and constraints. (See chapter 17 of the AMPL book, http://ampl.com/BOOK/CHAPTERS/20-piecewise.pdf.) However you do it, you will end up needing a mixed-integer solver; there's no way to convert maximization of absolute values into a linear optimization problem that has only continuous variables.

Bob Fourer
am...@googlegroups.com

=======