1
$\begingroup$

Input:

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

Task:
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.
Objective: Find an IP formulation that can be quickly solved e.g. with CPLEX. This means the formulation should minimize both number of constraints and number of additional variables.


My toughts so far:

  • $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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.