Logic-Based Methods for Optimization: A Tutorial
John Hooker · 1994
Logic-based methods for optimization are increasingly attractive, for three main reasons. Logical inference algorithms have improved dramatically, connections between logic and mathematicalprogramming are coming to light, and most importantly, logic-based methods solve models that combine logical and mathematical elements. This tutorial explains how integer programming problems can be naturally viewed as logical inference problems. It briefly describes a logic-based parallel of cutting plane theory and illustrates the solution of an IP by logic-based branch-and-bound. In particular it discusses and illustrates the generation of deep logic cuts. The tutorial also treats mixed integer programming from a logical point of view. It shows how integer variables may be eliminated entirely from the LP relaxation, and how logic cuts may be used to accelerate the solution. In particular it defines a class of logic cuts that may cut off feasible solutions but do not affect the optimal s...