A Sampling-Based Method to Estimate the Volume of Solution Space for Linear Arithmetic Constraints

The linear arithmetic constraints play important roles in many research fields. Estimating the volume of their solution spaces has specific applications, such as programming verification, linear programming, polyhedral optimization, and so on. In this paper, the authors provide an efficient estimation for the volume of the solution space for linear arithmetic constraints. This method sums up the estimations for volumes of oblique cones centered along randomly generated rays. The error analysis is provided to improve the accuracy.