Handling Nonlinear Integer Programs

Nonlinear IP problems can be converted to linear integer programs using binary variables. We shall illustrate this with a numerical example. 

This nonlinear integer problem can be converted to a linear IP problem for solution. Observe the fact that for any positive k and a binary variable Xj, x) = Xj. Hence, the objective function immediately reduces to Z = % + X2X3 - X3. Now consider the product term X2X3. For binary values of X2 and x, the product X2X3 is always 0 or 1. Now introduce a binary variable i/j such that i/j = XjXj. When X2 = x = 1, we want the value of 1/1 to be 1, while all other combinations of should be zero. This can be achieved by introducing the following two constraints  

Thus the equivalent linear (binary) integer program becomes Maximize 

A drawback of the aforementioned procedure for handling product terms is that an integer variable is introduced for each product term. It has been observed in practice that the solution time for IP problems increases with the number of integer variables. An alternate procedure has been suggested by Glover and Woolsey (1974) that introduces a continuous variable rather than an integer variable. This procedure replaces X2X3 by a continuous variable X23 and introduces three new constraints as follows  

Whenever X2, X3 or both are zero, the last two constraints force Xj3 to be zero. When %2 = 3 = 1/ all the three constraints together force Xj3 to be 1. The primary disadvantage of this procedure is that it adds more constraints than the previous method. 

---