A conditional logic approach for strengthening mixed 0–1 linear programs

A conditional logic approach for strengthening mixed 0–1 linear programs

0.00 Avg rating0 Votes
Article ID: iaor2006992
Country: Netherlands
Volume: 139
Issue: 1
Start Page Number: 289
End Page Number: 320
Publication Date: Oct 2005
Journal: Annals of Operations Research
Authors: ,
Keywords: cutting plane algorithms
Abstract:

We study a conditional logic approach for tightening the continuous relaxation of a mixed 0–1 linear program. The procedure first constructs quadratic inequalities by computing pairwise products of constraints, and then surrogates modified such inequalities to produce valid linear restrictions. Strength is achieved by adjusting the coefficients on the quadratic restrictions. The approach is a unifying framework for published coefficient adjustment methods, and generalizes the process of sequential lifting. We give illustrative examples and discuss various extensions, including the use of more complex conditional logic constructs that compute and surrogate polynomial expressions, and the application to general integer programs.

Reviews

Required fields are marked *. Your email address will not be published.