# Given a set of solutions, find an IP formulation with the same solution set

Input:

• A list of integer variables $$x_1, ..., x_n$$.
• A finite set of feasible solutions $$S \subset \mathbb{Z}^n$$.

Find an integer linear program (IP) on the integer variables $$x_1,...,x_n$$ such that the solutions to this IP equals S. One may introduce additional variables.
• $$S$$ may not be convex, so introducing additional variables is probably necessary.
• One can cover $$S$$ exactly by a set of convex polygons $$P_1, ..., P_m$$. By "exactly" I mean that no other integer point in $$\mathbb{Z}^n \setminus S$$ is covered by these polygons. For each polygon, one can find an LP description.
By adding $$m$$ additional binary variables and using the big-M notation to model implications, we can force that at least one of these LP descriptions is fulfilled in the solution to our IP.
For this approach to work one would need to find $$P_1,...,P_m$$ which I don't know how to do.
• In my application $$S$$ contains several million elements. However, the number of variables and their range is quite small ($$n \leq 20$$, $$x_i \in [0,1,...,30])$$
• I expect that the points in $$S$$ are somewhat clustered and a corresponding IP can be quite small.