Adder model for mixed integer linear programming

Abstract

Satisfiability problems (SAT) for register transfer level designs combine arithmetic blocks with Boolean logic to form a mixed integer linear programming (MILP) environment. The classic model of the two-input n-bit adder for MILP is straightforward. However, proposed is a more efficient method using a new set of inequalities that describes its integer hull polyhedron. This special model reduces the number of branches needed to solve the whole integer problem, optimising the overall efficiency of the SAT solver. Experimental results show a CPU time reduction greater than one order of magnitude or higher, depending on the size of the problem.