  The characterization of strong valid inequalities for integer and
mixed-integer programs is more of an artistic task than a systematic
methodology, requiring inspiration that can sometimes be elusive. Frequently,
this task is facilitated by somehow exploiting the structure of problems for
devising strong valid inequalities. Subsequently, various mathematical
techniques are utilized for proving that those inequalities, which are often
easily shown to be valid, are indeed strong in the sense that they represent
facets or other high dimensional faces. This paper develops a method to assist
modelers in the challenge to devise strong valid inequalities. In each
iteration, the proposed algorithm generates a valid inequality by solving a
suitably constructed linear mixed integer program and applies some quality
criteria in order to determine if it is a new strong valid inequality. To
illustrate the proposed algorithm, a new Traveling Salesman Problem (TSP)
formulation is developed based on a set of constraints already constructed in
the context of the Hamiltonian Cycle Problem (HCP), and then the proposed
algorithm is employed to derive a set of strong inequalities to tighten this
TSP formulation. Finally, a comparison study between the relaxation of the new
TSP formulation and that of a state-of-the-art TSP formulation is conducted.
The computational study confirms the effectiveness of the devised inequalities
due to the better quality of the relaxation provided by the new formulation.
