On various relaxations based on reformulation-linearization for 0-1

MIPs and their specialization to pseudoboolean optimization

M. Minoux

Abstract:

The use of valid inequalities deduced from optimizing over the rank-1

Lift&Project Closure has been shown to provide good quality bounds for some

classes of quadratic pseudoboolean optimization problems such

as MAX-2SAT. We will discuss links with other families of relaxations,

in particular the RLT hierarchy ( Sherali & Adams, 1990).

We show that known simple links between rank-1 Sherali-Adams

(RLT) relaxation and rank-1 Lift-and-Project closure do not readily

extend to rank 2 or more.To investigate the latter case, we introduce a new

hierarchy of relaxations, intermediate in strength between the RLT hierarchy and the

L&P hierarchy.This new hierarchy is shown to coincide with RLT for MIPs

arising from pseudoboolean function minimization. Some preliminary

computational results involving rank-2 relaxations will be reported,

concerning both 0-1optimization problems without special structure,

and MIP formulations related to linearly constrained pseudoboolean

optimization.