A Conditional Logic Approach for Strengthening Mixed 0-1 Linear Programs

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 select pairwise products of the problem constraints, and then surrogates modified versions of these inequalities to produce valid linear restrictions. There are two key ingredients that work cooperatively to yield improved representations. First, conditional logic is employed to adjust the coefficients on the quadratic restrictions while maintaining their validity. Second, the quadratic inequalities are strategically computed so that nonnegative surrogated having coefficients of zero in all the quadratic terms are available. The approach can be viewed as a unifying framework for published single and multiple coefficient increasing and decreasing methods that exploit such structure as special ordered sets, plant location and capacity expansion constraints, variable upper bounds, and logical implication restrictions that arise from pre-processing and probing techniques. It also generalizes the process of sequential lifting, which takes a valid linear inequality in a given variable space and lifts it to a higher-dimensional space. We give illustrative examples, and discuss various extensions, including the use of more complex conditional logic constructs that produce linear restrictions by computing and surrogating polynomial expressions, and the application to general integer programs.