(104g) Reformulation and Decomposition of Integer Programs Using Propositional Logic

Many optimization problems of practical interest (e.g., set-covering problem [1]) lead to integer programming (IP) models that contain discrete variables. These models can be formulated in many ways, some of which often contain nonintuitive redundant constraints. This in turn leads to large computational time to solve these problems. Currently, few methods can be applied to systematically eliminate these unnecessary constraints. In this work, we propose a technique to transform IP constraints into equivalent logical clauses and then use propositional logic rules to resolve and identify the redundant constraints. Interestingly, this approach can be also used to systematically decompose the original IP into smaller subproblems which can be solved sequentially or parallelly. We are also able to provide insights to the interpretation of the feasible domains of the decomposed IPs with respect to the feasible domain of the original IP and establish a relationship between the global solution of the original IP and the solutions of the decomposed IPs. With examples from literature, we will demonstrate these new logic-based reformulation and decomposition techniques that can be used to expedite the overall solution time of IP problems.

References:

[1] H.P. Williams, Logic and Integer Programming (2009), International Series in Operations Research & Management Science 130, DOI 10.1007/978-0-387-92280-5