A Conditional Logic Approach for Strengthening Mixed 0-1 Linear Programs |
| |
Authors: | Email author" target="_blank">R?Lougee-HeimerEmail author W?Adams |
| |
Institution: | (1) Mathematical Sciences, IBM T.J. Watson Research Center, Yorktown Heights, New York, 10598;(2) Department of Mathematical Sciences, Clemson University, Clemson, South Carolina, 29631 |
| |
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.
Partially supported by NSF grant #DMI-0423415 and ONR grant #N00014-97-1-0784. |
| |
Keywords: | integer programming coefficient adjustment cutting planes continuous relaxation |
本文献已被 SpringerLink 等数据库收录! |
|