A Comparison of Some Valid Inequality Generation Methods for General 0–1 Problems
We examine and compare different techniques for generating valid inequalities for linear 0–1 variable programs of general structures. The approaches used include classical techniques such as lift and project, disjunctive programming, and reformulation–linearization techniques. We have also included in our study a novel approach called restriction separation and relaxed lifting (RSRL) for generating valid inequalities (two variants of this method are implemented). Systematic comparisons of the computational results are made on test multidimensional knapsack problems by considering three principal criteria: the quality of the inequalities generated measured by the ratio between the two sides of the inequality; the quality of the inequalities measured by the strengthening brought to the continuous relaxation; and the computation time for the generation.
Since the end of the 1970s, polyhedral combinatorics has been a very active research domain which, in particular, has allowed us to provide very effective solution techniques for dealing with structured combinatorial optimization problems. Among these many studies, we mention in particular: