Reverse propagation of McCormick relaxations

TitleReverse propagation of McCormick relaxations
Publication TypeJournal Article
Year of Publication2015
AuthorsWechsung A, Scott JK, Watson HAJ, Barton PI
JournalJournal of Global Optimization
Date Published04/2015
KeywordsConstraint propagation, convex relaxations, global optimization, McCormick relaxations

Constraint propagation techniques have heavily utilized interval arithmetic while the application of convex and concave relaxations has been mostly restricted to the domain of global optimization. Here, reverse McCormick propagation, a method to construct and improve McCormick relaxations using a directed acyclic graph representation of the constraints, is proposed. In particular, this allows the interpretation of constraints as implicitly defining set-valued mappings between variables, and allows the construction and improvement of relaxations of these mappings. Reverse McCormick propagation yields potentially tighter enclosures of the solutions of constraint satisfaction problems than reverse interval propagation. Ultimately, the relaxations of the objective of a non-convex program can be improved by incorporating information about the constraints.