An example to demonstrate the importance of using ellipsoidal norm in lattice basis reduction for branching on hyperplane algorithms

The use of lattice basis reduction has been proposed in reformulating instances of hard integer programs. We construct integer programming instances showing that branching on hyperplane algorithms may benefit from using the geometrical information of the feasible set using an ellipsoidal approximation of the linear relaxation while using lattice basis reduction methods. Feasible as well as infeasible instances of these problems in four dimensions are given.