| Abstract: |
Characterizing the smallest dimension polytope containing all integer solution 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 modeler to obtain such equality constraints. The set of new
equality constraints is not unique and the proposed method generates a set of
these new equality constraints for some instances of the underlying problem. These
generated constraints may, or may not, be easily extendable to the general case of
the underlying problem. For the latter case, a mixed-integer program is developed
to detect an extendable new constraint. Furthermore, this mixed-integer model
allows modeler to check if there is a new constraint satisfying problem specific
criteria. These criteria can restrict the coefficients to be 1,0, and −1 or having
a sparse constraint. In order to elaborate the proposed method, a set of new
equality constraints defining a previously published “Base polytope” are derived.
Subsequently, exploiting these results, some techniques are proposed to tighten
integer program problems. Finally, relaxation of widely used TSP formulations are
compared against one another and strengthened with help of the newly discovered
equality constraints. |