Identification of unidentified equality constraints for integer programming problems

Characterising the smallest dimension polytope containing all integer solutions of an integer programming problem can be a very challenging task. Frequently, this task is facilitated by identifying linear equality constraints that all integer solutions must satisfy. Typically, some of these constraints are readily available but others need to be discovered by more technical means. This paper develops a method to assist modellers to obtain such equality constraints. Note that the set of new equality constraints is not unique, and the proposed method generates a set of these new equality constraints for a sufficiently large dimension of the underlying problem. These generated constraints may be of a form that is easily extended for general case of the underlying problem, or they may be in a more complicated form where a generalisable pattern is difficult to identify. For the latter case, a new mixed-integer program is developed to detect a pattern-recognisable constraints. Furthermore, this mixed-integer program allows modellers to check if there is a new constraint satisfying specific criteria, such as only permitting coefficients to be 1, 0, and −1, or placing a limit on the number of non-zero coefficients. In order to illustrate the proposed method, a set of new equality constraints to supplement a previously published “Base polytope” are derived. Subsequently, exploiting these results, some techniques are proposed to tighten integer programming problems. Finally, relaxations of widely used TSP formulations are compared against one another and strengthened with help of the newly discovered equality constraints.