Optimizing a Constraint: Reconstructing an Integer Programming Constraint More Simply

Problem Statement

In an integer programming problem the following constraint occurs:[19]

\[ 9x_1 + 13x_2 - 14x_3 + 17x_4 + 13x_5 - 19x_6 + 23x_7 + 21x_8 \le 37. \]

All the variables occurring in this constraint are 0-1 variables, i.e. they can only take the value of 0 or 1.

Find the ‘simplest’ version of this constraint. The objective is to find another constraint involving these variables which is logically equivalent to the original constraint but which has the smallest possible absolute value of the right-hand side (with all coefficients of similar signs to the original coefficients).

If the objective were to find an equivalent constraint where the sum of the absolute values of the coefficients (apart from the right-hand side coefficient) were a minimum what would be the result?


[19] Reproduced with permission of John Wiley & Sons Ltd. (Williams 1999, p. 249).