Applications of Combinatorial Optimization, 2nd Edition

Chapter 3

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.

3.1. Introduction

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:

– the traveling salesman problem [APP 01, CRO 80, PAD 87];

– the Steiner tree problem in graphs [CHO 92, CHO 94];

– network topology problems with connectivity constraints [GOE 94, GRÖ 92a, GRÖ 92b, GRÖ 95];

– multiflow optimization problems ...