We describe a procedure to reduce variable bounds in Mixed Integer Nonlinear Programming (MINLP) as well as Mixed Integer Linear Programming (MILP) problems. The procedure works by combining pairs of inequalities of a linear programming (LP) relaxation of the problem. This bound reduction technique extends the implied bounds procedure used in MINLP and MILP and can be seen as a special case of optimality based bound reduction, a method to infer variable bounds from the LP relaxation. For an LP relaxation with m constraints and n variables, the number of pairs of constraints is O(m^2), while a naive implementation of our proposed bound reduction scheme is O(n^3) for each pair. Therefore, its overall complexity is O(m^2 n^3), which can be prohibitive for relatively large problems. To this purpose, we have developed a more efficient procedure that has complexity O(m^2 n^2), and embedded it in two Open-Source solvers: one for MINLP and one for MILP. We provide computational results which substantiate the utility of this bound reduction technique for several instances.

## Article

Download

View Bound reduction using pairs of linear inequalities